【算法刷题day30】Leetcode：332. 重新安排行程、51. N 皇后、37. 解数独

2024-04-22 23:36:01
开发
11

文章目录

Leetcode 332. 重新安排行程

题目：332. 重新安排行程
解析：代码随想录解析

解题思路

代码


//第1版，通过 9/81（没看清题目，应该都是从JFK出发）
class Solution {
    List<String> res = new ArrayList<>();
    List<List<String>> paths = new ArrayList<>();
    boolean foundResult = false;
    boolean[] used;
    private void backtracking(List<List<String>> tickets) {
        if (foundResult)
            return;
        if (paths.size() == tickets.size()) {
            for (int i = 0; i < paths.size(); i++)
                res.add(paths.get(i).get(0));
            res.add(paths.get(paths.size()-1).get(1));
            foundResult = true;
            return;
        }
        for (int i = 0; i < tickets.size(); i++) {
            if (used[i])
                continue;
            if (!paths.isEmpty() && !(tickets.get(i).get(0)).equals(paths.get(paths.size() - 1).get(1)))
                continue;
            paths.add(tickets.get(i));
            used[i] = true;
            backtracking(tickets);
            paths.remove(paths.size()-1);
            used[i] = false;
        }
    }
    public List<String> findItinerary(List<List<String>> tickets) {
        //排序后找到的第一个。
        Collections.sort(tickets, new Comparator<List<String>>() {
            @Override
            public int compare(List<String> o1, List<String> o2) {
                int setOff = o1.get(0).compareTo(o2.get(0));
                if (setOff != 0)
                    return setOff;
                else
                    return o1.get(1).compareTo(o2.get(1));
            }
        });
        used = new boolean[tickets.size()];
        backtracking(tickets);
        return res;

    }
}

//第2版，通过80/81，剩一个奇怪的样例没通过。和卡哥的第一份答案一样有个样例没通过
class Solution {
    List<String> res = new ArrayList<>();
    List<String> paths = new ArrayList<>();
    boolean foundResult = false;
    boolean[] used;
    private void backtracking(List<List<String>> tickets) {
        if (foundResult)
            return;
        if (paths.size() == tickets.size() + 1) {
            res.addAll(paths);
            foundResult = true;
            return;
        }
        for (int i = 0; i < tickets.size(); i++) {
            if (used[i])
                continue;
            if (!(tickets.get(i).get(0)).equals(paths.get(paths.size()-1)))
                continue;
            paths.add(tickets.get(i).get(1));
            used[i] = true;
            backtracking(tickets);
            paths.remove(paths.size()-1);
            used[i] = false;
        }
    }
    public List<String> findItinerary(List<List<String>> tickets) {
        //排序后找到的第一个。
        Collections.sort(tickets, new Comparator<List<String>>() {
            @Override
            public int compare(List<String> o1, List<String> o2) {
                int setOff = o1.get(0).compareTo(o2.get(0));
                if (setOff != 0)
                    return setOff;
                else
                    return o1.get(1).compareTo(o2.get(1));
            }
        });
        used = new boolean[tickets.size()];
        paths.add("JFK");

        backtracking(tickets);
        return res;

    }
}

//第3版，通过81/81。使用 Map<String, Map<String, Integer>>来存储<出发站,<终点站, 票数>>，其中的终点站使用TreeMap来存储（保证了Key的有序性），比直接使用used更高效。
class Solution {
    List<String> res;
    Map<String, Map<String, Integer>> ticketMap;

    private boolean backtracking(int ticketNum) {
        if (res.size() == ticketNum + 1) {
            return true;
        }
        String destination = res.get(res.size()-1);
        if (ticketMap.containsKey(destination)) {
            for (Map.Entry<String, Integer> desNum : ticketMap.get(destination).entrySet()) {
                int count = desNum.getValue();
                if (count > 0) {
                    res.add(desNum.getKey());
                    desNum.setValue(count - 1);
                    if (backtracking(ticketNum))
                        return true;
                    desNum.setValue(count);
                    res.remove(res.size()-1);
                }
            }
        }
        return false;
    }

