chapter_backtracking/permutations_problem/ #477
Replies: 26 comments 21 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.
-
学习笔记,js版。 /* 全排列,有重复元素,回溯法,可指定子集长度 */
// @param {arr | str} nums
// @param {int} [len=nums.length]
// @returns {array}
// @example 'aabb',2 -> ['a','a'],['a','b'],['b','a'],['b','b']
function permute_backtracking(arr, len = arr.length) {
// 可接受字符串输入
const d = typeof arr === 'string' ? arr.split('') : arr
const [
res,
idxes, //计数各元素,以确保"全局范围内"同一元素不被重复使用
p, //具体排列(子集)
] = [[], [], []]
backtrack(len)
return res
function backtrack(len) {
// 计数各值,以确保"当前递归内"同一值不被重复展开递归
const vals = new Set()
/* 当状态长度等于元素数量时,记录解 */
if (p.length === len) {
return res.push([...p])
}
/* 遍历所有选择 */
d.map((e, i) => {
/* 剪枝 不允许重复选择同一元素,且不允许选择同值元素 */
if (idxes[i] || vals.has(e)) return
/* 尝试 做出选择,更新状态 */
idxes[i] = (idxes[i] ?? 0) + 1
vals.add(e)
p.push(e)
backtrack(len)
/* 回退 撤销选择,恢复状态 */
idxes[i]--
// vals.delete(e) //vals只存活于当前栈帧(stack frame)内,不会影响前后递归,故不必
p.pop()
})
}
} |
Beta Was this translation helpful? Give feedback.
-
C#框架的泛型优化(扩展实现了全排列),作者说完形填空就可以,个人认为如果要追求在极致的框架下完型填空,那么必须解开类型的枷锁,否则换成树或者链表或者其他类型又要重新复制粘贴一份
} |
Beta Was this translation helpful? Give feedback.
-
第一天学习
|
Beta Was this translation helpful? Give feedback.
-
duplicated在回退的过程中为什么不用撤销选择,而state和selected记录的都需要回退 |
Beta Was this translation helpful? Give feedback.
-
LeetCode对应题目传送门: 全排列I(无相等元素):https://leetcode.cn/problems/permutations/ 全排列 II(有相等元素):https://leetcode.cn/problems/permutations-ii/ |
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