算法-DFS

记了点自己有问题的题目

LeetCode题

Word Break II

给一个str s和一个str[] dict,输出所有s可能被dict拼接的组合。例如

s = "catsanddog", dict = ["cat", "cats", "and", "sand", "dog"].

A solution is ["cats and dog", "cat sand dog"].

一开始我的想法是用DFS维护一个栈，再用Trie优化字符串检索。可惜这种方式会超时。看了别人的代码，就感觉自己宛如一个智障。

用刀在字符串中切一刀。左边是i个字符，右边是len-i个字符。

|=======前i个位置=======|
  
|----------|----------|
|1,2,....,i|i+1,..,len|
|----------|----------|

如果：左边是字典里的词，右边是可以wordbreak的，那么把左边的字符串加到右边算出来的List中，生成新的list返回。

边界条件：
1. 当输入字符串为空的时候，应该给出一个空解。这个很重要，否则这个递归是不能运行的。
2. 递归时i应该从1开始递归，因为我们要把这个问题分解为2个部分，如果你左边给0，那就是死循环。

记忆：
为了加快DFS的速度，我们应该添加记忆，也就是说，算过的字符串不要再重复计算。举例子：
apple n feng
app len feng
如果存在以上2种划分，那么feng这个字符串会被反复计算，在这里至少计算了2次。我们使用一个Hashmap把对应字符串的解记下来，这样就能避免重复的计算。 否则这一道题目会超时。


public List<String> wordBreak(String s, Set<String> wordDict) {
    return DFS(s, wordDict, new HashMap<String, LinkedList<String>>());
}       

// DFS function returns an array including all substrings derived from s.
List<String> DFS(String s, Set<String> wordDict, HashMap<String, LinkedList<String>>map) {
    if (map.containsKey(s)) 
        return map.get(s);
        
    LinkedList<String>res = new LinkedList<String>();     
    if (s.length() == 0) { // 给出一个空解
        res.add("");
        return res;
    }               
    for (String word : wordDict) {
        if (s.startsWith(word)) {//如果左边是字典里的词
            List<String>sublist = DFS(s.substring(word.length()), wordDict, map);//如果有返回值，就会加入res里
            for (String sub : sublist) 
                res.add(word + (sub.isEmpty() ? "" : " ") + sub);               
        }
    }       
    map.put(s, res);
    return res;
}

Palindrome Partitioning

给一个str，输出它所有的可能的回文子串。

For example, given s = "aab",Return

[
  ["aa","b"],
  ["a","a","b"]
]

这道题我借鉴了上一题的解法，

用刀在字符串中切一刀。左边是i个字符，右边是len-i个字符。

|=======前i个位置=======|
  
|----------|----------|
|1,2,....,i|i+1,..,len|
|----------|----------|

如果：左边是回文序列，那就先把左边的放着。先算右边。最后把左边的str加到右边list中的每个结果前，再返回即可。

记忆：
同时也保存了一个hash表，存储第i位置之后的所有回文组合方式。

class Solution {
    HashMap<Integer,List<List<String>>> map;
    boolean[][] ifPalindrome; //存储从i到j是否是回文序列
    //计算从i到j是否是回文序列
    private boolean[][] palindrome(char[] c){
        int n = c.length;
        boolean[][] ifPalindrome = new boolean[n][n];
        // i 从n开始下降
        // j 从i开始到n
        for( int i = n - 2; i >= 0 ; --i ){
            ifPalindrome[i][i] = true;
            for( int j = i+1 ; j < n ; ++j ){
                if( c[i] == c[j] ){
                    ifPalindrome[i][j] = j == i + 1 || j == i + 2 || ifPalindrome[i+1][j-1];
                }
            }
        }
        ifPalindrome[n-1][n-1] = true;
        return ifPalindrome;
    }
    //深度优先遍历
    private List<List<String>> dfs(char[] c,int start,int n){
        List<List<String>> thisResult = new LinkedList<>();
        if( start == n ) return thisResult;
        if( map.containsKey(start) )
            return map.get(start);

        StringBuilder strBuilder = new StringBuilder();
        for( int j = start  ; j < n ; ++j ){
            strBuilder.append(c[j]);
            // start ,....,j,.....,end
            //如果从start到j是回文序列
            if( ifPalindrome[start][j] ){
                String preString = strBuilder.toString();//start...j的str
                List<List<String>> afterResult = dfs(c,j+1,n);//从j+1到n的所有回文串组合
                if( afterResult.size() == 0 ){ // preString是末尾元素，且它本身就是回文序列
                        List<String> elementUnit = new LinkedList<>();
                        elementUnit.add(preString);
                        thisResult.add(elementUnit);
                        continue;
                }
                // preString是前缀，且它本身就是回文序列
                for( List<String> oneAfterResult : afterResult ){
                    List<String> unitResult = new LinkedList<>();
                    unitResult.add(preString);
                    for( String e : oneAfterResult ){
                        unitResult.add(e);
                    }
                    thisResult.add(unitResult);
                }
            }
        }
        map.put(start,thisResult);
        return thisResult;

    }
    //分割主函数
    public List<List<String>> partition(String s) {
        map = new HashMap<>();
        ifPalindrome = palindrome(s.toCharArray());
        List<List<String>> res =  dfs( s.toCharArray(), 0, s.length() );
        return res;

    }
}

