刷题
刷题
learn
learn
日期
Sep 8, 2024 → Sep 13, 2024
带路径的递归 vs 不带路径的递归（大部分dp，状态压缩dp认为是路径简化了结构）
任何递归都是dfs且非常灵活。回溯这个术语并不重要
- 返回字符串的全部子序列，子序列要求去重。时间复杂度
- 返回数组的所有组合，可以无视元素顺序，但要求去重。时间复杂度
- 返回没有重复值数组的全部排列。时间复杂度
- 思路：比如有一个的数组，可以考虑当来到第一个位置的时候，后面产生了怎样的排列（用递归解决）；当来到第一个位置的时候，后面产生了怎样的排列，依次递归进行
- 注意，每次递归结束的时候注意恢复现场，回到递归前的状态；
- 返回可能有重复值数组的全部排列，排列要求去重。时间复杂度
- 思路和第三题完全相同，唯一的区别在于在排列前先将数组排个序，然后让每次交换的两个数都不一样即可
- 增加一个HashSet判断即可
- 用递归逆序一个栈。时间复杂度
- 逆序栈的两个方法：
- 要么开一个额外的栈，然后直接倒进去，额外空间复杂度是，额外时间复杂度是
- 要么用递归的方法，额外空间复杂度是，额外时间复杂度是（实际不会用，只是为了理解递归）
- 用递归排序一个栈。时间复杂度
- 打印层汉诺塔问题的最优移动轨迹。时间复杂度