leetcode回溯法题目解法若干

深碍√TFBOYSˉ_ 2023-06-09 15:24 34阅读 0赞

## N皇后问题 ##

![format_png][]

*  [N-Queens][]
 *  [N-Queens II][]

import java.util.ArrayList;
    import java.util.List;
    
    /*
     * @lc app=leetcode id=51 lang=java
     *
     * [51] N-Queens
     */
    public class Solution {
        
    
        List<List<String>> result = new ArrayList<>();
    
        private static int total = 0;
    
        public List<List<String>> solveNQueens(int n) {
        
            total = n;
            int[][] board = new int[n][n];
            backtrack(board, 1);
            return result;
        }
    
        private void backtrack(int[][] board, int idx) {
        
            if (idx > total) {
        
                // ok
                result.add(transform(board));
                return;
            }
    
            for (int i = 0; i < total; i ++) {
        
                if (isOk(board, idx - 1, i)) {
        
                    //
                    board[idx - 1][i] = 1;
                    backtrack(board, idx + 1);
                    board[idx - 1][i] = 0;
                }
            }
        }
    
        private boolean isOk(int[][] board, int xx, int yy) {
        
            for (int i = 0; i < total; i++) {
        
                if (board[xx][i] == 1) {
        
                    return false;
                }
                if (board[i][yy] == 1) {
        
                    return false;
                }
            }
            int x = xx, y = yy;
            while (x < total && y >= 0)
                if (board[x ++][y --] == 1)
                    return false;
            x = xx; y = yy;
            while (x < total && y < total)
                if (board[x ++][y ++] == 1)
                    return false;
            x = xx; y = yy;
            while (x >= 0 && y >= 0)
                if (board[x --][y --] == 1)
                    return false;
            x = xx; y = yy;
            while (x >=0 && y < total)
                if (board[x --][y ++] == 1)
                    return false;
    //        System.out.println("OK");
            return true;
        }
    
        private List<String> transform(int[][] board) {
        
            List<String> oneAnswer = new ArrayList<>();
            for (int i = 0; i < board.length; i ++) {
        
                StringBuilder sb = new StringBuilder();
                for (int j = 0; j < board[i].length; j ++) {
        
                    sb.append(board[i][j] == 0 ? '.' : 'Q');
                }
                oneAnswer.add(sb.toString());
            }
    //        showAnswer(oneAnswer);
            return oneAnswer;
        }
    
        private void showAnswer(List<String> answer) {
        
            System.out.println();
            for (String line : answer) {
        
                System.out.println(line);
            }
        }
    
        public static void main(String[] args) {
        
            List<List<String>> result = new Solution().solveNQueens(4);
            System.out.println(result.size());
        }
    }

## [Letter Combinations of a Phone Number][] ##

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

![format_png 1][]

import java.util.ArrayList;
    import java.util.List;
    
    /*
     * @lc app=leetcode id=17 lang=java
     *
     * [17] Letter Combinations of a Phone Number
     */
    class Solution {
        
        private int[][] maps = {
        
            {
        },
            {
        },
            {
        'a', 'b', 'c'},
            {
        'd', 'e', 'f'},
            {
        'g', 'h', 'i'},
            {
        'j', 'k', 'l'},
            {
        'm', 'n', 'o'},
            {
        'p', 'q', 'r', 's'},
            {
        't', 'u', 'v'},
            {
        'w', 'x', 'y', 'z'}
        };
        List<String> result = new ArrayList<>();
        public List<String> letterCombinations(String digits) {
        
             backtrack(digits, "", 0);
             return result;
        }
        private void backtrack(String digits, String sb, int idx) {
        
            if (idx >= digits.length()) {
        
                if (sb.length() > 0)
                    result.add(sb.toString());
                return;
            }
            int mapsIdx = digits.charAt(idx) - '0';
            for (int i = 0; i < maps[mapsIdx].length; i ++) {
        
                backtrack(digits, sb + (char) maps[mapsIdx][i], idx + 1);
            }
        }
    }

## [Generate Parentheses][] ##

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

[
      "((()))",
      "(()())",
      "(())()",
      "()(())",
      "()()()"
    ]

class Solution {
        
        List<String> sets = new ArrayList<>();
    
        // 22
        public List<String> generateParenthesis(int n) {
        
            produce(2 * n, 0, n, n, "");
            return sets;
        }
    