Minesweeper

扫雷题

E : 没打开的地方
M : 没打开的雷
B : 打开了，周围没有雷
数字1-8 ： 打开了，周围有k个雷
X: 打开了的雷

规则：

1. 点击某点，如果此点为雷，那么将此点设为X，游戏结束
2. 否则，自动探测周围的8个点，如果某点周围没有雷，则继续深入探测；如果某点周围有雷，则标记雷个数

int[] dx = {1, 1,1, 0,0,-1,-1,-1};
    int[] dy = {1,-1,0,-1,1, 1,-1,0 };

    private void helper(char[][] board, int x, int y){
        if(x >= board.length || x < 0 || y >= board[x].length || y < 0) return;
        if(board[x][y] == 'M') return ; // 有雷
        if(board[x][y] == 'E') {
            board[x][y] = '0';
          // 探测周围有没有雷
            for (int i = 0; i < dx.length; ++i) {
                int x_neibor = x + dx[i], y_neibor = y + dy[i];
                if(x_neibor >= board.length || x_neibor < 0 || y_neibor >= board[x].length || y_neibor < 0) continue;
                if (board[x_neibor][y_neibor] == 'M') {board[x][y] += 1;}
            }
          // 对没有雷的地方继续递归探测
            if(board[x][y] == '0') {
                board[x][y] = 'B';
                for(int i = 0; i < dx.length; ++i){
                    helper(board, x + dx[i], y + dy[i] );
                }
            }
        }
    }
    public char[][] updateBoard(char[][] board, int[] click) {
        /** E : 没打开的空地
         *  M : 没打开的雷**/
        if(board[click[0]][click[1]] == 'M') board[click[0]][click[1]] = 'X';
        else helper(board, click[0],click[1]);
        return board;
    }

Remove Invalid Parentheses

删除尽量少的括号，使得一个字符串的括号符合要求

实在是没思路，到现在也没做上。先记一下套路吧

方法1，DFS

public List<String> removeInvalidParentheses(String s){
        // 分别是多余的左括号和多余的右括号
        int rmL = 0, rmR = 0;
        for(int i = 0; i < s.length(); ++i){
            if(s.charAt(i) == '('){
                ++rmL;
            }else if(s.charAt(i) == ')'){
                if(rmL > 0){ // 还有多余的左括号
                    --rmL;
                }else { // 没有多余的左括号了
                    ++rmR;
                }
            }
        }
        Set<String> res = new HashSet<>();
        dfs(s, 0, res, new StringBuilder(), rmL, rmR, 0);
        return new ArrayList<>(res);
    }
    private void dfs(String s, int i, Set<String> res, StringBuilder sb, int rmL, int rmR, int open){
        int len = sb.length();
        // rmL和rmR分别限制着最大的可变边界
        if(open < 0 || rmL < 0 || rmR < 0)return;
        if(i == s.length()){
            if(open == 0)res.contains(sb.toString());
            return;
        }
        char c = s.charAt(i);
        if(c == '('){
            dfs(s, i + 1, res, sb, rmL - 1,rmR, open); // 尝试去除（
            dfs(s, i + 1, res, sb.append('('), rmL, rmR, open - 1);//不去除
        }else if(c == ')'){
            dfs(s, i + 1, res, sb, rmL, rmR - 1, open);//尝试去除 ）
            dfs(s, i + 1, res, sb.append(')'), rmL, rmR, open - 1);//不去除
        }else {
            dfs(s, i + 1,res, sb.append(c),rmL, rmR, open);
        }
        sb.setLength(len); //重置sb
    }

方法2，套路

