亲!马上注册或者登录会查看更多内容!
您需要 登录 才可以下载或查看,没有帐号?立即注册
x
总结一些recursion的练习题, 跟dfs和backtracking相关的,有一些固定写法,其中也有一些区别, 例如大家比较restore ip address 和palindrome partitioning 这两个题就可以看出来,一个是不断添加同一个pattern的结果到result里, 一个是把一个pattern拆分给几个部分分别insert。感觉backtracking主要是这两大块。
01-knapsack Maze(dfs): Visited[][], otherwise stackoverflow Optimize: 1. Visited【i】[j] = true => maze【i】[j] = X(wall) 2. use dx[], dy[] 3. move condition check into for loop Find maze path: To return path,need backtracking. New String, string 在java中是不可变object。
Knapsack: withduplicate number, can choose duplicate or not. Combinationsum(leetcode 39); i or i+1 depends onallow same number to be selected more than once. Combination sumII(leetcode 40) Combination sum IV P problem Generate parentheses:Catalan number
Letter combinationof a phone number public class Solution { String[] key = {"", "", "abc", "def","ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" }; public List<String> letterCombinations(String digits) { List<String> res = new ArrayList<String>(); if(digits ==null||digits.length()==0){ return res; } helper(digits, res, "",0); return res; } private void helper(String digits, List<String> res, String cur, int index){ if(cur.length() == digits.length()){ res.add(cur); return; } String letters = key[digits.charAt(index)-'0']; for(int i=0; i<letters.length(); i++){ cur = cur+letters.charAt(i); helper(digits, res, cur, index+1); cur = cur.substring(0,cur.length()-1); } }
} Subset public class Solution { public List<List<Integer>> subsets(int[] nums) { List<List<Integer>> res = new ArrayList<>(); helper(nums, res, 0, new ArrayList<Integer>()); return res; } private void helper(int[] nums, List<List<Integer>> res, int index, List<Integer> cur){ res.add(new ArrayList<Integer>(cur)); for(int i =index; i<nums.length; i++){ cur.add(nums【i】); helper(nums, res, i+1, cur); cur.remove(cur.size()-1); } }
} N-Queens public class Solution { public List<List<String>> solveNQueens(int n) { List<List<String>> res = new ArrayList<>(); int[] queens = new int[n]; helper(res, n, 0, queens); return res; } private void helper(List<List<String>> res, int n, int index, int[] queens){ if(index == n){ List<String> cur = new ArrayList<String>(); for(int num:queens){ StringBuilder sb = new StringBuilder(); for(int j=0; j<num; j++){ sb.append('.'); } sb.append('Q'); for(int j=num+1; j<n; j++){ sb.append('.'); } cur.add(sb.toString()); } res.add(new ArrayList<String>(cur)); return; } for(int num = 0; num < n; num++){ queens[index] = num; // 如果是有效的,继续搜索 if(isValid(queens, index)){ helper(res, n, index+1, queens); } } } private boolean isValid(int[] nqueens, int i){ for(int idx = 0; idx < i; idx++){ // 检查对角线只要判断他们差的绝对值和坐标的差是否相等就行了 if(nqueens[idx] == nqueens【i】 || Math.abs(nqueens[idx] - nqueens【i】) == i - idx){ return false; } } return true; }
} Palindromepartitioning public class Solution { public List<List<String>> partition(String s) { List<List<String>> res = new ArrayList<>(); helper(s, res, 0, new ArrayList<String>()); return res; } private void helper(String s, List<List<String>> res, int index, List<String> cur){ if(index==s.length()){ res.add(new ArrayList<String>(cur)); return; } for(int i =index; i<s.length(); i++){ String temp = s.substring(index, i+1); if(!isPalindrome(temp)) continue; cur.add(temp); helper(s, res, i+1, cur); cur.remove(cur.size()-1); } } private boolean isPalindrome(String s){ int i =0; int j = s.length()-1; while(i<j){ if(s.charAt(i) != s.charAt(j)) return false; i++; j--; } return true; }
} Subset II public class Solution { public List<List<Integer>> subsetsWithDup(int[] nums) { Arrays.sort(nums); List<List<Integer>> res = new ArrayList<>(); boolean[] visited = new boolean[nums.length]; helper(nums, res, 0, new ArrayList<Integer>(), visited); return res; } private void helper(int[] nums, List<List<Integer>> res, int index, List<Integer> cur, boolean[] visited){ res.add(new ArrayList<Integer>(cur)); for(int i =index;i<nums.length; i++){ if(visited【i】 ||i>0 &&nums【i】==nums[i-1]&&!visited[i-1]) continue; visited【i】 = true; cur.add(nums【i】); helper(nums, res, i+1, cur, visited); visited【i】 = false; cur.remove(cur.size()-1); } }
} Restore IP address public class Solution { public List<String> restoreIpAddresses(String s) { List<String> res = new ArrayList<>(); helper(res,s, "", 0, 0); return res; } private void helper(List<String> res, String s, String cur, int i, int count){ if(count>4){ return; } if(count==4 && i == s.length()){ res.add(cur.substring(1, cur.length())); } for(int j=1; j<=3; j++){ count++; if(i+j>s.length()) break; String sub = s.substring(i, i+j); if(j>1 && s.charAt(i) =='0') break; if(Integer.valueOf(sub)>255) break; cur = cur+ "." + sub; helper(res, s, cur, i+j, count); count--; cur = cur.substring(0, cur.length()-sub.length()-1); }
} }
|