2024-12-11：数组最后一个元素的最小值。用go语言，给定两个整数 n 和 x，构造一个长度为 n 的正整数数组 nums

福大大架构师每日一题

发布于 2024-12-19 18:39:40

22800

代码可运行

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

运行总次数：0

代码可运行

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 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{
letbit_count=128- n.leading_zeros()- x.leading_zeros();
letmut res= x asi64;
letm=(n -1)asi64;
letmut j=0;
foriin0..bit_count {
if res &(1<< i)==0{
if m &(1<< j)!=0{
                res |=1<< i;
}
            j +=1;
}
}
    res
}

fnmain(){
letn=3;
letx=4;
println!("{}",min_end(n, x));
}