        private void produce(int blank, int sum, int lcnt, int rcnt, String seq) {
        
            if (sum < 0)
                return;
    
            if (blank == 0) {
        
                sets.add(seq);
                return;
            }
    
            if (lcnt > 0) {
        
                produce(blank - 1, sum + 1, lcnt - 1, rcnt, seq + "(");
            }
    
            if (rcnt > 0) {
        
                produce(blank - 1, sum - 1, lcnt, rcnt - 1, seq + ")");
            }
        }
    }

## [Sudoku Solver][] ##

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

A sudoku solution must satisfy all of the following rules:

Each of the digits 1-9 must occur exactly once in each row.

Each of the digits 1-9 must occur exactly once in each column.

Each of the the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.

Empty cells are indicated by the character ‘.’.

![format_png 2][]

![format_png 3][]

/*
     * @lc app=leetcode id=37 lang=java
     *
     * [37] Sudoku Solver
     */
    public class Solution {
        
        private static class Point {
        
            public int x, y;
    
            public Point(int x, int y) {
        
                this.x = x;
                this.y = y;
            }
    
            @Override
            public String toString() {
        
                return "<" + x + ", " + y + ">";
            }
        }
    
        static char[][] data = {
        
                {
        '5', '3', '.', '.', '7', '.', '.', '.', '.'},
                {
        '6', '.', '.', '1', '9', '5', '.', '.', '.'},
                {
        '.', '9', '8', '.', '.', '.', '.', '6', '.'},
                {
        '8', '.', '.', '.', '6', '.', '.', '.', '3'},
                {
        '4', '.', '.', '8', '.', '3', '.', '.', '1'},
                {
        '7', '.', '.', '.', '2', '.', '.', '.', '6'},
                {
        '.', '6', '.', '.', '.', '.', '2', '8', '.'},
                {
        '.', '.', '.', '4', '1', '9', '.', '.', '5'},
                {
        '.', '.', '.', '.', '8', '.', '.', '7', '9'}
        };
    
        public static void main(String[] args) {
        
            new Solution().solveSudoku(data);
            printBoard(data, "最终结果");
        }
    
        private static void printBoard(char[][] data, String msg) {
        
            System.out.println("\n" + msg + ":");
            for (int i = 0; i < data.length; i ++) {
        
                for (int j = 0; j < data[i].length; j++) {
        
                    System.out.print(data[i][j] + " ");
                }
                System.out.println();
            }
            System.out.println();
        }
    
        boolean over = false;
    
        public void solveSudoku(char[][] board) {
        
            backtrack(board, nextPoint(board, new Point(0, 0)));
        }
    
        private void backtrack(char[][] board, Point focus) {
        
            if (over || isOver(board)) {
        
                over = true;
                return;
            }
    
            if (focus == null) {
        
                over = true;
                return;
            }
    
            for (int val = 1; val <= 9 && !over; val++) {
        
                board[focus.x][focus.y] = (char) ('0' + val);
                if (isValid(board, focus, (char) ('0' + val))) {
        
                    backtrack(board, nextPoint(board, focus));
                }
            }
            if (!over)
                board[focus.x][focus.y] = '.';
        }
    
        private boolean isValid(char[][] board, Point p, char val) {
        
            // 横向
            for (int i = 0; i <= 8; i++) {
        
                if (i != p.y && board[p.x][i] == val)
                    return false;
            }
            // 纵向
            for (int i = 0; i <= 8; i++) {
        
                if (i != p.x && board[i][p.y] == val)
                    return false;
            }
            // 方形
            for (int i = (p.x / 3 * 3); i <= (p.x / 3 * 3) + 2; i++) {
        
                for (int j = (p.y / 3 * 3); j <= (p.y / 3 * 3) + 2; j++) {
        
                    if (i != p.x && j != p.y && board[i][j] == val)
                        return false;
                }
            }
    //        printBoard(board, "位置" + p + ", 对值<" + (char)val + ">合适");
            return true;
        }
    
        private boolean isOver(char[][] board) {
        
            for (int i = 0; i < board.length; i++) {
        
                for (int j = 0; j < board[i].length; j++) {
        
                    if (board[i][j] == '.')
                        return false;
                }
            }
            return true;
        }
    
        private Point nextPoint(char[][] board, Point p) {
        
            Point returnPoint = null;
            int x = p.x, y = p.y;
            while (x <= 8 && returnPoint == null) {
        
                for (int i = y; i <= 8; i++) {
        
                    if (board[x][i] == '.') {
        
                        returnPoint = new Point(x, i);
                        break;
                    }
                }
                y = 0;
                x ++;
            }
    //        System.out.println(p + "  ->  " + returnPoint);
            return returnPoint;
        }
    }

