LeetCode之搜索专题

1.回溯算法

1.LeetCode之[N皇后问题]

• 解题思路

  • 回溯算法之递归

    https://labuladong.gitee.io/algo/4/29/105/

  • 回溯算法之非递归

    https://blog.csdn.net/computerme/article/details/18080031

• 代码实现

  1.递归解法（回溯方法基本套路）

  /*
   * @lc app=leetcode.cn id=51 lang=cpp
   *
   * [51] N 皇后
   */
  
  // @lc code=start
  class Solution {
  public:
      vector<vector<string>> res;
  
      vector<vector<string>> solveNQueens(int n) {
          vector<string> board(n, string(n, '.'));
          backtrace(board, 0);
          return res;
      }
  
      void backtrace(vector<string> &board, int row) {
          if (row == board.size()) {
              res.push_back(board);
              return;
          }
  
          int n = board[row].size();
          for (int col = 0; col < n; col++) {
              if (!isValid(board, row, col)) {
                  continue;
              }
              board[row][col] = 'Q';
              backtrace(board, row + 1);
              board[row][col] = '.';
          }
      }
  
      //是否能在board[row][col]放置皇后
      bool isValid(vector<string> &board, int row,int col) {
          int n = board.size();
  
          //检查列是否有皇后冲突
          for (int i = 0; i < n; i++) {
              if (board[i][col] == 'Q') {
                  return false;
              }
          }
  
          //检查右上方是否有冲突
          for (int i = row - 1, j = col + 1; i >= 0 && j < board[0].size(); i--, j++) {
              if (board[i][j] == 'Q') {
                  return false;
              }
          }
  
          //检查左上方是否有皇后冲突
          for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--,j--) {
              if (board[i][j] == 'Q') {
                  return false;
              }
          }
          return true;
      }
  };
  // @lc code=end
  

  2.非递归解法(回溯方法)

  class Solution {
  public:
  
      vector<vector<string>> res;
      int a[10];
  
      vector<vector<string>> solveNQueens(int n) {
          vector<string> nums(n,string(n,'.'));
          int k = 0;
          a[k] = 0;
          while (k >= 0) {
              if (k < n && a[k] < n) {
                  if (isValid(nums, k ,a[k])) {
                      nums[k][a[k]] = 'Q';
                      k++;
                      a[k] = 0;
                  } else {
                      a[k]++;
                  }
              } else {
                  if (k >= n) {
                      res.push_back(nums);
                  }
                  k--;
                  if (k < 0) break;
                  nums[k][a[k]] = '.';
                  a[k]++;
              }
          }
          return res;
      }
  
      bool isValid(vector<string> &board, int row, int col) {
          int n = board.size();
  
          //检查列是否有皇后冲突
          for (int i = 0; i < n; i++) {
              if (board[i][col] == 'Q') {
                  return false;
              }
          }
  
          //检查右上方是否有冲突
          for (int i = row - 1, j = col + 1; i >= 0 && j < board[0].size(); i--, j++) {
              if (board[i][j] == 'Q') {
                  return false;
              }
          }
  
          //检查左上方是否有皇后冲突
          for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--,j--) {
              if (board[i][j] == 'Q') {
                  return false;
              }
          }
          return true;
      }
  };
  

2.LeetCode之46全排列问题

• 解题思路

  • 采用回溯算法（递归）

    https://mp.weixin.qq.com/s/qT6WgR6Qwn7ayZkI3AineA

  • 采用交换元素的方法，也用到递归思想

  • 回溯非递归算法

    模仿上述N皇后非递归算法

• 代码实现

  1.回溯算法之递归

  /*
   * @lc app=leetcode.cn id=46 lang=cpp
   *
   * [46] 全排列
   */
  
  // @lc code=start
  class Solution {
  public:
      vector<vector<int>> res;
  
      vector<vector<int>> permute(vector<int>& nums) {
          vector<int> track;
          backtrace(nums, track);
          return res;
      }
  
      void backtrace(vector<int> nums, vector<int> track) {
          if(track.size() == nums.size()) {
              res.push_back(track);
              return;
          }
  
          for (int i = 0; i < nums.size(); i++) {
              if (find_element(track, nums[i])) {
                  continue;
              }
              track.push_back(nums[i]);
              backtrace(nums, track);
              track.pop_back();
          }
      }
  
      bool find_element(vector<int> num, int n) {
          for (const auto & d : num) {
              if(n == d) return true;
          }
          return false;
      }
  };
  // @lc code=end
  

  2.交换元素之递归

  class Solution {
  public:
      vector<vector<int>> res;
  
      vector<vector<int>> permute(vector<int>& nums) {
          int left = 0, right = nums.size() - 1;
          fullArr(nums, left, right);
          return res;
      }
  
      void fullArr(vector<int> &nums, int left, int right) {
          if (left == right) {
              res.push_back(nums);
              return;
          }
  
          for (int i = left; i <= right; i++) {
              swap(nums, left, i);
              fullArr(nums, left + 1, right);
              swap(nums, left, i);
          }
      }
  
      void swap(vector<int> &nums, int i, int j) {
          int temp = nums[i];
          nums[i] = nums[j];
          nums[j] = temp;
      }
  };
  

  3.回溯非递归算法

  class Solution {
  public:
      vector<vector<int>> res;
      int a[7] = { 0 };
  
      void swap(vector<int>& nums, int i, int j) {
          int temp = nums[i];
          nums[i] = nums[j];
          nums[j] = temp;
      }
  
      bool isValid(vector<int>& nums, int n) {
          for (const auto& d : nums) {
              if (d == n) return false;
          }
          return true;
      }
  
      vector<vector<int>> permute(vector<int>& nums) {
          vector<int> temp;
          int len = nums.size();
          int k = 0;
          while (k >= 0) {
              if (k < len && a[k] < len) {
                  if (isValid(temp, nums[a[k]])) {
                      temp.push_back(nums[a[k]]);
                      k++;
                      a[k] = 0;
                  }
                  else {
                      a[k]++;
                  }
              }
              else {
                  if (k == len) {
                      res.push_back(temp);
                  }
                  k--;
                  if (k < 0) break;
                  temp.pop_back();
                  a[k]++;
              }
          }
          return res;
      }
  };