丝袜美女操逼,骚逼丁香五月,亚洲蜜臀99

https://leetcode-cn.com/tag/backtracking/

10. 正則表達式匹配難度困難（看了題解理解的，動態(tài)規(guī)劃）

17. 電話號碼的字母組合難度中等

22. 括號生成難度中等

37. 解數(shù)獨難度困難(不會做)

39. 組合總和難度中等 [?]

40. 組合總和 II難度中等 [?]

44. 通配符匹配難度困難（看了題解理解的，動態(tài)規(guī)劃）

46. 全排列難度中等 [?]

47. 全排列 II難度中等 [?]

51. N皇后難度困難

回溯代碼的框架

result = []
def backtrack(路徑, 選擇列表):
    if 滿足結(jié)束條件:
        result.add(路徑)
        return
    
    for 選擇 in 選擇列表:
        做選擇
        backtrack(路徑, 選擇列表)
        撤銷選擇

10. 正則表達式匹配難度困難

給你一個字符串 s 和一個字符規(guī)律 p，請你來實現(xiàn)一個支持 '.' 和 '*' 的正則表達式匹配。
'.'匹配任意單個字符
'*' 匹配零個或多個前面的那一個元素
所謂匹配，是要涵蓋整個字符串 s的，而不是部分字符串。
說明:
s 可能為空，且只包含從 a-z 的小寫字母。
p 可能為空，且只包含從 a-z 的小寫字母，以及字符 . 和 *。

思路：動態(tài)規(guī)劃

class Solution {//執(zhí)行用時 :3 ms, 在所有 Java 提交中擊敗了90.91%的用戶
    public boolean isMatch(String s, String p) {
        //dp[i][j] 表示 s 的前 i 個是否能被 p 的前 j 個匹配
        boolean[][] dp = new boolean[s.length()+1][p.length()+1];
        dp[0][0] = true;
        //初始化
        for(int j=1;j<p.length()+1;j++){
            if(j == 1) //比如p = b， 只有一個元素，這時候一定是false
                dp[0][j] = false;
            if(p.charAt(j-1) == '*' && dp[0][j-2])//比如p = b*，這時看dp[0][j-2]是否為true
                dp[0][j] = true;
        }

        for(int i=1;i<=s.length();i++){
            for(int j=1;j<=p.length();j++){
                //最簡單的情況，字符相等或者p的字符是‘.'
                if(s.charAt(i-1) == p.charAt(j-1) || p.charAt(j-1) == '.')
                    dp[i][j] = dp[i-1][j-1];
                    
                else if(p.charAt(j-1) == '*'){
                    //如果p的*前邊的字符和s當前字符相等或者p的字符是‘.'
                    //三種可能
                    //匹配0個，比如aa aaa*  dp[i][j]=dp[i][j-2]
                    //匹配1個，比如aab aab*  dp[i][j]=dp[i][j-1]
                    //匹配多個，比如aabb aab*  就看aab 和aab*是否能匹配上，即dp[i][j]=dp[i-1][j]
                    if(p.charAt(j-2) == s.charAt(i-1) || p.charAt(j-2)=='.'){
                        dp[i][j] = dp[i-1][j] || dp[i][j-1] || dp[i][j-2];
                    }
                    //如果p的*前邊的字符和s當前字符不相等或者p的字符不是‘.'
                    //那就把*和*前邊一個字符都不要了
                    else{
                        dp[i][j] = dp[i][j-2];
                    }
                }else{
                    dp[i][j] = false;
                }
            }
        }
    return dp[s.length()][p.length()];
    }
}

17. 電話號碼的字母組合難度中等

給定一個僅包含數(shù)字 2-9 的字符串，返回所有它能表示的字母組合。
給出數(shù)字到字母的映射如下（與電話按鍵相同）。注意 1 不對應(yīng)任何字母。

示例:
輸入："23"
輸出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

說明:
盡管上面的答案是按字典序排列的，但是你可以任意選擇答案輸出的順序。

class Solution {
    public List<String> letterCombinations(String digits) {
        if(digits == null || digits.length() == 0)
            return new ArrayList<>();
        List<String> res = new ArrayList<>();
        if(digits.length() != 0)
            backtrack(res,"",digits);
        return res;
    }