## [Combination Sum][] ##

![format_png 4][]

相关问题：[Permutations II][]

class Solution {
        
        List<List<Integer>> result = new ArrayList();
    
        private boolean[] USAGE;
    
        public List<List<Integer>> permute(int[] nums) {
        
            USAGE = new boolean[nums.length];
            List<Integer> answer = new ArrayList();
            backtrack(nums, 0, answer);
            return result;
        }
    
        private void backtrack(int[] nums, int idx, List<Integer> answer) {
        
            if (idx >= nums.length) {
        
                result.add(new ArrayList(answer));
                return;
            }
            for (int i = 0; i < nums.length; i ++) {
        
                if (!USAGE[i]) {
        
                    answer.add(nums[i]);USAGE[i] = true;
                    backtrack(nums, idx + 1, answer);
                    answer.remove(answer.size() - 1);USAGE[i] = false;
                }
            }
        }
    }

## [Permutation Sequence][] ##

![format_png 6][]

class Solution {
        
        private boolean[] usage;
        private String result;
        private int targetIdx, currentIdx;
        private boolean over = false;
        public String getPermutation(int n, int k) {
        
            targetIdx = k;
            usage = new boolean[n + 1];
            StringBuilder sb = new StringBuilder();
            backtrack(n, 1, sb);
            return result;
        }
    
        private void backtrack(int n, int idx, StringBuilder sb) {
        
            if (over)
                return;
            if (idx > n) {
        
                currentIdx ++;
                if (currentIdx == targetIdx) {
        
                    result = sb.toString();
                    over = true;
                }
                return ;
            }
            for (int i = 1; i <= n; i ++) {
        
                if (over)
                    break;
                if (!usage[i]) {
        
                    sb.append(i);usage[i] = true;
                    backtrack(n, idx + 1, sb);
                    sb.deleteCharAt(sb.length() - 1);usage[i] = false;
                }
            }
        }
    }

## [Combinations][] ##

![format_png 7][]

class Solution {
        
        private List<List<Integer>> result = new ArrayList();
        private boolean[] USAGE;
        private int depth;
    
        public List<List<Integer>> combine(int n, int k) {
        
            depth = k;
            USAGE = new boolean[n + 1];
            backtrack(1, n, 1, new ArrayList<>());
            return result;
        }
    
        private void backtrack(int startIdx, int n, int idx, List<Integer> answer) {
        
            if (idx > depth) {
        
                result.add(new ArrayList(answer));
                return;
            }
            for (int i = startIdx; i <= n; i ++) {
        
                if (!USAGE[i]) {
        
                    answer.add(i);USAGE[i] = true;
                    backtrack(i + 1, n, idx + 1, answer);
                    answer.remove(answer.size() - 1);USAGE[i] = false;
                }
            }
        }
    }

[format_png]: /images/20230531/99936569ed6946d9a6daa484f3b64547.png
[N-Queens]: https://leetcode.com/problems/n-queens/
[N-Queens II]: https://leetcode.com/problems/n-queens-ii/
[Letter Combinations of a Phone Number]: https://leetcode.com/problems/letter-combinations-of-a-phone-number
[format_png 1]: /images/20230531/f525dc6f4fa347e589ba0f45ee4227f0.png
[Generate Parentheses]: https://leetcode.com/problems/generate-parentheses/
[Sudoku Solver]: https://leetcode.com/problems/sudoku-solver/
[format_png 2]: /images/20230531/daedd532d3e44a458ea5de9a10df9dca.png
[format_png 3]: /images/20230531/9861e855625b49f082aadf42b78ddb07.png
[Combination Sum]: https://leetcode.com/problems/combination-sum/
[format_png 4]: /images/20230531/23ca4d887b2c45b2b89ad09e172c2cb7.png
[Combination Sum II]: https://leetcode.com/problems/combination-sum-ii/
[Permutations]: https://leetcode.com/problems/permutations/
[format_png 5]: /images/20230531/bc331cbd5fe74dccbe38b9f025c96f86.png
[Permutations II]: https://leetcode.com/problems/permutations-ii
[Permutation Sequence]: https://leetcode.com/problems/permutation-sequence/
[format_png 6]: /images/20230531/59e07f57a02142128f4eda9bce1636a1.png
[Combinations]: https://leetcode.com/problems/combinations/
[format_png 7]: /images/20230531/e3cdb45a88b94a248777d9f7488b913a.png