专栏首页Michael阿明学习之路程序员面试金典 - 面试题 05.04. 下一个数(线性扫描)

程序员面试金典 - 面试题 05.04. 下一个数(线性扫描)

1. 题目

下一个数。给定一个正整数,找出与其二进制表达式中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. 解题

2.1 STL

  • prev_permutation\next_permutation,返回的是 bool 值,会改变原数组!!!
class Solution {
public:
    vector<int> findClosedNumbers(int num) {
    	vector<int> n(32,0);
    	int i = 31;
    	while(num)//数字转成二进制存在数组里
    	{
    		n[i--] = num&1;
    		num >>= 1;
    	}
    	vector<int> 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(vector<int>& num)
    {
    	long sum = 0;
    	for(int i : num)
    		sum = sum*2+i;
    	return sum;
    }
};

0 ms 6.1 MB

2.2 线性扫描

  • 手写下一个排列、前一个排列
class Solution {
public:
    vector<int> findClosedNumbers(int num) {
    	vector<int> n(32,0);
    	int i = 31;
    	while(num)
    	{
    		n[i--] = num&1;
    		num >>= 1;
    	}
    	vector<int> 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(vector<int>& n)
    {
    	int i = n.size()-2, j;
    	while(i>=0 && n[i] >= n[i+1])
    		i--;//找到下降点
    	if(i>=0)
        {
            j = i+1;
            while(j < n.size() && n[i] < n[j])
                j++;
            swap(n[i],n[j-1]);
        }
    	reverse(n,i+1,n.size()-1);
    }
    void prev_perm(vector<int>& n)
    {
    	int i = n.size()-2, j;
    	while(i>=0 && n[i] <= n[i+1])
    		i--;//找到上升点
    	if(i>=0)
        {
            j = i+1;
            while(j < n.size() && n[i] > n[j])
                j++;
            swap(n[i],n[j-1]);
        }
    	reverse(n,i+1,n.size()-1);
    }
    void reverse(vector<int>& n, int l ,int r)
    {
    	while(l < r)
    		swap(n[l++],n[r--]);
    }
    int calnum(vector<int>& num)
    {	//计算排列后的数值
    	long sum = 0;
    	for(int i : num)
    		sum = (sum<<1)+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:
    vector<int> findClosedNumbers(int num) {
    	bitset<32> big(num);
    	bitset<32> small(num);
    	vector<int> 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;
    }
};

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode 201. 数字范围按位与(位运算)

    给定范围 [m, n],其中 0 <= m <= n <= 2147483647,返回此范围内所有数字的按位与(包含 m, n 两端点)。

    Michael阿明
  • LeetCode 454. 四数相加 II(哈希)

    给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ,使得 A[i] + B[j] + C[k] + D[l]...

    Michael阿明
  • LeetCode 914. 卡牌分组(最大公约数)

    每组都有 X 张牌。 组内所有的牌上都写着相同的整数。 仅当你可选的 X >= 2 时返回 true。

    Michael阿明
  • 【LeetCode】面试题46. 把数字翻译成字符串

    给定一个数字,我们按照如下规则把它翻译为字符串:0 翻译成 “a” ,1 翻译成 “b”,……,11 翻译成 “l”,……,25 翻译成 “z”。一个数字可能有...

    韩旭051
  • block-基础概念和使用

    block主要准备分为3个文章记录。 第一章:基础概念和使用 第二章:捕获变量 第三章:持有变量

    大壮
  • BZOJ1059: [ZJOI2007]矩阵游戏(二分图匹配)

      小Q是一个非常聪明的孩子,除了国际象棋,他还很喜欢玩一个电脑益智游戏——矩阵游戏。矩阵游戏在一个N

    attack
  • 【LeetCode第 162 场周赛】回顾

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY 版权协议,转载请附上原文出处链接和本声明。 ...

    韩旭051
  • 数据结构和算法——动态规划

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    zhaozhiyong
  • 经典中的经典算法 动态规划(详细解释,从入门到实践,逐步讲解)

    动态规划算法是通过拆分问题,定义问题状态和状态之间的关系,使得问题能够以递推(或者说分治)的方式去解决。

    233333
  • 组合问题汇总-LeetCode 46、77、39、40、219、377、1014(回溯法,DP,贪心)

    来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/permutations

    算法工程师之路

扫码关注云+社区

领取腾讯云代金券