mysql 网站开发 问好,工业设计公司发展方向,wordpress5.0代码执行,商业网站建站目的算法题
Leetcode 39. 组合总和
题目链接:39. 组合总和
大佬视频讲解#xff1a;组合总和视频讲解 个人思路 这道组合题主要是有总和的限制#xff0c;当递归和超过了总和就return#xff0c;递归时加上回溯去遍历数组。 解法
回溯法
把组合问题抽象为如下树形结构 如上… 算法题
Leetcode 39. 组合总和
题目链接:39. 组合总和
大佬视频讲解组合总和视频讲解 个人思路 这道组合题主要是有总和的限制当递归和超过了总和就return递归时加上回溯去遍历数组。 解法
回溯法
把组合问题抽象为如下树形结构 如上图因为本题没有组合数量要求仅仅是总和的限制所以递归没有层数的限制只要选取的元素总和超过target就返回 回溯法三部曲
1.递归函数参数 定义两个全局变量二维数组result存放结果集数组path存放符合条件的结果。 首先是题目中给出的参数集合candidates, 和目标值target。 此外还需要定义int型的sum变量来统计单一结果path里的总和startIndex来控制for循环的起始位置. 关于startIndex的使用如果是一个集合来求组合的话就需要startIndex比如组合三。如果是多个集合取组合各个集合之间相互不影响那么就不用startIndex例子Leetcode 77.组合 2.递归终止条件 终止只有两种情况sum大于target和sum等于target。sum等于target的时候需要收集结果 3.单层搜索的逻辑 单层for循环依然是从startIndex开始搜索candidates集合。 本题元素为可重复选取的。所以在递归时i不需要加1。 剪枝
这道题的剪枝就是对总集合排序之后如果下一层的sum就是本层的 sum candidates[i]已经大于target就可以结束本轮for循环的遍历。
class Solution {public ListListInteger combinationSum(int[] candidates, int target) {ListListInteger res new ArrayList();Arrays.sort(candidates); // 先进行排序backtracking(res, new ArrayList(), candidates, target, 0, 0);return res;}public void backtracking(ListListInteger res, ListInteger path, int[] candidates, int target, int sum, int idx) {// 找到了数字和为 target 的组合if (sum target) {res.add(new ArrayList(path));return;}for (int i idx; i candidates.length; i) {// 如果 sum candidates[i] target 就终止遍历if (sum candidates[i] target) break;//剪枝path.add(candidates[i]);backtracking(res, path, candidates, target, sum candidates[i], i);path.remove(path.size() - 1); // 回溯移除路径 path 最后一个元素}}
} 时间复杂度:O(n * 2^n))循环n个元素2^n表示所有可能的子集数量 空间复杂度:O(n);递归栈的深度最多为 n Leetcode 40.组合总和II
题目链接:40.组合总和II
大佬视频讲解组合总和II视频讲解 个人思路 这道题的集合数组candidates有重复元素但还不能有重复的组合这是这道题难的关键思路就是 用一个标记数组标记该元素层次上是否使用过使用过的就跳过这样不会出现重复的组合。 解法
回溯法
把组合问题抽象为如下树形结构 “使用过”在这个树形结构上是有两个维度的一个维度是同一树枝上使用过一个维度是同一树层上使用过。 元素在同一个组合内是可以重复的怎么重复都没事但两个组合不能相同。所以要去重的是同一树层上的“使用过”同一树枝上的都是一个组合里的元素不用去重。(强调:树层去重的话需要对数组排序) 回溯法三部曲
1.递归函数参数
除开存放数组的集合和符合条件的路径, 这道题需要加一个bool型数组used用来记录同一树枝上的元素是否使用过。这个集合去重的重任就是used来完成的。 2.递归终止条件
终止条件为 sum target 和 sum target。
其中sum target 这个条件可以省略因为在递归单层遍历的时候会有剪枝的操作.
3.单层搜索的逻辑
如抽线的树形结构要去重的是“同一树层上的使用过”,判断逻辑如下:
如果candidates[i] candidates[i - 1] 并且 used[i - 1] false就说明前一个树枝使用了candidates[i - 1]也就是说同一树层使用过candidates[i - 1]。此时for循环里就应该做continue的操作。
所以值为 used[i - 1] true说明同一树枝candidates[i - 1]使用过
used[i - 1] false说明同一树层candidates[i - 1]使用过 因为同一树层used[i - 1] false 才能表示当前取的 candidates[i] 是从 candidates[i - 1] 回溯而来的。而 used[i - 1] true说明是进入下一层递归去下一个数所以是树枝上 剪枝
当和大于目标值直接返回即sum candidates[i] target为剪枝操作 class Solution {LinkedListInteger path new LinkedList();ListListInteger ans new ArrayList();boolean[] used;int sum 0;public ListListInteger combinationSum2(int[] candidates, int target) {used new boolean[candidates.length];// 加标志数组用来辅助判断同层节点是否已经遍历Arrays.fill(used, false);// 为了将重复的数字都放到一起所以先进行排序Arrays.sort(candidates);backTracking(candidates, target, 0);return ans;}private void backTracking(int[] candidates, int target, int startIndex) {if (sum target) {ans.add(new ArrayList(path));}for (int i startIndex; i candidates.length; i) {if (sum candidates[i] target) {break;}// 出现重复节点同层的第一个节点已经被访问过所以直接跳过if (i 0 candidates[i] candidates[i - 1] !used[i - 1]) {continue;}used[i] true;sum candidates[i];path.add(candidates[i]);// 每个节点仅能选择一次所以从下一位开始backTracking(candidates, target, i 1);used[i] false;sum - candidates[i];path.removeLast();}}
}时间复杂度:O(n * 2^n))循环n个元素2^n表示所有可能的子集数量 空间复杂度:O(n);递归栈的深度最多为 n Leetcode 131.分割回文串
题目链接:131.分割回文串
大佬视频讲解分割回文串视频讲解 个人思路
既要判断是否为回文子串还要切割只能用回溯法了但不知道如何切割这是个问题... 解法
回溯法
把分割问题抽象为如下树形结构 其实本题的切割问题类似组合问题。
例如对于字符串abcdef
组合问题选取一个a之后在bcdef中再去选取第二个选取b之后在cdef中再选取第三个.....切割问题切割一个a之后在bcdef中再去切割第二段切割b之后在cdef中再切割第三段..... 回溯法三部曲
1.递归函数参数 全局变量数组path存放切割后回文的子串二维数组result存放结果集。 本题递归函数参数还需要startIndex因为切割过的地方不能重复切割 2.递归函数终止条件 按照切割的思想去看切割线切到了字符串最后面说明找到了一种切割方法此时就是本层递归的终止条件。 那么在代码里什么是切割线呢其实在处理组合问题的时候递归参数需要传入startIndex表示下一轮递归遍历的起始位置这个startIndex就是切割线。 3.单层搜索的逻辑 在for (int i startIndex; i s.size(); i)循环中我们 定义了起始位置startIndex那么 [startIndex, i] 就是要截取的子串。 首先判断这个子串是不是回文如果是回文就加入path中path用来记录切割过的回文子串。 注意切割过的位置不能重复切割所以backtracking(s, i 1); 传入下一层的起始位置为i 1。 判断回文子串
可以使用双指针法一个指针从前向后一个指针从后向前如果前后指针所指向的元素是相等的就是回文字符串了。
这里需要一个个判断 class Solution {ListListString result new ArrayList();//结果集DequeString path new LinkedList();public ListListString partition(String s) {backTracking(s, 0);return result;}private void backTracking(String s, int startIndex) {//如果起始位置大于s的大小说明找到了一组分割方案if (startIndex s.length()) {result.add(new ArrayList(path));return;}for (int i startIndex; i s.length(); i) {//如果是回文子串则记录if (isPalindrome(s, startIndex, i)) {String str s.substring(startIndex, i 1);path.addLast(str);} else {continue;}backTracking(s, i 1);//起始位置后移保证不重复path.removeLast();}}//判断是否是回文串private boolean isPalindrome(String s, int startIndex, int end) {for (int i startIndex, j end; i j; i, j--) {if (s.charAt(i) ! s.charAt(j)) {return false;}}return true;}
} 时间复杂度:O(n * 2^n))循环n个元素2^n表示所有可能的子集数量 空间复杂度:O(n);递归栈的深度最多为 n 以上是个人的思考反思与总结若只想根据系列题刷参考卡哥的网址代码随想录算法官网
