class Solution {
public:
long long minEnd(int n, int x) {
}
};
3133. 数组最后一个元素的最小值
给你两个整数 n 和 x 。你需要构造一个长度为 n 的 正整数 数组 nums ，对于所有 0 <= i < n - 1 ，满足 nums[i + 1] 大于 nums[i] ，并且数组 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 <= 108原站题解
rust 解法, 执行用时: 0 ms, 内存消耗: 2.2 MB, 提交时间: 2024-08-22 09:40:00
impl Solution {
pub fn min_end(n: i32, x: i32) -> i64 {
let bit_count = 64 - n.leading_zeros() - x.leading_zeros();
let mut res = x as i64;
let mut j = 0;
let mut n = (n - 1) as i64;
for i in 0..bit_count {
if ((res >> i) & 1) == 0 {
if ((n >> j) & 1) != 0 {
res |= 1 << i;
}
j += 1;
}
}
res
}
}
javascript 解法, 执行用时: 71 ms, 内存消耗: 52 MB, 提交时间: 2024-08-22 09:39:42
/**
* @param {number} n
* @param {number} x
* @return {number}
*/
var minEnd = function(n, x) {
const bitCount = 64 - leadingZeros(n) - leadingZeros(x);
let res = BigInt(x);
let j = 0;
n--;
for (let i = 0; i < bitCount; ++i) {
if (((res >> BigInt(i)) & 1n) === 0n) {
if (((BigInt(n) >> BigInt(j)) & 1n) != 0n) {
res |= 1n << BigInt(i);
}
j++;
}
}
return Number(res);
};
function leadingZeros(x) {
return x === 0 ? 32 : 31 - Math.floor(Math.log2(x));
}
golang 解法, 执行用时: 0 ms, 内存消耗: 2.2 MB, 提交时间: 2024-05-01 10:57:40
func minEnd(n, x int) int64 {
n--
j := 0
for t, lb := ^x, 0; n>>j > 0; t ^= lb {
lb = t & -t
x |= n >> j & 1 * lb
j++
}
return int64(x)
}
func minEnd2(n, x int) int64 {
n-- // 先把 n 减一，这样下面讨论的 n 就是原来的 n-1
i, j := 0, 0
for n>>j > 0 {
// x 的第 i 个比特值是 0，即「空位」
if x>>i&1 == 0 {
// 空位填入 n 的第 j 个比特值
x |= n >> j & 1 << i
j++
}
i++
}
return int64(x)
}
java 解法, 执行用时: 0 ms, 内存消耗: 40 MB, 提交时间: 2024-05-01 10:57:16
class Solution {
public long minEnd(int n, int x) {
n--; // 先把 n 减一，这样下面讨论的 n 就是原来的 n-1
long ans = x;
int i = 0, j = 0;
while ((n >> j) > 0) {
// x 的第 i 个比特值是 0，即「空位」
if ((ans >> i & 1) == 0) {
// 空位填入 n 的第 j 个比特值
ans |= (long) (n >> j & 1) << i;
j++;
}
i++;
}
return ans;
}
public long minEnd2(int n, int x) {
n--;
long ans = x;
int j = 0;
for (long t = ~x, lb; (n >> j) > 0; t ^= lb) {
lb = t & -t;
ans |= (long) (n >> j++ & 1) * lb;
}
return ans;
}
}
cpp 解法, 执行用时: 2 ms, 内存消耗: 7.7 MB, 提交时间: 2024-05-01 10:56:47
class Solution {
public:
long long minEnd(int n, int x) {
n--;
long long ans = x;
int j = 0;
for (long long t = ~x, lb; n >> j; t ^= lb) {
lb = t & -t;
ans |= (long long) (n >> j++ & 1) * lb;
}
return ans;
}
long long minEnd2(int n, int x) {
n--; // 先把 n 减一，这样下面讨论的 n 就是原来的 n-1
long long ans = x;
int i = 0, j = 0;
while (n >> j) {
// x 的第 i 个比特值是 0，即「空位」
if ((ans >> i & 1) == 0) {
// 空位填入 n 的第 j 个比特值
ans |= (long long) (n >> j & 1) << i;
j++;
}
i++;
}
return ans;
}
};
python3 解法, 执行用时: 45 ms, 内存消耗: 16.4 MB, 提交时间: 2024-05-01 10:56:17
class Solution:
def minEnd(self, n: int, x: int) -> int:
n -= 1 # 先把 n 减一，这样下面讨论的 n 就是原来的 n-1
i = j = 0
while n >> j:
# x 的第 i 个比特值是 0，即「空位」
if (x >> i & 1) == 0:
# 空位填入 n 的第 j 个比特值
x |= (n >> j & 1) << i
j += 1
i += 1
return x
# 优化，把 x 取反，用 lowbit 枚举其中的 1，就是要填的空位
def minEnd2(self, n: int, x: int) -> int:
n -= 1
j = 0
t = ~x
while n >> j:
lb = t & -t
x |= (n >> j & 1) * lb
j += 1
t ^= lb
return x