gpt4 book ai didi

java - 几乎相同的语句,但不同的值

转载 作者:行者123 更新时间:2023-12-04 09:45:57 27 4
gpt4 key购买 nike

我正在研究一个经典的 DP 问题,Count Subset Sum。

如果您不确定问题,问题陈述如下:
给定一组正数,找出总和等于给定数字“S”的子集总数。

我正在尝试使用回溯方法解决它。

假设给定的数组是 [1, 1, 2, 3]sum是 4,所以预期的结果是 3奇怪的是代码吹得很好,它生成了正确的结果。

  private int backtrack2(int[] nums, int sum) {
int[] count = new int[1];
backtrack2Helper(nums, sum, count, 0);
return count[0];
}

private int backtrack2Helper(int[] nums, int sum, int[] count, int pos) {
if (0 == sum) return 1;
if (pos == nums.length) return 0;

for (int i = pos; i < nums.length; ++i) {
if (sum - nums[i] >= 0) {
int temp = backtrack2Helper(nums, sum - nums[i], count, i + 1);
count[0] += temp;
}
}

return 0;
}

但是,下面的代码无法生成正确的结果:

  private int backtrack2(int[] nums, int sum) {
int[] count = new int[1];
backtrack2Helper(nums, sum, count, 0);
return count[0];
}

private int backtrack2Helper(int[] nums, int sum, int[] count, int pos) {
if (0 == sum) return 1;
if (pos == nums.length) return 0;

for (int i = pos; i < nums.length; ++i) {
if (sum - nums[i] >= 0) {
count[0] += backtrack2Helper(nums, sum - nums[i], count, i + 1);
}
}

return 0;
}

唯一的区别是 if辅助函数中的语句部分。

int temp = backtrack2Helper(nums, sum - nums[i], count, i + 1);
count[0] += temp;



count[0] += backtrack2Helper(nums, sum - nums[i], count, i + 1);

应该是等价的吧?

但是第二个不能正常工作。
真是糊涂了,一步步调试,发现方法二的方法最后碰到return语句的时候, count[0]不是由返回的 0 添加,而是设置为 0。

发生了什么?

最佳答案

差异源于 backtrack2Helper()变化 count[0] .

例如,假设 backtrack2Helper(nums, sum - nums[i], count, i + 1)更改 count[0] 的值来自 01并返回 1 .

在一个片段中,您添加了更改后的值 count[0]到递归调用返回的值:

int temp = backtrack2Helper(nums, sum - nums[i], count, i + 1); // == 1
count[0] += temp; // == 1 + 1 == 2

但是在另一个片段中,您添加了 count[0] 的原始值到递归调用返回的值:
count[0] += backtrack2Helper(nums, sum - nums[i], count, i + 1); // == 0 + 1 == 1

编辑:

您可以在没有 count[] 的情况下编写更优雅的解决方案大批:
private static int backtrack2(int[] nums, int sum) {
return backtrack2Helper(nums, sum, 0);
}

private static int backtrack2Helper(int[] nums, int sum, int pos) {
if (0 == sum)
return 1;
if (pos == nums.length)
return 0;
int count = 0;
for (int i = pos; i < nums.length; ++i) {
if (sum - nums[i] >= 0) {
count += backtrack2Helper(nums, sum - nums[i], i + 1);
}
}

return count;
}

编辑:

为了改进关于两个片段差异的解释,这里有一个更简单的代码,它产生相同的行为:
int method2 (int[] arr)
{
arr[0] = 5;
return 0;
}

第一个片段:
void method1 ()
{
int[] arr = new int[1]; // arr[0] is 0
int temp = method2 (arr); // temp is assigned 0, arr[0] is changed to 5 by method2
arr[0] += temp // arr[0] = arr[0] + temp == 5 + 0 == 5
}

第二个片段:
void method1 ()
{
int[] arr = new int[1]; // arr[0] is 0
arr[0] += method2 (arr); // arr[0] = arr[0] + method2 (arr) == 0 + 0 == 0
}

关于java - 几乎相同的语句,但不同的值,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/62114679/

27 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com