Leetcode 的DFS题目们

-
包括但不限于：
1. Generate Parentheses
2. Letter Combinations of a Phone Number
3. Combination Sum
4. Combination Sum II
5. Combination Sum III
6. Combination
7. Permutations
8. Permutations II

 1. Generate Parentheses

解法：结果里面任意一个从左往右看的话 在任意位置都需要满足当前 "(" 的个数大于等于")"的个数。所以我们要维护的就是两个int值，left 和 right。分别代表"(" 以及 ")"的个数。当left > right，left < 0 , right < 0都属于应该回退的条件。 当left 和 right 都是0 的时候表示这时一个合法的解。其他情况都应该继续进行深搜。

当n==2时 问题的解空间：
public class Solution {
    public List generateParenthesis(int n) {
        StringBuilder sb = new StringBuilder();
        List result = new ArrayList();
        if(n &lt;= 0)
            return result;
        dfs("",result,n,n);
        return result;
    }
    
    static void dfs(String s,List result,int left,int right){
        if(left &gt; right || left &lt; 0 || right &lt; 0){
            return;
        }
        
        if(left == 0 &amp;&amp; right == 0){
            result.add(s);
            return;
        }
        
        dfs(s+"(",result,left -1,right);
        dfs(s+")",result,left,right -1);
    }
}

2. Letter Combinations of a Phone Number

要点：要得出的是一个所有组合情况，所以还是一个典型的DFS题目
明确一下回退条件：
当digits中的一个数字的所有第一个字符都已经尝试过了的时候就应该删除这个字符换这个数字对应的第二个字符进行接下来的连接。
需要的解的情况：
当我们的StringBuilder的长度和我们的digits的长度相等（即到我们要的长度）时候
其他情况需要继续深搜
public class Solution {
    public List letterCombinations(String digits) {
        List result = new ArrayList();
        if(digits.length() == 0 || digits == null){
            return result;
        }
        Map&lt;Character,char[]&gt; map = new HashMap&lt;Character,char[]&gt;();
        map.put('0',new char[] {});
        map.put('1',new char[] {});
        map.put('2',new char[] {'a','b','c'});
        map.put('3',new char[] {'d','e','f'});
        map.put('4',new char[] {'g','h','i'});
        map.put('5',new char[] {'j','k','l'});
        map.put('6',new char[] {'m','n','o'});
        map.put('7',new char[] {'p','q','r','s'});
        map.put('8',new char[] {'t','u','v'});
        map.put('9',new char[] {'w','x','y','z'});
        StringBuilder sb = new StringBuilder();
        dfs(digits,result,sb,map);
        return result;
    }
    static void dfs(String digits,List result,StringBuilder sb,Map&lt;Character,char[]&gt; map){
        if(sb.length() == digits.length()){
            result.add(sb.toString());
            return;
        }else{
            for(char c:map.get(digits.charAt(sb.length()))){
                sb.append(c);
                dfs(digits,result,sb,map);
                sb.deleteCharAt(sb.length() -1);// BACKTRACING
            }
        }
    }
}

 3. Combination Sum

题意：给出一个数组，挑出其中若干个数，他们的和等于target
解法: 这相当于一个记录路径的DFS，然而路径就是和组成target的那几个数字。还是先排序，然后从小到大遍历。
回退：当发现当前值大于target-之前已选的数的和时候回退
每次更新target -= 选中的数字
需要的解：target == 0 时候路径里面所有的数
其他条件应该继续深搜并记录路径。
public class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if(candidates.length == 0){
            return result;
        }
        Arrays.sort(candidates);
        List<Integer> path = new ArrayList<Integer>();
        dfs(candidates,target,path,0,result);
        return result;
            
    }
    static void dfs(int[] candidates,int target,List<Integer> path,int index,List<List<Integer>> result){
        if(target == 0){
            //result.add(path);
            result.add(new ArrayList<Integer>(path));
            return;
        }
        int pre = -1;
        for(int i = index;i<candidates.length;i++){
            if(candidates[i] > target){
                break;
            }
            if(candidates[i] == pre){ //这里就避免了结果集里面出现同样的答案
                continue;
            }
            path.add(candidates[i]);
            dfs(candidates,target - candidates[i],path,i,result);
            path.remove(path.size()-1);
            pre = candidates[i];
        }     
    }    
}

 4. Combination Sum II

