代码随想录算法训练营第30天 | 332.重新安排行程, 51.N皇后, 37.解数独, 回溯法总结

332.重新安排行程

代码随想录链接

题目

LeetCode-332.重新安排行程

给定几张机票, 从"JFK"出发, 将这些行程进行先后顺序的安排, 返回字母顺序最小的行程安排.

自己的想法

自己刚开始还想着用used布尔型数组, 来进行一个简单的排列组合, 最后在所有可以的行程内进行一个排序求出字母顺序最小的路程, 写出来之后过了给定的测试. 但是遇到比较大的输入样例就超时了, 不知道是环路了还是怎么样(理论上来讲给所有机票都加了used应该不会环路吧)

看了卡哥的思路才发现好像不用写那么麻烦hhh.

题解

自己的写法: (过了部分测试样例)

bool cmp(const vector<string> &a, const vector<string> &b) {
    for (int i = 0; i < b.size(); i++) {
        if (a[i] == b[i]) continue;
        return a[i] < b[i];
    }
    return false;
}

class Solution {
private:
    vector<vector<string>> possibleSolution;
    vector<string> path;
    int ticketUsed = 0;
    int totalTickets;
    void backtracing(vector<vector<string>> &tickets, vector<bool> &used, string airport) {
        if (ticketUsed == tickets.size()) {
            possibleSolution.push_back(path);
            return;
        }

        for (int i = 0; i < tickets.size(); i++) {
            if (tickets[i][0] == airport && !used[i]) {
                used[i] = true;
                ticketUsed++;
                path.push_back(tickets[i][1]);
                backtracing(tickets, used, tickets[i][1]);
                used[i] = false;
                ticketUsed--;
                path.pop_back();
            }
        }
    }

public:
    vector<string> findItinerary(vector<vector<string>>& tickets) {
        this -> totalTickets = tickets.size();
        vector<bool> used(tickets.size(), false);
        path.push_back("JFK");
        backtracing(tickets, used, "JFK");
        sort(possibleSolution.begin(), possibleSolution.end(), cmp);
        return possibleSolution[0];
    }
};

AC了的代码:

class Solution {
private:
    unordered_map<string, map<string, int>> targets;    // 使用这个结构来存储两个机场之间还剩几张机票, 后面使用map可以使得key按从小到大顺序存储, 不用再额外处理多个结果去字典排序最小的情况
    bool backtracing(int ticketNum, vector<string> &result) {
        if (result.size() == ticketNum + 1) {   // result个数等于机场票数+1时证明用完了所有机票, 保存结果
            return true;
        }

        for (pair<const string, int> &target : targets[result.back()]) { // 取当前机场出发的机票, 按目的地进行遍历
            if (target.second > 0) {    // 如果到一个目的地还有票没用完
                result.push_back(target.first); // 回溯法开始, 在路径中推入目的地
                target.second--;    // 没用过的票数-1
                if (backtracing(ticketNum, result)) return true;    // 如果纵向递归找到了答案, 就立刻返回
                result.pop_back();  // 否则回溯
                target.second++;
            }
        }
        return false;   // 没找到答案, 结束本层循环
    }


public:
    vector<string> findItinerary(vector<vector<string>>& tickets) {
        vector<string> result;
        for (const vector<string> &vec : tickets) { // 根据给定的机票处理来统计机场与机场之间的票数
            targets[vec[0]][vec[1]]++;
        }
        result.push_back("JFK");    // 按题目要求, 从"JFK"出发
        backtracing(tickets.size(), result);
        return result;
    }
};

51. N皇后

代码随想录链接

题目

LeetCode-51. N皇后

在一个\(n * n\)的棋盘里, 放入\(n\)个皇后, 要求同行同列以及同一斜线上不能存在其他皇后, 返回所有可能的摆放方式.

自己的想法

求所有可能的情况, 就很像是需要使用回溯法来解决的问题.

横向的for循环可以来确定一行上一个皇后应该摆放在哪里, 纵向的递归探索下一行, 且只当当前行摆放位置符合要求时, 才进行纵向递归.

题解

