JAVA刷題記錄: 遞歸,搜索與回溯

專題一 遞歸

面試題 08.06. 漢諾塔問題 - 力扣（LeetCode）

class Solution {public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {dfs(A, B, C, A.size());}public void dfs(List<Integer> a, List<Integer> b, List<Integer> c, int num) {if(num == 1) {c.add(a.remove(a.size() - 1));return;}dfs(a, c, b, num - 1);c.add(a.remove(a.size() - 1));dfs(b, a, c, num - 1);return;}
}

21. 合并兩個有序鏈表 - 力扣（LeetCode）

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode mergeTwoLists(ListNode list1, ListNode list2) {if(list1 == null) return list2;if(list2 == null) return list1;if(list1.val <= list2.val) {list1.next = mergeTwoLists(list1.next, list2); return list1;}else {list2.next = mergeTwoLists(list1, list2.next); return list2;}}
}

206. 反轉鏈表 - 力扣（LeetCode）

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode reverseList(ListNode head) {if(head == null || head.next == null) return head;ListNode newHead = reverseList(head.next);head.next.next = head;head.next = null;return newHead;}
}

24. 兩兩交換鏈表中的節點 - 力扣（LeetCode）

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode swapPairs(ListNode head) {if(head == null || head.next == null) return head;ListNode tmp = swapPairs(head.next.next);ListNode ret = head.next;head.next = tmp;ret.next = head;return ret;}
}

專題二 二叉樹中的深搜

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public boolean evaluateTree(TreeNode root) {if(root.left == null) return root.val == 0 ? false : true;boolean left = evaluateTree(root.left);boolean right = evaluateTree(root.right);return root.val == 2 ? left | right : left & right;}
}

129. 求根節點到葉節點數字之和 - 力扣（LeetCode）

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public int sumNumbers(TreeNode root) {return sum(root, 0);}public int sum(TreeNode root, int pre) {pre = pre * 10 + root.val;if(root.left == null && root.right == null) return pre; int ret = 0;if(root.left != null) ret += sum(root.left, pre);if(root.right != null) ret += sum(root.right, pre);return ret; }
}

814. 二叉樹剪枝 - 力扣（LeetCode）

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public TreeNode pruneTree(TreeNode root) {if(root == null) return null;root.left = pruneTree(root.left);root.right = pruneTree(root.right);if(root.left == null && root.right == null && root.val == 0) root = null;return root;}
}

98. 驗證二叉搜索樹 - 力扣（LeetCode）

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {long pre = Long.MIN_VALUE;public boolean isValidBST(TreeNode root) {if(root == null)  return true;boolean left = isValidBST(root.left);if(left == false) return false;boolean cur = false;if(pre < root.val) cur = true;if(cur == false) return false;pre = root.val;boolean right = isValidBST(root.right);return right;}
}

230. 二叉搜索樹中第 K 小的元素 - 力扣（LeetCode）

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {int count;int ret;public int kthSmallest(TreeNode root, int k) {count = k; ret = 0;dfs(root);return ret;}public void dfs(TreeNode root) {if(root == null || count == 0) return ;dfs(root.left);count--;if(count == 0) {ret = root.val;return;}dfs(root.right);}
}

257. 二叉樹的所有路徑 - 力扣（LeetCode）

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {List<String> ret;public List<String> binaryTreePaths(TreeNode root) {ret = new ArrayList<>();dfs(root, new StringBuffer());return ret;}public void dfs(TreeNode root, StringBuffer _path) {StringBuffer path = new StringBuffer(_path);path.append(Integer.toString(root.val));if(root.left == null && root.right == null) {ret.add(path.toString());return;}path.append("->");if(root.left != null) dfs(root.left, path);if(root.right != null) dfs(root.right, path);}
}

專題三 dfs

46. 全排列 - 力扣（LeetCode）

class Solution {List<List<Integer>> ret;List<Integer> path;boolean[] check;public List<List<Integer>> permute(int[] nums) {ret = new ArrayList<>();path = new ArrayList<>();check = new boolean[nums.length];dfs(nums);return ret;}public void dfs(int[] nums) {if(path.size() == nums.length) {ret.add(new ArrayList(path)); return ;}for(int i = 0; i < nums.length; i++) {if(check[i] == false) {check[i] = true;path.add(nums[i]);dfs(nums);check[i] = false;path.remove(path.size() - 1);}}}
}

78. 子集 - 力扣（LeetCode）

