找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 1579|回复: 4
收起左侧

[刷题总结] 总结下recursion入门的几个题

[复制链接]

1

主题

0

精华

28

积分

新米人

Rank: 1

积分
28
发表于 8-12-2017 10:46 PM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

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 IVP 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);
        }

    }
}

评分

参与人数 1金钱 +3 收起 理由
Sophia + 3 好帖!大米满满送上!

查看全部评分

0

主题

0

精华

11

积分

新米人

Rank: 1

积分
11
发表于 8-12-2017 10:46 PM 来自美国米群网手机版 | 显示全部楼层
感谢carybabywin分享~~~
回复 支持 反对

使用道具 举报

0

主题

0

精华

1

积分

新米人

Rank: 1

积分
1
发表于 8-13-2017 09:49 PM | 显示全部楼层
感谢carybabywin分享~~~
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表