chapter_backtracking/permutations_problem/ #477
Replies: 21 comments 20 replies
-
大佬写得真的简单易懂,牛!!! |
Beta Was this translation helpful? Give feedback.
-
这个duplicated有点难,每轮选择都有一个,duplicated设置在for循环遍历前面实在是太讲究了 |
Beta Was this translation helpful? Give feedback.
-
每次固定数组的一位值 public static void main(String[] args)
{
int[] arr = {1, 1, 2};
allQuery(arr, 0, arr.length - 1);
}
public static void allQuery(int[] arr, int start, int end)
{
if (start == end)
{
System.out.println(Arrays.toString(arr));
return;
}
for (int i = start; i <= end; i++)
{
// 选取一个固定在start位置
change2(arr, start, i);
allQuery(arr, start + 1, end);
// 恢复
change2(arr, start, i);
}
}
public static void change(int[] arr, int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static void change2(int[] arr, int i, int j)
{
if (i == j)
{
return;
}
arr[i] = arr[i] ^ arr[j];
arr[j] = arr[i] ^ arr[j];
arr[i] = arr[i] ^ arr[j];
} |
Beta Was this translation helpful? Give feedback.
-
不重复元素全排列的那个代码,是不是时间复杂度也挺高? 至少是 n*n! 吧 ? 因为每次都需要遍历choices数组 |
Beta Was this translation helpful? Give feedback.
-
假如有一nums[1,2,3,1],那么当nums[0]使用后被放入哈希表,直接判断元素不存在于哈希表就可以完成剪枝掉重复元素和表达selected了吧? |
Beta Was this translation helpful? Give feedback.
-
“相等元素剪枝:每轮选择(即每个开启的 backtrack 函数)都包含一个 duplicated 。它记录的是在遍历中哪些元素已被选择过,作用是保证相等元素只被选择一次。” |
Beta Was this translation helpful? Give feedback.
-
可以加一个回溯和分支界限的对比吗 |
Beta Was this translation helpful? Give feedback.
-
是不是可以这么理解
|
Beta Was this translation helpful? Give feedback.
-
我在c#的实现中看到了如下写法,但我没有找到相关文档,这种方式是否有误 HashSet<int> duplicated = []; |
Beta Was this translation helpful? Give feedback.
-
你好,请问“假设元素两两之间互不相同,则 𝑛 个元素共有 𝑛! 种排列(阶乘);在记录结果时,需要复制长度为 𝑛 的列表,使用 𝑂(𝑛) 时间。因此时间复杂度为 𝑂(𝑛!𝑛) 。”这里的“需要赋值长度为n的列表”指的是if (state.size() == choices.size()) { |
Beta Was this translation helpful? Give feedback.
-
请问duplicated的O(n^2)空间复杂度如何推算呢? |
Beta Was this translation helpful? Give feedback.
-
|
Beta Was this translation helpful? Give feedback.
-
有相同元素的情况,可不可以写个函数先把重复的元素剔除,然后就和第一种情况一样了,这样会不会更简单一些? |
Beta Was this translation helpful? Give feedback.
-
go语言版本都没有在记录解刹车,还让它多秏了点油 |
Beta Was this translation helpful? Give feedback.
-
着实是茅塞顿开了, |
Beta Was this translation helpful? Give feedback.
-
hello,K神,我记得你说空间复杂度统计的是暂存与输出空间,那么这个全排列问题的空间复杂度统计应该要算 |
Beta Was this translation helpful? Give feedback.
-
两种剪枝方式介绍的深入浅出,写的真好!! |
Beta Was this translation helpful? Give feedback.
-
两种剪枝实现的目的不同! |
Beta Was this translation helpful? Give feedback.
-
duplicated.find(choice) == duplicated.end() |
Beta Was this translation helpful? Give feedback.
-
def backtrack(
state: list[int], choices: list[int], selected: list[bool], res: list[list[int]]
):
"""回溯算法:全排列 I"""
# 当状态长度等于元素数量时,记录解
if len(state) == len(choices):
res.append(list(state))
return
# 遍历所有选择
for i, choice in enumerate(choices):
# 剪枝:不允许重复选择元素
if not selected[i]:
# 尝试:做出选择,更新状态
selected[i] = True
state.append(choice)
# 进行下一轮选择
backtrack(state, choices, selected, res)
# 回退:撤销选择,恢复到之前的状态
selected[i] = False
state.pop()
def permutations_i(nums: list[int]) -> list[list[int]]:
"""全排列 I"""
res = []
backtrack(state=[], choices=nums, selected=[False] * len(nums), res=res)
return res 里为什么把 |
Beta Was this translation helpful? Give feedback.
-
chapter_backtracking/permutations_problem/
一本动画图解、能运行、可提问的数据结构与算法入门书
https://www.hello-algo.com/chapter_backtracking/permutations_problem/
Beta Was this translation helpful? Give feedback.
All reactions