class Solution {List<List<Integer>> ret;List<Integer> path;public List<List<Integer>> subsets(int[] nums) {path = new ArrayList<>();ret = new ArrayList<>();dfs(nums, 0);return ret;}public void dfs(int[] nums, int i) {if(i == nums.length) {ret.add(new ArrayList(path));return ;}path.add(nums[i]);dfs(nums, i + 1);path.remove(path.size() - 1);dfs(nums, i + 1);}
}
class Solution {List<List<Integer>> ret;List<Integer> path;public List<List<Integer>> subsets(int[] nums) {path = new ArrayList<>();ret = new ArrayList<>();dfs(nums, 0);return ret;}public void dfs(int[] nums, int pos) {ret.add(new ArrayList(path));for(int i = pos; i < nums.length; i++) {path.add(nums[i]);dfs(nums, i + 1);path.remove(path.size() - 1);}}
}

專題四 綜合練習

1863. 找出所有子集的異或總和再求和 - 力扣（LeetCode）

class Solution {int sum = 0;int path = 0;public int subsetXORSum(int[] nums) {dfs(nums, 0);return sum;}public void dfs(int[] nums, int pos) {sum += path;for(int i = pos; i < nums.length; i++) {path ^= nums[i];dfs(nums, i + 1);path ^= nums[i];}}
}

47. 全排列 II - 力扣（LeetCode）

class Solution {List<List<Integer>> ret;List<Integer> path;boolean[] check;public List<List<Integer>> permuteUnique(int[] nums) {ret = new ArrayList<>();path = new ArrayList<>();check = new boolean[nums.length];Arrays.sort(nums);dfs(nums, 0);return ret;}public void dfs(int[] nums, int pos) {if(pos == nums.length){ ret.add(new ArrayList(path)); return;}for(int i = 0; i < nums.length; i++) {if(check[i] == true || (i != 0 && nums[i] == nums[i - 1] && check[i - 1] == false)) {continue;}check[i] = true;path.add(nums[i]);dfs(nums, pos + 1);check[i] = false;path.remove(path.size() - 1);}return;}
}

17. 電話號碼的字母組合 - 力扣（LeetCode）

class Solution {String[] hash = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxzy"};List<String> ret;StringBuffer path;public List<String> letterCombinations(String digits) {path = new StringBuffer();ret = new ArrayList<>();if(digits.length() == 0) return ret;dfs(digits, 0);return ret;}public void dfs(String digits, int pos) {if(pos == digits.length()) {ret.add(path.toString());return;}String cur = hash[digits.charAt(pos) - '0'];for(int i = 0; i < cur.length(); i++) {path.append(cur.charAt(i));dfs(digits, pos + 1);path.deleteCharAt(path.length() - 1);}}
}

22. 括號生成 - 力扣（LeetCode）

class Solution {int left, right, n;List<String> ret;StringBuffer path;public List<String> generateParenthesis(int _n) {left = right = 0;n = _n;ret = new ArrayList<>();path = new StringBuffer();dfs();return ret;}public void dfs() {if(right == n) {ret.add(path.toString());}if(left < n) {left++;path.append('(');dfs();left--;path.deleteCharAt(path.length() - 1);}if(right < left) {right++;path.append(')');dfs();right--;path.deleteCharAt(path.length() - 1);}}
}

77. 組合 - 力扣（LeetCode）

class Solution {int n, k;List<List<Integer>> ret;List<Integer> path;public List<List<Integer>> combine(int _n, int _k) {n = _n; k = _k;ret = new ArrayList<>();path = new ArrayList<>();dfs(1);return ret;}public void dfs(int start) {if(path.size() == k) {ret.add(new ArrayList<>(path));return;}for(int i = start; i <= n; i++) {path.add(i);dfs(i + 1);path.remove(path.size() - 1);}}
}

494. 目標和 - 力扣（LeetCode）

class Solution {int ret, aim;public int findTargetSumWays(int[] nums, int target) {aim = target;ret = 0;dfs(nums, 0, 0);return ret;}public void dfs(int[] nums, int pos, int path) {if(pos == nums.length) {if(path == aim) ret++;return;}dfs(nums, pos + 1, path + nums[pos]);dfs(nums, pos + 1, path - nums[pos]);}
}

39. 組合總和 - 力扣（LeetCode）

class Solution {int aim;List<List<Integer>> ret;List<Integer> path;public List<List<Integer>> combinationSum(int[] candidates, int target) {aim = target;ret = new ArrayList<>();path = new ArrayList<>();dfs(candidates, 0, 0);return ret;}public void dfs(int[] nums, int pos, int sum) {if(sum == aim) {ret.add(new ArrayList(path));return;}if(sum > aim || pos == nums.length) return;for(int i = pos; i < nums.length; i++) {path.add(nums[i]);dfs(nums, i, sum + nums[i]);path.remove(path.size() - 1); }}
}