class Solution {
private: 
    vector<vector<string>> result;  // 保存所有可能的结果
    void backtracing(int n, int row, vector<string> &board) {
        if (row == n) {     // 纵向递归超过了最后一行, 证明前面行都被填写了, 保存结果并结束本次递归
            result.push_back(board);
            return;
        }

        for (int i = 0; i < n; i++) {   // for循环横向确定本行的皇后要放在哪里
            if (isPositionAvailable(row, i, n, board)) {    // 若遍历到的位置合适, 则进行纵向回溯递归
                board[row][i] = 'Q';
                backtracing(n, row + 1, board);
                board[row][i] = '.';
            }
        }
    }
    bool isPositionAvailable(int x, int y, int n, vector<string> &board) {  // 判断给定的位置是否符合摆放一个皇后的要求
        int curx = x, cury = y;
        while (--curx > -1 && --cury > -1) {    // 找左上方的斜线
            if (board[curx][cury] == 'Q') return false;
        }
        curx = x; cury = y;
        while (--curx > -1 && ++cury < n) {     // 找右上方的斜线
            if (board[curx][cury] == 'Q') return false;
        }
        curx = -1; cury = y;
        while (++curx < x) {                    // 找同一列
            if (board[curx][cury] == 'Q') return false;
        }
        return true;
        /**
         * 为啥不找左下和右下呢, 因为纵向递归还没走到那里, 还没填到那些位置
         */
    }
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<string> board(n, string(n, '.'));
        backtracing(n, 0, board);
        return result;
    }
};

37. 解数独

代码随想录链接

题目

LeetCode-37. 解数独

找到一种填充方式, 来解决数独问题.

自己的想法

求填充方法, 还是回溯法.

横向的for循环来确定一个空位上应该填什么, 纵向的递归来找下一个空位填数字, 同样是在填的合适的时候, 才填并进行递归的, 所以还需要一个函数来判断某个位置填一个数是否可行.

题解

class Solution {
    bool backtracing(vector<vector<char>> &board) {
        for (int i = 0; i < board.size(); i++) {
            for (int j = 0; j < board[0].size(); j++) { 
                if (board[i][j] == '.') {   // 找一个空位置
                    for (char c = '1'; c <= '9'; c++) { // 对这个空位置分别试图填进去不同的数字
                        if (isPlaceAvailable(i, j, c, board)) { // 如果一个数字填到这里合适的话, 就填入并进行递归
                            board[i][j] = c;
                            if (backtracing(board)) return true;    // 找到了一种解法的话就返回true, 停止搜索
                            board[i][j] = '.';
                        }
                    }
                    return false;   // 当前位置没找到合适的数, 返回false
                }
            }
        }
        return true;    // 所有位置都填完了, 返回true
    }

    bool isPlaceAvailable(int row, int col, char c, vector<vector<char>> &board) {  // 判断在一个位置上填一个数是否合适
        for (int i = 0; i < board[0].size(); i++)   // 横向找是否有相同的
            if (board[row][i] == c) return false;

        for (int i = 0; i < board.size(); i++)      // 纵向找是否有相同的
            if (board[i][col] == c) return false;
        
        int startCol = (col / 3) * 3;               // 计算给定的位置的3x3方块的左上方起始点
        int startRow = (row / 3) * 3;
        for (int i = startRow; i < startRow + 3; i++) // 判断在3x3方格内是否有相同的数
            for (int j = startCol; j < startCol + 3; j++)
                if (board[i][j] == c) return false;
        return true;
    }
public:
    void solveSudoku(vector<vector<char>>& board) {
        backtracing(board);
    }
};

回溯法总结

代码随想录链接

回溯法解决的问题主要有:

• 求组合
  • LeetCode-77.组合
  • LeetCode-17.电话号码的字母组合
  • LeetCode-39.组合总和
  • LeetCode-40.组合总和II
  • LeetCode-216.组合总和III
• 求排列
  • LeetCode-46.全排列
  • LeetCode-47.全排列 II
  • LeetCode-491.递增子序列
  • LeetCode-332.重新安排行程
• 求子集
  • LeetCode-78.子集
  • LeetCode-90.子集II
• 填充问题
  • LeetCode-37. 解数独
  • LeetCode-51. N皇后