Powered by:NEFU AB-IN
文章目录
3133. 数组最后一个元素的最小值
题意
给你两个整数 n 和 x 。你需要构造一个长度为 n 的 正整数 数组 nums ,对于所有 0 <= i < n - 1 ,满足 nums[i + 1] 大于 nums[i] ,并且数组 nums 中所有元素的按位 AND 运算结果为 x 。
返回 nums[n - 1] 可能的 最小 值。
思路
可以说,如果都 AND 操作为 x,那么 x 的二进制位为 1 的地方,所有数都必须有,那么最优的情况就是最小值为 x
进而就是枚举 x 中二进制为 0 的位置,将 0 的位置进行塞 0 或 1 的操作
由于要严格递增,那么就要按照如,000,001,010的顺序塞
比如
x = “0b10010”
n = “0b11”
那么第一个数为 10010,第二个为10011,第三个为10110,所以第三个也就是把 10 填进了 x 的 0 的二进制位中,10 恰好就是 n - 1
所以思路就是枚举 x 的每一位,当为 0 的时候,开始填 n 的第一位,然后 n 右移,直到 n = 0
代码
'''
Author: NEFU AB-IN
Date: 2024-07-09 23:35:08
FilePath: \LeetCode\3133\3133.py
LastEditTime: 2024-07-11 16:14:56
'''
# 3.8.19 import
import random
from collections import Counter, defaultdict, deque
from datetime import datetime, timedelta
from functools import lru_cache
from heapq import heapify, heappop, heappush, nlargest, nsmallest
from itertools import combinations, compress, permutations, starmap, tee
from math import ceil, fabs, floor, gcd, log, sqrt
from string import ascii_lowercase, ascii_uppercase
from sys import exit, setrecursionlimit, stdin
from typing import Any, Dict, List, Tuple, TypeVar, Union
# Constants
TYPE = TypeVar('TYPE')
N = int(2e5 + 10) # If using AR, modify accordingly
M = int(20) # If using AR, modify accordingly
INF = int(2e9)
OFFSET = int(100)
# Set recursion limit
setrecursionlimit(INF)
class Arr:
array = staticmethod(lambda x=0, size=N: [x() if callable(x) else x for _ in range(size)])
array2d = staticmethod(lambda x=0, rows=N, cols=M: [Arr.array(x, cols) for _ in range(rows)])
graph = staticmethod(lambda size=N: [[] for _ in range(size)])
@staticmethod
def to_1_indexed(data: Union[List, str, List[List]]):
"""Adds a zero prefix to the data and returns the modified data and its length."""
if isinstance(data, list):
if all(isinstance(item, list) for item in data): # Check if it's a 2D array
new_data = [[0] * (len(data[0]) + 1)] + [[0] + row for row in data]
return new_data, len(new_data) - 1, len(new_data[0]) - 1
else:
new_data = [0] + data
return new_data, len(new_data) - 1
elif isinstance(data, str):
new_data = '0' + data
return new_data, len(new_data) - 1
else:
raise TypeError("Input must be a list, a 2D list, or a string")
class Str:
letter_to_num = staticmethod(lambda x: ord(x.upper()) - 65) # A -> 0
num_to_letter = staticmethod(lambda x: ascii_uppercase[x]) # 0 -> A
removeprefix = staticmethod(lambda s, prefix: s[len(prefix):] if s.startswith(prefix) else s)
removesuffix = staticmethod(lambda s, suffix: s[:-len(suffix)] if s.endswith(suffix) else s)
class Math:
max = staticmethod(lambda a, b: a if a > b else b)
min = staticmethod(lambda a, b: a if a < b else b)
class IO:
input = staticmethod(lambda: stdin.readline().rstrip("\r\n"))
read = staticmethod(lambda: map(int, IO.input().split()))
read_list = staticmethod(lambda: list(IO.read()))
class Std:
pass
# ————————————————————— Division line ——————————————————————
class Solution:
def minEnd(self, n: int, x: int) -> int:
n -= 1
# x = "10010"
# n - 1 = "10"
for j in range(64):
if x >> j & 1:
continue
x |= (n & 1) << j
n >>= 1
if not n:
break
return x
print(Solution().minEnd(3, 18))