    public void backtrack(List<String> res, String combination, String next_digit){
        HashMap<String,String> map = new HashMap<>();
        map.put("2","abc");
        map.put("3","def");
        map.put("4","ghi");
        map.put("5","jkl");
        map.put("6","mno");
        map.put("7","pqrs");
        map.put("8","tuv");
        map.put("9","wxyz");
        if(next_digit.length() == 0){
            res.add(combination);
        }else{
            String digit = next_digit.substring(0,1);
            String letters = map.get(digit);
            for(int i = 0; i < letters.length(); i++){
                String letter = letters.substring(i, i+1);
                backtrack(res, combination + letter, next_digit.substring(1));
            }
        }
    }
}

22. 括號生成難度中等

數(shù)字 n 代表生成括號的對數(shù)，請你設(shè)計一個函數(shù)，用于能夠生成所有可能的并且 **有效的 **括號組合。
示例：
輸入：n = 3
輸出：[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]

思路：DFS不用回溯

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        if(n == 0)  
            return new ArrayList<>();
        dfs(res, n, n, "");
        return res;

    }

    /**
     * @param res    結(jié)果集
     * @param left   左括號還有幾個可以使用
     * @param right  右括號還有幾個可以使用
     * @param curStr 當前遞歸得到的結(jié)果
     */
    public void dfs(List<String> res, int left, int right, String curStr){
        if(left == 0 && right == 0)
            res.add(curStr);
        if(left > right)    return;//這一步剛開始沒考慮到，是剪枝
        if(left > 0){
             dfs(res, left - 1, right, curStr + "(");
        }
        if(right > 0){
            dfs(res, left, right - 1, curStr + ")");
        }
    }
}

37. 解數(shù)獨難度困難

編寫一個程序，通過已填充的空格來解決數(shù)獨問題。
一個數(shù)獨的解法需遵循如下規(guī)則：
（1）數(shù)字 1-9 在每一行只能出現(xiàn)一次。
（2）數(shù)字 1-9 在每一列只能出現(xiàn)一次。
（3）數(shù)字 1-9 在每一個以粗實線分隔的 3x3 宮內(nèi)只能出現(xiàn)一次。
空白格用 '.' 表示。

給定輸入

輸出結(jié)果

答案被標成紅色。
Note:

給定的數(shù)獨序列只包含數(shù)字 1-9 和字符 '.' 。

你可以假設(shè)給定的數(shù)獨只有唯一解。

給定數(shù)獨永遠是 9x9 形式的。

思路：回溯

https://leetcode-cn.com/problems/sudoku-solver/solution/hui-su-fa-jie-shu-du-by-i_use_python/自己對題解中部分還是不理解

class Solution {
    public void solveSudoku(char[][] board) {
        //三個布爾數(shù)組，表示在每行，每列，每個格子中，這個數(shù)字是否使用過
        boolean[][] rowUsed = new boolean[9][10];
        boolean[][] colUsed = new boolean[9][10];
        boolean[][][] boxUsed = new boolean[3][3][10];

        //初始化三個布爾數(shù)組，遍歷board，表示在每行，每列，每個格子中，這個數(shù)字被使用過了
        for(int row = 0; row < 9; row++){
            for(int col = 0; col < 9; col++){
                int num = board[row][col] - '0';
                if(num >= 1 && num <= 9){
                    rowUsed[row][num] = true;
                    colUsed[col][num] = true;
                    boxUsed[row/3][col/3][num] = true;
                }
            }
        }
        //填充數(shù)組
        solveSudokuHelper(board, rowUsed, colUsed, boxUsed, 0, 0);
    }

    public boolean solveSudokuHelper(char[][] board, boolean[][] rowUsed, boolean[][] colUsed,boolean[][][] boxUsed, int row, int col){
        // 邊界校驗, 如果已經(jīng)填充完成, 返回true, 表示一切結(jié)束
        if(col == 9){
            col = 0;
            row++;
            if(row == 9){
                return true;
            }
        }

        if(board[row][col] == '.'){
            for(int num = 1; num <= 9; num++){
                boolean canUsed = !(rowUsed[row][num] || colUsed[col][num] || boxUsed[row/3][col/3][num]);
                if(canUsed){
                    rowUsed[row][num] = true;
                    colUsed[col][num] = true;
                    boxUsed[row/3][col/3][num] = true;
                    board[row][col] = (char)('0' + num);
                    if(solveSudokuHelper(board, rowUsed, colUsed, boxUsed, row, col + 1)){
                        return true;
                    }
                    board[row][col] = '.';
                    
                    rowUsed[row][num] = false;
                    colUsed[col][num] = false;
                    boxUsed[row/3][col/3][num] = false;
                }
            }
        }else{
            return solveSudokuHelper(board, rowUsed, colUsed, boxUsed, row, col + 1);
        }
        return false;
    }
            
}