39. 組合總和 - 力扣（LeetCode）

class Solution {int aim;List<List<Integer>> ret;List<Integer> path;public List<List<Integer>> combinationSum(int[] candidates, int target) {aim = target;ret = new ArrayList<>();path = new ArrayList<>();dfs(candidates, 0, 0);return ret;}public void dfs(int[] nums, int pos, int sum) {if(sum == aim) {ret.add(new ArrayList(path));return;}if(sum > aim || pos == nums.length) return;for(int i = pos; i < nums.length; i++) {path.add(nums[i]);dfs(nums, i, sum + nums[i]);path.remove(path.size() - 1); }}
}

784. 字母大小寫全排列 - 力扣（LeetCode）

class Solution {StringBuffer path;List<String> ret;public List<String> letterCasePermutation(String s) {path = new StringBuffer();ret = new ArrayList<>();dfs(s, 0);return ret;}public char change(char ch) {if(ch >= 'a' && ch <= 'z') return ch -= 32;else return ch += 32;}public void dfs(String s, int pos) {if(pos == s.length()) {ret.add(path.toString());return;}path.append(s.charAt(pos));dfs(s, pos + 1);path.deleteCharAt(path.length() - 1);if(s.charAt(pos) < '0' || s.charAt(pos) > '9'){path.append(change(s.charAt(pos)));dfs(s, pos + 1);path.deleteCharAt(path.length() - 1);}}
}

51. N 皇后 - 力扣（LeetCode）

class Solution {List<List<String>> ret;char[][] path;boolean[] checkCol, checkDig1, checkDig2;int n;public List<List<String>> solveNQueens(int _n) {n = _n;path = new char[n][n];ret = new ArrayList<>();checkCol = new boolean[n];checkDig1 = new boolean[2 * n];checkDig2 = new boolean[2 * n];for(int i = 0; i < n; i++) {Arrays.fill(path[i], '.');}dfs(0);return ret;}public void dfs(int row) {if(row == n) {List<String> tmp = new ArrayList<>();for(int i = 0; i < n; i++) {tmp.add(new String(path[i]));}ret.add(tmp);}for(int col = 0; col < n; col++) {if(checkCol[col] == false && checkDig1[row - col + n] == false && checkDig2[row + col] == false){path[row][col] = 'Q';checkCol[col] = checkDig1[row - col + n] = checkDig2[row + col] = true;dfs(row + 1);checkCol[col] = checkDig1[row - col + n] = checkDig2[row + col] = false;path[row][col] = '.';}}}
}

36. 有效的數獨 - 力扣（LeetCode）

class Solution {boolean[][] row, col;boolean[][][] grid;public boolean isValidSudoku(char[][] board) {col = new boolean[9][10];row = new boolean[9][10];grid = new boolean[3][3][10];for(int i = 0; i < 9; i++) {for(int j = 0; j < 9; j++) {if(board[i][j] != '.'){int num = board[i][j] - '0';if(row[i][num] || col[j][num] || grid[i / 3][j / 3][num]){return false;}row[i][num] = col[j][num] = grid[i / 3][j / 3][num] = true;}}}return true;}
}

37. 解數獨 - 力扣（LeetCode）

class Solution {boolean[][] row, col;boolean[][][] grid;public void solveSudoku(char[][] board) {col = new boolean[9][10];row = new boolean[9][10];grid = new boolean[3][3][10];for(int i = 0; i < 9; i++) {for(int j = 0; j < 9; j++) {if(board[i][j] != '.'){int num = board[i][j] - '0';row[i][num] = col[j][num] = grid[i / 3][j / 3][num] = true;}}}dfs(board);}public boolean dfs(char[][] board) {for(int i = 0; i < 9; i++) {for(int j = 0; j < 9; j++) {if(board[i][j] == '.') {for(int num = 1; num < 10; num++) {if(!row[i][num] && !col[j][num] && !grid[i / 3][j / 3][num]) {board[i][j] = (char)(num + '0');row[i][num] = col[j][num] = grid[i / 3][j / 3][num] = true;if(dfs(board) == true) return true;board[i][j] = '.';row[i][num] = col[j][num] = grid[i / 3][j / 3][num] = false;}}return false;}}}return true;}
}

79. 單詞搜索 - 力扣（LeetCode）