private void remove(String s, List<String> ans, int last_i, int last_j, char[] pair){
        for(int stack = 0, i = last_i; i < s.length(); ++i){
            if(s.charAt(i) == pair[0])++stack;
            if(s.charAt(i) == pair[1])--stack;
            //左括号多于右括号，那就继续循环
            if(stack > 0)continue;
            // 此时左括号少于右括号，一定是不合法的，那就尝试去除一个
            for(int j = last_j; j <= i; ++j){
                // j是右括号，且j的前一个不是右括号

                if(s.charAt(j) == pair[1] &&(j == last_j || s.charAt(j-1) != pair[1])){
                    remove(s.substring(0,j) + s.substring(j + 1), ans, i, j, pair);
                }
                return;
            }
            // 因为之前我们只考虑了删除右括号。那么现在反过来，考虑试一试删除左括号
            String reversed = new StringBuilder(s).reverse().toString();
            if (pair[0] == '(') // finished left to right
                remove(reversed, ans, 0, 0, new char[]{')', '('});
            else // finished right to left
                ans.add(reversed);
        }
    }

Decode String

给一个字符串3[a]2[bc] 。数字表示后面括号里的字符重复次数。求解压之后的字符串。

这道题第一遍没想明白，第二遍重写的时候才一气呵成。其实就是dfs，当遇到数字时，就将数字后面的东西视为一个新的str，递归下去，遇到] 就跳出。跳出时需要携带跳出时的结束idx，因此我用了一个Node包装起来

  以3[a2[c]]为例
  3 [ a 2 [ c d ] ]
  1 2 3 4 5 6 7 8 9
  idx = 0, 遇到3 --> a2[cd]] , 跳过[
  idx = 2, 遇到2 --> cd]] ,将c、d分别加入sb,然后遇到了](idx = 8)，就跳出，返回到上层
  idx = idxEnd = 9, 且将`cd`重复2次变为cdcd，此时遇到](idx = 9)，再次跳出，返回上层
  idx = idxEnd = 10, 且将cdcd加入到sb中，此时sb变成acbcd，跳出，返回上层
  再将acbcd重复3次

class Node{
       String str;
       int endIdx;
       Node(String str, int endIdx){
           this.str = str;
           this.endIdx = endIdx;
       }
   }
   private boolean isLetter(char c){
       return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z');
   }
   private boolean isNum(char c){
       return c >='0' && c <= '9';
   }
   private Node helper(String s, int idx){
       StringBuilder sb = new StringBuilder();
       while (idx < s.length()){
           while (idx < s.length() && isLetter(s.charAt(idx))){
               sb.append(s.charAt(idx++));
           }
           int numStart = idx;
           while(idx < s.length() && isNum(s.charAt(idx))){++idx;}
           int repeat = 0;
           if(idx > numStart){
               repeat = Integer.valueOf(s.substring(numStart, idx));
               Node next = helper(s, idx + 1);
               while (repeat-- > 0){sb.append(next.str);}
               idx = next.endIdx;
           }
           if(idx < s.length() && s.charAt(idx) == ']'){
               return new Node(sb.toString(), idx + 1);
           }
       }
       return new Node(sb.toString(), idx + 1);
   }
   public String decodeString(String s) {
       return helper(s,0).str;
   }

其实再思考了一下，idx完全可以设为全局变量！

private boolean isLetter(char c){
        return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z');
    }
    private boolean isNum(char c){
        return c >='0' && c <= '9';
    }
    int idx = 0;
    private String helper(String s){
        StringBuilder sb = new StringBuilder();
        while (idx < s.length()){
            while (idx < s.length() && isLetter(s.charAt(idx))){
                sb.append(s.charAt(idx++));
            }
            int numStart = idx;
            while(idx < s.length() && isNum(s.charAt(idx))){++idx;}
            int repeat = 0;
            if(idx > numStart){
                repeat = Integer.valueOf(s.substring(numStart, idx));
                ++idx; // 跳过[符号
                String next = helper(s);
                while (repeat-- > 0){sb.append(next);}
            }
            if(idx < s.length() && s.charAt(idx) == ']'){
                ++idx;//跳过]符号
                break;
            }
        }
        return sb.toString();
    }
    public String decodeString(String s) {
        return helper(s);
    }

Pacific Atlantic Water Flow

给一个矩阵。左和上是太平洋，右和下是大西洋。求中间哪些点的水可以同时流到两个洋

思路：反向思考。从边界出发，寻找递增的方向。所有递增的都是能流到的。

