专栏首页机器学习入门算法细节系列(23):回溯

算法细节系列(23):回溯

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/u014688145/article/details/72655010

算法细节系列(23):回溯

详细代码可以fork下Github上leetcode项目,不定期更新。

题目摘自leetcode: 1. Leetcode 093: Restore IP address 2. Leetcode 037: Sudoku Solver 3. Leetcode 051: N-Queens 4. Leetcode 079: Word Search 5. Leetcode 212: Word Seach II 6. Leetcode 211: Add and Seach Word - Data Structure Design

Leetcode 093: Restore IP address

思路: 这类题,都可以暴力DFS+回溯来求解,比较注重细节,来练练手。知识点:字符串的状态回归,用一个index变量记录当前滑动的位置即可,而不需要真的对字符串裁剪。

回溯的精要在于找到大问题化为子问题的状态区分,或许有点抽象,但还是要明确一下。如在本题中,状态区分一定是每个下标点,我们知道IP address总共就三个下标点,所以只需要递归四次即可,把合法的ip拼接上,不合法的剪枝掉即可。

代码如下:

    public List<String> restoreIpAddresses(String s) {
        List<String> ans = new ArrayList<>();
        backTrack(ans, "", 3, s, 0);
        return ans;
    }

    private void backTrack(List<String> ans, String ip, int k, String address, int index){
        if (k == 0){
            if (valid(address.substring(index))){
                ip += address.substring(index);
                ans.add(ip);
                return;
            }
        } else {
            for (int i = 0; i < 3; i++) {
                if (index + i >= address.length())
                    continue;
                String cut = address.substring(index, index + i + 1);
                if (valid(cut)) {
                    ip += cut + ".";
                    backTrack(ans, ip, k - 1, address, index + i + 1);
                    ip = ip.substring(0, ip.length() - (i + 1) - 1);
                }
            }
        }
    }

    private boolean valid(String s){
        if (s.length() >= 4 || s.length() == 0 || (s.charAt(0) == '0' && s.length() > 1))
            return false;
        return Integer.parseInt(s) >= 0 && Integer.parseInt(s) <= 255; 
    }

回溯是暴力的首席代表,该问题还可以转换成暴力迭代,代码如下:

public List<String> restoreIpAddresses(String s) {
        List<String> ans = new ArrayList<>();
        for (int i = 1; i < 4; i++){
            if (i >= s.length()) continue;
            for (int j = i + 1; j < i + 4; j++){
                if (j >= s.length()) continue;
                for (int k = j + 1; k < j + 4; k++){
                    if (k >= s.length()) continue;
                    String s1 = s.substring(0, i);
                    String s2 = s.substring(i, j);
                    String s3 = s.substring(j, k);
                    String s4 = s.substring(k);
                    if (valid(s1) && valid(s2) && valid(s3) && valid(s4)){
                        ans.add(s1+"."+s2+"."+s3+"."+s4);
                    }
                }
            }
        }

        return ans;
    }

Leetcode 037: Sudoku Solver

思路: 还是暴搜,能够解决数独的充分必要条件时,所在行和列,已经3*3的格子内无重复元素。代码如下:

public void solveSudoku(char[][] board) {
        backTrack(board);
    }

    private boolean backTrack(char[][] board) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '.') {
                    for (char c = '1'; c <= '9'; c++) {
                        if (isValid(board, i, j, c)) {
                            board[i][j] = c;
                            if (backTrack(board)) {
                                return true;
                            } else {
                                board[i][j] = '.';
                            }
                        }
                    }
                    //说明遍历了1-9都没找到答案 直接false即可
                    return false;
                }
            }
        }
        return true;
    }

    private boolean isValid(char[][] board, int row, int col, char c) {
        for (int i = 0; i < 9; i++) {
            if (board[i][col] != '.' && board[i][col] == c)
                return false;
            if (board[row][i] != '.' && board[row][i] == c)
                return false;
            if (board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] != '.'
                    && board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == c)
                return false;
        }
        return true;
    }

leetcode的测试数据中不存在多解的情况,所以一旦solve直接范围true即可,而如果尝试了1-9之后都没解决,那只能返回false了。

Leetcode 051: N-Queens

思路: 纠结在如何表达两条斜对角线不能使用,技巧是给定row和col,能够唯一确定斜对角线和反斜对角线,如下:

斜对角表示法:
int diag = row + col;

  0 1 2 3