这题和上一题的区别在于这里不能重复使用一个元素。只要在dfs的时候多纪录一个下标就行，每次新的下标＋1
public class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if(candidates.length <= 0){
            return result;
        }
        Arrays.sort(candidates);
        List<Integer> path = new ArrayList<Integer>();
        dfs(candidates,target,result,path,0);
        return result;
    }
    
    private void dfs(int[] candidates, int target, List<List<Integer>> result, List<Integer> path, int index){
        if(target == 0){
            result.add(new ArrayList<Integer>(path));
            return;
        }
        if(index >= candidates.length){
            return;
        }
        int prev = -1;
        
        for(int i = index;i<candidates.length;i++){
            if(candidates[i] > target){
                break;
            }
            if( candidates[i] == prev ){
                continue;
            }
            path.add(candidates[i]);
            prev = candidates[i];
            dfs(candidates,target - candidates[i],result,path,i+1);
            path.remove(path.size() - 1);
        }
    }
}

 5. Combination Sum III

题意：从1到9的一个数组中挑出k个数，他们的和是n 求所有的解
解法：DFS，
需要的解：路径的长度等于k 且 他们的和等于n
回退情况：路径的长度为k但是和不为n
路径的和为n但是长度不为k
接下来的数字都大于n
其他情况继续深搜
public class Solution {
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        List<Integer> path = new ArrayList<Integer>();
        dfs(k,n,result,path,1);
        return result;
        
    }
    private void dfs(int k,int target,List<List<Integer>> result,List<Integer> path,int index){
        if(target == 0 && path.size() == k){
            result.add(new ArrayList<Integer>(path));
            return;
        }
        if(index > target){
            return;
        }
        if(target == 0 && path.size() != k){
            return;
        }
        if(path.size() == k && target != 0){
            return;
        }    
        for(int i = index;i<=9;i++){
            path.add(i);
            dfs(k,target - i,result,path,i+1);
            path.remove(path.size() -1 );
        }
        
    }
}

 6. Combination

这题目比较简单，就问从1到n中间挑出k个数字，求所有情况。直接DFS
所求的解：路径的长度等于k 就退出
否则继续深搜
public class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        List<Integer> path = new ArrayList<Integer>();
        dfs(n,k,path,result,1);
        return result;
    }
    private void dfs(int n,int k,List<Integer> path,List<List<Integer>> result,int index){
        if(path.size() == k){
            result.add(new ArrayList<Integer>(path));
            return;
        }
        
        for(int i = index;i<=n;i++){
            path.add(i);
            dfs(n,k,path,result,i+1);
            path.remove(path.size()-1);
        }
    }
}

 7. Permutations

题意：找到一个数组的全排列
解法：DFS的时候要注意每个元素只能出现一次。
public class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        List<Integer> path = new ArrayList<Integer>();
        Arrays.sort(nums);
        dfs(nums,result,path);
        return result;
    }
    
    private void dfs(int[] nums,List<List<Integer>> result,List<Integer> path){
        if(path.size() == nums.length){
            result.add(new ArrayList<Integer>(path));
            return;
        }
        for(int i = 0;i<nums.length;i++){
            if(path.contains(nums[i])){ //控制每个元素只出现一次
                continue;
            }
            path.add(nums[i]);
            dfs(nums,result,path);
            path.remove(path.size() -1);
        }
    }
}

 8. Permutations II

