【Leetcode】3133. 数组最后一位的最小值

题目
   给你两个整数 n 和 x 。你必要构造一个长度为 n 的 正整数 数组 nums ，对于全部 0 <= i < n - 1 ，满足 nums[i + 1] 大于 nums ，并且数组 nums 中全部元素的按位 AND 运算结果为 x 。返回 nums[n - 1] 可能的 最小 值。
  

---

示例1
   输入：n = 3, x = 4
输出：6
  表明：
   数组 nums 可以是 [4,5,6] ，最后一个元素为 6 。
  示例2
   输入：n = 2, x = 7
输出：15
  表明：
   数组 nums 可以是 [7,15] ，最后一个元素为 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[0]为x.
已知条件的n怎么用呢，它包管数目，我刚开始想遍历，哈哈哈哈，就是把全部的0位置上的值遍历n-1个，因为我们已知最小的数，然后走最大，每次获取最低的0，再遍历，往上加。应该就和我看到的下面的这个题解1差不多。（为啥有这个想法没写出来，缘故原由就在于本身位运算真的很差了…）
背面又看其他的优化题解，即讲0位置搞出来，然后我们将[1,n-1]填充到这些x的0的位置上。即比如，上面示例的4 = 100B，因为n=3,因为我们最小的值知道了为2，以是我们只要再填入n-1=2个值即可，而它的0提取出来为00，则其填上1（01B），2（10B），再将其分别添加到其上，那么就得到了4，5，6.
  代码展示1

1. class Solution {
2.     public long minEnd(int n, int x) {
3.         // n = 3：nums的长度，且对于nums[i+1]>nums[i],即低位大于高位
4.         // 且nums中所有元素按位 AND 的结果为x
5.         //以n=3,x=4为例，因为x=4，则表明nums[0] AND nums[1] AND nums[2] = 100B，则100B为最小值，后者可以在其的基础上加，即101B,110B
6.         // 以n=2,x=7为例，因为x=7,nums[0] AND nums[1] = 111B,所以nums[0]为7，nums[1] = 1111B = 8+7 = 15
7.         // 由于n的二进制有log2n位，x的二进制就有log2n+log2x位
8.         // 找最大的，即x = 100,n - 1 = 001，所以，1 = 100 + 001 = 101, 2  = 101+1 = 110,
9.         
10.         long res = x;
11.         // 则给x中0的位置上布满n-1种的1
12.         for(int i = 0;i<n-1;i++){
13.             res += 1;
14.             res = res | x;
15.         }
16.         return res;
17.     }
18. }

复制代码

代码展示2

1. class Solution {
2.     public long minEnd(int n, int x) {
3.         n -= 1;  // 填入n-1
4.         long res = x;
5.         for(int j = 0;n>0;j++){
6.             // res 向右移动j位，并判断其最后一位是否为0,如果是那么我可以在该位上填1
7.             if((res >> j & 1) == 0){
8.                 // 表明我们的n对应的位为1，则表明该位置可以添加，因而添加
9.                 if((n&1)==1){
10.                     res |= 1L << j;
11.                 }
12.                 // n = n/2
13.                 n >>= 1;
14.             }
15.         }
16.         return res;
17.     }
18. }

复制代码

最后
   感觉位运算必要很熟悉我们二进制操纵，可以比力巧妙的用，比如我们题解1,他就是用                                        r                            e                            s                            =                            r                            e                            s                            ∣                            x                                  res = res | x                     res=res∣x，在保存x的二进制1的底子上增加1这些，这也是背面必要增强的地方。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。