如果条件可以是真或假，为什么有必要
我对这个超级困惑。该代码用于生成给定整数列表的所有排列。一旦你这样做了，他们就会添加另一个约束，即给定的输入可以有重复，我们只需要唯一的排列。
我的代码工作正常...我只是对我注意到的事情感到惊讶。在查看了代码之后，我质疑我所拥有的特定条件是否必要，所以我否定了它，看看会发生什么。该代码在100个测试用例中仍然没有缺陷。从本质上讲，无论此条件是否为 或 ，此代码都有效。truefalse
所以很自然地，我认为我可以消除这种情况，因为它似乎是不必要的。长话短说。。。。该代码现在返回一个空结果集。我希望比我更聪明的人可以解释这是怎么可能的，因为我现在正在质疑我是否属于这个职业。
有问题的代码行是：
if(seen[i] || (i > 0 && nums[i] == nums[i - 1] && !seen[i - 1]))
具体来说，如果按原样运行此代码，则它有效。如果您删除否定并运行它，因为它仍然有效。如果完全删除，则条件如下所示：!seen[i - 1]seen[i - 1]!seen[i - 1]
if(seen[i] || (i > 0 && nums[i] == nums[i - 1]))则代码返回空结果集。我完全糊涂了。
我使用该方法作为输入，我的预期结果集是：[1,1,2][[1,1,2],[1,2,1],[2,1,1]]
class PermutationGenerator {
List<List<Integer>> result = new ArrayList<>();
public List<List<Integer>> permuteUnique(int[] nums) {
if(nums == null || nums.length == 0){
return result;
}
Arrays.sort(nums);
backtrack(nums, new ArrayList<>(), new boolean[100]);
return result;
}
private void backtrack(int[] nums, List<Integer> permutation, boolean[] seen){
if(permutation.size() == nums.length){
result.add(new ArrayList<>(permutation));
return;
}
for(int i = 0; i < nums.length; i++){
if(seen[i] || (i > 0 && nums[i] == nums[i - 1] && !seen[i - 1])){
continue;
}
seen[i] = true;
permutation.add(nums[i]);
backtrack(nums, permutation, seen);
seen[i] = false;
permutation.remove(permutation.size() - 1);
}
}
}
我的问题是，这怎么可能？如果代码是真的或假的，代码是有效的，但完全删除它是行不通的。
慕的地108432回答
-
有只小跳蛙
我可以确认您的代码在否定条件的最后一部分的情况下产生相同的结果，并且在删除条件时会产生不同的结果。这可能看起来像一个奇迹，除非你认为整个条件在循环中被评估了很多次，并且很可能是三种情况（有条件，有否定条件，没有条件）都有不同的处理和结果的方式。我想说的是，对于条件和否定的条件，可以达到相同的结果，但以不同的方式。这里就是这种情况。如果在循环中引入一些 printf 调试，您将看到以完全不同的方式获得结果。具有否定的现有条件允许完整条件在其他迭代中变为 true，而不是没有否定的条件。最终两者导致相同的结果纯属偶然（无需进一步研究算法）。下面是 number 的执行跟踪、完整条件的结果以及 、 和 的中间值：inumsseenresult无条件：0 F [1, 1, 2] [0, 0, 0] []0 T [1, 1, 2] [True, 0, 0] []1 T [1, 1, 2] [True, 0, 0] []2 F [1, 1, 2] [True, 0, 0] []0 T [1, 1, 2] [True, 0, True] []1 T [1, 1, 2] [True, 0, True] []2 T [1, 1, 2] [True, 0, True] []1 T [1, 1, 2] [False, 0, False] []2 F [1, 1, 2] [False, 0, False] []0 F [1, 1, 2] [False, 0, True] []0 T [1, 1, 2] [True, 0, True] []1 T [1, 1, 2] [True, 0, True] []2 T [1, 1, 2] [True, 0, True] []1 T [1, 1, 2] [False, 0, True] []2 T [1, 1, 2] [False, 0, True] []附带条件：seen[i-1]0 F [1, 1, 2] [0, 0, 0] []0 T [1, 1, 2] [True, 0, 0] []1 T [1, 1, 2] [True, 0, 0] []2 F [1, 1, 2] [True, 0, 0] []0 T [1, 1, 2] [True, 0, True] []1 T [1, 1, 2] [True, 0, True] []2 T [1, 1, 2] [True, 0, True] []1 F [1, 1, 2] [False, 0, False] []0 F [1, 1, 2] [False, True, False] []0 T [1, 1, 2] [True, True, False] []1 T [1, 1, 2] [True, True, False] []2 F [1, 1, 2] [True, True, False] []1 T [1, 1, 2] [False, True, False] [[1, 1, 2]]2 F [1, 1, 2] [False, True, False] [[1, 1, 2]]0 F [1, 1, 2] [False, True, True] [[1, 1, 2]]1 T [1, 1, 2] [False, True, True] [[1, 1, 2], [1, 2, 1]]2 T [1, 1, 2] [False, True, True] [[1, 1, 2], [1, 2, 1]]2 F [1, 1, 2] [False, False, False] [[1, 1, 2], [1, 2, 1]]0 F [1, 1, 2] [False, False, True] [[1, 1, 2], [1, 2, 1]]0 T [1, 1, 2] [True, False, True] [[1, 1, 2], [1, 2, 1]]1 T [1, 1, 2] [True, False, True] [[1, 1, 2], [1, 2, 1]]2 T [1, 1, 2] [True, False, True] [[1, 1, 2], [1, 2, 1]]1 F [1, 1, 2] [False, False, True] [[1, 1, 2], [1, 2, 1]]0 F [1, 1, 2] [False, True, True] [[1, 1, 2], [1, 2, 1]]1 T [1, 1, 2] [False, True, True] [[1, 1, 2], [1, 2, 1], [2, 1, 1]]2 T [1, 1, 2] [False, True, True] [[1, 1, 2], [1, 2, 1], [2, 1, 1]]2 T [1, 1, 2] [False, False, True] [[1, 1, 2], [1, 2, 1], [2, 1, 1]]而对于否定的条件：!seen[i-1]0 F [1, 1, 2] [0, 0, 0] []0 T [1, 1, 2] [True, 0, 0] []1 F [1, 1, 2] [True, 0, 0] []0 T [1, 1, 2] [True, True, 0] []1 T [1, 1, 2] [True, True, 0] []2 F [1, 1, 2] [True, True, 0] []2 F [1, 1, 2] [True, False, False] [[1, 1, 2]]0 T [1, 1, 2] [True, False, True] [[1, 1, 2]]1 F [1, 1, 2] [True, False, True] [[1, 1, 2]]2 T [1, 1, 2] [True, False, True] [[1, 1, 2], [1, 2, 1]]1 T [1, 1, 2] [False, False, False] [[1, 1, 2], [1, 2, 1]]2 F [1, 1, 2] [False, False, False] [[1, 1, 2], [1, 2, 1]]0 F [1, 1, 2] [False, False, True] [[1, 1, 2], [1, 2, 1]]0 T [1, 1, 2] [True, False, True] [[1, 1, 2], [1, 2, 1]]1 F [1, 1, 2] [True, False, True] [[1, 1, 2], [1, 2, 1]]2 T [1, 1, 2] [True, False, True] [[1, 1, 2], [1, 2, 1], [2, 1, 1]]1 T [1, 1, 2] [False, False, True] [[1, 1, 2], [1, 2, 1], [2, 1, 1]]2 T [1, 1, 2] [False, False, True] [[1, 1, 2], [1, 2, 1], [2, 1, 1]]在这三种情况下，执行步骤都不同。两个（偶然）具有相同的结果。 -
回首忆惘然
当您删除看到的 [i-1] 或 ！seen[i -1] 时，对于 2 个或更多 int 数组值匹配并实现的输入类型 nums[i] == nums[i - 1]if 条件获得 TRUE 并循环访问 int 数组，而不添加。并且“排列.add”和“排列.remove”被按顺序调用，对于第一个/最后一个元素，导致一个空集。使用 {1，1，2} 或 {1，2，2} 或 {1，2，1} 尝试调用的序列Add calledAdd calledRemove calledRemove calledAdd calledAdd calledRemove calledRemove called[]对于 {2，2，2}Add calledRemove called[]使用的代码： for(int i = 0; i < nums.length; i++){ //System.out.println(seen[i]); if(seen[i] || (i > 0 && nums[i] == nums[i - 1])){ //System.out.println("Inside if"); continue; } seen[i] = true; System.out.println("Add called"); permutation.add(nums[i]); backtrack(nums, permutation, seen); seen[i] = false; System.out.println("Remove called"); permutation.remove(permutation.size() - 1); }
随时随地看视频慕课网APP
相关分类
Java