day30 | 回溯6

0.引言

● 332.重新安排行程
● 51. N皇后
● 37. 解数独

332.# 重新安排行程

Category	Difficulty	Likes	Dislikes
algorithms	Hard (47.53%)	757	-

给你一份航线列表 tickets ，其中 tickets[i] = [fromi, toi] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。

所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。如果存在多种有效的行程，请你按字典排序返回最小的行程组合。

例如，行程 ["JFK", "LGA"] 与 ["JFK", "LGB"] 相比就更小，排序更靠前。

假定所有机票至少存在一种合理的行程。且所有的机票必须都用一次且只能用一次。

示例 1：

image.png

输入：tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]
输出：["JFK","MUC","LHR","SFO","SJC"]

示例 2：

image.png

输入：tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
输出：["JFK","ATL","JFK","SFO","ATL","SFO"]
解释：另一种有效的行程是 ["JFK","SFO","ATL","JFK","ATL","SFO"] ，但是它字典排序更大更靠后。

提示：

1 <= tickets.length <= 300
tickets[i].length == 2
fromi.length == 3
toi.length == 3
fromi 和 toi 由大写英文字母组成
fromi != toi

Discussion | Solution

回溯

这个数据结构设计很巧妙：

// unordered_map<出发机场, map<到达机场, 航班次数>> targets
unordered_map<string, map<string, int>> targets;

cover了 [A-->B, A-->B] 这种重复的情况。

/*
 * @lc app=leetcode.cn id=332 lang=cpp
 *
 * [332] 重新安排行程
 */

// @lc code=start
class Solution {
 public:
  vector<string> findItinerary(vector<vector<string>>& tickets) {
    // unordered_map<出发机场, map<到达机场, 航班次数>> targets
    std::unordered_map<std::string, std::map<std::string, int>> targets;
    for (const auto& ticket : tickets) {
      // targets[ticket[0]] --> std::map<string, int>
      targets[ticket[0]][ticket[1]]++;
    }
    std::vector<std::string> res;
    res.push_back("JFK");
    dfs(tickets.size(), targets, res);
    return res;
  }

 private:
  // bool找到满足条件的一种解即可
  bool dfs(int tickets_size,
           std::unordered_map<std::string, std::map<std::string, int>>& targets,
           std::vector<std::string>& res) {
    // 1.终止条件
    if (res.size() == tickets_size + 1) {
      return true;
    }
    // 已知出发地（res的最后一个元素），遍历目的地：
    // A-->{B,1}、 A-->{C,2}，已知A,遍历{B,1}、{C,2}
    for (auto& target : targets[res[res.size() - 1]]) {
      // 已经用过这张票
      if (target.second <= 0) continue;
      target.second--;
      res.push_back(target.first);
      if (dfs(tickets_size, targets, res)) return true;
      res.pop_back();
      target.second++;
    }
    return false;
  }
};
// @lc code=end

51. # N 皇后

Category	Difficulty	Likes	Dislikes
algorithms	Hard (74.21%)	1703	-

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

示例 1：

image.png

输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释：如上图所示，4 皇后问题存在两个不同的解法。

示例 2：

输入：n = 1
输出：[["Q"]]

提示：

1 <= n <= 9

Discussion | Solution

回溯法

/*
 * @lc app=leetcode.cn id=51 lang=cpp
 *
 * [51] N 皇后
 */

// @lc code=start
class Solution {
 public:
  vector<vector<string>> solveNQueens(int n) {
    std::vector<string> queen;             // 存储皇后的位置
    std::vector<std::vector<int>> attack;  // attack标记皇后攻击的位置
    std::vector<std::vector<string>> res;  // 最后的结果

    for (int i = 0; i < n; i++) {
      attack.push_back(std::vector<int>());  // 少定义一个变量
      for (int j = 0; j < n; j++) {
        attack[i].push_back(0);
      }
      queen.push_back("");
      queen[i].append(n, '.');
    }

    backtrack(0, n, queen, attack, res);
    return res;
  }