0 . . . X
1 . . X .
2 . X . .
3 X . . .

反斜对角表示法:
int diag = row - col + len;

  -3 -2 -1 -0
0  X  .  .  .
1  .  X  .  .
2  .  .  X  .
3  .  .  .  X

是不是这个道理?

代码如下:

public List<List<String>> solveNQueens(int n) {
        List<List<String>> ans = new ArrayList<>();
        char[][] cs = new char[n][n];
        for (int i = 0; i < n; i++){
            Arrays.fill(cs[i], '.');
        }

        boolean[] cols = new boolean[n];
        boolean[] diag = new boolean[2*n];
        boolean[] riag = new boolean[2*n];
        backTrack(ans, cs, n, 0, cols, diag, riag);
        return ans;
    }

    private void backTrack(List<List<String>> ans, char[][] path, int n, int start, boolean[] cols, boolean[] diag, boolean[] riag){
        if (start == n){
            List<String> pp = new ArrayList<>();
            for (int i = 0; i < path.length; i++){
                pp.add(new String(path[i]));
            }
            ans.add(new ArrayList<>(pp));
            return;
        }else{
            for (int i = 0; i < n; i++){
                if (!cols[i] && !diag[start + i] && !riag[start-i+n]){
                    path[start][i] = 'Q';
                    cols[i] = true;
                    diag[start + i] = true;
                    riag[start - i + n] = true;
                    backTrack(ans, path, n, start+1, cols, diag, riag);
                    path[start][i] = '.';
                    cols[i] = false;
                    diag[start + i] = false;
                    riag[start - i + n] = false;
                }
            }
        }
    }

思路: 没什么,直接爆搜就好了,用pos记录word所在的位置,如果能搜到结尾就返回true,并且不断把结果返回给上一层。代码如下:

public boolean exist(char[][] board, String word) {
        char[] words = word.toCharArray();
        for (int i = 0; i < board.length; i++){
            for (int j = 0; j < board[i].length; j++){
                if(board[i][j] == words[0]){
                    board[i][j] = '#';
                    if (helper(board, i, j, words, 1)) return true;
                    board[i][j] = words[0];
                }
            }
        }
        return false;
    }

    int[][] dir = {{1,0},{-1,0},{0,-1},{0,1}};

    private boolean helper(char[][] board, int x, int y, char[] words, int pos) {
        if (pos == words.length) {
            return true;
        } else {
            int row = board.length, col = board[0].length;
            for (int[] d : dir){
                int nx = x + d[0];
                int ny = y + d[1];
                if (nx >= 0 && nx < row && ny >= 0 && ny < col && board[nx][ny] != '#' && board[nx][ny] == words[pos]){
                    board[nx][ny] = '#';
                    if(helper(board, nx, ny, words, pos+1)) return true;
                    board[nx][ny] = words[pos];
                }
            }
        }
        return false;
    }

Leetcode 212: Word Seach II

这道题需要一些优化知识,就拿上面那种解法,每遍历一个单词就check一次board,如果返回true,则把答案加入ans集合中,TLE了。

超时的原因在于每次都得重新遍历一次board,如果以word去拟合board的视角来看,的确找不到什么可优化的地方。但这道题巧就巧在,搜索视角可以是:以borad去拟合word,而这就可以极大的改善搜索时间。

如在borad中,我们假设有”aaabc”的有效路径,优化的思路在于,在word集合中,所有符合前缀”aaabc”的单词,只需搜索一遍board。如

words = ["aaabcc","aaabcd","aaabce"]

"aaabcc"是它们的公共前缀,所以让board去check这个前缀是否存在,如果存在,在去递归check:
"c","d","e"的路径,存在返回。

省去了"aaabcc"的两次check操作。

所以,我们需要设计一种数据结构用来保存单词的公共前缀,没错,就是Trie树,整体代码如下:

