综合商城网站程序,wordpress导航改哪个php文件夹,交友平台网站建设,深圳微信网站开发公司第七章 回溯算法part03● 39. 组合总和
● 40.组合总和II
● 131.分割回文串详细布置 39. 组合总和 本题是 集合里元素可以用无数次#xff0c;那么和组合问题的差别 其实仅在于 startIndex上的控制题目链接/文章讲解#xff1a;https://programmercarl.com/0039.%E7%BB%84%E…第七章 回溯算法part03● 39. 组合总和
● 40.组合总和II
● 131.分割回文串详细布置 39. 组合总和 本题是 集合里元素可以用无数次那么和组合问题的差别 其实仅在于 startIndex上的控制题目链接/文章讲解https://programmercarl.com/0039.%E7%BB%84%E5%90%88%E6%80%BB%E5%92%8C.html
视频讲解https://www.bilibili.com/video/BV1KT4y1M7HJ 40.组合总和II 本题开始涉及到一个问题了去重。注意题目中给我们 集合是有重复元素的那么求出来的 组合有可能重复但题目要求不能有重复组合。 题目链接/文章讲解https://programmercarl.com/0040.%E7%BB%84%E5%90%88%E6%80%BB%E5%92%8CII.html
视频讲解https://www.bilibili.com/video/BV12V4y1V73A131.分割回文串 本题较难大家先看视频来理解 分割问题明天还会有一道分割问题先打打基础。 https://programmercarl.com/0131.%E5%88%86%E5%89%B2%E5%9B%9E%E6%96%87%E4%B8%B2.html
视频讲解https://www.bilibili.com/video/BV1c54y1e7k6 往日任务
● day 1 任务以及具体安排https://docs.qq.com/doc/DUG9UR2ZUc3BjRUdY
● day 2 任务以及具体安排https://docs.qq.com/doc/DUGRwWXNOVEpyaVpG
● day 3 任务以及具体安排https://docs.qq.com/doc/DUGdqYWNYeGhlaVR6
● day 4 任务以及具体安排https://docs.qq.com/doc/DUFNjYUxYRHRVWklp
● day 5 周日休息
● day 6 任务以及具体安排https://docs.qq.com/doc/DUEtFSGdreWRuR2p4
● day 7 任务以及具体安排https://docs.qq.com/doc/DUElCb1NyTVpXa0Jj
● day 8 任务以及具体安排https://docs.qq.com/doc/DUGdsY2JFaFhDRVZH
● day 9 任务以及具体安排https://docs.qq.com/doc/DUHVXSnZNaXpVUHN4
● day 10 任务以及具体安排https://docs.qq.com/doc/DUElqeHh3cndDbW1Q
●day 11 任务以及具体安排https://docs.qq.com/doc/DUHh6UE5hUUZOZUd0
●day 12 周日休息
●day 13 任务以及具体安排https://docs.qq.com/doc/DUHNpa3F4b2dMUWJ3
●day 14 任务以及具体安排https://docs.qq.com/doc/DUHRtdXZZSWFkeGdE
●day 15 任务以及具体安排https://docs.qq.com/doc/DUHN0ZVJuRmVYeWNv
●day 16 任务以及具体安排https://docs.qq.com/doc/DUHBQRm1aSWR4T2NK
●day 17 任务以及具体安排https://docs.qq.com/doc/DUFpXY3hBZkpabWFY
●day 18 任务以及具体安排https://docs.qq.com/doc/DUFFiVHl3YVlReVlr
●day 19 周日休息
●day 20 任务以及具体安排https://docs.qq.com/doc/DUGFRU2V6Z1F4alBH
●day 21 任务以及具体安排https://docs.qq.com/doc/DUHl2SGNvZmxqZm1X
●day 22 任务以及具体安排https://docs.qq.com/doc/DUHplVUp5YnN1bnBL
●day 23 任务以及具体安排https://docs.qq.com/doc/DUFBUQmxpQU1pa29C
●day 24 任务以及具体安排https://docs.qq.com/doc/DUEhsb0pUUm1WT2NP
●day 25 任务以及具体安排https://docs.qq.com/doc/DUExTYXVzU1BiU2Zl
day27
组合总和 class Solution {ListListInteger result new ArrayList();LinkedListInteger path new LinkedList();int sum 0;//组合问题,用回溯,回溯函数里面有for循环,for循环里面有回溯函数;//回溯宽度:for写每次分支的宽度,从index到最后;//回溯深度:通过sum去判断public ListListInteger combinationSum(int[] candidates, int target) {backtracting( candidates, target, 0);return result;}private void backtracting(int[] candidates, int target, int index){ if(sum target) return;if(sum target) {result.add(new ArrayList(path));}//回溯深度结束for( int i index; i candidates.length; i){//每次分支的宽度path.add(candidates[i]);sum candidates[i];backtracting(candidates,target,i);//元素可以重复,不用1sum -candidates[i];path.removeLast();}}}//剪枝class Solution {ListListInteger result new ArrayList();LinkedListInteger path new LinkedList();int sum 0;public ListListInteger combinationSum(int[] candidates, int target) {Arrays.sort(candidates);//排序backtracting( candidates, target, 0);return result;}private void backtracting(int[] candidates, int target, int index){ if(sum target) return;if(sum target) {result.add(new ArrayList(path));}for( int i index; i candidates.length sum candidates[i] target; i){//如果回溯宽度上的下一个分支target,直接退出这次for循环path.add(candidates[i]);sum candidates[i];backtracting(candidates,target,i);sum -candidates[i];path.removeLast();}}} 组合总和2 class Solution {ListListInteger result new ArrayList();//保存结果LinkedListInteger path new LinkedList();//结果集中的每一个集合,用linkedlist方便随后一个元素弹出,便于回溯处理int sum 0;//用于判断回溯深度什么时候停止boolean[] used;//控制树枝不去重public ListListInteger combinationSum2(int[] candidates, int target) {//本题关键在于区分树层去重和树枝去重,target8,{1,7}和{1,7}不能同时存在,树层去重我们在for循环下面(回溯宽度方向上)做一个判断;//树枝方向上不需要去重,我们用used[]数组去标记此时到底是在树枝方向上还是树层方向上//回溯深度上的结束我们用sum target以及sum target去控制//回溯宽度上我们用i遍历到candidates.length去控制Arrays.sort(candidates);//排序,方便去重used new boolean[candidates.length];backtracking(candidates,target,0);//index用于控制for循环(回溯宽度方向的开始和停止)return result;}private void backtracking(int[] candidates, int target, int index){//回溯深度控制if(sum target) return;if(sum target) {result.add(new ArrayList(path));//收货return;}//回溯宽度控制for(int i index; i candidates.length; i){if( i 0 candidates[i] candidates[i-1] used[i-1] ! true) continue;//树层去重,树枝不去重//注意是continue而不是return或者break,只跳过这一个重复数就行,后面非重复元素还要继续判断的path.add(candidates[i]);//加到可能的路径中sum candidates[i];used[i] true;backtracking(candidates, target, i1);//进入树枝(下一层回溯),里面的判断都是used[i - 1]为trueused[i] false;//回溯到树层sum -candidates[i];path.removeLast();}}} 分割回文串 class Solution {LinkedListString path new LinkedList();ListListString result new ArrayList();public ListListString partition(String s) {//分割回文子串和组合问题本质是一样的,只不是组合问题是选择每次添加的元素的index,而回文串是选择每次子串的结束位置的indexbacktracking(s, 0);return result;}private void backtracking(String s, int index){if( index s.length()) {result.add(new ArrayList(path));//path类型转换return;//结束深度方向的回溯,回文串合法性交给每次index划分后去判断}// 遍历所有的子串for (int i index; i s.length(); i) {String substring s.substring(index, i1 ); // 提取子串,左闭右开if (!check(s, index, i)) continue; // 如果不是回文串跳过 // 添加回文子串到路径path.add(substring);// 继续回溯处理下一个子串backtracking(s, i 1); // 回溯移除当前子串path.removeLast();}}private boolean check( String s, int left,int right){while(left right){if(s.charAt(left) s.charAt(right)){left;right--;}else return false;}return true;}}//也可以不用s.substring(),可以每次进入backtricking就new一个StringBuilder 小结:
回溯就是深度控制宽度控制,进入回溯函数之后先判断是不是深度要结束了(不进入下一层回溯函数),然后用for循环控制宽度,如果满足条件就收集起来1,然后进入下一层回溯函数,回溯函数出来之后要把收集的1再抛弃出去,这样才能进入下一个大分支.
感受:
参考了一个用c做算法题的大佬的做题方式,写了很多注释,也加入了自己的小结,独立把代码写出来后对回溯的理解更深了.还是要慢慢做题,写上自己的理解,做一道题有一道题的收获. 感谢大佬们分享:
代码随想录-算法训练营day27【回溯算法03组合总和、分割回文串】-CSDN博客
代码随想录算法训练营第二十三天|Day23 回溯算法-CSDN博客