class Solution {int m, n;char[] word;boolean[][] vis;public boolean exist(char[][] board, String _word) {m = board.length;n = board[0].length;vis = new boolean[m][n];word = _word.toCharArray();for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (board[i][j] == word[0]) {vis[i][j] = true;if (dfs(board, i, j, 1))return true;vis[i][j] = false;}}}return false;}int[] dx = { 0, 0, 1, -1 };int[] dy = { 1, -1, 0, 0 };public boolean dfs(char[][] board, int i, int j, int pos) {if (pos == word.length) {return true;}for (int k = 0; k < 4; k++) {int x = i + dx[k], y = j + dy[k];if (x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && board[x][y] == word[pos]) {vis[x][y] = true;if (dfs(board, x, y, pos + 1))return true;vis[x][y] = false;}}return false;}
}

1219. 黃金礦工 - 力扣（LeetCode）

class Solution {int ret, n, m;boolean[][] vis;int[] dx = {0, 0, -1, 1};int[] dy = {-1, 1, 0, 0};public int getMaximumGold(int[][] grid) {m = grid.length; n = grid[0].length;vis = new boolean[m][n];for(int i = 0; i < m; i++) {for(int j = 0; j < n; j++) {if(grid[i][j] != 0) {vis[i][j] = true;dfs(grid, i, j, grid[i][j]);vis[i][j] = false;}}}return ret;}public void dfs(int[][] grid, int i, int j, int path) {ret = Math.max(ret, path);for(int k = 0; k < 4; k++) {int x = i + dx[k], y = j + dy[k];if(x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && grid[x][y] != 0) {vis[x][y] = true;dfs(grid, x, y, path + grid[x][y]);vis[x][y] = false;}}}
}

980. 不同路徑 III - 力扣（LeetCode）

class Solution {int m, n, step, ret;boolean[][] vis;int[] dx = {0, 0, -1, 1};int[] dy = {-1, 1, 0, 0};public int uniquePathsIII(int[][] grid) {m = grid.length; n = grid[0].length;int bx = 0, by = 0;vis = new boolean[m][n];for(int i = 0; i < m; i++) {for(int j = 0;j < n; j++) {if(grid[i][j] == 0) step++;else if(grid[i][j] == 1) {bx = i; by = j;}else if(grid[i][j] == -1) vis[i][j] = true;}}step += 2;vis[bx][by] = true;dfs(grid, bx, by, 1);return ret;}public void dfs(int[][] grid, int i, int j, int count) {if(grid[i][j] == 2) {if(count == step) {ret++;}return;}for(int k = 0; k < 4; k++) {int x = i + dx[k], y = j + dy[k];if(x >= 0 && x < m && y >= 0 && y < n && !vis[x][y]) {vis[x][y] = true;dfs(grid, x, y, count + 1);vis[x][y] = false;}}}
}

專題五 floodfill算法

733. 圖像渲染 - 力扣（LeetCode）

class Solution {int[] dx = {0, 0, -1, 1};int[] dy = {-1, 1, 0, 0};int prev, m, n;public int[][] floodFill(int[][] image, int sr, int sc, int color) {if(image[sr][sc] == color) return image;prev = image[sr][sc];m = image.length;n = image[0].length;dfs(image, sr, sc, color);return image;     }public void dfs(int[][] image, int i, int j, int color) {image[i][j] = color;for(int k = 0; k < 4; k++) {int x = i + dx[k], y = j + dy[k];if(x >= 0 && x < m && y >= 0 && y < n && image[x][y] == prev) {dfs(image, x, y, color);}}}
}

200. 島嶼數量 - 力扣（LeetCode）

class Solution {int m, n, ret;boolean[][] vis;int[] dx = {0, 0, -1, 1};int[] dy = {-1, 1, 0, 0};public int numIslands(char[][] grid) {m = grid.length; n = grid[0].length;vis = new boolean[m][n];for(int i = 0; i < m; i++) {for(int j = 0; j < n; j++) {if(grid[i][j] == '1' && vis[i][j] == false) {ret++;dfs(grid, i, j);}   }}return ret;    }public void dfs(char[][] grid, int i, int j) {if(grid[i][j] == '0') return;grid[i][j] = '0';for(int k = 0; k < 4; k++) {int x = i + dx[k], y = j + dy[k];if(x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && grid[x][y] == '1') {dfs(grid, x, y);}}}
}

695. 島嶼的最大面積 - 力扣（LeetCode）