 private:
  void put_queen(int x, int y, std::vector<std::vector<int>>& attack) {
    static const int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1};  // 八个方向
    static const int dy[] = {-1, 0, 1, -1, 1, -1, 0, 1};
    attack[x][y] = 1;
    int n = attack[0].size();
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < 8; j++) {
        int tmp_x = x + i * dx[j];
        int tmp_y = y + i * dy[j];
        // 坐标在棋盘内
        if (0 <= tmp_x && tmp_x < n && 0 <= tmp_y && tmp_y < n) {
          attack[tmp_x][tmp_y] = 1;
        }
      }
    }
  }

  // 大的递归是按行进行
  void backtrack(
      int k,                                  // 当前处理的行
      int n,                                  // N皇后中的N
      std::vector<string>& queen,             // 存储皇后的位置
      std::vector<std::vector<int>>& attack,  // attack标记皇后攻击的位置
      std::vector<std::vector<string>>& res) {
    if (k == n) {
      res.push_back(queen);
      return;
    }
    // 遍历 0 至 n-1 列，在循环中，回溯试探皇后可以放置的位置
    for (int i = 0; i < n; i++) {
      // 判断是否可以放皇后，如果k行所有列都满了，backtrack执行完由栈递归返回
      if (attack[k][i] == 0) {
        std::vector<std::vector<int>> tmp = attack;  // 备份attack数组
        queen[k][i] = 'Q';                           // 标记皇后位置
        put_queen(k, i, attack);                     // 更新attack
        // 递归试探 k+1 行的皇后放置位置回溯回来， 恢复状态
        backtrack(k + 1, n, queen, attack, res);
        attack = tmp;       // 恢复attack数组
        queen[k][i] = '.';  // 恢复queen数组
      }
    }
  }
};
// @lc code=end

37. # 解数独

Category	Difficulty	Likes	Dislikes
algorithms	Hard (67.61%)	1584	-

编写一个程序，通过填充空格来解决数独问题。

数独的解法需** 遵循如下规则**：

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

数独部分空格内已填入了数字，空白格用 '.' 表示。

示例 1：

image.png

输入：board =
 [["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"]]
输出：
[["5","3","4","6","7","8","9","1","2"],
["6","7","2","1","9","5","3","4","8"],
["1","9","8","3","4","2","5","6","7"],
["8","5","9","7","6","1","4","2","3"],
["4","2","6","8","5","3","7","9","1"],
["7","1","3","9","2","4","8","5","6"],
["9","6","1","5","3","7","2","8","4"],
["2","8","7","4","1","9","6","3","5"],
["3","4","5","2","8","6","1","7","9"]]
解释：输入的数独如上图所示，唯一有效的解决方案如下所示：

image.png

提示：

board.length == 9
board[i].length == 9
board[i][j] 是一位数字或者 '.'
题目数据保证输入数独仅有一个解

Discussion | Solution

回溯法

/*
 * @lc app=leetcode.cn id=37 lang=cpp
 *
 * [37] 解数独
 */

// @lc code=start
class Solution {
 public:
  void solveSudoku(vector<vector<char>>& board) {
    dfs(board);
  }

 private:
  bool dfs(std::vector<std::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 k = '1'; k <= '9'; k++) {  // (i, j) 这个位置放k是否合适
            if (is_valid(i, j, k, board)) {
              board[i][j] = k;                       // 放置k
              if (dfs(board)) return true;  // 如果找到合适一组立刻返回
              board[i][j] = '.';                     // 回溯，撤销k
            }
          }
          return false;  // 9个数都试完了，都不行，那么就返回false
        }
      }
    }
    return true;  // 遍历完没有返回false，说明找到了合适棋盘位置了
  }

  bool is_valid(int row, int col, char val,
                std::vector<std::vector<char>>& board) {
    for (int i = 0; i < 9; i++) {  // 判断行里是否重复
      if (board[row][i] == val) {
        return false;
      }
    }
    for (int j = 0; j < 9; j++) {  // 判断列里是否重复
      if (board[j][col] == val) {
        return false;
      }
    }
    int startRow = (row / 3) * 3;
    int startCol = (col / 3) * 3;
    for (int i = startRow; i < startRow + 3; i++) {  // 判断9方格里是否重复
      for (int j = startCol; j < startCol + 3; j++) {
        if (board[i][j] == val) {
          return false;
        }
      }
    }
    return true;
  }
};

day30 | 回溯6

0.引言

332.# 重新安排行程

回溯

51. # N 皇后

回溯法

37. # 解数独

回溯法

推荐阅读更多精彩内容