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

题目来自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 main

import (
	"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));
}