39. 組合總和難度中等

給定一個無重復(fù)元素的數(shù)組 candidates 和一個目標數(shù) target ，找出 candidates 中所有可以使數(shù)字和為 target 的組合。candidates 中的數(shù)字可以無限制重復(fù)被選取。
說明：
所有數(shù)字（包括 target）都是正整數(shù)。
解集不能包含重復(fù)的組合。
示例 1：
輸入：candidates = [2,3,6,7], target = 7,
所求解集為：
[
[7],
[2,2,3]
]

思路：回溯

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();//存放結(jié)果集
        backtrack(res, candidates, target, 0, new ArrayList<>());
        return res;
    }

    public void backtrack(List<List<Integer>> res, int[] candidates, int target,int start, List<Integer> cur){
        if(target == 0)
            res.add(new ArrayList<>(cur));
        
        for(int i = start; i < candidates.length; i++){
            if(target < candidates[i])  continue;
            List<Integer> list = new ArrayList<>(cur);
            list.add(candidates[i]);
            backtrack(res, candidates, target - candidates[i], i, list);

        }
    }
}

40. 組合總和 II難度中等339

給定一個數(shù)組 candidates 和一個目標數(shù) target ，找出 candidates 中所有可以使數(shù)字和為 target 的組合。
candidates 中的每個數(shù)字在每個組合中只能使用一次。
說明：
所有數(shù)字（包括目標數(shù)）都是正整數(shù)。
解集不能包含重復(fù)的組合。
示例 1:
輸入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集為:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]

思路：回溯

class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();//存放結(jié)果集
        Arrays.sort(candidates);
        backtrack(res, candidates, target, 0, new ArrayList<>());
        return res;
    }

    public void backtrack(List<List<Integer>> res, int[] candidates, int target,int start, List<Integer> cur){
        if(target == 0)
            res.add(new ArrayList<>(cur));
        
        for(int i = start; i < candidates.length; i++){
            if(target < candidates[i])  continue;
             // 小剪枝，去除重復(fù)元素
            if (i > start && candidates[i] == candidates[i - 1]) {
                continue;
            }
            List<Integer> list = new ArrayList<>(cur);
            list.add(candidates[i]);
            backtrack(res, candidates, target - candidates[i], i + 1, list);//i+1避免重復(fù)選取數(shù)組元素

        }
    }
}

44. 通配符匹配難度困難

給定一個字符串 (s) 和一個字符模式 (p) ，實現(xiàn)一個支持 '?' 和 '*' 的通配符匹配。
'?'可以匹配任何單個字符。
'*' 可以匹配任意字符串（包括空字符串）。
兩個字符串完全匹配才算匹配成功。
說明:
（1）s 可能為空，且只包含從 a-z 的小寫字母。
（2）p 可能為空，且只包含從 a-z 的小寫字母，以及字符 ? 和 *。
示例 1:
輸入:
s = "aa"
p = "a"
輸出: false，解釋: "a" 無法匹配 "aa" 整個字符串。
示例 2:
輸入:
s = "aa"
p = "*"
輸出: true，解釋:"*"可以匹配任意字符串。
示例 3:
輸入:
s = "acdcb"
p = "a*c?b"
輸出: false

思路：動態(tài)規(guī)劃

class Solution {//執(zhí)行用時 :36 ms, 在所有 Java 提交中擊敗了48.23%的用戶
    public boolean isMatch(String s, String p) {
        int slen = s.length();
        int plen = p.length();
        //dp[i][j] : 表示 s 的前 i 個字符和 p 的前 j 個字符是否匹配
        boolean[][] dp = new boolean[slen+1][plen+1];
        //初始化
        dp[0][0] = true;
        for(int j=1;j<=plen;j++){
            if(p.charAt(j-1) == '*' && dp[0][j-1])
                dp[0][j] = true;//s 為空，與 p 匹配
        }


        for(int i=1;i<=slen;i++){
            for(int j=1;j<=plen;j++){
                if(s.charAt(i-1) == p.charAt(j-1) || p.charAt(j-1) == '?')
                    dp[i][j] = dp[i-1][j-1];
                else if(p.charAt(j-1) == '*')  
                    //dp[i][j - 1] 表示 * 代表的是空字符，例如 ab, ab*
                    //dp[i - 1][j] 表示 * 代表的是非空字符，例如 abcd, ab*
                    dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
            }
        }
    return dp[slen][plen];
    }
}

