2024-12-11：数组最后一个元素的最小值。用go语言，给定两个整数 n 和 x，构造一个长度为 n 的正整数数组 nums，使得数组中相邻元素递增且所有元素按位与的结果为 x。返回可能的最小 nums 数组中的最后一个元素的值。

1 <= n, x <= 100000000。

输入：n = 3, x = 4。

输出：6。

解释：

数组 nums 可以是 [4,5,6] ，最后一个元素为 6 。

答案2024-12-11：

chatgpt[1]

题目来自leetcode3133。

大体步骤如下：

1.计算变量 bitCount，表示 n 和 x 转换为二进制后的位数差。

2.设置初始解 res 为 x，并初始化另一个变量 m 为 n - 1。

3.通过循环处理每个位，检查 res 中每一位是否为 0。

4.如果某位为 0，则检查 m 对应位是否为 1，若是，则将 res 中该位设置为 1。

5.返回最终的 res 值，即可能的最小 nums 数组。

总体时间复杂度：

• 该算法的时间复杂度取决于 bitCount，即 O(bitCount)。• bitCount 的计算时间复杂度为 O(1)。• 循环处理每个位的时间复杂度为 O(bitCount)。• 因此，总的时间复杂度为 O(bitCount)。

总体额外空间复杂度：

• 该算法只使用少量变量来存储数据，额外空间复杂度为 O(1)，即为常量级别的空间消耗。Go完整代码如下：package mainimport ( "fmt" "math/bits")func minEnd(n int, x int) int64 { bitCount := 128 - bits.LeadingZeros(uint(n)) - bits.LeadingZeros(uint(x)) res := int64(x) m := int64(n) - 1 j := 0 for i := 0; i < bitCount; i++ { if res&(1<<i) == 0 { if m&(1<<j) != 0 { res |= 1 << i } j++ } } return res}func main() { n := 3 x := 4 fmt.Println(minEnd(n, x))}

Rust完整代码如下：fn min_end(n: i64, x: i64) -> i64 { let bit_count = 128 - n.leading_zeros() - x.leading_zeros(); let mut res = x as i64; let m = (n - 1) as i64; let mut j = 0; for i in 0..bit_count { if res & (1 << i) == 0 { if m & (1 << j) != 0 { res |= 1 << i; } j += 1; } } res}fn main() { let n = 3; let x = 4; println!("{}", min_end(n, x));}

引用链接

[1] chatgpt: https://chatbotsplace.com/?rc=nnNWSCJ7EP