1. 顺子刻子

  1. 题目：小包最近迷上了一款叫做雀魂的麻将游戏，但是这个游戏规则太复杂，小包玩了几个月了还是输多赢少。
  2. 于是生气的小包根据游戏简化了一下规则发明了一种新的麻将，只留下一种花色，并且去除了一些特殊和牌方式（例如七对子等），具体的规则如下：
  4. 1.总共有36张牌，每张牌是1~9。每个数字4张牌。
  5. 2.你手里有其中的14张牌，如果这14张牌满足如下条件，即算作和牌
  6. （1）14张牌中有2张相同数字的牌，称为雀头。
  7. （2）除去上述2张牌，剩下12张牌可以组成4个顺子或刻子。顺子的意思是递增的连续3个数字牌（例如234,567等），刻子的意思是相同数字的3个数字牌（例如111,777）
  9. 例如：
  10. 1 1 1 2 2 2 6 6 6 7 7 7 9 9 可以组成1,2,6,7的4个刻子和9的雀头，可以和牌
  11. 1 1 1 1 2 2 3 3 5 6 7 7 8 9 用1做雀头，组123,123,567,789的四个顺子，可以和牌
  12. 1 1 1 2 2 2 3 3 3 5 6 7 7 9 无论用1 2 3 7哪个做雀头，都无法组成和牌的条件。
  14. 现在，小包从36张牌中抽取了13张牌，他想知道在剩下的23张牌中，再取一张牌，取到哪几种数字牌可以和牌。
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  5. vector<int> card(9);
  7. //检查剩余的牌能否组成n个顺子或刻子
  8. bool hasTrible(int n){
  9.     if(n==0) return true;
  10.     for(int i=0; i<card.size(); ++i){
  11.         //因为仍是从1开始查验，因此若检查到其牌数>=3，则必定是刻子
  12.         if(card[i]>2){   
  13.             card[i] -= 3;
  14.             if(hasTrible(n-1)){   //检查余下的牌能否组成n-1个顺子或刻子
  15.                 card[i] += 3;
  16.                 return true;
  17.             }
  18.             card[i] += 3;
  19.         }
  20.         //否则只能是顺子
  21.         else if(i<card.size()-2 && card[i]>0 && card[i+1]>0 && card[i+2]>0){
  22.                 card[i]--;
  23.                 card[i+1]--;
  24.                 card[i+2]--;
  25.                 if(hasTrible(n-1)){
  26.                     card[i]++;
  27.                     card[i+1]++;
  28.                     card[i+2]++;
  29.                     return true;
  30.                 }
  31.                 card[i]++;
  32.                 card[i+1]++;
  33.                 card[i+2]++;
  34.         }
  35.     }
  36.     return false;
  37. }
  38. //检查14张牌能否和牌
  39. bool isWin(){
  40.     for(int i=0; i<9; ++i){  //依次把1~9作为雀头拿出来，检查剩下的12张牌能否顺或刻子
  41.         if(card[i]<2)
  42.             continue;
  43.         card[i] -= 2;
  44.         if(hasTrible(4)){    
  45.             card[i] += 2;
  46.             return true;
  47.         }
  48.         card[i] += 2;
  49.     }
  50.     return false;
  51. }
  53. int main(){
  54.     vector<int> res;
  55.     int tmp;
  56.     for(int i=0; i<13; ++i){
  57.         cin >> tmp;
  58.         card[tmp-1]++;
  59.     }
  60.     for(int i=0; i<9; ++i){  //1~9依次添加，检查是否可以和牌
  61.         if(card[i]>3)
  62.             continue;
  63.         card[i]++;
  64.         if(isWin())           //如果添加的这张牌可以和牌，则将其加入输出结果
  65.             res.push_back(i+1);
  66.         card[i]--;
  67.     }
  68.     if(res.empty()) res.push_back(0);
  69.     for(int i=0; i<res.size(); ++i)
  70.         cout << res[i] << ' ';
  71.     return 0;
  72. }