class Solution {int m, n, ret, count;boolean[][] vis;int[] dx = {0, 0, -1, 1};int[] dy = {-1, 1, 0, 0};public int maxAreaOfIsland(int[][] grid) {m = grid.length; n = grid[0].length;vis = new boolean[m][n];for(int i = 0; i < m; i++) {for(int j = 0; j < n; j++) {if(grid[i][j] == 1 && !vis[i][j]) {count = 0;dfs(grid, i, j);ret = Math.max(ret, count);} }}    return ret;}public void dfs(int[][] grid, int i, int j) {if(grid[i][j] == 0) return;vis[i][j] = true;count++;for(int k = 0; k < 4; k++) {int x = i + dx[k];int y = j + dy[k];if(x >= 0 && x < m && y >= 0 && y < n && (grid[x][y] == 1) && (vis[x][y] == false)) {dfs(grid, x, y);}}}
}

130. 被圍繞的區域 - 力扣（LeetCode）

class Solution {int m, n;int[] dx = {0, 0, -1, 1};int[] dy = {-1, 1, 0, 0};public void solve(char[][] board) {m = board.length;n = board[0].length;for(int i = 0; i < n; i++) {if(board[0][i] == 'O') dfs(board, 0, i);if(board[m - 1][i] == 'O') dfs(board, m - 1, i);}    for(int j = 0; j < m; j++) {if(board[j][0] == 'O') dfs(board, j, 0);if(board[j][n - 1] == 'O') dfs(board, j, n - 1);}for(int i = 0; i < m; i++) {for(int j = 0; j < n; j++) {if(board[i][j] == '.') board[i][j] = 'O';else if(board[i][j] == 'O') board[i][j] = 'X';}}}public void dfs(char[][] board, int i, int j) {board[i][j] = '.';for(int k = 0; k < 4; k++) {int x = i + dx[k], y = j + dy[k];if(x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'O') {dfs(board, x, y);}} }
}

417. 太平洋大西洋水流問題 - 力扣（LeetCode）

class Solution {int m, n;int[] dx = {0, 0, -1, 1};int[] dy = {-1, 1, 0, 0};public List<List<Integer>> pacificAtlantic(int[][] h) {m = h.length;n = h[0].length;boolean[][] pac = new boolean[m][n];boolean[][] atl = new boolean[m][n];for(int i = 0; i < m; i++) {dfs(h, i, 0, pac);dfs(h, i, n - 1, atl);}for(int j = 0; j < n; j++) {dfs(h, 0, j, pac);dfs(h, m - 1, j, atl);}List<List<Integer>> ret = new ArrayList<>();for(int i = 0; i < m; i++) {for(int j = 0; j < n; j++) {if(pac[i][j] && atl[i][j]) {List<Integer> tmp = new ArrayList<>();tmp.add(i); tmp.add(j);ret.add(tmp);}}}return ret;}public void dfs(int[][] h, int i, int j, boolean[][] vis) {vis[i][j] = true;for(int k = 0; k < 4; k++) {int x = i + dx[k], y = j + dy[k];if(x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && h[x][y] >= h[i][j]) {dfs(h, x, y, vis);}}}
}

529. 掃雷游戲 - 力扣（LeetCode）

class Solution {int m, n;int[] dx = {0, 0, -1, 1, 1, 1, -1, -1};int[] dy = {-1, 1, 0, 0, 1, -1, 1, -1};public char[][] updateBoard(char[][] board, int[] click) {m = board.length; n = board[0].length;int x = click[0], y = click[1];if(board[x][y] == 'M') {board[x][y] = 'X';return board;}dfs(board, x, y);return board;}public void dfs(char[][] board, int i, int j) {int count = 0;for(int k = 0; k < 8; k++) {int x = i + dx[k], y = j + dy[k];if(x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'M') {count++;}}if(count == 0) {board[i][j] = 'B';for(int k = 0; k < 8; k++) {int x = i + dx[k], y = j + dy[k];if(x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'E') {dfs(board, x, y);}}} else {board[i][j] = (char)(count + '0');}}
}

LCR 130. 衣櫥整理 - 力扣（LeetCode）

class Solution {int m, n, k, ret;boolean[][] vis;int[] dx = {0, 1};int[] dy = {1, 0};public int wardrobeFinishing(int _m, int _n, int _k) {k = _k; m = _m; n = _n;vis = new boolean[m][n];dfs(0,0);return ret;}public boolean check(int i, int j) {int tmp = 0;while(i != 0) {tmp += i % 10;i /= 10;}while(j != 0) {tmp += j % 10;j /= 10;}return tmp <= k;}public void dfs(int i, int j) {ret++;vis[i][j] = true;for(int k = 0; k < 2; k++) {int x = i + dx[k], y = j + dy[k];if(x < m && y < n && check(x, y) && !vis[x][y]) {dfs(x, y);}}       }
}

專題六 記憶化搜索

