Leetcode总结之Backtracking
2024-10-21 06:18:49
本文我们就Leetcode中的一个类型的题目backtracking进行一系列的总结和归纳。
backtracking这个方法本质是建立在递归的基础上，不断尝试新的路径，这里关键是每次尝试完以后需要退回来也就是回溯。
backtracking这个方法本质是建立在递归的基础上，不断尝试新的路径，这里关键是每次尝试完以后需要退回来也就是回溯。
如果你已经找到了解决方案，那么返回成功
for(现在位置可以的所有可能选择）｛
选择其中一个方案然后沿着路径前进一步
使用递归的方法从新的位置解决问题
如果新的位置可以成功解决，向上一级返回成功
从现在位置恢复到循环之前的位置 ｝
如果到这里表示仍然没有成功，返回失败
下面我们来看一下的例题：
package DFS; import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;
import java.util.Stack; public class DFSProblem { public static void main(String[] args) {
List<List<Integer>> res=new ArrayList<List<Integer>>();
res=getFactors(12);
System.out.println(res.size());
}
/*
* 113. Path Sum II
* 11.18 By Mingyang
* 典型的backtracking，不过注意，这里的值可能是负数，所以不能用sum小于0来做任何判断
* 1.长度标准：无
* 2.可选的范围：每一个node的左边和右边子节点（不为空的情况）。
* 3.往前走一步：temp加一个，sum减一个
* 4.后退一步：把temp remove掉
* 5.特殊的case：root==null也就是走到了根节点的下一个空了
*/
public List<List<Integer>> pathSum(TreeNode root, int sum) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
List<Integer> temp = new ArrayList<Integer>();
dfs(root, sum, res, temp);
return res;
}
public void dfs(TreeNode root, int sum, List<List<Integer>> res, List<Integer> temp){
if(root==null) return;
temp.add(root.val);
if(root.left==null && root.right==null ){
if(root.val==sum)
res.add(new ArrayList<Integer>(temp));
return;
}
if(root.left!=null) {
dfs(root.left,sum-root.val,res,temp);
temp.remove(temp.size()-1);
}
if(root.right!=null) {
dfs(root.right,sum-root.val,res,temp);
temp.remove(temp.size()-1);
}
}
/*
* 320 Generalized Abbreviation
* 2016-3-14 by Mingyang
* Given "word" Return the following list (order does not matter):
* ["word", "1ord", "w1rd", "wo1d", "wor1", "2rd", "w2d", "wo2", "1o1d", "1or1", "w1r1", "1o2", "2r1", "3d", "w3", "4"]
* 这道题目的题意是比较难懂的，网上找了很多，都是copy过来copy过去的，都是一个答案，所以后面自己想出来了一个最好的题意的解释。就是把四个数xxxx，用分别用一个1，两个1，三个1来代替其中的字母
* 如果出现111x就自动转化为3x，所以我的思路就是先找出所有包含1的排列组合，然后转换为标准格式。典型的backtracking。
* 1.长度标准：有1，2，3（0和4）单独来看的
* 2.可选的范围：从start开始的每一个字符（有一定的顺序，所以用start）
* 3.往前走一步：count-1，start+1，改变string
* 4.后退一步：把string改回来
* 5.特殊的case：count等于0，也就是输入了相应的个数的1
*/
public static List<String> generateAbbreviations(String word) {
List<String> res = new ArrayList<String>();
for(int i=1;i<word.length();i++){
dfs(word,res,i,0,"");
}
res.add(word);
res.add(Integer.toString(word.length()));
return res;
}
public static void dfs(String word,List<String> res,int count,int start,String copy){
if(count==0){
copy=format(copy);
res.add(copy);
return;
}
StringBuffer sb=new StringBuffer();
if(copy.length()==0){
sb.append(word);
}else{
sb.append(copy);
}
for(int i=start;i<word.length();i++){
sb.setCharAt(i,'1');//学习一下stringbuffer的技巧
dfs(word,res,count-1,i+1,sb.toString());
sb.setCharAt(i, word.charAt(i));
}
}
public static String format(String s){
StringBuffer sb=new StringBuffer();
int num=0;
for(int i=0;i<s.length()-1;i++){
if(Character.isDigit(s.charAt(i))&&Character.isDigit(s.charAt(i+1))){
if(num!=0)
num=num+s.charAt(i+1)-'0';
else
num=s.charAt(i)-'0'+s.charAt(i+1)-'0';
}else{
if(Character.isDigit(s.charAt(i))&&num!=0){
sb.append(num);
num=0;
}else{
sb.append(s.charAt(i));
}
}
}
if(num!=0){
sb.append(num);
}else{
sb.append(s.charAt(s.length()-1));}
return sb.toString();
}
/*
* 294 Flip Game II
* 2016-3-13 by Buttercola
* You and your friend take turns to flip twoconsecutive "++" into "--".
* The game ends when a person can no longer make a move and therefore the other person will be the winner.
* 总而言之就是一句话，我走了一步以后，你就没法走了。这道题目也算backtracking，不过跟典型的不一样，只用return boolean，并且传参只有数组（不用string，是因为string改参数比较麻烦，也是一种技巧）
* 1.长度标准：无
* 2.可选的范围：从0开始的每一个字符
* 3.往前走一步：改变整个char array
* 4.后退一步：把char array改回来
*/
public boolean canWin(String s) {
if (s == null || s.length() == 0) {
return false;
}
char[] arr = s.toCharArray();
return canWinHelper(arr);
}
private boolean canWinHelper(char[] arr) {
int i = 0;
for (i = 0; i < arr.length - 1; i++) {
if (arr[i] == '+' && arr[i + 1] == '+') {
arr[i] = '-';
arr[i + 1] = '-';
boolean win = !canWinHelper(arr);
arr[i] = '+';
arr[i + 1] = '+';
if (win) {
return true;
}
}
}
return false;
}
/*
* 291 Word Pattern II
* 2016-3-13 by Mingyang
* Given a pattern and a string str, find if str follows the same pattern.
* pattern = "abab", str = "redblueredblue" should return true.
* pattern = "aaaa", str = "asdasdasdasd" should return true.
* pattern = "aabb", str = "xyzabcxzyabc" should return false.
* 这道题目有一定的难度，又是一个backtracking boolean的题目，不过这里多了一个参数Hashmap
* 1.长度标准：无
* 2.可选的范围：从j开始，也就是从str未match的第一个字符开始的一系列的substring
* 3.往前走一步：改变map，将两个对应的东西分别放入map
* 4.后退一步：把map刚刚加入的值去掉
* 5.特别的case：刚好搜完和一个搜完了另一个没搜完，一个return true。另一个return false
* 我们要backtracking所有的可能的string的组合, 对于每个组合, 我们都需要添加到hashmap中,
* 这里, 我们在遍历pattern和string时, 要同时记录pattern中每个char对应在pattern的位置和当前string中substring对应的pattern的位置.
* 通过string和pattern在pattern中的位置i来判断是否相同. 为了区分pattern和string, 我们可以同两个hashmap。
*/
public boolean wordPatternMatch(String pattern, String str) {
HashMap map = new HashMap();
return dfs(pattern, 0, str, 0, map);
}
private boolean dfs(String pattern, int i, String str, int j, HashMap map){
if(i == pattern.length() && j == str.length()){// 如果刚好搜完. 返回true
return true;
}
if(i == pattern.length() || j == str.length()){// 如果一个完了, 另一个没完, 返回false
return false;
}
char c = pattern.charAt(i); //initialize new value
for(int k = j; k < str.length(); k++){
if(map.get(c) == map.get(str.substring(j, k+1))){//如果map中的i对应的值(可以是null) 和 sbustring对应的值相同(也可以是null)
Integer val = (Integer)map.get(c);
if(val == null){//如果是null
map.put(pattern.charAt(i), i);//把pattern的<char,integer>放map中
map.put(str.substring(j, k+1), i);//把string的<string,integer>放map中
}
if(dfs(pattern, i+1, str, k+1, map)){//dfs
return true;
}
if(val == null){// backtracking
map.remove(pattern.charAt(i));
map.remove(str.substring(j, k+1));
}
}
}
return false;//注意不要忘了，不能继续走下去拿到合适的match一定要return false
}
/*
* 267. Palindrome Permutation II
* 2016-3-13 by Mingyang
* Given a string s, return all the palindromic permutations (without duplicates) of it. Return an empty list if no palindromic permutation could be form.
* Given s = "aabb", return ["abba", "baab"].
* Given s = "abc", return [].
* 这道题目就相对来说简单多了，就跟permutation II类似，如果不写那个比较重要的判断句，那么久会出现很多的重复的。整题原理就是找到所有的组合可能性，再选择其中合适的
* 1.长度标准：无（固定）
* 2.可选的范围：对于一个array的所有permutation，这个array有重复（所以多了一句判断句），而且前后可以颠倒（所以用visited）。具体参考permutation II
* 3.往前走一步：sb加入这个数，visited改为true
* 4.后退一步：sb减去，visited改为false
* 5.特别的case：到了长度检查。
* 6.关于重复：因为可以有重复aabb可能会有abba和abba，第一个a在第一个，第二个a在第二个
*/
public static List<String> generatePalindromes(String s) {
List<String> res=new ArrayList<String>();
boolean[] visited=new boolean[s.length()];
char[] model=s.toCharArray();
StringBuffer sb=new StringBuffer();
dfs(res,model,visited,sb);
return res;
}
public static void dfs(List<String> res,char[] model,boolean[] visited,StringBuffer sb){
if(sb.toString().length()==model.length){
if(isPalindrome(sb.toString())){
res.add(sb.toString());
}
return;
}
for(int i=0;i<model.length;i++){
if (i > 0 && !visited[i - 1] && model[i] == model[i - 1]) // 这个非常的重要！！！！！！！！！！
continue;
if(!visited[i]){
sb.append(model[i]);
visited[i]=true;
dfs(res,model,visited,sb);
visited[i]=false;
sb.deleteCharAt(sb.length()-1);
}
}
}
/*
* 254 Factor Combinations
* 2016-3-13 by Mingyang
* Numbers can be regarded as product of its factors. For example,
* 8 = 2 x 2 x 2; 8= 2 x 4.
* Write a function that takes an integer n and return all possible combinations of its factors
* 1.长度标准：无（固定）
* 2.可选的范围：最开始是从2到n-1的所有整数，每一次递进以后。就是从上次取得那个数起到n-1的所有整数。
* 3.往前走一步：temp加入这个数，num乘以这个数--网上的版是这个数除以i。少了一个参数，一样的原理
* 4.后退一步：temp remove
* 5.特别的case：到了长度检查。
*/
public static List<List<Integer>> getFactors(int n) {
List<List<Integer>> res=new ArrayList<List<Integer>>();
List<Integer> temp=new ArrayList<Integer>();
dfs1(res,temp,1,n,2);
return res;
}
public static void dfs1(List<List<Integer>> res, List<Integer>temp, int num,int n,int start){
if(num==n){
res.add(new ArrayList<Integer>(temp));
return;
}
if(num>n)
return;
for(int i=start;i<n;i++){
if(n%(num*i)==0){//这里很巧妙地判断整除性，这样可以省去很多不必要的数
//num=num*i;原来这么分开写，但是这么分开写后面就要重新赋初值，把num改回去。所以直接在dfs1的参数里面乘
temp.add(i);
dfs1(res,temp,num*i,n,i);
temp.remove(temp.size()-1);
//num=num/i;
}
}
}
/*
* 39. Combination Sum
* 2015-12-13 by Mingyang
* The same repeated number may be chosen from C unlimited number of times.
* 注意在实现中for循环中第一步有一个判断，那个是为了去除重复元素产生重复结果的影响
* 因为在这里每个数可以重复使用，所以重复的元素也就没有作用了，所以应该跳过那层递归。
* 1.长度标准：无（固定）
* 2.可选的范围：从start开始到最后一个数
* 3.往前走一步：temp加入这个数，remain再减去
* 4.后退一步：temp减去这个数
* 5.特别的case：剩下的小于0直接return
* 6.关于重复：因为每个数可以用很多次。所以223时会出现重复，所以可以跳过第二个2.
*/
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
List<Integer> temp = new ArrayList<Integer>();
if (candidates == null || candidates.length == 0)
return res;
Arrays.sort(candidates);
dfs(candidates, target, 0, temp, res);
return res;
}
public void dfs(int[] candidates, int remain, int start,List<Integer> temp, List<List<Integer>> res) {
if (remain == 0) {
res.add(new ArrayList<Integer>(temp));
return;
}
if (remain < 0)
return;
for (int i = start; i < candidates.length; i++) {
if (i > 0 && candidates[i] == candidates[i - 1]) // 这里就是跳过那个重复的元素，因为每次已经可以重复使用自己了，这一步很重要！！
continue;
temp.add(candidates[i]);
dfs(candidates, remain - candidates[i], i, temp, res);
temp.remove(temp.size() - 1);
}
}
/*
* 40. Combination Sum II
* 2015-12-13 by Mingyang
* Each number in C may only be used
* once in the combination.
* 在这里我们还是需要在每一次for循环前做一次判断，因为虽然一个元素不可以重复使用，但是如果这个元素重复出现是允许的，
* 但是为了避免出现重复的结果集，我们只对于第一次得到这个数进行递归，接下来就跳过这个元素了，
* 因为接下来的情况会在上一层的递归函数被考虑到，这样就可以避免重复元素的出现。 Each number in C may only be used
* once in the combination. I 是The same repeated number may be chosen from C unlimited number of times.
* 1.长度标准：无（固定）
* 2.可选的范围：从start开始到最后一个数
* 3.往前走一步：temp加入这个数，remain再减去
* 4.后退一步：temp减去这个数
* 5.特别的case：剩下的小于0直接return
* 6.关于重复：11 和1 在第一个1用了以后，第二个1就不用了
*/
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
List<Integer> temp = new ArrayList<Integer>();
if (candidates == null || candidates.length == 0)
return res;
Arrays.sort(candidates);
dfs2(candidates, target, 0, temp, res);
return res;
}
public void dfs2(int[] candidates, int remain, int begin,List<Integer> temp, List<List<Integer>> res) {
if (remain == 0) {
res.add(new ArrayList<Integer>(temp));
return;
}
if (remain < 0)
return;
for (int i = begin; i < candidates.length; i++) {
if (i > begin && candidates[i] == candidates[i - 1])//去重复
continue;
temp.add(candidates[i]);
dfs2(candidates, remain - candidates[i], i + 1, temp, res);//所以在1中，这里的下一个还是i
temp.remove(temp.size() - 1);
}
}
/*
* 216. Combination Sum III
* 2015-12-18 by Mingyang
* i一定要取到9，虽然大小聪明，想只取到7，但是后面的遍历可能也会遍历到9啊。
* 1.长度标准：无（固定等于k）
* 2.可选的范围：从start开始到9
* 3.往前走一步：temp加入这个数，k-1表示又来了一位，n-i，然后start加1表示从下一位加起
* 4.后退一步：temp减去这个数
* 5.特别的case：剩下的小于0直接return
* 6.关于重复：11 和1 在第一个1用了以后，第二个1就不用了
*/
public List<List<Integer>> combinationSum3(int k, int n) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
List<Integer> temp = new ArrayList<Integer>();
dfs(res, temp, k, n, 1);
return res;
}
public void dfs(List<List<Integer>> res, List<Integer> temp, int k, int n,int start) {
if (k == 0) {
if (n == 0) {
res.add(new ArrayList<Integer>(temp));
}
return;
}
for (int i = start; i <= 9; i++) {
temp.add(i);
dfs(res, temp, k - 1, n - i, start+1);
temp.remove(temp.size() - 1);
}
}
/*
* 131. Palindrome Partitioning
* 2015-12-17 by Mingyang
* Return all possible palindrome partitioning of s.
* 1.长度标准：无（固定）
* 2.可选的范围：从start开始到最后一个
* 3.往前走一步：temp加入这个数，然后start加1表示从下一位加起
* 4.后退一步：temp减去这个数
* 5.特别的case：start到最后一位
* 6.关于重复：无
*/
public List<List<String>> partition(String s) {
List<String> item = new ArrayList<String>();
List<List<String>> res = new ArrayList<List<String>>();
if (s == null || s.length() == 0)
return res;
dfs(s, 0, item, res);
return res;
}
public void dfs(String s, int start, List<String> item,List<List<String>> res) {
if (start == s.length()) {
res.add(new ArrayList<String>(item));
return;
}
for (int i = start; i < s.length(); i++) {
String str = s.substring(start, i + 1);// 每一轮dfs进来都是先取第一个数，start index，可以不用stringbuffer来存
if (isPalindrome(str)) {
item.add(str);
dfs(s, i + 1, item, res);// 上面取到i，所以下一个start index就是i+1
item.remove(item.size() - 1);
}
}
}
public static boolean isPalindrome(String s) {
int low = 0;
int high = s.length() - 1;
while (low < high) {
if (s.charAt(low) != s.charAt(high))
return false;
low++;
high--;
}
return true;
}
/*
* 93. Restore IP Addresses
* 2015.12.16 by Mingyang
* 这里不用StringBuffer因为我们最后要检查每一小块string到底是否符合要求
* 1.长度标准：无（固定）
* 2.可选的范围：从start开始到最后一个
* 3.往前走一步：stringbuffer 变成string跟前面的相加成为一个新的string，然后start加1表示从下一位加起，然后count也减一个
* 4.后退一步：不用，因为传进去是string，不会对当前状态进行影响
* 5.特别的case：count小于等于0
* 6.关于重复：无
*/
public static List<String> restoreIpAddresses1(String s) {
List<String> res = new ArrayList<String>();
dfs(res, s, 0, "", 4);
return res;
}
public static void dfs(List<String> res, String s, int start, String item,int count) {
if (start == s.length() && count == 0) {
res.add(item);
return;
}
if (count <= 0) {
return;
}
StringBuffer sb = new StringBuffer();
for (int i = start; i < s.length(); i++) {
sb.append(s.charAt(i));
if (isValid(sb.toString())) {
dfs(res, s, i + 1, item.isEmpty() ? (sb.toString()): (item + '.' + sb.toString()), count-1);
} else {
return;// 为什么需要写这个呢，因为这个可以防止多余的计算，比如数字太大2552551113，会让下面的isValid失效，就是省去多余的
}
}
}
public static boolean isValid(String s) {
if (s.charAt(0) == '0')
return s.equals("0"); // 如果以0开头的，必须要检查是否等于001，011等不合格的，若开头为0，整个数必须为0
System.out.println(s);
int num = Integer.parseInt(s); if (num <= 255 && num > 0)
return true;
else
return false;
}
/*
* 78. Subsets
* 2015.12.16 by Mingyang
* 注意这里虽然感觉很像combine，但是这个array可以随意的，可以为任意数的array，所以还是得用array来
* 并且那个array要sort一下，记住，千万不要忘了加空集
* 1.长度标准：从空集，到本身长度的集合
* 2.可选的范围：从start开始到最后一个
* 3.往前走一步：item加一个，然后start加1表示从下一位加起，然后count也减一个
* 4.后退一步：不用，因为传进去是string，不会对当前状态进行影响
* 5.特别的case：count小于等于0
* 6.关于重复：无
*/
public static List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
ArrayList<Integer> item = new ArrayList<Integer>();
if (nums.length == 0 || nums == null)
return res;
Arrays.sort(nums);
for (int len = 1; len <= nums.length; len++)
dfs3(nums, 0, len, item, res);
res.add(new ArrayList<Integer>());
return res;
}
public static void dfs3(int[] S, int start, int len, List<Integer> item,List<List<Integer>> res) {
if (item.size() == len) {
res.add(new ArrayList<Integer>(item));
return;
}
for (int i = start; i < S.length; i++) {
item.add(S[i]);
dfs3(S, i + 1, len, item, res);
item.remove(item.size() - 1);
}
}
/*
* 90. Subsets II 12.16 by Mingyang
* 这里我们将后面重复的部分算进来，就是当有重复出现的时候，结果不能重复，我就加了一个boolean array
* 1.长度标准：从空集，到本身长度的集合
* 2.可选的范围：从start开始到最后一个
* 3.往前走一步：item加一个，然后start加1表示从下一位加起，然后count也减一个
* 4.后退一步：不用，因为传进去是string，不会对当前状态进行影响
* 5.特别的case：count小于等于0
* 6.关于重复：这里有重复出现，所以多了boolean array
*/
public static List<List<Integer>> subsetsWithDup(int[] nums) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
ArrayList<Integer> item = new ArrayList<Integer>();
if (nums.length == 0 || nums == null)
return res;
Arrays.sort(nums);
boolean[] array = new boolean[nums.length];
for (int len = 1; len <= nums.length; len++)
dfs3(nums, 0, len, item, res, array);
res.add(new ArrayList<Integer>());
return res;
}
public static void dfs3(int[] S, int start, int len, List<Integer> item,List<List<Integer>> res, boolean[] array) {
if (item.size() == len) {
res.add(new ArrayList<Integer>(item));
return;
}
for (int i = start; i < S.length; i++) {
if (i != 0 && S[i] == S[i - 1] && array[i - 1] == false)//这句非常关键，表示出了第一个以外，所有的跟前面一样的，并且前面还没用过（多半用了被重新还原的）
continue;
item.add(S[i]);
array[i] = true;
dfs3(S, i + 1, len, item, res, array);
item.remove(item.size() - 1);
array[i] = false;
}
}
/*
* 79. Word Search
* 2015.12.16 by Mingyang
* 这里的起点就是遍历所有的点，找出这个起点
* 我自己做的时候，用了一个StringBuffer来进行加减，判断条件就是sb和word相等，但是！每次加减sb造成了时间上的浪费
* 这里我们用一个index来就好了，每次完了以后，index+1.这样的话我们就可以通过index和word的长度来判断
* 另外有一个技巧就是index不用自己加加，只用加1，这样不会改变index的本质，不用退回来再减一个了。
* 1.长度标准：所有表格进行遍历，对每一个进行dfs，只要有一个可以就成功了
* 2.可选的范围：没有可选范围，已经规定死了xy轴
* 3.往前走一步：可以往上下左右四个方向分别加1
* 4.后退一步：mark unvisited
* 5.特别的case：出界了，访问过了，或者达标了
* 6.关于重复：无
*/
public boolean exist(char[][] board, String word) {
int m = board.length;
int n = board[0].length;
boolean[][] visited = new boolean[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (dfs4(board, word, 0, i, j, visited))
return true;
}
}
return false;
}
public boolean dfs4(char[][] board, String word, int index, int rowindex,int colindex, boolean[][] visited) {
if (index == word.length())
return true;
if (rowindex < 0 || colindex < 0 || rowindex >= board.length|| colindex >= board[0].length)
return false;
if (visited[rowindex][colindex])
return false;
if (board[rowindex][colindex] != word.charAt(index))
return false;
visited[rowindex][colindex] = true;
boolean res = dfs4(board, word, index + 1, rowindex - 1, colindex,visited)
|| dfs4(board, word, index + 1, rowindex + 1, colindex, visited)
|| dfs4(board, word, index + 1, rowindex, colindex + 1, visited)
|| dfs4(board, word, index + 1, rowindex, colindex - 1, visited);
visited[rowindex][colindex] = false;
return res;
}
/*
* 77. Combinations
* 2015.12.16 by Mingyang
* 这里有个一个start的多的参数以后就可以保证所有序列按顺序输出的，并且不会重复 12-13-14-23-24-34
* 1.长度标准：无
* 2.可选的范围：从start到最后一个
* 3.往前走一步：可以往上下左右四个方向分别加1
* 4.后退一步：mark unvisited
* 5.特别的case：出界了，访问过了，或者达标了
* 6.关于重复：无
*/
public static List<List<Integer>> combine(int n, int k) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
if (n <= 0 || n < k)
return res;
List<Integer> item = new ArrayList<Integer>();
dfs2(n, k, 1, item, res);// because it need to begin from 1-------从1开始的哦
return res;
}
private static void dfs2(int n, int k, int start, List<Integer> item,List<List<Integer>> res) {
if (item.size() == k) {
res.add(new ArrayList<Integer>(item));// because item is ArrayList<T> so it will not disappear from stack to stack
return;
}
for (int i = start; i <= n; i++) { // 这里多加了一个start，这样就不用再判断重复了
item.add(i);
dfs2(n, k, i + 1, item, res);
item.remove(item.size() - 1);
}
}
/*
* 51. N-Queens
* 2016.3.12 by Mingyang
* 在这道题目里面，到了最后一步，才把整个棋盘转换成List of String
* 其余的大部分时间都是只是把棋盘相应的位置填满 另外这道题目走的方式，不是像word
* search那么上下左右到处走，而是在列数确定的情况下，行数从第一个到最后一个loop
* 1.长度标准：无
* 2.可选的范围：在col固定的情况下，遍历所有的row
* 3.往前走一步：如果某一个row可以就检查是否validate，并且把棋盘上的值改了
* 4.后退一步：棋盘上的值改回来
* 5.特别的case：column走到了最后一个
* 6.关于重复：无
*/
public List<List<String>> solveNQueens(int n) {
char[][] board = new char[n][n];
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
board[i][j] = '.';
List<List<String>> res = new ArrayList<List<String>>();
dfs(board, 0, res);
return res;
}
private void dfs(char[][] board, int colIndex, List<List<String>> res) {
if (colIndex == board.length) {
res.add(construct(board));
return;
}
for (int i = 0; i < board.length; i++) {
if (validate(board, i, colIndex)) {
board[i][colIndex] = 'Q';
dfs(board, colIndex + 1, res);
board[i][colIndex] = '.';
}
}
}
private boolean validate(char[][] board, int x, int y) {
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < y; j++) {
if (board[i][j] == 'Q'&& (x + j == y + i || x + y == i + j || x == i))
return false;
}
}
return true;
}
private List<String> construct(char[][] board) {
List<String> res = new LinkedList<String>();
for (int i = 0; i < board.length; i++) {
String s = new String(board[i]);
res.add(s);
}
return res;
}
/*
* 52. N-Queens II
* 2015.12.16 by Mingyang
* 1.长度标准：无
* 2.可选的范围：在row固定的情况下，遍历所有的列
* 3.往前走一步：如果某一个col可以就检查是否validate，并且存上column的信息
* 4.后退一步：棋盘上的值改回来
* 5.特别的case：row走完了
* 6.关于重复：无
*/
public int totalNQueens(int n) {
int[] res = { 0 };
if (n <= 0)
return res[0];
int[] columnVal = new int[n];
DFS_helper(n, res, 0, columnVal);
return res[0];
}
public void DFS_helper(int nQueens, int[] res, int row, int[] columnVal) {
if (row == nQueens) {
res[0] += 1;
} else {
for (int i = 0; i < nQueens; i++) {
columnVal[row] = i;// (row,columnVal[row)==>(row,i)
if (isValid(row, columnVal))
DFS_helper(nQueens, res, row + 1, columnVal);
}
}
}
public boolean isValid(int row, int[] columnVal) {
for (int i = 0; i < row; i++) {
if (columnVal[row] == columnVal[i]|| Math.abs(columnVal[row] - columnVal[i]) == row - i)
return false;
}
return true;
}
/*
* 46. Permutations
* 2015.12.13 by Mingyang 方法还是原来那个套路，还是用一个循环递归处理子问题。
* 区别是这里并不是一直往后推进的，前面的数有可能放到后面，所以我们需要维护一个visited数组来表示该元素是否已经在当前结果中，
* 因为每次我们取一个元素放入结果，然后递归剩下的元素，所以不会出现重复
* 这道题还有一个扩展就是如果元素集合中会出现重复，那么意味着我们需要跳过一些重复元素
* 1.长度标准：无
* 2.可选的范围：任何一个都可以选！没有顺序
* 3.往前走一步：在未访问某一个的前提下，直接带入
* 4.后退一步：remove
* 5.特别的case：size到了
* 6.关于重复：无
*/
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
if (nums == null || nums.length == 0)
return res;
boolean[] visited = new boolean[nums.length];
List<Integer> temp = new ArrayList<Integer>();
dfs3(nums, visited, temp, res);
return res;
}
private void dfs3(int[] nums, boolean[] visited, List<Integer> temp,List<List<Integer>> res) {
if (temp.size() == nums.length) {
res.add(new ArrayList<Integer>(temp));
return;
}
for (int i = 0; i < nums.length; i++) {
if (!visited[i]) {
visited[i] = true;
temp.add(nums[i]);
dfs3(nums, visited, temp, res);
temp.remove(temp.size() - 1);
visited[i] = false;
}
}
}
/*
* 47. Permutations II
* 2015.12.13 by Mingyang 唯一的区别就是在这个题目中元素集合可以出现重复。
* 这给我们带来一个问题就是如果不对重复元素加以区别， 那么类似于{1,1,2}这样的例子我们会有重复结果出现。那么如何避免这种重复呢？
* 方法就是对于重复的元素循环时跳过递归函数的调用，只对第一个未被使用的进行递归，
* 我们那么这一次结果会出现在第一个的递归函数结果中，而后面重复的会被略过。 如果第一个重复元素前面的元素还没在当前结果中，那么我们不需要进行递归。
* 首先我们要对元素集合排序，从而让重复元素相邻，接下来就是一行代码对于重复元素和前面元素使用情况的判断即可。
* 这样的解法是带有一般性的，把这个代码放到Permutations中也是正确的，所以如果熟悉的话，
* 面试时如果碰到这个题目建议直接实现这个代码，不要假设元素没有重复，当然可以跟面试官讨论，不过一般来说都是要考虑这个情况的哈。
* 1.长度标准：无
* 2.可选的范围：任何一个都可以选！没有顺序
* 3.往前走一步：在未访问某一个的前提下，直接带入
* 4.后退一步：remove
* 5.特别的case：size到了
* 6.关于重复：这里对于重复有要求，因为这个可以允许重复的字符，所以如果我等于前面的一个，并且前面的一个未访问（其实已经访问并且清除了）直接return
*/
public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
if (nums == null || nums.length == 0)
return res;
Arrays.sort(nums);
boolean[] visited = new boolean[nums.length];
List<Integer> temp = new ArrayList<Integer>();
dfs4(nums, visited, temp, res);
return res;
}
private void dfs4(int[] nums, boolean[] visited, List<Integer> temp,List<List<Integer>> res) {
if (temp.size() == nums.length) {
res.add(new ArrayList<Integer>(temp));
return;
}
for (int i = 0; i < nums.length; i++) {
if (i > 0 && !visited[i - 1] && nums[i] == nums[i - 1]) // 这个非常的重要！！！！！！！！！！
continue;
if (!visited[i]) {
visited[i] = true;
temp.add(nums[i]);
dfs4(nums, visited, temp, res);
temp.remove(temp.size() - 1);
visited[i] = false;
}
}
}
/*
* 37. Sudoku Solver
* 2015.12.13 by Mingyang
* 1.长度标准：无
* 2.可选的范围：所有木有值得点，选取从1到9的数字
* 3.往前走一步：如果放进去是validate的，那就放
* 4.后退一步：若果放进去，后面是false的，就把这个点改回来
* 5.特别的case：无了
* 6.关于重复：无
* 本题目的isValid是难点
*/
public void solveSudoku(char[][] board) {
if (board == null || board.length == 0)
return;
helper(board);
}
private boolean helper(char[][] board) {
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
if (board[i][j] == '.') {
for (char num = '1'; num <= '9'; num++) {// 尝试
if (isValid(board, i, j, num)) {
board[i][j] = num;
if (helper(board))
return true;
else
board[i][j] = '.';// 回退
}
}
return false;
}
}
}
return true;
}
private boolean isValid(char[][] board, int i, int j, char c) {
// check column
for (int row = 0; row < 9; row++)
if (board[row][j] == c)
return false;
// check row
for (int col = 0; col < 9; col++)
if (board[i][col] == c)
return false;
// check block
for (int row = i / 3 * 3; row < i / 3 * 3 + 3; row++)
for (int col = j / 3 * 3; col < j / 3 * 3 + 3; col++)
if (board[row][col] == c)
return false;
return true;
}
/*
* 22. Generate Parentheses
* 2015.12.13 by Mingyang
* 1.长度标准：无
* 2.可选的范围：只有左括号和右括号，先一直加左边，完了再加右边
* 3.往前走一步：sb加了，left或right减一
* 4.后退一步：sb remove
* 5.特别的case：left和right都为0
* 6.关于重复：无
*/
public static List<String> generateParenthesis(int n) {
List<String> res = new ArrayList<String>();
if (n <= 0)
return res;
StringBuffer sb = new StringBuffer();
dfs100(n, n, res, sb);
return res;
}
public static void dfs100(int left, int right, List<String> res,StringBuffer sb) {
if (left == 0 && right == 0) {
res.add(sb.toString());
System.out.println(sb.toString());
return;
}
if (left > right)
return;
if (left < 0 || right < 0)
return;
sb.append('(');
dfs100(left - 1, right, res, sb);
sb.deleteCharAt(sb.length() - 1);
sb.append(')');
dfs100(left, right - 1, res, sb);
sb.deleteCharAt(sb.length() - 1);
}
/*
* 17. Letter Combinations of a Phone Number
* 2015.11.30 by Mingyang 是对keyboard的循环
* 1.长度标准：无
* 2.可选的范围：数字对应的keyboard的string遍历每一个char
* 3.往前走一步：加上这个char以后，index又加1
* 4.后退一步：stringbuffer remove
* 5.特别的case：长度相等
* 6.关于重复：无
*/
public List<String> letterCombinations(String digits) {
List<String> result = new ArrayList<String>();
if (digits == null || digits.length() == 0)
return result;
String[] keyboard = { "", "", "abc", "def", "ghi", "jkl", "mno","pqrs", "tuv", "wxyz" };
StringBuilder current = new StringBuilder();
int index = 0;
dfs(digits, index, current, keyboard, result);
return result;
}
private void dfs(String digits, int index, StringBuilder current,String[] keyboard, List<String> result) {
if (index == digits.length()) {
result.add(current.toString());
return;
}
int num = digits.charAt(index) - '0';// get integer number
for (int i = 0; i < keyboard[num].length(); i++) {
current.append(keyboard[num].charAt(i));
dfs(digits, index + 1, current, keyboard, result);
current.deleteCharAt(current.length() - 1);
}
} /*
* Number of Islands 12.19 by Mingyang
* 直接设一个叫count的值，没遇到一个1，就把所有相连的1全部变为0，这样，到底遇到几次1，就是最终有几个小岛啦
*/
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0 || grid[0].length == 0)
return 0;
int count = 0; for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (grid[i][j] == '1') {
count++;
dfs(grid, i, j);
}
}
}
return count;
} public void dfs(char[][] grid, int i, int j) {
// validity checking
if (i < 0 || j < 0 || i > grid.length - 1 || j > grid[0].length - 1)
return; // if current cell is water or visited
if (grid[i][j] != '1')
return; // set visited cell to '0'
grid[i][j] = '0'; // merge all adjacent land
dfs(grid, i - 1, j);
dfs(grid, i + 1, j);
dfs(grid, i, j - 1);
dfs(grid, i, j + 1);
} /*
* 212. Word Search II 12.17 by Mingyang 这么做可以在word
* search的基础之上做，但是效率不高，所以后面可以用tire tree
*/
public List<String> findWords(char[][] board, String[] words) {
ArrayList<String> result = new ArrayList<String>();
int m = board.length;
int n = board[0].length;
for (String word : words) {
boolean flag = false;
boolean[][] visited = new boolean[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
char[][] newBoard = new char[m][n];
for (int x = 0; x < m; x++)
for (int y = 0; y < n; y++)
newBoard[x][y] = board[x][y];
if (dfs4(newBoard, word, i, j, 0, visited)) {
flag = true;
}
}
}
if (flag) {
result.add(word);
}
}
return result;
} /*
* Simplify Path 12.3 by Mingyang 当遇到“/../"则需要返回上级目录，需检查上级目录是否为空。
*
* 当遇到"/./"则表示是本级目录，无需做任何特殊操作。
*
* 当遇到"//"则表示是本级目录，无需做任何操作。
*
* 当遇到其他字符则表示是文件夹名，无需简化。
*
* 当字符串是空或者遇到”/../”，则需要返回一个"/"。
*
* 当遇见"/a//b"，则需要简化为"/a/b"。 所以我们这里遇到简化的时候，先split为//之间的值。然后用两个堆栈来解决，因为方向是反的
* 当字符串为空或者为"."，不做任何操作。
*
* 当字符串不为".."，则将字符串入栈。
*
* 当字符串为"..", 则弹栈（返回上级目录）。
*/
public String simplifyPath(String path) {
if (path == null || path.length() == 0)
return path; Stack<String> stack = new Stack<String>();
String[] list = path.split("/"); for (int i = 0; i < list.length; i++) {
if (list[i].equals(".") || list[i].length() == 0)
continue;
else if (!list[i].equals(".."))
stack.push(list[i]);
else {
if (!stack.isEmpty())
stack.pop();
}
} StringBuilder res = new StringBuilder(); Stack<String> temp = new Stack<String>();
while (!stack.isEmpty())
temp.push(stack.pop()); while (!temp.isEmpty())
res.append("/" + temp.pop()); if (res.length() == 0)
res.append("/"); return res.toString();
} /*
* Additive Number 1.2 by Mingyang
*/
public boolean isAdditiveNumber(String s) {
int n = s.length();
for (int i = 1; i < n; i++) {
for (int j = i + 1; j < n; j++) {
long a = parse(s.substring(0, i));
long b = parse(s.substring(i, j));
if (a == -1 || b == -1)
continue;
if (dfs(s.substring(j), a, b))
return true;
}
}
return false;
} boolean dfs(String s, long a, long b) {
if (s.length() == 0)
return true; for (int i = 1; i <= s.length(); i++) {
long c = parse(s.substring(0, i));
if (c == -1)
continue;
if (c - a == b && dfs(s.substring(i), b, c)) {
return true;
}
}
return false;
} long parse(String s) {
if (!s.equals("0") && s.startsWith("0"))
return -1;
long result = 0;
try {
result = Long.parseLong(s);
} catch (NumberFormatException e) {
return -1;
}
return result;
}
}
最新文章
- 不要让catalogs搞死你的eclipse
- 转载--tomcat整合apr
- paper 98：图像视觉各个领域文献目录
- 【poj1090】 Chain
- ionic react-native和native开发移动app到底那个好
- POJ 1930
- ubuntu13.04 Thinkpad W520安装nvidia显卡驱动
- Java学习03
- Org-mode五分钟教程ZZZ - Kaka Abel的日志 - 网易博客
- SOLID 设计原则 In C# 代码实现
- HTML DOM应用案例2
- 用Nodejs+Express搭建web，nodejs路由和Ajax传数据并返回状态，nodejs+mysql通过ajax获取数据并写入数据库
- javascript 复制数组
- PyQt4 的部件 -- CheckBox 单选框
- 10.socket网络编程
- Python_字符串之删除空白字符或某字符或字符串
- Java学习路线图分析
- html 基本指令
- F. 数学上来先打表
- Oracle数据库访问其他用户下的表,不加表所属的用户名的实现方法