• 代码随想录训练营二刷第三十天 | 332.重新安排行程 51. N皇后 37. 解数独


    代码随想录训练营二刷第三十天 | 332.重新安排行程 51. N皇后 37. 解数独

    一、332.重新安排行程

    题目链接:https://leetcode.cn/problems/reconstruct-itinerary/
    思路:直接看题解了,没太想明白为什么需要排序

    class Solution {
        private Deque<String> res;
        private Map<String, Map<String, Integer>> map;
    
        private boolean backTracking(int ticketNum){
            if(res.size() == ticketNum + 1){
                return true;
            }
            String last = res.getLast();
            if(map.containsKey(last)){//防止出现null
                for(Map.Entry<String, Integer> target : map.get(last).entrySet()){
                    int count = target.getValue();
                    if(count > 0){
                        res.add(target.getKey());
                        target.setValue(count - 1);
                        if(backTracking(ticketNum)) return true;
                        res.removeLast();
                        target.setValue(count);
                    }
                }
            }
            return false;
        }
    
        public List<String> findItinerary(List<List<String>> tickets) {
            map = new HashMap<String, Map<String, Integer>>();
            res = new LinkedList<>();
            for(List<String> t : tickets){
                Map<String, Integer> temp;
                if(map.containsKey(t.get(0))){
                    temp = map.get(t.get(0));
                    temp.put(t.get(1), temp.getOrDefault(t.get(1), 0) + 1);
                }else{
                    temp = new TreeMap<>();//升序Map
                    temp.put(t.get(1), 1);
                }
                map.put(t.get(0), temp);
    
            }
            res.add("JFK");
            backTracking(tickets.size());
            return new ArrayList<>(res);
        }
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44

    二、51. N皇后

    题目链接:https://leetcode.cn/problems/n-queens/
    思路:题目不难主要要知道N皇后的限制,不能同行同列,斜着45度135度都不行。这些是判断条件。然后for循环控制每层是n,递归深度也是n,每层递归处理一行。

    class Solution {
       List<List<String>> arrayLists = new ArrayList<>();
        public List<List<String>> solveNQueens(int n) {
            char[][] queens = new char[n][n];
            for (int i = 0; i < n; i++) {
                Arrays.fill(queens[i], '.');
            }
            backTracking(0, n, queens);
            return arrayLists;
        }
        void backTracking(int row, int n, char[][] queens) {
            if (row == n) {
                arrayLists.add(arrayToList(queens));
                return;
            }
            for (int i = 0; i < n; i++) {
                if (isTrue(queens, row, i, n)) {
                    queens[row][i] = 'Q';
                    backTracking(row+1, n, queens);
                    queens[row][i] = '.';
                }
            }
        }
        List<String> arrayToList(char[][] queens) {
            List<String> list = new ArrayList<>();
            for (char[] queen : queens) {
                list.add(String.copyValueOf(queen));
            }
            return list;
        }
        boolean isTrue(char[][] queens, int row, int col, int n) {
            for (int i = 0; i < n; i++) {
                if (queens[i][col] == 'Q') {
                    return false;
                }
            }
            for (int i = row-1, j = col-1; i >= 0 && j >= 0; i--, j--) {
                if (queens[i][j] == 'Q') {
                    return false;
                }
            }
            for (int i = row-1, j = col+1; i >= 0 && j < n; i--, j++) {
                if (queens[i][j] == 'Q') {
                    return false;
                }
            }
            return true;
        }
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49

    三、37. 解数独

    题目链接:https://leetcode.cn/problems/sudoku-solver/
    思路:二维递归

    class Solution {
        public void solveSudoku(char[][] board) {
            backTracking(board);
        }
        boolean backTracking(char[][] board) {
            for (int i = 0; i < board.length; i++) {
                for (int j = 0; j < board.length; j++) {
                    if (board[i][j] != '.')continue;
                    for (char k = '1'; k <= '9'; k++) {
                        if (isTrue(board, i, j, k)) {
                            board[i][j] = k;
                            if (backTracking(board))return true;
                            board[i][j] = '.';
                        }
                    }
                    return false;
                }
            }
            return true;
        }
    
        boolean isTrue(char[][] board, int row, int col, int val) {
            for (int i = 0; i < 9; i++) {
                if (board[row][i] == val) return false;
            }
            for (int i = 0; i < 9; i++) {
                if (board[i][col] == val) return false;
            }
            int a = (row/3) * 3, b = (col/3)*3;
            for (int i = a; i < a + 3; i++) {
                for (int j = b; j < b + 3; j++) {
                    if (board[i][j] == val) return false;
                }
            }
            return true;
        }
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
  • 相关阅读:
    C++算法 —— 动态规划(4)子数组
    傻妞旧版本(合集)
    土壤类型、土壤质地、土壤养分空间分布
    实验2:Arduino的nRF24L01双向收发实验
    .NET 云原生架构师训练营(权限系统 代码实现 Store.EntityFramework)--学习笔记
    !还不了解位操作符?????!!!!!
    Chapter8 : Predicting Residence Time of GPCR Ligands with Machine Learning
    《运营商劫持, 中间人攻击, 黑客入侵怎么办?》- HTTPS 技术反制
    简单的学生信息管理系统
    docker 的 limits 使用,控制内存,cpu等的最大占用率
  • 原文地址:https://blog.csdn.net/qq_43511039/article/details/133126934