62. 不同路徑 - 力扣（LeetCode）

class Solution {int m, n;public int uniquePaths(int _m, int _n) {m = _m; n = _n;int[][] memo = new int[m + 1][n + 1];return dfs(m, n, memo);}public int dfs(int i, int j, int[][] memo) {if(memo[i][j] != 0) {return memo[i][j];}if(i == 0 || j == 0) {return 0;}if(i == 1 && j == 1) {memo[i][j] = 1;return 1;}memo[i][j] = dfs(i - 1, j, memo) + dfs(i, j - 1, memo);return memo[i][j];}
}

300. 最長遞增子序列 - 力扣（LeetCode）

class Solution {int[] memo;int n, ret;public int lengthOfLIS(int[] nums) {n = nums.length;memo = new int[n];for(int i = 0; i < n; i++) {ret = Math.max(ret, dfs(nums, i));}return ret;}public int dfs(int[] nums, int pos) {if(memo[pos] != 0) return memo[pos];int ret = 1;for(int i = pos + 1; i < n; i++) {if(nums[i] > nums[pos]) {ret = Math.max(ret, dfs(nums, i) + 1);}}memo[pos] = ret;return ret;}
}

375. 猜數字大小 II - 力扣（LeetCode）

class Solution {int[][] memo;public int getMoneyAmount(int n) {memo = new int[n + 1][n + 1];return dfs(1, n);}public int dfs(int left, int right) {if(left >= right) return 0;if(memo[left][right] != 0) return memo[left][right];int ret = Integer.MAX_VALUE;for(int i = left; i <= right; i++) {int x = dfs(left, i - 1), y = dfs(i + 1, right);ret = Math.min(ret, Math.max(x, y) + i);}memo[left][right] = ret;return ret;}
}

329. 矩陣中的最長遞增路徑 - 力扣（LeetCode）

class Solution {int[][] memo;int m, n;int[] dx = {0, 0, -1, 1};int[] dy = {-1, 1, 0, 0};public int longestIncreasingPath(int[][] matrix) {m = matrix.length; n = matrix[0].length;memo = new int[m][n];int ret = 0;for(int i = 0; i < m;i++) {for(int j = 0; j < n; j++) {ret = Math.max(ret, dfs(matrix, i, j));}}   return ret;}public int dfs(int[][] matrix, int i, int j) {if(memo[i][j] != 0) return memo[i][j];int ret = 1;for(int k = 0; k < 4; k++) {int x = i + dx[k], y = j + dy[k];if(x >= 0 && x < m && y >= 0 && y < n && matrix[x][y] > matrix[i][j]) {ret = Math.max(ret, dfs(matrix, x, y) + 1);}}memo[i][j] = ret;return ret;}
}

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/pingmian/79249.shtml
繁體地址，請注明出處：http://hk.pswp.cn/pingmian/79249.shtml
英文地址，請注明出處：http://en.pswp.cn/pingmian/79249.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！

相關文章

YOLOv11改進：利用RT-DETR主干網絡PPHGNetV2助力輕量化目標檢測

YOLOv11改進：利用RT-DETR主干網絡PPHGNetV2助力輕量化目標檢測

這里寫自定義目錄標題 YOLOv11改進&#xff1a;利用RT-DETR主干網絡PPHGNetV2助力輕量化目標檢測1. 介紹2. 引言3. 技術背景3.1 YOLOv11概述3.2 RT-DETR與PPHGNetV23.3 相關工作 4. 應用使用場景5. 詳細代碼實現5.1 環境準備5.2 PPHGNetV2主干網絡實現5.3 YOLOv11與PPHGNetV2集…
閱讀更多...
WPF之Button控件詳解

WPF之Button控件詳解

文章目錄 1. 引言2. Button控件基礎Button類定義 3. Button控件的核心屬性3.1 Content屬性3.2 IsDefault屬性3.3 IsCancel屬性3.4 其他常用屬性 4. 按鈕樣式與模板自定義4.1 簡單樣式設置4.2 使用Style對象4.3 觸發器使用4.4 使用ControlTemplate完全自定義4.5 按鈕視覺狀態 5.…
閱讀更多...
【Java】2025 年 Java 學習路線：從入門到精通

【Java】2025 年 Java 學習路線：從入門到精通

文章目錄 一、Java基礎階段（4-8周）1. 開發環境搭建2. 核心語法基礎3. 面向對象編程（OOP）4. 核心類庫二、Java進階階段（6-10周）1. JVM深度理解2. 并發編程3. 新特性掌握4. 設計模式三、開發框架與中間件（8-12周）1. Spring生態2. 持久層框架3. 常用中間件四、項目實戰階段…
閱讀更多...
虛幻引擎入門筆記

