用织梦做外文网站,南充做网站的公司,win7优化教程,wordpress大学 永久链接LeetCode 热题 HOT 100#xff1a;https://leetcode.cn/problem-list/2cktkvj/ 文章目录 17. 电话号码的字母组合22. 括号生成39. 组合总和46. 全排列补充#xff1a;47. 全排列 II #xff08;待优化)78. 子集79. 单词搜索124. 二叉树中的最大路径和200. 岛屿数量437. 路径… LeetCode 热题 HOT 100https://leetcode.cn/problem-list/2cktkvj/ 文章目录 17. 电话号码的字母组合22. 括号生成39. 组合总和46. 全排列补充47. 全排列 II 待优化)78. 子集79. 单词搜索124. 二叉树中的最大路径和200. 岛屿数量437. 路径总和 III 17. 电话号码的字母组合
题目链接https://leetcode.cn/problems/letter-combinations-of-a-phone-number/description/?envTypefeatured-listenvId2cktkvj?envTypefeatured-listenvId2cktkvj
class Solution {ListString list;MapCharacter, String map;public ListString letterCombinations(String digits) {ap new HashMap();res new LinkedList();if(digits.length() 0){return res;}map.put(2, abc);map.put(3, def);map.put(4, ghi);map.put(5, jkl);map.put(6, mno);map.put(7, pqrs);map.put(8, tuv);map.put(9, wxyz);backTrack(digits, 0, new StringBuilder());return list;}public void backTrack(String digits, int ind, StringBuilder sb){ // 参数输入的字符串、字符串的索引、拼接的英文字符串if(digits.length() ind){list.add(sb.toString());}else{char ch digits.charAt(ind);String str map.get(ch); // 获取按键下面的字符序列for (int i 0; i str.length(); i) {sb.append(str.charAt(i));backTrack(digits, ind 1, sb);sb.deleteCharAt(sb.length()-1); // 回溯}}}
}参考题解https://leetcode.cn/problems/letter-combinations-of-a-phone-number/solutions/388738/dian-hua-hao-ma-de-zi-mu-zu-he-by-leetcode-solutio/?envTypefeatured-listenvId2cktkvj?envTypefeatured-listenvId2cktkvj 22. 括号生成
题目链接https://leetcode.cn/problems/generate-parentheses/description/?envTypefeatured-listenvId2cktkvj?envTypefeatured-listenvId2cktkvj
思路一
class Solution {ListString res;public ListString generateParenthesis(int n) {res new LinkedList();backTrack(n, 0, 0, );return res;}public void backTrack(int n, int left, int right, String str){if(left right){return;}if(left n right n){res.add(str);return;}else{if(left n){backTrack(n, left1, right, str();}backTrack(n, left, right1, str));}}
}思路二
class Solution {ListString res new ArrayList();public ListString generateParenthesis(int n) {if(n0){return res;}getBracket(, n, n);return res;}public void getBracket(String str, int left, int right){if(left 0 right 0){res.add(str);return;}if(left right){getBracket(str(, left-1, right);}else{if(left 0){getBracket(str(, left-1, right);}getBracket(str), left, right-1);}}
}39. 组合总和
题目链接https://leetcode.cn/problems/combination-sum/description/?envTypefeatured-listenvId2cktkvj?envTypefeatured-listenvId2cktkvj
class Solution {ListListInteger res new ArrayList();ListInteger list new ArrayList();public ListListInteger combinationSum(int[] candidates, int target) {dfs(candidates, target, 0);return res;}public void dfs(int[] candidates, int target, int ind){ // 关键点在于索引if(target 0){res.add(new ArrayList(list));return;}for(int i ind; i candidates.length; i ){if(target - candidates[i] 0){list.add(candidates[i]);dfs(candidates, target - candidates[i], i); // 每次在当前的索引上进行遍历作用在于如果没有索引target55-3-2 作用等同于 5-2-3, 那么会有两种组合[2,3]与[3,2]// 但是在索引的约束下不会出现这种情况 list.remove(list.size()-1);}}}
}参考链接https://leetcode.cn/problems/combination-sum/solutions/14697/hui-su-suan-fa-jian-zhi-python-dai-ma-java-dai-m-2/?envTypefeatured-listenvId2cktkvj?envTypefeatured-listenvId2cktkvj 46. 全排列
题目链接https://leetcode.cn/problems/permutations/description/?envTypefeatured-listenvId2cktkvj?envTypefeatured-listenvId2cktkvj
class Solution {ListListInteger res new ArrayList();ListInteger list new ArrayList();public ListListInteger permute(int[] nums) {boolean[] visited new boolean[nums.length]; // 标志数组dfs(nums, 0, visited);return res;}public void dfs(int[] nums, int size, boolean[] visited){if(size nums.length){res.add(new ArrayList(list));return;}for(int i 0; i nums.length; i ){if(!visited[i]){visited[i] true;list.add(nums[i]);dfs(nums, size1, visited);list.remove(list.size()-1); // 回溯visited[i] false;}}}
}参考链接https://leetcode.cn/problems/permutations/solutions/9914/hui-su-suan-fa-python-dai-ma-java-dai-ma-by-liweiw/?envTypefeatured-listenvId2cktkvj?envTypefeatured-listenvId2cktkvj 补充47. 全排列 II 待优化)
题目链接https://leetcode.cn/problems/permutations-ii/description/?envTypefeatured-listenvId2cktkvj%3FenvType%3Dfeatured-listenvId2cktkvj
class Solution {ListListInteger res new LinkedList();ListInteger list new LinkedList();public ListListInteger permuteUnique(int[] nums) {boolean[] visited new boolean[nums.length]; // 标志数组dfs(nums, 0, visited);return res;}public void dfs(int[] nums, int size, boolean[] visited){if(size nums.length){for (ListInteger result : res) {if(result.equals(list)){return;}}res.add(new ArrayList(list));return;}for(int i 0; i nums.length; i ){if(!visited[i]){visited[i] true;list.add(nums[i]);dfs(nums, size1, visited);list.remove(list.size()-1);visited[i] false;}}}
}78. 子集
题目链接https://leetcode.cn/problems/subsets/description/?envTypefeatured-listenvId2cktkvj?envTypefeatured-listenvId2cktkvj
class Solution {ListListInteger res new ArrayList();ListInteger list new ArrayList();public ListListInteger subsets(int[] nums) {dfs(nums, 0);return res;}public void dfs(int[] nums, int i){if(inums.length){res.add(new ArrayList(list));return;}// 选 nums[i]list.add(nums[i]);dfs(nums, i1);// 不选 nums[i]list.remove(list.size()-1);dfs(nums, i1);}
}79. 单词搜索
题目链接https://leetcode.cn/problems/word-search/description/?envTypefeatured-listenvId2cktkvj?envTypefeatured-listenvId2cktkvj
class Solution {public boolean exist(char[][] board, String word) {for(int i 0; i board.length; i ){for(int j 0; j board[0].length; j ){if(board[i][j] word.charAt(0)){if(dfs(board, i, j, word, 0)){ // 路径开头不一定只有一处所以要遍历整个数组return true;}}}}return false;}public boolean dfs(char[][] board, int i, int j, String word, int ind){if(ind word.length()){return true;}if(i0 iboard.length j0 jboard[0].length board[i][j]word.charAt(ind) board[i][j]!\0){ // 剪枝char tmp board[i][j];board[i][j] \0; // 设置不可访问boolean f1 dfs(board, i, j-1, word, ind1); // 左boolean f2 dfs(board, i-1, j, word, ind1); // 上boolean f3 dfs(board, i, j1, word, ind1); // 右boolean f4 dfs(board, i1, j, word, ind1); // 下board[i][j] tmp; // 回溯return f1 || f2 || f3 ||f4;}return false;}
}124. 二叉树中的最大路径和
题目链接https://leetcode.cn/problems/binary-tree-maximum-path-sum/description/?envTypefeatured-listenvId2cktkvj?envTypefeatured-listenvId2cktkvj
二叉树 abca 是根结点递归中的 rootbc 是左右子结点代表其递归后的最优解。最大的路径可能的路径情况 a / \ b c ① b a c。 ② b a a 的父结点。需要再次递归 ③ a c a 的父结点。需要再次递归其中情况 1表示如果不联络父结点的情况或本身是根结点的情况。这种情况是没法递归的但是结果有可能是全局最大路径和因此可以在递归过程中通过比较得出。情况 2 和 3递归时计算 ab 和 ac选择一个更优的方案返回也就是上面说的递归后的最优解。
class Solution {int max Integer.MIN_VALUE;public int maxPathSum(TreeNode root) {if(root null){return 0;}dfs(root);return max;}/*** 返回经过root的单边分支最大和 即 Math.max(root, rootleft, rootright)*/public int dfs(TreeNode root){if(root null){return 0;}// 计算左子树最大值左边分支如果为负数还不如不选择int leftMax Math.max(0, dfs(root.left));// 计算右子树最大值右边分支如果为负数还不如不选择int rightMax Math.max(0, dfs(root.right));// left-root-right 作为路径与已经计算过历史最大值做比较max Math.max(max, leftMax root.val rightMax);// 返回经过root的单边最大分支给当前root的父节点计算使用return root.val Math.max(leftMax, rightMax);}
}200. 岛屿数量
题目链接https://leetcode.cn/problems/number-of-islands/description/?envTypefeatured-listenvId2cktkvj?envTypefeatured-listenvId2cktkvj
class Solution {public int numIslands(char[][] grid) {int sum 0;for(int i 0; i grid.length; i ){for(int j 0; j grid[0].length; j ){if(grid[i][j] 1){dfs(grid, i, j);sum;}}}return sum;}public void dfs(char[][] grid, int x, int y){if(0x xgrid.length 0y ygrid[0].length grid[x][y] 1){grid[x][y] 0;dfs(grid, x, y-1); // 左dfs(grid, x-1, y); // 上dfs(grid, x, y1); // 右dfs(grid, x1, y); // 下}}
}437. 路径总和 III
题目链接https://leetcode.cn/problems/path-sum-iii/description/?envTypefeatured-listenvId2cktkvj?envTypefeatured-listenvId2cktkvj
class Solution {// key 是前缀和value 是前缀和为这个值的路径数量。MapLong, Integer map new HashMap();int target;public int pathSum(TreeNode root, int targetSum) {this.target targetSum;// 可能路径从根节点开始算map.put(0l, 1);return dfs(root, 0l);}public int dfs(TreeNode root, long curSum){if(root null){return 0;}curSum root.val; // 当前累计的结点值int res 0;// 以当前节点为止去查看从前的 map 集合中是否还存在目标前缀和// 1// /// 2// /// 3// 假设目标和为 5// 节点 1 的前缀和为1// 节点 3 的前缀和为: 123 6// pre(3) - pre(1) 5// 所以从节点 1 到节点 3 之间有一条符合要求的路径res map.getOrDefault(curSum-target, 0);// 存储路径的原因是可能节点的前缀和存在相等的情况// 2// /// 0// /// 4// 从节点 2 到节点 4 有两条路径长度等于2map.put(curSum, map.getOrDefault(curSum, 0) 1);int left dfs(root.left, curSum); // 调用左子树int right dfs(root.right, curSum); // 调用右子树res res left right;map.put(curSum, map.get(curSum)-1); // 恢复状态return res;}
}
