复习搜索
复习:蛮力搜索的三种基本类型
复习:初级搜索
搜索树–三子棋
搜索树–围棋
剪枝
具有多项式时间算法的问题只是很少的一部分，更多的问题只能采用搜索的方式求解
蛮力搜索（或者说回溯）作为最原始的遍历状态空间的方法，本质上是试错
一个分支不可行，就需要取消上一步甚至前几步的计算，换个分支重新来过
在分支较多、较深的问题中，很容易导致复杂度为指数时间的运算
剪枝，就是通过已有的信息，提前判定某些分支不可行或一定不优，从而减少需要访问的状态数量形象地说就像剪去“搜索树”的枝条，所以叫剪枝
22.括号生成
https://leetcode.cn/problems/generate-parentheses/
class Solution { public: vector<string> generateParenthesis(int n) { if(n == 0) return {""}; if(store.find(n) != store.end()) return store[n]; vector<string> ans; for(int k=1;k<=n;k++) { vector<string> A = generateParenthesis(k-1); vector<string> B = generateParenthesis(n-k); for(string & a:A) { for(string & b:B) { ans.push_back("(" + a + ")" +b); } } } store[n]=ans; return ans; } private: unordered_map<int ,vector<string>> store; };
51.N皇后
https://leetcode.cn/problems/n-queens/
class Solution { public: vector<vector<string>> solveNQueens(int n) { this->n = n; used = vector<bool>(n, false); dfs(0); vector<vector<string>> result; for(vector<int>& p : ans) { vector<string> pattern(n , string(n, '.')); for(int row = 0; row < n; row++){ pattern[row][p[row]] = 'Q'; } result.push_back(pattern); } return result; } private: void dfs(int row) { if(row == n) { ans.push_back(p); return ; } for(int col = 0;col < n; col++){ if(!used[col] && !usedPlus[row + col] && !usedMinus[row - col]) { p.push_back(col); used[col] = true; usedPlus[row + col] = true; usedMinus[row - col] = true; dfs(row + 1); usedMinus[row - col] = false; usedPlus[row + col] = false; used[col] = false; p.pop_back(); } } } int n; vector<int> p; vector<bool> used; unordered_map<int, bool> usedPlus; unordered_map<int, bool> usedMinus; vector<vector<int>> ans; };
36.有效的数独
https://leetcode.cn/problems/valid-sudoku/
class Solution { public: bool isValidSudoku(vector<vector<char>>& board) { int rows[9][9]; int columns[9][9]; int subboxes[3][3][9]; memset(rows,0,sizeof(rows)); memset(columns,0,sizeof(columns)); memset(subboxes,0,sizeof(subboxes)); for (int i = 0; i < 9; i++) { for (int j = 0; j < 9; j++) { char c = board[i][j]; if (c != '.') { int index = c - '0' - 1; rows[i][index]++; columns[j][index]++; subboxes[i / 3][j / 3][index]++; if (rows[i][index] > 1 || columns[j][index] > 1 || subboxes[i / 3][j / 3][index] > 1) { return false; } } } } return true; } };
37.解数独
https://leetcode.cn/problems/sudoku-solver/
class Solution { private: int line[9]; int column[9]; int block[3][3]; bool valid; vector<pair<int, int>> spaces; public: void flip(int i, int j, int digit) { line[i] ^= (1 << digit); column[j] ^= (1 << digit); block[i / 3][j / 3] ^= (1 << digit); } void dfs(vector<vector<char>>& board, int pos) { if (pos == spaces.size()) { valid = true; return; } auto [i, j] = spaces[pos]; int mask = ~(line[i] | column[j] | block[i / 3][j / 3]) & 0x1ff; for (; mask && !valid; mask &= (mask - 1)) { int digitMask = mask & (-mask); int digit = __builtin_ctz(digitMask); flip(i, j, digit); board[i][j] = digit + '0' + 1; dfs(board, pos + 1); flip(i, j, digit); } } void solveSudoku(vector<vector<char>>& board) { memset(line, 0, sizeof(line)); memset(column, 0, sizeof(column)); memset(block, 0, sizeof(block)); valid = false; for (int i = 0; i < 9; ++i) { for (int j = 0; j < 9; ++j) { if (board[i][j] == '.') { spaces.emplace_back(i, j); } else { int digit = board[i][j] - '0' - 1; flip(i, j, digit); } } } dfs(board, 0); } };
class Solution { public: bitset<9> getPossibleStatus(int x, int y) { return ~(rows[x] | cols[y] | cells[x / 3][y / 3]); } vector<int> getNext(vector<vector<char>>& board) { vector<int> ret; int minCnt = 10; for (int i = 0; i < board.size(); i++) { for (int j = 0; j < board[i].size(); j++) { if (board[i][j] != '.') continue; auto cur = getPossibleStatus(i, j); if (cur.count() >= minCnt) continue; ret = { i, j }; minCnt = cur.count(); } } return ret; } void fillNum(int x, int y, int n, bool fillFlag) { rows[x][n] = (fillFlag) ? 1 : 0; cols[y][n] = (fillFlag) ? 1 : 0; cells[x/3][y/3][n] = (fillFlag) ? 1: 0; } bool dfs(vector<vector<char>>& board, int cnt) { if (cnt == 0) return true; auto next = getNext(board); auto bits = getPossibleStatus(next[0], next[1]); for (int n = 0; n < bits.size(); n++) { if (!bits.test(n)) continue; fillNum(next[0], next[1], n, true); board[next[0]][next[1]] = n + '1'; if (dfs(board, cnt - 1)) return true; board[next[0]][next[1]] = '.'; fillNum(next[0], next[1], n, false); } return false; } void solveSudoku(vector<vector<char>>& board) { rows = vector<bitset<9>>(9, bitset<9>()); cols = vector<bitset<9>>(9, bitset<9>()); cells = vector<vector<bitset<9>>>(3, vector<bitset<9>>(3, bitset<9>())); int cnt = 0; for (int i = 0; i < board.size(); i++) { for (int j = 0; j < board[i].size(); j++) { cnt += (board[i][j] == '.'); if (board[i][j] == '.') continue; int n = board[i][j] - '1'; rows[i] |= (1 << n); cols[j] |= (1 << n); cells[i / 3][j / 3] |= (1 << n); } } dfs(board, cnt); } private: vector<bitset<9>> rows; vector<bitset<9>> cols; vector<vector<bitset<9>>> cells; };
数独–剪枝
优先选择“能填的合法数字”最少的位置，而不是第一个位置
- 如果是人类来玩数独，策略一定是先填上“已经能够唯一确定的位置”，然后从那些填得比较
满、选项比较少的位置实施突破
快速判定数独有效性
- 对于每行、每列、每个九宫格，分别用一个9位bool数组保存哪些数字还可以填
- 对于一个位置，合并它所在行、列、九宫格的3个bool数组，就可以得到能填的数字
- 当一个位置填上某个数后，更新对应的行、列、九宫格bool数组，回溯时还原现场
迭代加深、折半搜索与双向搜索
BFS
双向BFS
迭代加深
折半搜索
单词接龙
127.单词接龙
https://leetcode.cn/problems/word-ladder/
class Solution { public: unordered_map<string, int> wordId; vector<vector<int>> edge; int nodeNum = 0; void addWord(string& word) { if (!wordId.count(word)) { wordId[word] = nodeNum++; edge.emplace_back(); } } void addEdge(string& word) { addWord(word); int id1 = wordId[word]; for (char& it : word) { char tmp = it; it = '*'; addWord(word); int id2 = wordId[word]; edge[id1].push_back(id2); edge[id2].push_back(id1); it = tmp; } } int ladderLength(string beginWord, string endWord, vector<string>& wordList) { for (string& word : wordList) { addEdge(word); } addEdge(beginWord); if (!wordId.count(endWord)) { return 0; } vector<int> dis(nodeNum, INT_MAX); int beginId = wordId[beginWord], endId = wordId[endWord]; dis[beginId] = 0; queue<int> que; que.push(beginId); while (!que.empty()) { int x = que.front(); que.pop(); if (x == endId) { return dis[endId] / 2 + 1; } for (int& it : edge[x]) { if (dis[it] == INT_MAX) { dis[it] = dis[x] + 1; que.push(it); } } } return 0; } };
class Solution { public: unordered_map<string, int> wordId; vector<vector<int>> edge; int nodeNum = 0; void addWord(string& word) { if (!wordId.count(word)) { wordId[word] = nodeNum++; edge.emplace_back(); } } void addEdge(string& word) { addWord(word); int id1 = wordId[word]; for (char& it : word) { char tmp = it; it = '*'; addWord(word); int id2 = wordId[word]; edge[id1].push_back(id2); edge[id2].push_back(id1); it = tmp; } } int ladderLength(string beginWord, string endWord, vector<string>& wordList) { for (string& word : wordList) { addEdge(word); } addEdge(beginWord); if (!wordId.count(endWord)) { return 0; } vector<int> disBegin(nodeNum, INT_MAX); int beginId = wordId[beginWord]; disBegin[beginId] = 0; queue<int> queBegin; queBegin.push(beginId); vector<int> disEnd(nodeNum, INT_MAX); int endId = wordId[endWord]; disEnd[endId] = 0; queue<int> queEnd; queEnd.push(endId); while (!queBegin.empty() && !queEnd.empty()) { int queBeginSize = queBegin.size(); for (int i = 0; i < queBeginSize; ++i) { int nodeBegin = queBegin.front(); queBegin.pop(); if (disEnd[nodeBegin] != INT_MAX) { return (disBegin[nodeBegin] + disEnd[nodeBegin]) / 2 + 1; } for (int& it : edge[nodeBegin]) { if (disBegin[it] == INT_MAX) { disBegin[it] = disBegin[nodeBegin] + 1; queBegin.push(it); } } } int queEndSize = queEnd.size(); for (int i = 0; i < queEndSize; ++i) { int nodeEnd = queEnd.front(); queEnd.pop(); if (disBegin[nodeEnd] != INT_MAX) { return (disBegin[nodeEnd] + disEnd[nodeEnd]) / 2 + 1; } for (int& it : edge[nodeEnd]) { if (disEnd[it] == INT_MAX) { disEnd[it] = disEnd[nodeEnd] + 1; queEnd.push(it); } } } } return 0; } };
推荐一个零声学院免费公开课程，个人觉得老师讲得不错，分享给大家：Linux，Nginx，ZeroMQ，MySQL，Redis，fastdfs，MongoDB，ZK，流媒体，CDN，P2P，K8S，Docker，TCP/IP，协程，DPDK等技术内容，立即学习
