网站开发翻译,软文写作案例,黑龙江省建筑工程网,校园推广是什么工作文章目录1. 题目2. 解题2.1 STL2.2 线性扫描2.3 位运算1. 题目
下一个数。给定一个正整数#xff0c;找出与其二进制表达式中1的个数相同且大小最接近的那两个数#xff08;一个略大#xff0c;一个略小#xff09;。
例1:输入#xff1a;num 2#xff08;或者0b10找出与其二进制表达式中1的个数相同且大小最接近的那两个数一个略大一个略小。
例1:输入num 2或者0b10输出[4, 1] 或者[0b100, 0b1]例2:输入num 1输出[2, -1]提示:
num的范围在[1, 2147483647]之间
如果找不到前一个或者后一个满足条件的正数那么输出 -1。来源力扣LeetCode 链接https://leetcode-cn.com/problems/closed-number-lcci 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。
2. 解题
类似题目LeetCode 31. 下一个排列线性扫描
2.1 STL
prev_permutation\next_permutation返回的是 bool 值会改变原数组
class Solution {
public:vectorint findClosedNumbers(int num) {vectorint n(32,0);int i 31;while(num)//数字转成二进制存在数组里{n[i--] num1;num 1;}vectorint ans(2,-1);next_permutation(n.begin(),n.end());//会改变原数组long a calnum(n);if(0 a a INT_MAX)ans[0] a;prev_permutation(n.begin(), n.end());//上面next了一下这里往回退2步prev_permutation(n.begin(), n.end());a calnum(n);if(0 a a INT_MAX)ans[1] a;return ans;}int calnum(vectorint num){long sum 0;for(int i : num)sum sum*2i;return sum;}
};0 ms 6.1 MB
2.2 线性扫描
手写下一个排列、前一个排列
class Solution {
public:vectorint findClosedNumbers(int num) {vectorint n(32,0);int i 31;while(num){n[i--] num1;num 1;}vectorint ans(2,-1);next_perm(n);long a calnum(n);if(0 a a INT_MAX)ans[0] a;prev_perm(n);prev_perm(n);a calnum(n);if(0 a a INT_MAX)ans[1] a;return ans;}void next_perm(vectorint n){int i n.size()-2, j;while(i0 n[i] n[i1])i--;//找到下降点if(i0){j i1;while(j n.size() n[i] n[j])j;swap(n[i],n[j-1]);}reverse(n,i1,n.size()-1);}void prev_perm(vectorint n){int i n.size()-2, j;while(i0 n[i] n[i1])i--;//找到上升点if(i0){j i1;while(j n.size() n[i] n[j])j;swap(n[i],n[j-1]);}reverse(n,i1,n.size()-1);}void reverse(vectorint n, int l ,int r){while(l r)swap(n[l],n[r--]);}int calnum(vectorint num){ //计算排列后的数值long sum 0;for(int i : num)sum (sum1)i;return sum;}
};4 ms 6.3 MB
2.3 位运算
bitset 存储各个位注意 bitset 的位置是反的【0—n-1】对应【低位。。。高位】下一个排列从低往高找下降点即找到 01–10高位变大后面的低位变成[000… 111]最小上一个排列从低往高找上升点即找到 10–01高位变小后面的低位变成[111… 000]最大
class Solution {
public:vectorint findClosedNumbers(int num) {bitset32 big(num);bitset32 small(num);vectorint ans(2,-1);int i, l, r;for(i 1; i 32; i)//next 找下降点{if(big[i-1] big[i]){big.flip(i);big.flip(i-1);l 0, r i-1;while(l r){while(l r big[l]1)//高位的1全部挪到低位l;while(l r big[r]0)r--;big.flip(l);big.flip(r--);}long a big.to_ulong();if(a INT_MAX)ans[0] a;break;}}for(i 1; i 32; i)//prev 找上升点{if(small[i-1] small[i]){small.flip(i);small.flip(i-1);l 0, r i-1;while(l r){while(l r small[l]0)//低位的1全部挪到高位l;while(l r small[r]1)r--;small.flip(l);small.flip(r--);}long a small.to_ulong();if(a INT_MAX)ans[1] a;break;}}return ans;}
};