虛幻引擎入門筆記

【虛幻5】UE5新手入門嘗試 虛幻引擎的基礎設置 1.驗證-當文件誤刪的時候&#xff0c;對其進行驗證&#xff0c;可以恢復。 2.虛幻引擎極其強大&#xff0c;可以實現多種復合技能&#xff0c;所在創建項目頁面可以看見不只是創建游戲的項目 3.更改虛幻引擎默認的緩存地址。有些…
閱讀更多...
【PostgreSQL數據分析實戰：從數據清洗到可視化全流程】1.1 數據庫核心概念與PostgreSQL技術優勢

【PostgreSQL數據分析實戰：從數據清洗到可視化全流程】1.1 數據庫核心概念與PostgreSQL技術優勢

&#x1f449; 點擊關注不迷路 &#x1f449; 點擊關注不迷路 &#x1f449; 點擊關注不迷路 文章大綱 深度解析PostgreSQL核心架構與技術優勢&#xff1a;從數據庫原理到實戰場景1.1 數據庫核心概念與PostgreSQL技術優勢1.1.1 關系型數據庫核心架構解析1.1.1.1 數據庫系統的底…
閱讀更多...
詳解SLAM中的李群和李代數（上）

詳解SLAM中的李群和李代數（上）

1 概述 最近閱讀高翔大神的《視覺SLAM十四講》這本書&#xff0c;感覺整本書寫的非常的平實&#xff0c;用非常接地氣的語言毫無保留的介紹了視覺SLAM的相關知識&#xff0c;非常值得一讀。不過&#xff0c;在第4章出現的李群和李代數的相關概念就有點令人難以費解了。其實這段…
閱讀更多...
libevent庫詳解：高性能異步IO的利器

libevent庫詳解：高性能異步IO的利器

目錄 一、libevent 簡介 主要特點&#xff1a; 二、事件模型原理 1. event_base 2. event 3. evconnlistener&#xff08;TCP監聽器&#xff09; 4. bufferevent 簡化流程如下&#xff1a; 三、libevent 使用示例 1. 創建事件主循環 2. 創建監聽器&#xff08;TCP&a…
閱讀更多...
從 “零” 做個開源音樂軟件“SteadyBeat”吧！＜1＞ 準備

從 “零” 做個開源音樂軟件“SteadyBeat”吧！＜1＞ 準備

換換腦子&#xff0c;做個音樂軟件&#xff0c;根據調性、和弦走向&#xff08;情感&#xff09;、節拍、速度等需求&#xff0c;結合AI和一眾工具&#xff0c;自動生成伴奏、Solo等&#xff0c;有點像庫樂隊&#xff01;自己平時也用得著&#xff0c;暫時取名叫《SteadyBeat》…
閱讀更多...
npm error code CERT_HAS_EXPIRED

npm error code CERT_HAS_EXPIRED

npm error code CERT_HAS_EXPIRED 歡迎來到我的主頁&#xff0c;我是博主英杰&#xff0c;211科班出身&#xff0c;就職于醫療科技公司&#xff0c;熱衷分享知識&#xff0c;武漢城市開發者社區主理人 擅長.net、C、python開發&#xff0c; 如果遇到技術問題&#xff0c;即可私…
閱讀更多...
數字世界的“私人車道“：網絡切片如何用Python搭建專屬通信高速路？

數字世界的“私人車道“：網絡切片如何用Python搭建專屬通信高速路？

數字世界的"私人車道"&#xff1a;網絡切片如何用Python搭建專屬通信高速路&#xff1f; 2024年6月&#xff0c;中國移動宣布在浙江某智能工廠完成全球首個"5G工業網絡切片"規模商用——這條為生產線定制的"數字專屬車道"&#xff0c;將設備控制…
閱讀更多...
VSCode Verilog編輯仿真環境搭建

VSCode Verilog編輯仿真環境搭建

VSCode Verilog環境搭建 下載Iverilog安裝Iverilog驗證安裝VS Code安裝插件 下載Iverilog 官網下載Iverilog 安裝Iverilog 一定要勾選這兩項 建議勾選這兩項 驗證安裝 運行Windows PowerShell輸入命令&#xff1a;iverilog輸入命令&#xff1a;Get-Command gtkwave …
閱讀更多...
C++ - 數據容器之 list（創建與初始化、元素訪問、容量判斷、元素遍歷、添加元素、刪除元素）

C++ - 數據容器之 list（創建與初始化、元素訪問、容量判斷、元素遍歷、添加元素、刪除元素）