2. 八皇后进阶

  1. 题目：
  2. 设计一种算法，打印 N 皇后在 N × N 棋盘上的各种摆法，
  3. 其中每个皇后都不同行、不同列，也不在同一条对角线上。
  4. 这里的“对角线”指的是所有的对角线，不只是平分整个棋盘的那两条对角线。

算法思想：
为了判断一个位置所在的列和两条斜线上是否已经有皇后，使用三个集合 columns、diagonals1和diagonals2分别记录每一列以及两个方向的每条斜线上是否有皇后。

列的表示法很直观，一共有 NN 列，每一列的下标范围从 00 到 N-1N−1，使用列的下标即可明确表示每一列。

如何表示两个方向的斜线呢？对于每个方向的斜线，需要找到斜线上的每个位置的行下标与列下标之间的关系。
方向一的斜线为从左上到右下方向，同一条斜线上的每个位置满足行下标与列下标之差相等，例如 (0,0)(0,0) 和 (3,3)(3,3) 在同一条方向一的斜线上。因此使用行下标与列下标之差即可明确表示每一条方向一的斜线。方向二同理。
(BHWILO5SFGTJ9VO)ZUKJWY.png

  1. class Solution {
  2. public:
  3.     vector<vector<string>> solveNQueens(int n) {
  4.         auto solutions = vector<vector<string>>();
  5.         auto queens = vector<int>(n, -1);
  6.         auto columns = unordered_set<int>();
  7.         auto diagonals1 = unordered_set<int>();
  8.         auto diagonals2 = unordered_set<int>();
  9.         backtrack(solutions, queens, n, 0, columns, diagonals1, diagonals2);
  10.         return solutions;
  11.     }
  13.     void backtrack(vector<vector<string>> &solutions, vector<int> &queens, int n, int row, unordered_set<int> &columns, unordered_set<int> &diagonals1, unordered_set<int> &diagonals2) {
  14.         if (row == n) {
  15.             vector<string> board = generateBoard(queens, n);
  16.             solutions.push_back(board);
  17.         } else {
  18.             for (int i = 0; i < n; i++) {
  19.                 if (columns.find(i) != columns.end()) {
  20.                     continue;
  21.                 }
  22.                 int diagonal1 = row - i;
  23.                 if (diagonals1.find(diagonal1) != diagonals1.end()) {
  24.                     continue;
  25.                 }
  26.                 int diagonal2 = row + i;
  27.                 if (diagonals2.find(diagonal2) != diagonals2.end()) {
  28.                     continue;
  29.                 }
  30.                 queens[row] = i;
  31.                 columns.insert(i);
  32.                 diagonals1.insert(diagonal1);
  33.                 diagonals2.insert(diagonal2);
  34.                 backtrack(solutions, queens, n, row + 1, columns, diagonals1, diagonals2);
  35.                 queens[row] = -1;
  36.                 columns.erase(i);
  37.                 diagonals1.erase(diagonal1);
  38.                 diagonals2.erase(diagonal2);
  39.             }
  40.         }
  41.     }
  43.     vector<string> generateBoard(vector<int> &queens, int n) {
  44.         auto board = vector<string>();
  45.         for (int i = 0; i < n; i++) {
  46.             string row = string(n, '.');
  47.             row[queens[i]] = 'Q';
  48.             board.push_back(row);
  49.         }
  50.         return board;
  51.     }
  52. }
  55. My solution:(Better)
  56. class Solution {
  57. public:
  58.     vector<string> buffer;
  59.     string line;
  60.     vector<int> pos;
  61.     vector<int> Visit;
  62.     int N;
  63.     vector<vector<string> > res;
  65.     vector<vector<string>> solveNQueens(int n) {
  66.         if(n<=0) return res;
  67.         N = n;
  68.         pos.resize(n);
  69.         Visit.resize(n);
  71.         line = "";
  72.         for (int i = 0; i < N; i++) {
  73.             line += ".";
  74.             Visit[i] = 0;
  75.         }
  77.         find_res(0);
  79.         return res;
  80.     }
  82.     bool isValid(int i, int j) {
  83.         for (int x = 0; x < i; x++) {
  84.             if (abs(x - i) == abs(pos[x] - j))  //good, but time cost:O(n)
  85.                 return false;
  86.         }
  87.         return true;
  88.     }
  90.     void find_res(int index) {
  91.         if (index == N) {
  92.             res.push_back(buffer);
  93.             return ;
  94.         }
  96.         for (int i = 0; i < N; i++) {
  97.             if (Visit[i] || !isValid(index, i) ) continue;
  98.             Visit[i] = 1;
  100.             line[i] = 'Q';
  101.             buffer.push_back(line); //good!
  102.             line[i] = '.';
  104.             pos[index] = i;
  106.             find_res(index + 1);
  108.             buffer.pop_back();
  109.             Visit[i] = 0;
  110.         }
  112.     }
  113. };

