JZX轻语：简

LeetCode 3133 - 数组最后一个元素的最小值

发表于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