知名做网站公司有哪些,网站建设写代码,关键词排名方法,如何快速网站排名Letter Combinations of a Phone Number - LeetCode
子集问题#xff0c;从多重循环到回溯
用一个path记录
回溯三问#xff1a;
dfs(i)-dfs(i 1)
这题要注意idx是我们遍历的数字的位数#xff0c;backtracking的时候要到下一层就是下一个数字#xff0c;每个数字…Letter Combinations of a Phone Number - LeetCode
子集问题从多重循环到回溯
用一个path记录
回溯三问
dfs(i)-dfs(i 1)
这题要注意idx是我们遍历的数字的位数backtracking的时候要到下一层就是下一个数字每个数字都是不同得集合这题是求不同集合得组合.
Time: On*4^n)
Space: O(n)
class Solution {String[] keypad new String[]{, , abc, def, ghi,jkl, mno, pqrs, tuv, wxyz};public ListString letterCombinations(String digits) {ListString res new ArrayList();if (digits null || digits.length() 0) return res;StringBuilder sb new StringBuilder();backtracking(res, sb, digits, 0);return res;}private void backtracking(ListString res, StringBuilder sb, String digits, int idx) {if (idx digits.length()) {res.add(sb.toString());return;}String key keypad[digits.charAt(idx) - 0];for (int i 0; i key.length(); i) {sb.append(key.charAt(i));backtracking(res, sb, digits, idx 1);sb.deleteCharAt(sb.length() - 1);}}
} Restore IP Addresses - LeetCode
判断isValid的地方要注意细节
Time: O(3^4)
Space: O(n)
class Solution {public ListString restoreIpAddresses(String s) {ListString res new ArrayList();StringBuilder sb new StringBuilder(s);backtracking(res, sb, 0, 0);return res;}private void backtracking(ListString res, StringBuilder sb, int points, int idx) {if (points 3) {if (isValid(sb, idx, sb.length() - 1)) {res.add(sb.toString());}return;}for (int i idx; i sb.length(); i) {if (isValid(sb, idx, i)) {sb.insert(i 1, .);points 1;backtracking(res, sb, points, i 2);sb.deleteCharAt(i 1);points - 1;}}}private boolean isValid(StringBuilder sb, int left, int right) {if (left right) return false;if (sb.charAt(left) 0 left ! right) return false;int num 0;for (int i left; i right; i) {if (sb.charAt(i) 0 || sb.charAt(i) 9) return false;int digit sb.charAt(i) - 0;num num * 10 digit;if (num 255) return false;}return true;}
} N-Queens - LeetCode
因为在单层搜索的过程中每一层递归只会选for循环也就是同一行里的一个元素所以不用去重了。
Time: O(n!)
Space: O(n)
class Solution {public ListListString solveNQueens(int n) {ListListString res new ArrayList();char[][] chess new char[n][n];for (char[] c : chess) {Arrays.fill(c, .);}backtracking(res, chess, n, 0);return res;}private void backtracking(ListListString res, char[][] chess, int n, int row) {if (row n) {res.add(construct(chess));return;}for (int i 0; i n; i) {if (isValid(row, i, n, chess)) {chess[row][i] Q;backtracking(res, chess, n, row 1);chess[row][i] .;}}}private boolean isValid(int row, int col, int n, char[][] chess) {for (int i 0; i row; i) {if (chess[i][col] Q) return false;}for (int i row - 1, j col - 1; i 0 j 0; i--, j--) {if (chess[i][j] Q) return false;}for (int i row - 1, j col 1; i 0 j n - 1; i--, j ) {if (chess[i][j] Q) return false;}return true;}private ListString construct(char[][] chess) {ListString path new ArrayList();for (int i 0; i chess.length; i) {path.add(new String(chess[i]));}return path;}
}
