您的位置:首页 > 娱乐 > 明星 > 【leetcode详解】数组最后一个元素的最小值(位运算典例)

【leetcode详解】数组最后一个元素的最小值(位运算典例)

2024/10/6 0:26:21 来源:https://blog.csdn.net/H13420972436/article/details/141470544  浏览:    关键词:【leetcode详解】数组最后一个元素的最小值(位运算典例)

 

思路分析

为便于叙述,下记:

  • A: x的二进制
  • B: x的二进制中非1的位置

由AND运算特点可知:

nums数组中的元素满足:如果 在某一位上为1,则nums中元素对应二进制在该位上也必须是1

换言之,从二进制码的视角看nums中元素,他们的二进制相当于以 为基础,在 上做了些调整

又因nums中元素互异且最小

  • nums中最小值nums[0]就是x本身(将 中所有位置置于0
  • nums中最小值nums[n-1]就是将 中所有位置依次填上n-1的二进制的每一位

所以嗦,要计算返回的结果就是

        先计算x的二进制码,再计算n-1的二进制码,最后将后者依次填进前者的0位上,得到的“杂交二进制”所对应的整数就是结果。


以下附上代码 & 笔者基于自身理解给出的注释:

class Solution {
public:long long minEnd(int n, int x) {//通过对x取反得到t,//通过计算t的lowbit来从低到高位遍历t的1位,即x的0位n-=1;int j=0;long long t = ~x;		long long ans = x;//注意:n>>j 和 n>>j & 1的判断条件并不等价!while(n >> j){int lb = t & -t;//计算t的lowbitans |= (long long)((n>>j & 1) << j) * lb;//通过乘法运算巧妙实现了if语句的功能j++;t ^= lb;//更新t,将lb为1那位t值变成0}return ans;}
};

题解参考,膜拜灵神!

3133. 数组最后一个元素的最小值 - 力扣(LeetCode)

~希望对你有启发~

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com