电信保温杯笔记——代码随想录 刷题攻略 回溯算法

• 代码随想录 刷题攻略 笔记
• 1.关于回溯算法，你该了解这些！
• 2.回溯算法：组合问题
• • 第77题. 组合
• 3.回溯算法：组合问题再剪剪枝
• 4.回溯算法：求组合总和！
• • 216.组合总和III
• 5.回溯算法：电话号码的字母组合
• • 17.电话号码的字母组合
• 6.本周小结！（回溯算法系列一）
• 小结
• • 核心代码
• 7.回溯算法：求组合总和（二）
• • 39. 组合总和
• 8.回溯算法：求组合总和（三）
• • 40.组合总和II
• 9.回溯算法：分割回文串
• • 131.分割回文串
• 10.回溯算法：复原IP地址
• • 93.复原IP地址
• 11.回溯算法：求子集问题！
• • 78.子集
• 12.本周小结！（回溯算法系列二）
• 13.回溯算法：求子集问题（二）
• • 90.子集II
• 14.回溯算法：递增子序列
• • 491.递增子序列
• 15.回溯算法：排列问题！
• • 46.全排列
• 16.回溯算法：排列问题（二）
• • 47.全排列 II
• 17.本周小结！（回溯算法系列三）
• 18.回溯算法去重问题的另一种写法
• 19.回溯算法：重新安排行程
• • 332.重新安排行程
• 20.回溯算法：N皇后问题
• • 第51题. N皇后
  • • 方式一：使用数组代替位运算
    • 方式二
• 21.回溯算法：解数独
• • 37. 解数独
• 22.一篇总结带你彻底搞透回溯算法！

代码随想录 刷题攻略 笔记 电信保温杯笔记——代码随想录 刷题攻略
电信保温杯笔记——代码随想录 刷题攻略 笔记

文章图片

1.关于回溯算法，你该了解这些！ 讲义地址
2.回溯算法：组合问题 讲义地址
第77题. 组合 leetcode地址

public class Solution { List> result = new ArrayList<>(); LinkedList path = new LinkedList<>(); public List> combine(int n, int k){ combineHelper(n, k, 1); return result; }public void combineHelper(int n, int k, int startIndex){ if (path.size() == k){ result.add(new ArrayList<>(path)); return; } for (int i = startIndex; i <= n - (k - path.size()) + 1; i++){ path.add(i); combineHelper(n, k, i+1); path.removeLast(); } } }

文章图片

3.回溯算法：组合问题再剪剪枝 讲义地址
4.回溯算法：求组合总和！ 讲义地址
216.组合总和III leetcode地址

class Solution { List> res = new ArrayList<>(); LinkedList path = new LinkedList<>(); public List> combinationSum3(int k, int n) { combineHelper(k, n, 1, 0); return res; }public void combineHelper(int k, int n, int startNum, int sum){ if (sum > n){ return; } if (path.size() == k){ if (sum == n){ res.add(new ArrayList<>(path)); return; } } for (int i = startNum; i <= 9 - (k - path.size()) + 1; i++){ path.add(i); combineHelper(k, n, i + 1, sum + i); path.removeLast(); } }}

文章图片

5.回溯算法：电话号码的字母组合 讲义地址
17.电话号码的字母组合 leetcode地址