这题相比于上面的 Permutations 更Tricky一点。由于允许数组中的内容重复。所以我们不能像上面一样用path.contains()来判断。
我最初的想法是把当前循环的数字nums[i]先另外开个int保留其内容，然后在添加进Path之后把nums[i]设为-1,并且for循环里加一个条件判断，如果nums[i] == -1 则 continue 然而这里的数组元素是整个int范围，所以标记为-1或者其他数字会有问题。所以只能另外引入一个boolean数组来标记当前的状态。
P.S. for循环下的条件判断的||后面的判断是一个优化，没有这个的话leetcode报TLE, 这里的作用是去除重复的判断。比如数组{1,1,2} 当我们已经处理完第一个1的时候，第二个1其实可以跳过，因为结果是一样的。
public class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        List<Integer> path = new ArrayList<Integer>();
        Arrays.sort(nums);
        boolean[] visited  = new boolean[nums.length];
        Arrays.fill(visited,false);
        dfs(nums,result,path,visited);
        return result;
    }
    private void dfs(int[] nums,List<List<Integer>> result,List<Integer> path,boolean[] visited){
        if(path.size() == nums.length){
            result.add(new ArrayList<Integer>(path));
            return;
        }
        for(int i = 0;i<nums.length;i++){
            if(visited[i] == true || (i > 0 && visited[i-1]==true && nums[i] == nums[i-1] ) ) {
                continue;
            }
            visited[i] = true;
            path.add(nums[i]);
            dfs(nums,result,path,visited);
            path.remove(path.size()-1);
            visited[i] = false;
        }
    }
}

Comments

Post a Comment

Popular posts from this blog

Malware Report: iauzzy.exe

-
Image
Malware report of iauzzy.exe Summary This malware will create a file named ‘qqt.exe’ under the %WinDir%. This is the exact malicious executable file. qqt.exe is able to communicate to the ‘Command & Control’ server via IRC. The controller behind is able to execute any code; reboot the infected machine; clean the malware itself, etc.
Read more

Malware Report: withme.exe

-
Image
Malware Report withme.exe Summary This Withme.exe will drop a executable file ‘A-1980682553.exe’ to the location %AppData%. Also It will add itself to runonce registry. This is the exact malware. It’s able to communicate with C2 server, which domain is ‘sexwithme.info’ wia port 6667.
Read more

根因分析之iDice 文章复现

-
Image
1 Abstract  原文 给的场景是对于大规模集群的运维，当一条issue被上报的时候，通常会带上一些attribute，比如时间，软件版本，所处的国家，城市，具体在哪个机房，浏览器，操作系统等等。 在平时的时候，每天的上报的issue数量应该是差不多的，但有些时候，报错数量会突然上升，对于运维人员定位到问题所在往往很花时间。背后的问题可能是某个attribute或者某几个attributes的组合，文章称为effective combination。 这里通过三个步骤来从所有的attribute combination中找到最后可能引发报错激增的effective combination。 2 Challenge 想要找到所有effective combination的最暴力的做法就是，枚举所有attribute combination，然后以某种方式来衡量它对于总体issue激增的关系。 这里主要的问题在于搜索空间过大，本文最大的创新在于对搜索空间的剪枝。如果一共有m个attribute，那一共的组合方式就是(2^m - 1)种 3 Approach 文章把整个流程主要分成三个步骤（用做剪枝）和一个结果排序 Impact based Pruning: 基于影响的用户量做剪枝（不含时间信息） Change Detection based Pruning: 基于时间线上的突变来剪枝（时间序列处理） Isolation Power based Pruning: 计算一个类似信息熵增益的值来判断这个attribute combination的区分度 Result Ranking: 计算这个attribute combination对于全局的显著性 3.1 Impact based Pruning 对于一个effective combination而言，它必须影响足够多的用户。所以这里定一个threshold来过滤掉一些不可能的参数组合。（排除时间这个维度） 这里的目的是 寻找closed frequent itemsets，文章里的没有对算法进行详细描述，就说用BFS-based closed itemset mining algorithm。 在复现的时候，我先用了现成的找 frequent itemset 的算法（ Apriori /FPMax/ FPGrowt
Read more