class Solution {
public:
vector<int> findClosedNumbers(int num) {
}
};
面试题 05.04. 下一个数
下一个数。给定一个正整数，找出与其二进制表达式中1的个数相同且大小最接近的那两个数（一个略大，一个略小）。
示例1:
输入：num = 2（或者0b10） 输出：[4, 1] 或者（[0b100, 0b1]）
示例2:
输入：num = 1 输出：[2, -1]
提示:
num的范围在[1, 2147483647]之间；原站题解
python3 解法, 执行用时: 36 ms, 内存消耗: 15 MB, 提交时间: 2023-04-22 11:46:20
class Solution:
def findClosedNumbers(self, num: int) -> List[int]:
mn, mx = 1, 2147483647
def findLarge(n):
# 从右开始找到第1个1
# 然后记录1的个数ones直到再遇到0或到最高位
# 然后将这个0变成1
# 然后右边的位数用000...111(ones-1个1)填充
checkMask = 1
bits = 0
while checkMask <= n and checkMask & n == 0:
checkMask <<= 1
bits += 1
ones = 0 # 直接构造出000...111
while checkMask <= n and checkMask & n != 0:
ones = (ones << 1) + 1
checkMask <<= 1
bits += 1
# 因为在改变的位已经将1个0转成1了, 所以这里ones要向右移动一位
ones >>= 1
# 将0转成1
n |= checkMask
# 清除右边的0
n = (n >> bits) << bits
# 将右边填充上ones
n |= ones
return n if mn <= n <= mx else -1
def findSmall(n):
# 从右开始找到第1个0, 记录此过程1的个数ones
# 然后继续往左找直到再遇到1
# 然后将这个1变成0, ones也要左移一位(也可以初始化为1)
# 然后右边的位数用高位ones个1填充, 即构造出111...000, 可以直接基于ones构造
# 注意如果全为1的话是无解的, 直接返回-1
checkMask = 1
bits = 0
ones = 1
while checkMask <= n and checkMask & n != 0:
checkMask <<= 1
bits += 1
ones = (ones << 1) + 1
if checkMask > n:
# 全部是1
return -1
while checkMask <= n and checkMask & n == 0:
checkMask <<= 1
bits += 1
ones <<= 1
# 因为ones初始化为1, 所以ones需要右移一位
ones >>= 1
# 将需要改变的1变成0
n &= ~checkMask
# 清除右边的0
n = (n >> bits) << bits
# 将右边填充上ones
n |= ones
return n if mn <= n <= mx else -1
return [findLarge(num), findSmall(num)]
golang 解法, 执行用时: 0 ms, 内存消耗: 1.8 MB, 提交时间: 2023-04-22 11:45:54
func findClosedNumbers(num int) []int {
find := 0
ans := []int{-1, -1}
sn := 0
on := uint(0) // sn中1的个数
for num > 0 {
pn := num & (-num)
num &= num - 1
// 1<<30判断是否超出范围
if pn&(1<<30) == 0 && num&(pn<<1) == 0 && ans[0] == -1 {
ans[0] = num | (pn << 1) | (1<<on - 1)
find++
}
// pn<=1无略小值
if pn > 1 && sn&(pn>>1) == 0 && ans[1] == -1 {
ans[1] = num | (pn >> 1) | ((pn>>1 - 1) ^ (pn>>1-1)>>on)
find++
}
if find == 2 {
break
}
sn |= pn
on++
}
return ans
}
cpp 解法, 执行用时: 4 ms, 内存消耗: 6 MB, 提交时间: 2023-04-22 11:45:25
/*
较小的数
1. 最低位1相邻的右侧有0，1 <-> 0 交换
2. 无0，倒数第二个1相邻的右侧有0,1<->0交换
3. 循环 1、2直到找到一个右侧有0的项，再把低位上的1全部左移；
4. 如果所有的1右侧都无0，返回-1；
较大的数
1. 最低位1相邻的左侧有0，0 <-> 1 交换
2. 无0，倒数第二个1相邻的左侧有0，0<->1 交换
3. 循环 1、2直到找到一个左侧有0的项，再把低位上的1全部移到右移
4. 所有1相邻的左侧都无0，返回-1；
*/
class Solution {
public:
vector<int> findClosedNumbers(int num) {
//return {1,1};
vector<int> nums(31,0);
for(int i=0;i<=30;++i){
nums[i]=pow(2,i);
}//预处理一个数组，{1,2,4,8,16...}某一位为1,nums[i]^INT_MAX可以将num[i]取反，即0000 ... 0001转化为1111 ... 1110
vector<int> res(2,-1);
int flag1=1,flag0=1;
for(int i=0;i<30;++i){
if((nums[i]&num)==0&&flag1&&nums[i+1]&num) {
//遇到了第一个10
res[1]=num-nums[i+1]+nums[i];
flag1=0;
int k=-1,l=i;//k记录从最右边开始未处理的1，l处理10转化为01后的0
while(l&&(nums[l-1]&num)==0&&nums[k+1]&num){//处理类似1001,10011这种情况(转化完应为0110,01110)
res[1]=res[1]-nums[++k]+nums[--l];
if(l==0) break;
}
}
if((nums[i]&num)&&flag0&&(nums[i+1]&num)==0){
//遇到了第一个01
res[0]=num-nums[i]+nums[i+1];
flag0=0;
int k=-1,l=i;//k记录从最右边开始未处理的0，l处理01转化为10后的1
while(l&&nums[l-1]&num&&(nums[k+1]&num)==0){//处理类似1111000,1111100这种情况（转化完应为10000111,10001111）
res[0]=res[0]+nums[++k]-nums[--l];
if(l==0) break;
}
}
}
return res;
}
};