3. 搜索——矩阵上的单词搜索

给定一个二维网格和一个单词，找出该单词是否存在于网格中。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例:
board =
[
[‘A’,’B’,’C’,’E’],
[‘S’,’F’,’C’,’S’],
[‘A’,’D’,’E’,’E’]
]
给定 word = “ABCCED”, 返回 true
给定 word = “SEE”, 返回 true
给定 word = “ABCB”, 返回 false

  1. class Solution {
  2. public:
  3.     bool check(vector<vector<char>>& board, vector<vector<int>>& visited, int i, int j, string& s, int k) {
  4.         if (board[i][j] != s[k]) {
  5.             return false;
  6.         } else if (k == s.length() - 1) {
  7.             return true;
  8.         }
  9.         visited[i][j] = true;
  10.         vector<pair<int, int>> directions{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
  11.         bool result = false;
  12.         for (const auto& dir: directions) {
  13.             int newi = i + dir.first, newj = j + dir.second;
  14.             if (newi >= 0 && newi < board.size() && newj >= 0 && newj < board[0].size()) {
  15.                 if (!visited[newi][newj]) {
  16.                     bool flag = check(board, visited, newi, newj, s, k + 1);
  17.                     if (flag) {
  18.                         result = true;
  19.                         break;
  20.                     }
  21.                 }
  22.             }
  23.         }
  24.         visited[i][j] = false;
  25.         return result;
  26.     }
  28.     bool exist(vector<vector<char>>& board, string word) {
  29.         int h = board.size(), w = board[0].size();
  30.         vector<vector<int>> visited(h, vector<int>(w));
  31.         for (int i = 0; i < h; i++) {
  32.             for (int j = 0; j < w; j++) {
  33.                 bool flag = check(board, visited, i, j, word, 0);
  34.                 if (flag) {
  35.                     return true;
  36.                 }
  37.             }
  38.         }
  39.         return false;
  40.     }
  41. };
  45. # mysolution:
  46. class Solution {
  47. private:
  48.     int  n,m;
  49. public:
  50.     bool exist(vector<vector<char>>& board, string word) {
  51.         n=board.size();
  52.         m=board[0].size();
  53.         vector<vector<bool>> visited(n,vector<bool>(m,false) );
  55.         for(int i=0;i<n;i++){
  56.             for(int j=0;j<m;j++){
  57.                 if(backtrace(i,j,word,0,board,visited)){
  58.                     return true;
  59.                 }
  60.             }
  61.         }
  62.         return false;
  63.     }
  65.     bool backtrace(int i,int j,string word,int k,vector<vector<char>> board,vector<vector<bool>> &visited)    {
  66.         std::cout<< "[" <<i <<","<<j <<"]" << ","<< k <<endl;
  67.         if(board[i][j] != word[k]) return false;
  68.         else if(k == word.length()-1) return true;
  70.         bool flag = false;
  71.         if(j>=1 && !visited[i][j-1]){
  72.             visited[i][j] = true;
  73.             flag = backtrace(i,j-1,word,k+1,board,visited);
  74.             visited[i][j] = false;
  75.             if(flag) return true;
  76.         } 
  77.         if(j<m-1 && !visited[i][j+1]){
  78.             visited[i][j] = true;
  79.             flag = backtrace(i,j+1,word,k+1,board,visited);
  80.             visited[i][j] = false;
  81.             if(flag) return true;
  82.         } 
  83.         if(i>=1 && !visited[i-1][j]){
  84.             visited[i][j] = true;
  85.             flag = backtrace(i-1,j,word,k+1,board,visited);
  86.             visited[i][j] = false;
  87.             if(flag) return true;
  88.         } 
  89.         if(i<n-1 && !visited[i+1][j]){
  90.             visited[i][j] = true;
  91.             flag = backtrace(i+1,j,word,k+1,board,visited);
  92.             visited[i][j] = false;
  93.             if(flag) return true;
  94.         }
  95.         return false;
  96.     }
  97. };

4. 无重复子集

给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。
示例:
输入: [1,2,2]
输出:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]