public List<String> findWords(char[][] board, String[] words) {
        List<String> ans = new ArrayList<>();
        TrieNode root = buildTrie(words);
        for (int i = 0; i < board.length; i++){
            for (int j = 0; j < board[i].length; j++){
                dfs(board, i, j, root, ans);
            }
        }
        return ans;
    }

    private void dfs(char[][] board, int i, int j, TrieNode root, List<String> ans){
        char c = board[i][j];
        if (c == '#' || root.next[c-'a'] == null) return;
        root = root.next[c-'a'];
        if (root.word != null){
            ans.add(root.word);
            root.word = null;
        }

        board[i][j] = '#';
        if (i > 0) dfs(board, i - 1, j ,root, ans); 
        if (j > 0) dfs(board, i, j - 1, root, ans);
        if (i < board.length - 1) dfs(board, i + 1, j, root, ans); 
        if (j < board[0].length - 1) dfs(board, i, j + 1, root, ans); 
        board[i][j] = c;
    }

    private class TrieNode{
        TrieNode[] next = new TrieNode[26];
        String word;
    }

    private TrieNode buildTrie(String[] words){
        TrieNode root = new TrieNode();
        for (String w : words){
            TrieNode p = root;
            for (char c : w.toCharArray()){
                int i = c- 'a';
                if (p.next[i] == null) p.next[i] = new TrieNode();
                p = p.next[i];
            }
            p.word = w;
        }
        return root;
    }

Leetcode 211: Add and Seach Word - Data Structure Design

最近Trie树做的有点多,这道题也是基于Trie树的字符匹配问题。主要针对的是"."的处理,它比较特殊,只要搜索当前结点中所有非空的结点,就算匹配成功,最后不管是"."过来的,还是从某个字符过来的,统一交给pos == chs.length来处理。

代码如下:

public class WordDictionary {

    private class TrieNode {
        TrieNode[] next = new TrieNode[26];
        String word;
    }

    TrieNode root;

    public WordDictionary() {
        root = new TrieNode();
    }

    public void addWord(String word) {
        TrieNode p = root;
        for (char c : word.toCharArray()) {
            int i = c - 'a';
            if (p.next[i] == null)
                p.next[i] = new TrieNode();
            p = p.next[i];
        }
        p.word = word;
    }

    public boolean search(String word) {
        return match(word.toCharArray(), 0, root);
    }

    private boolean match(char[] chs, int pos, TrieNode node){
        if (pos == chs.length) return node.word != null;
        if (chs[pos] != '.'){
            return node.next[chs[pos]-'a'] != null && match(chs, pos+1, node.next[chs[pos]-'a']);
        }else{
            for (char c = 'a'; c <= 'z'; c++){
                if (node.next[c-'a'] != null){
                    if(match(chs, pos+1, node.next[c-'a'])){
                        return true;
                    }
                }
            }
        }
        return false;
    }

    public static void main(String[] args) {
        WordDictionary wd = new WordDictionary();
        wd.addWord("bad");
        wd.addWord("dad");
        wd.addWord("mad");
        wd.search("pad");
        wd.search("bad");
        wd.search(".ad");
        wd.search("b..");
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode Weekly Contest 35解题思路

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • LeetCode Weekly Contest 33解题思路

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • LWC 63: 749. Contain Virus

    Problem: A virus is spreading rapidly, and your task is to quarantine the infec...

    用户1147447
  • 消灭 Java 代码的“坏味道”

    代码中的"坏味道",如"私欲"如"灰尘",每天都在增加,一日不去清除,便会越累越多。如果用功去清除这些"坏味道",不仅能提高自己的编码水平,也能使代码变得"精白...

    程序亦非猿
  • 消灭 Java 代码的“坏味道”

    代码中的"坏味道",如"私欲"如"灰尘",每天都在增加,一日不去清除,便会越累越多。如果用功去清除这些"坏味道",不仅能提高自己的编码水平,也能使代码变得"精白...

    用户1564362
  • MySql “找不到请求的 .Net Framework 数据提供程序。可能没有安装。”

    需要在app.config或者web.config中添加下面的配置项 <system.data>     <DbProviderFactories> ...

    用户1177380
  • 消灭 Java 代码的“坏味道”

    代码中的"坏味道",如"私欲"如"灰尘",每天都在增加,一日不去清除,便会越累越多。如果用功去清除这些"坏味道",不仅能提高自己的编码水平,也能使代码变得"精白...

    程序员小明
  • 消灭 Java 代码的“坏味道”

    代码中的"坏味道",如"私欲"如"灰尘",每天都在增加,一日不去清除,便会越累越多。如果用功去清除这些"坏味道",不仅能提高自己的编码水平,也能使代码变得"精白...

    Java技术江湖
  • Leetcode 题解——541/1018

    出其东门
  • 【每日一题】37. Sudoku Solver

    Write a program to solve a Sudoku puzzle by filling the empty cells.

    公众号-不为谁写的歌

扫码关注云+社区

领取腾讯云代金券