一、創建與初始化 引入 <list> 并使用 std 命名空間 #include <list>using namespace std;創建一個空 list list<int> my_list;創建一個包含 5 個元素&#xff0c;每個元素初始化為 0 的 list list<int> my_list(5);創建一個包含 5 個元素&#xf…
閱讀更多...
自動化測試項目1 --- 嘮嗑星球 [軟件測試實戰 Java 篇]

自動化測試項目1 --- 嘮嗑星球 [軟件測試實戰 Java 篇]

目錄 項目介紹 項目源碼庫地址 項目功能測試 1.自動化實施步驟 1.1 編寫測試用例 1.2 自動化測試腳本開發 1.2.1 配置相關環境, 添加相關依賴 1.2.2 相關代碼編寫 2. 自動化功能測試總結 2.1 彈窗的解決相關問題 2.2 斷言的使用和說明 2.3 重新登錄問題 項目性能…
閱讀更多...
Codeforces Round 1022 (Div. 2)（ABC）

Codeforces Round 1022 (Div. 2)（ABC）

A. Permutation Warm-Up 翻譯&#xff1a; 對于長度為 n 的排列 p&#xff0c;我們定義函數&#xff1a; 給你一個數 n。你需要計算函數 f(p) 在考慮從 1 到 n 的所有可能的數字排列時&#xff0c;可以取多少個不同的值。 思路&#xff1a; 按序排列時和為0&…
閱讀更多...
數據結構------C語言經典題目（6）

數據結構------C語言經典題目（6）

1.數據結構都學了些什么&#xff1f; 1.基本數據類型 算數類型&#xff1a; char&#xff08;字符&#xff09;、int&#xff08;整數&#xff09;、float&#xff08;單精度浮點數&#xff09;、double&#xff08;雙精度浮點數&#xff09;等。 枚舉類型&#xff1a; enum…
閱讀更多...
如何封裝一個線程安全、可復用的 HBase 查詢模板

如何封裝一個線程安全、可復用的 HBase 查詢模板

目錄 一、前言&#xff1a;原生 HBase 查詢的痛點 &#xff08;一&#xff09;連接管理混亂&#xff0c;容易造成資源泄露 &#xff08;二&#xff09;查詢邏輯重復&#xff0c;缺乏統一的模板 &#xff08;三&#xff09;多線程/高并發下的線程安全性隱患 &#xff08;四…
閱讀更多...
【中間件】bthread_基礎_TaskControl

【中間件】bthread_基礎_TaskControl

TaskControl 1 Definition2 Introduce**核心職責** 3 成員解析**3.1 數據結構與線程管理****3.2 任務調度與負載均衡****3.3 線程停放與喚醒&#xff08;ParkingLot&#xff09;****3.4 統計與監控** 4 **工作流程**5 **設計亮點**6 **使用場景示例**7 **總結**8 學習過程中的疑…
閱讀更多...
win11 終端 安裝ffmpeg 使用終端Scoop

win11 終端 安裝ffmpeg 使用終端Scoop

1、安裝scoop (Windows 包管理器) Set-ExecutionPolicy RemoteSigned -Scope CurrentUser iwr -useb get.scoop.sh | iex 2、使用scoop來安裝ffmpeg scoop install ffmpeg 3、測試一下ffmpeg&#xff0c;將Mp3文件轉為Wav文件 ffmpeg -i A.mp3 A.wav 然后我們就看到A.wav生成…
閱讀更多...
力扣838.推多米諾隨筆

力扣838.推多米諾隨筆

“生活就像海洋&#xff0c;只有意志堅強的人&#xff0c;才能到達彼岸。”—— 馬克思 題目 n 張多米諾骨牌排成一行&#xff0c;將每張多米諾骨牌垂直豎立。在開始時&#xff0c;同時把一些多米諾骨牌向左或向右推。 每過一秒&#xff0c;倒向左邊的多米諾骨牌會推動其左側…
閱讀更多...
超級好用的??參數化3D CAD 建模??圖形庫 （CadQuery庫介紹）

超級好用的??參數化3D CAD 建模??圖形庫 （CadQuery庫介紹）

CadQuery 庫詳細介紹?? ??CadQuery?? 是一個基于 ??Python?? 的 ??參數化 3D CAD 建模?? 庫&#xff0c;允許用戶通過編寫代碼&#xff08;而不是傳統 GUI&#xff09;來創建精確的 ??3D 模型??。它特別適用于 ??自動化設計、機械工程、3D 打印?? 等場景…
閱讀更多...
最新文章

Copyright @ 2022~2023