    public List<String> findItinerary(List<List<String>> tickets) {
        res = new ArrayList<>();
        ticketMap = new HashMap<>();
        for (List<String> ticket : tickets) {
            Map<String, Integer> tmp;
            if (ticketMap.containsKey(ticket.get(0))) {//是否有出发站的票
                tmp = ticketMap.get(ticket.get(0));//获取以此为出发站的终点站的票及对应票数量
                tmp.put(ticket.get(1), tmp.getOrDefault(ticket.get(1), 0) + 1);//让对应票数加1
            } else {
                tmp = new TreeMap<>();
                tmp.put(ticket.get(1), 1);
            }
            ticketMap.put(ticket.get(0), tmp);
        }

        res.add("JFK");
        backtracking(tickets.size());
        return res;
    }
}

总结

hard果然不容易

Leetcode 51. N 皇后

题目：51. N 皇后
解析：代码随想录解析

解题思路

每次是否下棋，就判断一下能否下这个皇后。一行一行下。一列一列判断。

代码

class Solution {
    List<List<String>> res;
    List<StringBuilder> chess;
    private boolean isValid(int row, int col, int n) {
        // for (int i = 0; i < n; i++)
        //     if (chess.get(row).charAt(i) == 'Q')
        //         return false;
        for (int i = 0; i < row; i++)
            if (chess.get(i).charAt(col) == 'Q')
                return false;
        for (int i = row-1, j = col-1; i >= 0 && j >= 0; i--, j--)
            if (chess.get(i).charAt(j) == 'Q')
                return false;
        for (int i = row-1, j = col+1; i >= 0 && j < n; i--, j++)
            if (chess.get(i).charAt(j) == 'Q')
                return false;
        return true;
    }

    private void backtracking(int n, int row) {
        if (row == n) {
            List<String> newChess = new ArrayList<>();
            for (int i = 0; i < chess.size(); i++)
                newChess.add(chess.get(i).toString());
            res.add(newChess);
            return;
        }
        for (int col = 0; col < n; col++) {
            if (isValid(row, col, n)) {
                chess.get(row).setCharAt(col, 'Q');
                backtracking(n, row + 1);
                chess.get(row).setCharAt(col, '.');
            }
        }
    }
    public List<List<String>> solveNQueens(int n) {
        res = new ArrayList<>();
        chess =  new ArrayList<>();
        for (int i = 0; i < n; i++) {
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < n; j++)
                sb.append('.');
            chess.add(sb);
        }

        backtracking(n, 0);
        return res;
    }
}

总结

暂无

Leetcode 37. 解数独

题目：37. 解数独
解析：代码随想录解析

解题思路

每次是否填入数字1-9，如果填入1-9都错误，则返回false。如果全部填完了，返回true。其中如果isValid已经达到了，就提前退出当前层的递归。

代码

class Solution {
    private boolean isValid(int row, int col, int val, char[][] board) {
        for (int i = 0; i < board.length; i++) {
            if (i == row)
                continue;
            if (board[i][col] == val)
                return false;
        }
        for (int j = 0; j < board.length; j++) {
            if (j == col)
                continue;
            if (board[row][j] == val)
                return false;
        }
        int beginRow = (row / 3) * 3;
        int beginCol = (col / 3) * 3;
        for (int i = beginRow; i < beginRow + 3; i++)
            for (int j = beginCol; j < beginCol + 3; j++) {
                if (i == row && j == col)
                    continue;
                if (board[i][j] == val)
                    return false;
            }
        return true;
    }
    private boolean backtracking(char[][] board) {

        for (int row = 0; row < board.length; row++) {
            for (int col = 0; col < board.length; col++) {
                if (board[row][col] == '.') {
                    for (char val = '1'; val <= '9'; val++) {
                        if (isValid(row, col, val, board)) {
                            board[row][col] = val;
                            if (backtracking(board))
                                return true;
                            board[row][col] = '.';
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }
    public void solveSudoku(char[][] board) {
        backtracking(board);
    }
}

总结

暂无

原文地址:https://blog.csdn.net/qq_45022758/article/details/137914904 本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：https://www.suanlizi.com/kf/1782433181467807744.html 如若内容造成侵权/违法违规/事实不符，请联系《酸梨子》网邮箱：1419361763@qq.com进行投诉反馈，一经查实，立即删除！

阅读全部