【Leetcode】3133. 数组最后一位的最小值
题目给你两个整数 n 和 x 。你必要构造一个长度为 n 的 正整数 数组 nums ，对于全部 0 <= i < n - 1 ，满足 nums 大于 nums ，并且数组 nums 中全部元素的按位 AND 运算结果为 x 。返回 nums 可能的 最小 值。
示例1
输入：n = 3, x = 4
输出：6
表明：
数组 nums 可以是 ，最后一个元素为 6 。
示例2
输入：n = 2, x = 7
输出：15
表明：
数组 nums 可以是 ，最后一个元素为 15 。
限定
1 < = n , x < = 1 0 8 1 <= n, x <= 10^8 1<=n,x<=108
分析：
好了，位运算，漏点漏点。
先分析一下吧：
起首题目中有说要把nums数组中全部的数字AND处理 ，
AND处理是什么？就是1&1 = 1，1&0=0，0&0 = 0，那么这也就决定了我们的最小为就是题目中全部的AND处理后的值x.
缘故原由在于我们要包管全部数AND后为x,即其x的二进制数中1地点的位置必须为1，且必要包管nums中全部数中存在x二进制0地点的位置必须为0。因而这就决定了我们的最小数，即nums为x.
已知条件的n怎么用呢，它包管数目，我刚开始想遍历，哈哈哈哈，就是把全部的0位置上的值遍历n-1个，因为我们已知最小的数，然后走最大，每次获取最低的0，再遍历，往上加。应该就和我看到的下面的这个题解1差不多。（为啥有这个想法没写出来，缘故原由就在于本身位运算真的很差了…）
背面又看其他的优化题解，即讲0位置搞出来，然后我们将填充到这些x的0的位置上。即比如，上面示例的4 = 100B，因为n=3,因为我们最小的值知道了为2，以是我们只要再填入n-1=2个值即可，而它的0提取出来为00，则其填上1（01B），2（10B），再将其分别添加到其上，那么就得到了4，5，6.
代码展示1
class Solution {
public long minEnd(int n, int x) {
// n = 3：nums的长度，且对于nums>nums,即低位大于高位
// 且nums中所有元素按位 AND 的结果为x
//以n=3,x=4为例，因为x=4，则表明nums AND nums AND nums = 100B，则100B为最小值，后者可以在其的基础上加，即101B,110B
// 以n=2,x=7为例，因为x=7,nums AND nums = 111B,所以nums为7，nums = 1111B = 8+7 = 15
// 由于n的二进制有log2n位，x的二进制就有log2n+log2x位
// 找最大的，即x = 100,n - 1 = 001，所以，1 = 100 + 001 = 101, 2= 101+1 = 110,
long res = x;
// 则给x中0的位置上布满n-1种的1
for(int i = 0;i<n-1;i++){
res += 1;
res = res | x;
}
return res;
}
}
代码展示2
class Solution {
public long minEnd(int n, int x) {
n -= 1;// 填入n-1
long res = x;
for(int j = 0;n>0;j++){
// res 向右移动j位，并判断其最后一位是否为0,如果是那么我可以在该位上填1
if((res >> j & 1) == 0){
// 表明我们的n对应的位为1，则表明该位置可以添加，因而添加
if((n&1)==1){
res |= 1L << j;
}
// n = n/2
n >>= 1;
}
}
return res;
}
}
最后
感觉位运算必要很熟悉我们二进制操纵，可以比力巧妙的用，比如我们题解1,他就是用 r e s = r e s ∣ x res = res | x res=res∣x，在保存x的二进制1的底子上增加1这些，这也是背面必要增强的地方。
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]