46. 全排列難度中等

給定一個 沒有重復(fù) 數(shù)字的序列，返回其所有可能的全排列。
示例:
輸入: [1,2,3]
輸出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]

思路：回溯

class Solution {
   public List<List<Integer>> permute(int[] nums) {
       int len = nums.length;
       List<List<Integer>> res = new ArrayList<>();
       if(len == 0)    return res;
       boolean[] used = new boolean[len];
       List<Integer> path = new ArrayList<>();
       backtrack(res, nums, len, 0, used, path);
       return res;
   }

   public void backtrack(List<List<Integer>> res, int[] nums, int len, 
   int depth, boolean[] used, List<Integer> path){
       if(depth == len)
           res.add(new ArrayList<>(path));
       for(int i = 0; i < len; i++){
           if(!used[i]){
               path.add(nums[i]);
               used[i] = true;
               backtrack(res, nums, len, depth + 1, used, path);
               //狀態(tài)重置，回溯
               used[i] = false;
               path.remove(path.size() - 1);
           }
       }
       
   }
}

47. 全排列 II難度中等

給定一個可包含重復(fù)數(shù)字的序列，返回所有不重復(fù)的全排列。
示例:
輸入: [1,1,2]
輸出:
[
[1,1,2],
[1,2,1],
[2,1,1]
]

思路：回溯

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        int len = nums.length;
       List<List<Integer>> res = new ArrayList<>();
       if(len == 0)    return res;
       Arrays.sort(nums);//相比上題
       boolean[] used = new boolean[len];
       List<Integer> path = new ArrayList<>();
       backtrack(res, nums, len, 0, used, path);
       return res;
   }

   public void backtrack(List<List<Integer>> res, int[] nums, int len, 
   int depth, boolean[] used, List<Integer> path){
        if(depth == len)
           res.add(new ArrayList<>(path));
        for(int i = 0; i < len; i++){
            if (used[i]) {
                continue;
            }
            //剪枝
            if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
                continue;
            }

            path.add(nums[i]);
            used[i] = true;
            backtrack(res, nums, len, depth + 1, used, path);
            //狀態(tài)重置，回溯
            used[i] = false;
            path.remove(path.size() - 1);
           }
    }       
}

51. N皇后難度困難

n 皇后問題研究的是如何將 n 個皇后放置在 n×n 的棋盤上，并且使皇后彼此之間不能相互攻擊。

上圖為 8 皇后問題的一種解法。
給定一個整數(shù) n，返回所有不同的 n 皇后問題的解決方案。
每一種解法包含一個明確的 n 皇后問題的棋子放置方案，該方案中 'Q' 和 '.' 分別代表了皇后和空位。

提示：
皇后，是國際象棋中的棋子，意味著國王的妻子。皇后只做一件事，那就是“吃子”。當她遇見可以吃的棋子時，就迅速沖上去吃掉棋子。當然，她橫、豎、斜都可走一到七步，可進可退。（引用自百度百科 - 皇后）

思路：回溯

class Solution {
    // 定義三個布爾數(shù)組，表示列和主副對角線的元素是否使用過
    private boolean[] col;
    private boolean[] dia1;
    private boolean[] dia2;
    private List<List<String>> ans = new ArrayList<>();

    public List<List<String>> solveNQueens(int n) {
        col = new boolean[n];
        dia1 = new boolean[2 * n - 1]; // 對角線個數(shù)為 2 * n - 1
        dia2 = new boolean[2 * n - 1];

        // 定義每行的元素個數(shù)
        List<Integer> list = new LinkedList<>();
        // 回溯尋找符合要求的每組解
        putQueen(n, 0, list);
        return ans;
    }

