发表于 2024.08.22

• 一个想起来挺复杂，但想出来后实现挺简单的题目。由于要求数组内所有元素按位AND之后的值为x，这意味着，x每个为1的位，数组中每个元素的对应位也都要为1。因此，我们可以按照以下方式构造一个递增数组：第一个元素除了x中为1的位之外，其他位都为0，第二个元素其他位中后两位为10，第三个元素其他位中后两位为11，第四个元素其他位中后三位为100，以此类推。这样构造的数组，其最后一个元素的值就是返回值。因此，题目就可以转化为：满足x中为1的位，对应位也都要为1的(for all b, if x[b] == 1 then elem[b] == 1)，第n个元素的值。。换句话说，本质就是将n转化为二进制，然后插入到x中为0的位。

  举个例子，假设x = 5, n = 5，此时x可以使用二进制表示为101，那么：(注意，尖括号内的1是指x中同样也为1的位，这意味着数组内所有元素中，这个位只能为1)

  • 数组第一个元素：<1>0<1>，也就是其余位为000

  • 数组第二个元素：<1>1<1>，其余位为001

  • 数组第三个元素：1<1>0<1>，其余位为010

  • 数组第四个元素：1<1>1<1>，其余位为011

  • 数组第五个元素：10<1>0<1>，其余位为100

  class Solution:
      def minEnd(self, n: int, x: int) -> int:
          n -= 1  # 转化为0-based
          mask = 1
          while n:
              if not (x & mask):  # 如果x中对应位为0
                  # 将n对应位插入到x中位置
                  if n & 1:
                      x |= mask
                  n >>= 1
              mask <<= 1
          return x

• LC 题目链接