督促自己——Java演算法題四道（某扣）——深度優先搜索、回溯演算法

督促自己——Java演算法題四道——深度優先搜索、回溯演算法

第一題：——回溯演算法
給你一個字串 s，請你將 s 分割成一些子串，使每個子串都是 回文串 ，回傳 s 所有可能的分割方案，
回文串 是正著讀和反著讀都一樣的字串，
示例 1：
輸入：s = “aab”
輸出：[[“a”,“a”,“b”],[“aa”,“b”]]
示例 2：
輸入：s = “a”
輸出：[[“a”]]
基本思路：
針對不同路徑，對每條路徑分別判斷，當本條路徑走完，回溯，走另一條路，總而言之，遞回就完事了，
例如a a b、aa b就是不同的兩條路徑，不斷遞回縮短路徑，就是這道題的做法，

class Solution {
    List<List<String>>list=new ArrayList<>();
    public List<List<String>> partition(String s) {
        List<String>l=new ArrayList<>();
        part(s,l);
        return list;
    }
    public void part(String s,List<String>l){
        if(s.length()==0){//一條路徑以便歷完
            if(!l.isEmpty()){
                list.add(new ArrayList<>(l));
            }
            return;
        }
        for(int j=0;j<s.length();++j){
            String str=s.substring(0,j+1);
            if(trueOrFalse(s,0,j)){
                l.add(str);//是回文子串就入順序表
                part(s.substring(j+1,s.length()),l);
                if(!l.isEmpty()){
                   l.remove(l.size()-1);//表示當前這個回文子串已經完成使命，出順序表，回溯
                }
            }
        }
    }
    public boolean trueOrFalse(String s,int start,int end){
         if(start>end||s==null){
            return false;
        }
        while(start<end&&s.charAt(start)==s.charAt(end)){
            start++;
            end--;
        }
        if(start>=end){
            return true;
        }else{
            return false;
        }
    }
}

第二題：——回溯演算法
一個 「開心字串」定義為：
僅包含小寫字母 [‘a’, ‘b’, ‘c’].
對所有在 1 到 s.length - 1 之間的 i ，滿足 s[i] != s[i + 1] （字串的下標從 1 開始），
比方說，字串 “abc”，“ac”，“b” 和 “abcbabcbcb” 都是開心字串，但是 “aa”，“baa” 和 “ababbc” 都不是開心字串，
給你兩個整數 n 和 k ，你需要將長度為 n 的所有開心字串按字典序排序，
請你回傳排序后的第 k 個開心字串，如果長度為 n 的開心字串少于 k 個，那么請你回傳 空字串 ，
示例 1：
輸入：n = 1, k = 3
輸出：“c”
解釋：串列 [“a”, “b”, “c”] 包含了所有長度為 1 的開心字串，按照字典序排序后第三個字串為 “c” ，
示例 2：
輸入：n = 1, k = 4
輸出：""
解釋：長度為 1 的開心字串只有 3 個，
示例 3：
輸入：n = 3, k = 9
輸出：“cab”
解釋：長度為 3 的開心字串總共有 12 個 [“aba”, “abc”, “aca”, “acb”, “bab”, “bac”, “bca”, “bcb”, “cab”, “cac”, “cba”, “cbc”] ，第 9 個字串為 “cab”
基本思路：
分別用a、b、c做頭，連接到定義的一個臨時字串變數上，當長度達到要求就用全域的一個順序表保存，否則遞回，但要注意滿足（ s[i] != s[i + 1] （字串的下標從 1 開始）），以及遞回結束條件：就是子串長度達到要求就結束，return回傳，每一個字母做完頭就要從臨時字串變數中移除，回溯，遞回下一個新頭，

class Solution {
    List<String>list=new ArrayList<>();
    public String getHappyString(int n, int k) {
         getHappy(new StringBuilder(""),n);
        if(k>list.size()){
            return "";
        }
        return list.get(k-1);
    }
    public void getHappy(StringBuilder s,int n){
        if(s.length()==n){
            list.add(s.toString());
            return;
        }
        for(char x='a';x<='c';++x){
           if(s.length()==0||s.charAt(s.length()-1)!=x){
               s.append(x);
               getHappy(s,n);
                s.deleteCharAt(s.length()-1);
           }
        }
    }
}

