2024-12-02：划分数组得到最小的值之和。用go语言，你有两个数组，nums 和 andValues，它们的长度分别为 n

2024-12-02：划分数组得到最小的值之和。用go语言，你有两个数组，nums 和 andValues，它们的长度分别为 n 和 m。定义数组的“值”为其最后一个元素。

你的任务是将 nums 划分为 m 个不重叠的连续子数组。对于第 i 个子数组 [li, ri]，该子数组的所有元素通过按位与运算后，结果必须等于 andValues[i]。换句话说，对于所有的 1 <= i <= m，应该满足 nums[li] & nums[li + 1] & ... & nums[ri] == andValues[i]，其中 & 表示按位与运算符。

你的目标是返回将 nums 划分为 m 个子数组时，得到的可能的最小子数组值之和。如果无法完成这样的划分，则返回 -1。 提示：

1 <= n == nums.length <= 10000。

1 <= m == andValues.length <= min(n, 10)。

1 <= nums[i] < 100000。

0 <= andValues[j] < 100000。

输入： nums = [1,4,3,3,2], andValues = [0,3,3,2]。

输出： 12。

解释：

唯一可能的划分方法为：

1.[1,4] 因为 1 & 4 == 0；

2.[3] 因为单元素子数组的按位 AND 结果就是该元素本身；

3.[3] 因为单元素子数组的按位 AND 结果就是该元素本身；

4.[2] 因为单元素子数组的按位 AND 结果就是该元素本身。

这些子数组的值之和为 4 + 3 + 3 + 2 = 12。

答案2024-12-02：

chatgpt[1]

题目来自leetcode3117。

大体步骤如下：

1.定义常量 INF 作为无穷大的表示，为 (1 << 20) - 1。

2.初始化 nums 和 andValues 的长度 n 和 m。

3.创建 memo 数组，大小为 n*m，用于记忆化搜索过程中的中间结果。

4.定义递归函数 dfs(i, j, cur int) int，用于计算最小子数组值之和，函数体如下：

• 计算当前状态的键值 key 以在 memo 中保存中间结果。

• 检查结束条件：如果 i 和 j 都达到末尾则返回 0，如果其中一个到达末尾则返回 INF。

• 检查 memo 中是否已有当前状态结果，若有则直接返回。

• 对当前的 cur 进行按位与操作并检查是否符合条件，若不符合则返回 INF。

• 递归调用 dfs 处理两种情况：不选当前元素和选取当前元素。

• 更新 memo 并返回结果。

5.调用 dfs(0, 0, INF) 启动递归计算最小值之和，并将结果存储在 res 中。

6.检查 res 是否小于INF，如果是则返回 res，否则返回 -1。

总的时间复杂度为 O(n*m)。

总的额外空间复杂度为 O(n*m)。

Go完整代码如下：

package main

import(

"fmt"

)

func minimumValueSum(nums []int, andValues []int)int{

const INF =(1<<20)-1

n :=len(nums)

m :=len(andValues)

memo :=make([]map[int]int, n*m)

for i :=range memo {

memo[i]=make(map[int]int)

}

var dfs func(i, j, cur int)int

dfs =func(i, j, cur int)int{

key := i*m + j

if i == n && j == m {

return0

}

if i == n || j == m {

return INF

}

if val, ok := memo[key][cur]; ok {

return val

}

cur &= nums[i]

if cur&andValues[j]< andValues[j]{

return INF

}

res := dfs(i+1, j, cur)

if cur == andValues[j]{

res = min(res, dfs(i+1, j+1, INF)+nums[i])

}

memo[key][cur]= res

return res

}

res := dfs(0,0, INF)

if res < INF {

return res

}

return-1

}

func main(){

nums :=[]int{1,4,3,3,2}

andValues :=[]int{0,3,3,2}

fmt.Println(minimumValueSum(nums, andValues))

}

在这里插入图片描述Rust完整代码如下：

use std::collections::HashMap;

const INF:i32=(1<<20)-1;

fnminimum_value_sum(nums:&[i32], and_values:&[i32])->i32{

letn= nums.len();

letm= and_values.len();

letmut memo=vec![HashMap::new(); n * m];

fndfs(

i:usize,

j:usize,

cur:i32,

nums:&[i32],

and_values:&[i32],

memo:&mutVec<HashMap<i32,i32>>,

)->i32{

if i == nums.len()&& j == and_values.len(){

return0;

}

if i == nums.len()|| j == and_values.len(){

return INF;

}

letkey= i * and_values.len()+ j;

ifletSome(&val)= memo[key].get(&cur){

return val;

}

letnew_cur= cur & nums[i];

if new_cur & and_values[j]< and_values[j]{

return INF;

}

letmut res=dfs(i +1, j, new_cur, nums, and_values, memo);

if new_cur == and_values[j]{

res = res.min(dfs(i +1, j +1, INF, nums, and_values, memo)+ nums[i]);

}

memo[key].insert(cur, res);

res

}

letres=dfs(0,0, INF, nums, and_values,&mut memo);

if res < INF {

res

}else{

-1

}

}

fnmain(){

letnums=vec![1,4,3,3,2];

letand_values=vec![0,3,3,2];

println!("{}",minimum_value_sum(&nums,&and_values));

}

在这里插入图片描述引用链接