算法核心：
1RTAA8%JFZSVE~(C7C}]H%3.png**

  1. 排序
  2. 同层不重复判断.
  3. 每次循环起始位置为start…n-1而不是0…n-1 ```cpp class Solution { private: vector> result; vector path; //注意：此处的use用来规范同层的行为，而不是子孙的行为。 void backtracking(vector& nums, int startIndex, vector& used) {
    1.  result.push_back(path);
    2.  for (int i = startIndex; i < nums.size(); i++) {
    3.      // used[i - 1] == true，说明同一树支candidates[i - 1]使用过
    4.      // used[i - 1] == false，说明同一树层candidates[i - 1]使用过
    5.      // 而我们要对同一树层使用过的元素进行跳过
    6.      if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
    7.          continue;
    8.      }
    9.      path.push_back(nums[i]);
    10.      used[i] = true;
    11.      backtracking(nums, i + 1, used);
    12.      used[i] = false;
    13.      path.pop_back();
    14.  }
    }

public: vector> subsetsWithDup(vector& nums) { result.clear(); path.clear(); vector used(nums.size(), false); sort(nums.begin(), nums.end()); // 去重需要排序 backtracking(nums, 0, used); return result; } };

去重改进1：不用used数组，使用set { … unordered_set uset; for (int i = startIndex; i < nums.size(); i++) { if (uset.find(nums[i]) != uset.end()) { continue; } uset.insert(nums[i]); path.push_back(nums[i]); backtracking(nums, i + 1); path.pop_back(); } … } 去重改进2：不用used数组，也不用set if (i > startIndex && nums[i] == nums[i - 1] ) { continue; }

  2. <a name="RMVuP"></a>
  3. # 5. 分割——[分割回文串](https://leetcode-cn.com/problems/palindrome-partitioning/)
  5. 给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。<br />返回 s 所有可能的分割方案。<br />**示例:**<br />**输入:** "aab"<br />**输出:**<br />[<br />  ["aa","b"],<br />  ["a","a","b"]<br />]
  6. ```cpp
  7. class Solution {
  8. public:
  9.     vector<vector<string>> partition(string s) {
  10.         vector<vector<string>> res;
  11.         vector<string> tmp;
  12.         backtrace(0,s,tmp,res);
  13.         return res;
  14.     }
  16.     void backtrace(int i, string s, vector<string> &tmp, vector<vector<string>> &res){
  17.         int n = s.length();
  18.         if(i==n){
  19.             res.push_back(tmp);
  20.         }
  21.         for(int j=i+1;j<=n;j++){
  22.             string xs = s.substr(i,j-i);
  23.             if(is_symmetry(xs)){
  24.                 tmp.push_back(xs);
  25.                 backtrace(j,s,tmp,res);
  26.                 tmp.pop_back();
  27.             }
  28.         }
  29.     }
  31.     bool is_symmetry(string s){
  32.         int n= s.length();
  33.         //std::cout<<s;
  34.         for(int i=0;i<n/2;i++){
  35.             if(s[i] != s[n-i-1]){
  36.                 //std::cout<< "false" <<endl;
  37.                 return false;
  38.             }
  39.         }
  40.         //std::cout<< "true" <<endl;
  41.         return true;
  42.     }
  43. };
  46. //优化：使用动态规划提前计算回文串: 
  47. //dp[i][j] = true when a[i] == a[j] && (j-i<=2 || dp[i+1][j-1]==true)