网站镜像 动态,苏州网架公司,淘宝购物网站,网站建设人员春招计划组合问题
LeetCode39: 组合总和
LeetCode39. 组合总和 目标和#xff0c;除了累加所有的数外还可以用目标值减去所有的数。 添加第i个元素后#xff0c;可以继续添加第i个元素。可以添加第i个元素#xff0c;也可以添加索引为candidates.length-1的元素 这类回溯的问题可以…组合问题
LeetCode39: 组合总和
LeetCode39. 组合总和 目标和除了累加所有的数外还可以用目标值减去所有的数。 添加第i个元素后可以继续添加第i个元素。可以添加第i个元素也可以添加索引为candidates.length-1的元素 这类回溯的问题可以想象成多叉数对于根节点有左右子树对于组合而言多叉树的集合是candidates的所有的元素。以及考虑所有子元素的下一层的子元素集合是什么。 class Solution {ListListInteger res new ArrayList();LinkedListInteger path new LinkedList();public ListListInteger combinationSum(int[] candidates, int target) {backtrack(candidates, target, 0);return res;}private void backtrack(int[] candidates, int target, int idx) {if (target 0) {res.add(new ArrayList(path));}if (target 0 || idx candidates.length) {return;}for (int i idx; i candidates.length; i) {path.add(candidates[i]);backtrack(candidates, target - candidates[i], i );path.pollLast();}}
}LeetCode40: 组合总和II
LeetCode40: 组合总和II 每个数字只能使用一次并不意味着不允许重复元素。如果原数组中存在两个1和是2是可以有[1,1]的组合 进入下一次递归的时候需要进行索引加1当前元素不能再用。 i idx candidates[i] candidates[i - 1]目的是防止数组中有两个1第一个1和第二个1在与其他元素搭配的时候作用是一样的需要过滤。因此数组必须是有序的保证相等的元素相邻。 class Solution {ListListInteger res new ArrayList();LinkedListInteger path new LinkedList();public ListListInteger combinationSum2(int[] candidates, int target) {Arrays.sort(candidates);backtrack(candidates, target, 0);return res;}private void backtrack(int[] candidates, int target, int idx) {if (target 0) {res.add(new ArrayList(path));}if (target 0) {return;}for (int i idx; i candidates.length; i) {if (i idx candidates[i] candidates[i - 1]) {continue;}path.add(candidates[i]);backtrack(candidates, target - candidates[i], i 1);path.pollLast();}}}LeetCode17. 电话号码的字母组合
LeetCode17. 电话号码的字母组合 当长度相等满足则加入结果集 字符’2’转为数字2digits.charAt(idx) - 0 class Solution {ListString res new ArrayList();StringBuilder sb new StringBuilder();String[] numString {, , abc, def, ghi, jkl, mno, pqrs, tuv, wxyz};public ListString letterCombinations(String digits) {if (digits null || digits.length() 0) {return res;}dfs(digits, 0);return res;}private void dfs(String digits, int idx) {if (sb.length() digits.length()) {res.add(sb.toString());return;}String str numString[digits.charAt(idx) - 0];for (int i 0; i str.length(); i) {sb.append(str.charAt(i));dfs(digits, idx 1);sb.deleteCharAt(sb.length() - 1);}}
}子集问题
LeetCode78子集
LeetCode78. 子集 startIndex nums.length这个校验可有可无。 子集第一层子集合是[0,nums.length-1]对于选择0的元素下一层的子集合是[1,nums.length-1] class Solution {ListListInteger res new ArrayList();LinkedListInteger path new LinkedList();public ListListInteger subsets(int[] nums) {dfs(nums, 0);return res;}private void dfs(int[] nums, int idx) {res.add(new ArrayList(path));if (startIndex nums.length) {return;}for (int i idx; i nums.length; i) {path.add(nums[i]);dfs(nums, i 1);path.pollLast();}}
}LeetCode90子集II
LeetCode90子集II i idx nums[i] nums[i - 1]可以理解为同一层元素不能重复。iidx的时候i是第一个元素。 需要对数组进行排序排序好的数组元素相等的在一起。 class Solution {ListListInteger res new ArrayList();LinkedListInteger path new LinkedList();public ListListInteger subsetsWithDup(int[] nums) {Arrays.sort(nums);dfs(nums, 0);return res;}private void dfs(int[] nums, int idx) {res.add(new ArrayList(path));for (int i idx; i nums.length; i) {if (i idx nums[i] nums[i - 1]) {continue;}path.add(nums[i]);dfs(nums, i 1);path.pollLast();}}
}LeetCode491: 非递减子序列
LeetCode491: 非递减子序列 子序列就是不能改变数组中的元素。 去重使用boolean数组或者HashMap 递增的判断是获取path中最后一个元素和当前元素比较。 class Solution {ListListInteger res new ArrayList();LinkedListInteger path new LinkedList();public ListListInteger findSubsequences(int[] nums) {dfs(nums, 0);return res;}private void dfs(int[] nums, int idx) {if (path.size() 1) {res.add(new ArrayList(path));}if (idx nums.length) {return;}boolean[] used new boolean[201];for (int i idx; i nums.length; i) {if (used[nums[i] 100] || (!path.isEmpty() path.peekLast() nums[i])) {continue;}path.add(nums[i]);used[nums[i] 100] true;dfs(nums, i 1);path.pollLast();}}
}全排列问题
LeetCode46. 全排列
LeetCode46. 全排列 第一层集合是[0,nums.length-1]第二层集合是[0,nums.length-1]再减去第一层用的元素。 class Solution {ListListInteger res new ArrayList();LinkedListInteger path new LinkedList();boolean[] used;public ListListInteger permute(int[] nums) {used new boolean[nums.length];dfs(nums);return res;}private void dfs(int[] nums) {if (path.size() nums.length) {res.add(new ArrayList(path));return;}for (int i 0; i nums.length; i) {if (used[i]) {continue;}path.add(nums[i]);used[i] true;dfs(nums);used[i] false;path.removeLast();}}
}LeetCode47: 全排列II
LeetCode47: 全排列II 不能有重复的组合 i 0 nums[i] nums[i - 1] !vis[i - 1]。连续三个1第一层使用第一个1第二层使用第二个1used[i-1]true。等于是1(a),1(b),1(c)只能有一个顺序。 class Solution {ListListInteger result new ArrayList();LinkedListInteger path new LinkedList();boolean[] used;public ListListInteger permuteUnique(int[] nums) {Arrays.sort(nums);used new boolean[nums.length];dfs(nums);return result;}private void dfs(int[] nums) {if (nums.length path.size()) {result.add(new ArrayList(path));return;}for (int i 0; i nums.length; i) {if (used[i] || (i 0 nums[i] nums[i - 1]) !used[i - 1]) {continue;}path.add(nums[i]);used[i] true;dfs(nums);used[i] false;path.pollLast();}}
}切割问题
LeetCode93: 复原IP地址**
LeetCode93: 复原IP地址 判断某字符串是否为合法字符串大于等于0小于等于255的字符串。 要切分为合理的4段记录start为字符串的起始字符。当符合要求的时候start s.length() split 4 子树集合[start,start 2]只有3个位置可选。 题目的难点需要把应用题理解为可以做回溯的题目。 class Solution {ListString res new ArrayList();LinkedListString path new LinkedList();public ListString restoreIpAddresses(String s) {dfs(s, 0, 0);return res;}private void dfs(String s, int start, int split) {if (start s.length() split 4) {res.add(String.join(., path));return;}for (int i start; i start 3; i) {if (i s.length()) {break;}if ((4 - split) * 3 s.length() - i) {continue;}if (isValid(s, start, i)) {path.add(s.substring(start, i 1));dfs(s, i 1, split 1);path.removeLast();}}}private boolean isValid(String s, int start, int end) {if (start ! end s.charAt(start) 0) {return false;}int res 0;for (int i start; i end; i) {res res * 10 (s.charAt(i) - 0);}return res 0 res 255;}
}网格类问题
LeetCode200: 岛屿数量
LeetCode200: 岛屿数量 回溯方法计数如果当前点为岛屿将附近的土地置为0避免重复计数。 class Solution {public int numIslands(char[][] grid) {if (grid null || grid.length 0 || grid[0].length 0) {return 0;}int count 0;int m grid.length; //行的个数int n grid[0].length; // 列的个数for (int i 0; i m; i) {for (int j 0; j n; j) {if (grid[i][j] 1) {count;dfs(grid, i, j);}}}return count;}private void dfs(char[][] grid, int i, int j) {if (i 0 || i grid.length || j 0 || j grid[0].length || grid[i][j] 0) {return;}grid[i][j] 0;dfs(grid, i - 1, j);dfs(grid, i 1, j);dfs(grid, i, j - 1);dfs(grid, i, j 1);}
}LeetCode695: 岛屿的最大面积
LeetCode695: 岛屿的最大面积
class Solution {public int maxAreaOfIsland(int[][] grid) {if (grid null || grid.length 0 || grid[0].length 0) {return 0;}int m grid.length;int n grid[0].length;int ans 0;for (int i 0; i m; i) {for (int j 0; j n; j) {if (grid[i][j] 1) {ans Math.max(ans, dfs(grid, i, j));}}}return ans;}private int dfs(int[][] grid, int i, int j) {int res 1;if (i grid.length || i 0 || j 0 || j grid[0].length || grid[i][j] 0) {return 0;}grid[i][j] 0;res dfs(grid, i - 1, j);res dfs(grid, i 1, j);res dfs(grid, i, j - 1);res dfs(grid, i, j 1);return res;}
}LeetCode79. 单词搜索
LeetCode79. 单词搜索 board[i][j] .设置为该点位已经使用过。 比较索引为index的元素判断是否相等相等则继续不等则返回结果false。比较前后左右的结果。当索引为最后一个元素判断为相等则返回结果。 class Solution {public boolean exist(char[][] board, String word) {int m board.length;int n board[0].length;for (int i 0; i m; i) {for (int j 0; j n; j) {if (dfs(board, word, 0, i, j)) {return true;}}}return false;}private boolean dfs(char[][] board, String word, int index, int i, int j) {if (i 0 || i board.length || j 0 || j board[0].length || word.charAt(index) ! board[i][j]|| board[i][j] .) {return false;}if (index word.length() - 1) {return true;}char tmp board[i][j];board[i][j] .;boolean b dfs(board, word, index 1, i 1, j)|| dfs(board, word, index 1, i - 1, j)|| dfs(board, word, index 1, i, j 1)|| dfs(board, word, index 1, i, j - 1);board[i][j] tmp;return b;}
}LeetCode207. N皇后
51. N 皇后 定义一个n*n的数组插入所有的网格 .。 校验新增的元素是否合理竖向比较45度比较横向比较135度比较 将当前board保存到ListString中加入结果集 class Solution {ListListString res new ArrayList();public ListListString solveNQueens(int n) {char[][] board new char[n][n];for (int i 0; i board.length; i) {Arrays.fill(board[i], .);}dfs(board, 0, n);return res;}private void dfs(char[][] board, int index, int n) {if (index n) {res.add(toArray(board));return;}for (int i 0; i board[index].length; i) {if (isValid(board, index, i, n)) {board[index][i] Q;dfs(board, index 1, n);board[index][i] .;}}}private boolean isValid(char[][] board, int row, int col, int n) {for (int i 0; i row; i) {if (board[i][col] Q) {return false;}}for (int i 0; i col; i) {if (board[row][i] Q) {return false;}}for (int i row - 1, j col - 1; i 0 j 0; i--, j--) {if (board[i][j] Q) {return false;}}for (int i row - 1, j col 1; i 0 j n; i--, j) {if (board[i][j] Q) {return false;}}return true;}public ListString toArray(char[][] board) {ListString list new ArrayList();for (int i 0; i board.length; i) {list.add(new String(board[i]));}return list;}
}括号问题
LeetCode22. 括号生成
LeetCode22. 括号生成 这条题目我看到想过并且看答案已经不止3次了每次看都像看新的题目一样感觉很熟悉就是不会做。 记录左括号的次数和右括号的次数当左括号的次数和右括号的次数都等于n满足条件。当左括号的次数小于右括号的次数进行剪枝比如()) class Solution {ListString res new ArrayList();public ListString generateParenthesis(int n) {dfs(0, 0, n, );return res;}private void dfs(int left, int right, int n, String s) {if (left n right n) {res.add(s);return;}if (left right) {return;}if (left n) {dfs(left 1, right, n, s ();}if (right n) {dfs(left, right 1, n, s ));}}
}图问题
LeetCode207. 课程表
LeetCode207. 课程表 记录每个课程的先学课程数量没有先学课程的加入队列。 记录边边是[先学,后学] class Solution {public boolean canFinish(int numCourses, int[][] prerequisites) {int[] indegree new int[numCourses];ListListInteger edges new ArrayList();for (int i 0; i numCourses; i) {edges.add(new ArrayList());}for (int[] prereq : prerequisites) {indegree[prereq[0]]; // 入度,[1,2] 先学2再学1edges.get(prereq[1]).add(prereq[0]);}QueueInteger queue new LinkedList();for (int i 0; i indegree.length; i) {if (indegree[i] 0) {queue.add(i);}}while (!queue.isEmpty()) {int poll queue.poll();numCourses--;for (Integer pre : edges.get(poll)) {indegree[pre]--;if (indegree[pre] 0) {queue.add(pre);}}}return numCourses 0;}
}