第三題：——深度優先搜索
讓我們一起來玩掃雷游戲！
給定一個代表游戲板的二維字符矩陣， ‘M’ 代表一個未挖出的地雷，‘E’ 代表一個未挖出的空方塊，‘B’ 代表沒有相鄰（上，下，左，右，和所有4個對角線）地雷的已挖出的空白方塊，數字（‘1’ 到 ‘8’）表示有多少地雷與這塊已挖出的方塊相鄰，‘X’ 則表示一個已挖出的地雷，
現在給出在所有未挖出的方塊中（‘M’或者’E’）的下一個點擊位置（行和列索引），根據以下規則，回傳相應位置被點擊后對應的面板：
如果一個地雷（‘M’）被挖出，游戲就結束了- 把它改為 ‘X’，
如果一個沒有相鄰地雷的空方塊（‘E’）被挖出，修改它為（‘B’），并且所有和其相鄰的未挖出方塊都應該被遞回地揭露，
如果一個至少與一個地雷相鄰的空方塊（‘E’）被挖出，修改它為數字（‘1’到’8’），表示相鄰地雷的數量，
如果在此次點擊中，若無更多方塊可被揭露，則回傳面板，
示例 1：
輸入:
[[‘E’, ‘E’, ‘E’, ‘E’, ‘E’],
[‘E’, ‘E’, ‘M’, ‘E’, ‘E’],
[‘E’, ‘E’, ‘E’, ‘E’, ‘E’],
[‘E’, ‘E’, ‘E’, ‘E’, ‘E’]]
Click : [3,0]
輸出:
[[‘B’, ‘1’, ‘E’, ‘1’, ‘B’],
[‘B’, ‘1’, ‘M’, ‘1’, ‘B’],
[‘B’, ‘1’, ‘1’, ‘1’, ‘B’],
[‘B’, ‘B’, ‘B’, ‘B’, ‘B’]]
基本思路：
判斷當前點擊位置的值，針對不同值有不同操作：
雷：M->X（排雷，并結束）
未翻開：E
翻開：數字1~8或者B，數字代表周圍8格內雷的個數，B代表沒雷，
回圈判斷當前位置周圍是否有雷，有就計數，最終看計數是否為零，零->B,非零->數字;
之后遞回，對8個方向分別做出判斷，最后回傳即可，

class Solution {
    int[][]index=new int[][]{{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
    public char[][] updateBoard(char[][] board, int[] click) {
       int x=click[0];
       int y=click[1];
       if(x<0||x>=board.length||y<0||y>board[0].length){
           return board;
       }else if(board[x][y]=='M'){
           board[x][y]='X';
           return board;
       }else if(board[x][y]=='E'){
           int count=0;
           for(int i=0;i<index.length;++i){
             int nx=x+index[i][0];
             int ny=y+index[i][1];
             if(nx>=0&&nx<board.length&&ny>=0&&ny<board[0].length){
                 if(board[nx][ny]=='M'){
                     count++;
                 }
             }
           }
           if(count==0){
               board[x][y]='B';
           }else{
               board[x][y]=(char)(count+'0');
               return board;
           }
               for(int i=0;i<index.length;++i){
                  int nx=x+index[i][0];
                  int ny=y+index[i][1];
                  if(nx>=0&&nx<board.length&&ny>=0&&ny<board[0].length){
                    click[0]=nx;
                    click[1]=ny;
                    if(board[nx][ny]!='M'&&board[nx][ny]=='E'){
                        updateBoard(board,click);
                    }
                  }
               }
           return board;
       }else{
           return board;
       }
    }
}

第四題：——深度優先搜索
給出二叉 搜索 樹的根節點，該樹的節點值各不相同，請你將其轉換為累加樹（Greater Sum Tree），使每個節點 node 的新值等于原樹中大于或等于 node.val 的值之和，
提醒一下，二叉搜索樹滿足下列約束條件：
節點的左子樹僅包含鍵 小于 節點鍵的節點，
節點的右子樹僅包含鍵 大于 節點鍵的節點，
左右子樹也必須是二叉搜索樹，

輸入：[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
輸出：[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]
基本思路：
依次遍歷右樹->中->左樹，利用變數記錄和即可.

class Solution {
    int sum=0;
    public TreeNode convertBST(TreeNode root) {
        if(root==null){
            return null;
        }
       convertBST(root.right);
       root.val+=sum;
       sum=root.val;
       convertBST(root.left);
       return root; 
    }
}

有三天左右沒更新編程題了，今天有點手生，但是要堅持呀！！！！！！