    // row 代表當前訪問的行數(shù),最多到 n; list 用來存放滿足題意的一種情況
    private void putQueen(int n, int row, List<Integer> list) {
        // 如果遍歷到了最后一行，即代表已經(jīng)找出一組解出來
        if (row == n) {
            // 將找到的一組解轉(zhuǎn)化為棋盤格的形式后再放入 ans
            ans.add(changeBoard(n, list));
            return;
        }
        // 遍歷當前 row 行的所有位置(從前往后依次遍歷)
        for (int i = 0; i < n; i++) {
            // row + i 表示橫縱坐標相加
            // row - i + n - 1 表示橫縱坐標之差
            // 如果當前位置元素與他同一列，同一主副對角線上沒有重復(fù)元素
            if (!col[i] && !dia1[row + i] && !dia2[row - i + n - 1]) {
                // 則該位置即皇后放置的位置，放入 list 存儲位置信息，并標記為 true
                list.add(i);
                // 此時在該元素所在的列和主副對角線上就不能在遍歷找到其他元素了
                // 即標記為 true
                col[i] = true;
                dia1[row + i] = true;
                dia2[row - i + n - 1] = true;

                // 接著遞歸尋找下一行
                putQueen(n, row + 1, list);

                // 遍歷完后再退出標記
                col[i] = false;
                dia1[row + i] = false;
                dia2[row - i + n - 1] = false;
                // 回退上一格子(回溯)
                list.remove(list.size() - 1);
            }
        }
        return;
    }

    // 將找到的一組解轉(zhuǎn)化為棋盤格形式存儲
    private List<String> changeBoard(int n, List<Integer> list) {
        List<String> tmp = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            char[] ch = new char[n];
            Arrays.fill(ch, '.');  // 初始化 ch 中所有位置元素為 ‘.’
            // 將 row 中已經(jīng)確定下來的 Queen 位置改為 ‘Q’
            ch[list.get(i)] = 'Q';
            // 然后放入 tmp 中
            tmp.add(new String(ch));
        }
        return tmp;
    }
}

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

1.回溯問題（一）

1.回溯問題（一）

10. 正則表達式匹配難度困難（看了題解理解的，動態(tài)規(guī)劃）

17. 電話號碼的字母組合難度中等

22. 括號生成難度中等

37. 解數(shù)獨難度困難(不會做)

39. 組合總和難度中等 [?]

40. 組合總和 II難度中等 [?]

44. 通配符匹配難度困難（看了題解理解的，動態(tài)規(guī)劃）

46. 全排列難度中等 [?]

47. 全排列 II難度中等 [?]

51. N皇后難度困難

10. 正則表達式匹配難度困難

思路：動態(tài)規(guī)劃

17. 電話號碼的字母組合難度中等

22. 括號生成難度中等

思路：DFS不用回溯

37. 解數(shù)獨難度困難

思路：回溯

39. 組合總和難度中等

思路：回溯

40. 組合總和 II難度中等339

思路：回溯

44. 通配符匹配難度困難

思路：動態(tài)規(guī)劃

46. 全排列難度中等

思路：回溯

47. 全排列 II難度中等

思路：回溯

51. N皇后難度困難

思路：回溯

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

1.回溯問題（一）

10. 正則表達式匹配難度困難（看了題解理解的，動態(tài)規(guī)劃）

17. 電話號碼的字母組合難度中等

22. 括號生成難度中等

37. 解數(shù)獨難度困難(不會做)

39. 組合總和難度中等 [?]

40. 組合總和 II難度中等 [?]

44. 通配符匹配難度困難（看了題解理解的，動態(tài)規(guī)劃）

46. 全排列難度中等 [?]

47. 全排列 II難度中等 [?]

51. N皇后難度困難

10. 正則表達式匹配難度困難

思路：動態(tài)規(guī)劃

17. 電話號碼的字母組合難度中等

22. 括號生成難度中等

思路：DFS不用回溯

37. 解數(shù)獨難度困難

思路：回溯

39. 組合總和難度中等

思路：回溯

40. 組合總和 II難度中等339

思路：回溯

44. 通配符匹配難度困難

思路：動態(tài)規(guī)劃

46. 全排列難度中等

思路：回溯

47. 全排列 II難度中等

思路：回溯

51. N皇后難度困難

思路：回溯

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

10. 正則表達式匹配難度困難（看了題解理解的，動態(tài)規(guī)劃）

44. 通配符匹配難度困難（看了題解理解的，動態(tài)規(guī)劃）