private void setVisited(int[][] matrix,int i, int j, int val ){
    if(i >= matrix.length || i < 0 || j >= matrix[i].length || j < 0) return;
    if(visited[i][j] != 0 && visited[i][j] != val){
        result.add(new int[]{i,j});
        visited[i][j] = 3;
    }else{
        visited[i][j] = val;
    }
    //System.out.println(i + "\t"  + j + "\t" + visited[i][j] + val);
}
private void dfs(int[][] matrix, int i, int j, int last, int val){
    if(i >= matrix.length || i < 0 || j >= matrix[i].length || j < 0) return;
    if(matrix[i][j] < last || visited[i][j] == val || visited[i][j] == 3) return;
    setVisited(matrix,i, j, val );
    // 继续探测周围的点
    for(int k = 0; k < 4; ++k){
        dfs(matrix, i + di[k], j + dj[k], matrix[i][j], val);
    }
}
List<int[]> result = new LinkedList<>();
int[][] visited;
int[] di = {1,0,-1,0};
int[] dj = {0,1,0,-1};
public List<int[]> pacificAtlantic(int[][] matrix) {
    if(matrix.length == 0 || matrix[0].length == 0)return result;
    visited = new int[matrix.length][matrix[0].length];
    // pacific : i == 0 or j == 0
    // atlantic : i == matrix.length - 1 or j == matrix[i].length - 1
    for(int j = 0; j < matrix[0].length; ++j){
        dfs(matrix, 0, j, matrix[0][j], 1);// pacific
    }
    for(int i = 0; i < matrix.length; ++i){
        dfs(matrix, i, 0,  matrix[i][0], 1);// pacific
    }
    for(int j = 0; j < matrix[0].length; ++j){
        dfs(matrix, matrix.length - 1, j,matrix[matrix.length - 1][j], 2);// atlantic
    }
    for(int i = 0; i < matrix.length; ++i){
        dfs(matrix, i, matrix[i].length - 1,  matrix[i][matrix[i].length - 1], 2);// atlantic
    }
    return result;
}

消除游戏集锦

Strange Printer

有一种打印方式，每轮只打印元素相同的字符串，打印时还会覆盖原来的字符串。给一个字符串，求打印这个字符串所需要最少的轮数。

我好像理解错题意了。看完了答案，想哭。回头再战。

Zuma Game

直到三刷才做出来的题。

给两个字符串，字符串board表示现在的球，hand表示手里拿的球。可以把手里的某个颜色球插入到board，使得插入位置相邻的有3个或以上的球颜色一样，就会消除颜色一样的球。

求能消除所有球时，插入的最小次数。

HashMap<Character, Integer> hand_hash;
    private int findLongestSame(String board, int start){
        int end = start +1;
        while (end < board.length() && board.charAt(start) == board.charAt(end)){
            ++end;
        }
        int counter = end - start;
        return counter;

    }
    // 求board最少插入次数
    private int helper(String board){
        if(board.length() == 0) return 0;
        int used = 1000;
        for(int i = 0; i < board.length(); ){
            //从i开始寻找最长的子数组
            int counter = findLongestSame(board, i);
            if(counter>= 3){ // 从i开始可以消除counter个，那就先消除了！
                return helper(board.substring(0,i) + board.substring(i+counter));
            }
            // 否则，看看手里球够不够，尝试消除试一试
            if(hand_hash.getOrDefault(board.charAt(i), 0) + counter >= 3){
                int used_curr = 3 - counter;
                hand_hash.replace(board.charAt(i), hand_hash.get(board.charAt(i)) - used_curr);
                used = Math.min(used,
                        used_curr + helper(board.substring(0,i) + board.substring(i + counter)));
                hand_hash.replace(board.charAt(i), hand_hash.get(board.charAt(i)) + used_curr);
            }
            i = i + counter;
        }
        return used;
    }
    public int findMinStep(String board, String hand) {
        hand_hash = new HashMap<>(hand.length());
        for(char c : hand.toCharArray()){
            hand_hash.put(c, hand_hash.getOrDefault(c, 0) + 1);
        }
        int result = helper(board);
        return result == 1000 ? -1 : result;
    }

Remove Boxes leetcode

其它递归相关

Lexicographical Numbers

将[1,n]之间的数字按照字典顺序加入到一个list里

我的思路：递归

int n;
    private List<Integer> helper(int startNum){
        List<Integer> result = new ArrayList<>();
        if(startNum > n) return result;
        for(int i = 0; i < 10; ++i){
            if(startNum + i > n || (startNum == 1 && i == 9)) break;
            result.add(startNum + i);
            result.addAll(helper(10*(startNum + i)));
        }
        return result;
    }
    public List<Integer> lexicalOrder(int n) {
        this.n = n;
        List<Integer> result = helper(1);
        return result;
    }

别人的较快的方案：

public List<Integer> lexicalOrder(int n) {
        List<Integer> re = new LinkedList<>();
        int cur = 1;
        while (re.size() < n) {
            re.add(cur);
            if ( cur*10 <= n)
                cur*=10;
            else if ( cur % 10 != 9 && cur+1 <= n)
                cur+=1;
            else{
                while (cur/10 % 10 == 9)
                    cur/=10;
                cur = cur/10+1;
            }
            
        }
        return re;
    }