class Solution { List res = new ArrayList<>(); StringBuilder path = new StringBuilder(); public List letterCombinations(String digits) { if (digits == null || digits.length() == 0){ return res; } String[] map = new String[]{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; combineHelper(digits, map, 0); return res; } public void combineHelper(String digits, String[] map, int startNum){ if (path.length() == digits.length()){ res.add(path.toString()); return; } int temp = digits.charAt(startNum) - '0'; String str = map[temp]; for(int i = 0; i < str.length(); i++){ path.append(str.charAt(i)); combineHelper(digits, map, startNum + 1); path.deleteCharAt(path.length() -1); } } }

文章图片

6.本周小结！（回溯算法系列一） 讲义地址
小结 核心代码

class Solution { List res = new ArrayList<>(); // 保存结果 StringBuilder path = new StringBuilder(); //保存满足条件的项public List letterCombinations(String digits) { if (digits == null || digits.length() == 0){ res.add(path.toString()); return res; } String[] map = new String[]{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; combineHelper(digits, map, 0); return res; } // 递归函数变量：项的最终长度，项取值的集合，项的当前长度 public void combineHelper(String digits, String[] map, int startNum){ if (path.length() == digits.length()){ // 保存满足条件的项 res.add(path.toString()); return; } int temp = digits.charAt(startNum) - '0'; String str = map[temp]; for(int i = 0; i < str.length(); i++){ // 项某个位置遍历取值 path.append(str.charAt(i)); //项长度增加 combineHelper(digits, map, startNum + 1); path.deleteCharAt(path.length() -1); //项长度减小 } } }

7.回溯算法：求组合总和（二） 讲义地址
39. 组合总和 leetcode地址

class Solution { List> res = new ArrayList<>(); LinkedList path = new LinkedList<>(); public List> combinationSum(int[] candidates, int target) { if (candidates == null || candidates.length == 0){ return res; } Arrays.sort(candidates); combineHelper(candidates, target, 0, 0); return res; }public void combineHelper(int[] candidates, int target, int sum, int idx){ // # if (sum == target){ res.add(new ArrayList<>(path)); return; }for (int i = idx; i < candidates.length; i++){ if (sum + candidates[i]> target){ return; // 这里可以return，可以break，因为candidates是经过排序的，所以没有关系，这个判断也可以写在#号的位置，但那样就多了path的add和removeLast的步骤，效率变低 } path.add(candidates[i]); combineHelper(candidates, target, sum + candidates[i], i); // 这个i是与前门题目的区别 path.removeLast(); } } }

文章图片

8.回溯算法：求组合总和（三） 讲义地址
40.组合总和II leetcode地址

class Solution { List> lists = new ArrayList<>(); LinkedList path = new LinkedList<>(); public List> combinationSum2(int[] candidates, int target) { //为了将重复的数字都放到一起，所以先进行排序 Arrays.sort(candidates); //加标志数组，用来辅助判断同层节点是否已经遍历 boolean[] flag = new boolean[candidates.length]; backTracking(candidates, target, 0, 0, flag); return lists; }public void backTracking(int[] candidates, int target, int sum, int index, boolean[] flag) { if (sum == target) { lists.add(new ArrayList(path)); return; }for (int i = index; i < candidates.length; i++) { // i 是从0开始还是index开始，决定了它是否是组合 if (sum + candidates[i] > target){ return; } //出现重复节点，同层的第一个节点已经被访问过，所以直接跳过 if (i > 0 && candidates[i] == candidates[i - 1] && !flag[i - 1]) { continue; } flag[i] = true; path.add(candidates[i]); //每个节点仅能选择一次，所以从下一位开始 backTracking(candidates, target, sum + candidates[i], i + 1, flag); path.removeLast(); flag[i] = false; } } }

文章图片

9.回溯算法：分割回文串 讲义地址
131.分割回文串 【算法与数据结构|电信保温杯笔记——代码随想录 刷题攻略 回溯算法】leetcode地址

class Solution { List> res = new ArrayList<>(); LinkedList path = new LinkedList<>(); public List> partition(String s) { backTracking(s, 0); return res; }public void backTracking (String s, int idx){ if (idx >= s.length()){ res.add(new ArrayList<>(path)); return; }for (int i = idx; i < s.length(); i++){ if (!isPalindrome(s, idx, i)){ continue; } String str = s.substring(idx, i + 1); path.add(str); backTracking(s, i + 1); path.removeLast(); } }public boolean isPalindrome(String str, int left, int right){ for (int i = left, j = right; i < j; i++, j--){ if (str.charAt(i) != str.charAt(j)){ return false; } } return true; } }

文章图片

10.回溯算法：复原IP地址 讲义地址
93.复原IP地址 leetcode地址

class Solution { List res = new ArrayList(); StringBuilder path = new StringBuilder(); public List restoreIpAddresses(String s) { restoreIpAddressesHelper(s, 0, 0); return res; }public void restoreIpAddressesHelper(String s, int start, int number) { if (start == s.length() && number == 4) { res.add(path.toString()); return; } if (start == s.length() || number > 4){ return; } for (int i = start; i < start + 3 && i < s.length(); i++){ if (i - start > 0 && s.charAt(start) == '0'){ continue; } int temp= Integer.parseInt(s.substring(start, i + 1)); if (temp < 0 || temp > 255){ continue; } path.append(s.substring(start, i + 1)); if (number < 3) { path.append("."); } restoreIpAddressesHelper(s, i + 1, number + 1); path.delete(start + number, i + number + 2); } } }

文章图片

11.回溯算法：求子集问题！ 讲义地址
78.子集 leetcode地址

class Solution { List> res = new ArrayList<>(); LinkedList path = new LinkedList<>(); public List> subsets(int[] nums) { res.add(new ArrayList<>()); subsetsHelper(nums, 0); return res; } public void subsetsHelper(int[] nums, int startNum){ if (startNum == nums.length){ return; } for (int i = startNum; i < nums.length; i++){ path.add(nums[i]); res.add(new ArrayList<>(path)); subsetsHelper(nums, i + 1); path.removeLast(); } } }

文章图片

12.本周小结！（回溯算法系列二） 讲义地址
13.回溯算法：求子集问题（二） 讲义地址
90.子集II leetcode地址

class Solution { List> res = new ArrayList<>(); LinkedList path = new LinkedList<>(); public List> subsetsWithDup(int[] nums) { Arrays.sort(nums); boolean[] flag = new boolean[nums.length]; res.add(new ArrayList<>()); subsetsWithDupHelper(nums, 0, flag); return res; } public void subsetsWithDupHelper(int[] nums, int startNum, boolean[] flag){ if (startNum == nums.length){ return; } for (int i = startNum; i < nums.length; i++){ if (i > 0 && nums[i] == nums[i - 1] && !flag[i-1]){ continue; } flag[i] = true; path.add(nums[i]); res.add(new ArrayList<>(path)); subsetsWithDupHelper(nums, i + 1, flag); path.removeLast(); flag[i] = false; } } }

文章图片

14.回溯算法：递增子序列 讲义地址
491.递增子序列 leetcode地址

class Solution { List> res = new ArrayList<>(); LinkedList path = new LinkedList<>(); public List> findSubsequences(int[] nums) { findSubsequencesHelper(nums, 0); return res; }public void findSubsequencesHelper(int[] nums, int startNum){ if (path.size() > 1){ res.add(new ArrayList<>(path)); } HashMap map = new HashMap<>(); for (int i = startNum; i < nums.length; i++){ if (map.getOrDefault(nums[i], 0) > 0){ // 已经用过 continue; } if (path.size() > 0 && path.getLast() > nums[i]){ // 不递增 continue; } // 没用过 map.put(nums[i], 1); path.add(nums[i]); findSubsequencesHelper(nums, i + 1); path.removeLast(); } } }

文章图片

15.回溯算法：排列问题！ 讲义地址
46.全排列 leetcode地址

class Solution { List> res = new ArrayList<>(); LinkedList path = new LinkedList<>(); public List> permute(int[] nums) { boolean[] flag = new boolean[nums.length]; permuteHelper(nums, 0, flag); return res; } public void permuteHelper(int[] nums, int k, boolean[] flag){ if (k == nums.length){ res.add(new ArrayList<>(path)); return; }for (int i = 0; i < nums.length; i++){ if (flag[i]){ continue; } path.add(nums[i]); flag[i] = true; permuteHelper(nums, k + 1, flag); path.removeLast(); flag[i] = false; } } }

文章图片

16.回溯算法：排列问题（二） 讲义地址
47.全排列 II leetcode地址

class Solution { List> res = new ArrayList<>(); LinkedList path = new LinkedList<>(); public List> permuteUnique(int[] nums) { Arrays.sort(nums); boolean[] flag = new boolean[nums.length]; permuteUniqueHelper(nums, 0, flag); return res; }public void permuteUniqueHelper(int[] nums, int k, boolean[] flag){ if (k == nums.length){ res.add(new ArrayList<>(path)); return; } for (int i = 0; i < nums.length; i++){ if (i > 0 && nums[i] == nums[i - 1] && !flag[i - 1]){ continue; } if (!flag[i]){ flag[i] = true; path.add(nums[i]); permuteUniqueHelper(nums, k + 1, flag); path.removeLast(); flag[i] = false; } } } }

文章图片

17.本周小结！（回溯算法系列三） 讲义地址
18.回溯算法去重问题的另一种写法 讲义地址
19.回溯算法：重新安排行程 讲义地址
332.重新安排行程 [leetcode地址](

1

20.回溯算法：N皇后问题 讲义地址
第51题. N皇后 leetcode地址
左神视频有最高效的做法：位运算，一周刷爆LeetCode，算法da神左神（左程云）耗时100天打造算法与数据结构基础到高级全家桶教程，直击BTAJ等一线大厂必问算法面试题真题详解 笔记
方式一：使用数组代替位运算

class Solution { List> res = new ArrayList<>(); LinkedList path = new LinkedList<>(); public List> solveNQueens(int n) { if (n == 0){ return res; } if (n == 1){ path.add("Q"); res.add(new ArrayList<>(path)); return res; } int[] colLim = new int[n]; int[] leftLim = new int[n]; int[] rightLim = new int[n]; Arrays.fill(colLim, 1); Arrays.fill(leftLim, 1); Arrays.fill(rightLim, 1); solveNQueensHelper(n, colLim, leftLim, rightLim); return res; } public void solveNQueensHelper(int n, int[] colLim, int[] leftLim, int[] rightLim){ if (path.size() == n){ res.add(new ArrayList<>(path)); return; } int[] newLeftLim = getLeftLim(leftLim); int[] newRightLim = getRightLim(rightLim); int[] flag = getFlag(colLim, newLeftLim, newRightLim); for (int i = 0; i < n; i ++){ if (flag[i] == 0){ continue; } StringBuilder sb = new StringBuilder(); for (int j = 0; j < n; j++){ if (j == i){ sb.append('Q'); }else{ sb.append('.'); } } path.add(sb.toString()); colLim[i] = 0; newLeftLim[i] = 0; newRightLim[i] = 0; solveNQueensHelper(n, colLim, newLeftLim, newRightLim); colLim[i] = 1; newLeftLim[i] = 1; newRightLim[i] = 1; path.removeLast(); } } public int[] getLeftLim(int[] leftLim){ int len = leftLim.length; int[] newLeftLim = new int[len]; for (int i = 0; i < len - 1; i++){ newLeftLim[i] = leftLim[i + 1]; } newLeftLim[len - 1] = 1; return newLeftLim; } public int[] getRightLim(int[] rightLim){ int len = rightLim.length; int[] newRightLim = new int[len]; for (int i = len - 1; i > 0; i--){ newRightLim[i] = rightLim[i - 1]; } newRightLim[0] = 1; return newRightLim; } public int[] getFlag(int[] colLim, int[] leftLim, int[] rightLim){ int len = colLim.length; int[] flag = new int[len]; for (int i = 0; i < len; i++){ flag[i] = colLim[i] * leftLim[i] * rightLim[i]; } return flag; } }

文章图片

方式二

class Solution { List> res = new ArrayList<>(); public List> solveNQueens(int n) { char[][] chessboard = new char[n][n]; for (char[] c : chessboard) { Arrays.fill(c, '.'); } backTrack(n, 0, chessboard); return res; }public void backTrack(int n, int row, char[][] chessboard) { if (row == n) { res.add(Array2List(chessboard)); return; }for (int col = 0; col < n; ++col) { if (isValid (row, col, n, chessboard)) { chessboard[row][col] = 'Q'; backTrack(n, row+1, chessboard); chessboard[row][col] = '.'; } }}public List Array2List(char[][] chessboard) { List path = new ArrayList<>(); for (char[] c : chessboard) { path.add(String.valueOf(c)); } return path; }public boolean isValid(int row, int col, int n, char[][] chessboard) { // 检查列 for (int i=0; i=0 && j>=0; i--, j--) { if (chessboard[i][j] == 'Q') { return false; } }// 检查135度对角线 for (int i=row-1, j=col+1; i>=0 && j<=n-1; i--, j++) { if (chessboard[i][j] == 'Q') { return false; } } return true; } }

文章图片

21.回溯算法：解数独 讲义地址
37. 解数独 leetcode地址

class Solution { boolean find = false; char[] set = new char[]{'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'}; public void solveSudoku(char[][] board) { solveSudokuHelper(board, 0); } public void solveSudokuHelper(char[][] board, int num){ if (num == 81){ find = true; return; }int row = num / 9; int col = num % 9; if(board[row][col] == '.'){ for (int i = 1; i < 10; i++){ if (isValid(board, set[i], row, col)){ board[row][col] = set[i]; solveSudokuHelper(board, num + 1); if (!find){ board[row][col] = '.'; } }else{ continue; } } }else{ solveSudokuHelper(board, num + 1); } }public boolean isValid(char[][] board, char c, int row, int col){ for (int i = 0; i < 9; i++){ if (board[row][i] == c || board[i][col] == c){ return false; } } int baseRow = (row / 3) * 3; int baseCol = (col / 3) * 3; for (int i = baseRow; i < baseRow + 3; i++){ for (int j = baseCol; j < baseCol + 3; j++){ if (board[i][j] == c){ return false; } } } return true; } }

文章图片

22.一篇总结带你彻底搞透回溯算法！ 讲义地址

推荐阅读

• 

  劲爆体育的节目在哪里可以看到
• 

  Markdown使用技巧
• 

  2020年MotoGP FIM冻结技术工作到2021年
• 

  安卓5.0移动数据限制,手机数据已打开无线局域网已关闭
• 

  汉堡steam模拟游戏，模拟汉堡店的游戏
• 

  模拟计算器 2023年河南退休工资最低多少钱一个月河南养老金计算公式2023举例
• 

  最近长智齿了，第一磨牙轻微 疼，第二磨牙不疼，怎么回事？因为长智齿？但隔着第二磨牙啊
• 

  清明节什么时间修坟好 修坟在清明节哪天最好?
• 

  描写翠绿的成语
• 

  养护视力方法
• 

  某个淘宝店内部信息分析
• 

  汽车贴膜哪个品牌好
• 

  mysql商业版本 mysql是商业版
• 

  防溺水四牢记是什么
• 

  为什么泡了艾叶脚会脱皮
• 

  松下电视机故障代码
• 

  2019东莞入户标准
• 

  励志语句 励志语句50字
• 

  是我错了吗（）
• 

  满口假牙的人,刷牙和不刷牙有区别吗？刷牙的时候有感觉吗？

• Java之集合
• Java之API的使用
• 数据结构|【数据结构】图的基本概念—无/有向图、权和网、完全图、路径与回路
• 安利Java零基础|【安利Java零基础】java基础语法—20道常见异常库
• 数据结构|数据结构— 数组、特殊矩阵、稀疏矩阵
• 数据结构|数据结构—算法概念与设计、学生成绩管理系统【习题篇】
• 数据结构|数据结构—栈的应用举例【算术表达式求值转换、后缀表达式求值计算】
• 被LeetCode锤爆的日子|【LeetCode】 梦的开始---两数之和
• leetcode|【LeetCode】set集合+哈希表+快慢指针