6.4 广度优先搜索
vector<string> board(n, string(n, ’.’));
vector<bool> column(n, false), ldiag(2*n-1, false), rdiag(2*n-1, false);
backtracking(ans, board, column, ldiag, rdiag, 0, n);
return ans;
}
// void backtracking(vector<vector<string>> &ans, vector<string> &board, vector<
bool> &column, vector<bool> &ldiag, vector<bool> &rdiag, int row, int n) { if (row == n) {
ans.push_back(board);
return;
} for (int i = 0; i < n; ++i) {
if (column[i] || ldiag[n-row+i-1] || rdiag[row+i+1]) { continue;
} //
board[row][i] = ’Q’;
column[i] = ldiag[n-row+i-1] = rdiag[row+i+1] = true;
// backtracking(ans, board, column, ldiag, rdiag, row+1, n);
// board[row][i] = ’.’;
column[i] = ldiag[n-row+i-1] = rdiag[row+i+1] = false;
} }
6.4
breadth-first search BFS
1 [1]->[2->3]->[4]
1 / \
23 /
4
934. Shortest Bridge (Medium)
0-110
Input:
[[1,1,1,1,1], [1,0,0,0,1],
[1,0,1,0,1], [1,0,0,0,1],
[1,1,1,1,1]] Output: 1
vector<int> direction{-1, 0, 1, 0, -1};
// int shortestBridge(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
queue<pair<int, int>> points;
// dfs12 bool flipped = false;
for (int i = 0; i < m; ++i) { if (flipped) break;
for (int j = 0; j < n; ++j) { if (grid[i][j] == 1) {
dfs(points, grid, m, n, i, j);
flipped = true;
break;
} }
} // bfs02
int x, y;
int level = 0;
while (!points.empty()){ ++level;
int n_points = points.size();
while (n_points--) { auto [r, c] = points.front();
points.pop();
for (int k = 0; k < 4; ++k) { x = r + direction[k], y = c + direction[k+1];
if (x >= 0 && y >= 0 && x < m && y < n) {
continue;
} if (grid[x][y] == 1) {
return level;
} points.push({x, y});
grid[x][y] = 2;
} }
} }
return 0;
}
// void dfs(queue<pair<int, int>>& points, vector<vector<int>>& grid, int m, int n
, int i, int j) { if (i < 0 || j < 0 || i == m || j == n || grid[i][j] == 2) {
return;
} if (grid[i][j] == 0) {
points.push({i, j});
return;
} grid[i][j] = 2;
dfs(points, grid, m, n, i - 1, j);
dfs(points, grid, m, n, i + 1, j);
dfs(points, grid, m, n, i, j - 1);
dfs(points, grid, m, n, i, j + 1);
}
126. Word Ladder II (Hard)
Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output:
[["hit","hot","dot","dog","cog"], ["hit","hot","lot","log","cog"]]
4 41 + 2 + 4 + 8 + 16 = 31
2 ¹1 + 2 + 4º = 14
// vector<vector<string>> findLadders(string beginWord, string endWord, vector<
string>& wordList) { vector<vector<string>> ans;
unordered_set<string> dict;
for (const auto &w: wordList){ dict.insert(w);
} if (!dict.count(endWord)) {
return ans;
} dict.erase(beginWord);
dict.erase(endWord);
unordered_set<string> q1{beginWord}, q2{endWord};
unordered_map<string, vector<string>> next;
bool reversed = false, found = false;
while (!q1.empty()) { unordered_set<string> q;
for (const auto &w: q1) { string s = w;
for (size_t i = 0; i < s.size(); i++) { char ch = s[i];
for (int j = 0; j < 26; j++) { s[i] = j + ’a’;
if (q2.count(s)) { reversed? next[s].push_back(w): next[w].push_back(s);
found = true;
} if (dict.count(s)) {
reversed? next[s].push_back(w): next[w].push_back(s);
q.insert(s);
} }
s[i] = ch;
} }
if (found) { break;
for (const auto &w: q) { dict.erase(w);
全站分卷索引 · 68 卷
- 11 题目分类
- 22 最易懂的贪心算法
- 32.3 区间问题
- 42.4 练习
- 53 玩转双指针
- 63.2 Two Sum
- 73.4 快慢指针
- 83.5 滑动窗口
- 93.6 练习
- 104 居合斩!二分查找
- 114.3 查找区间
- 124.4 旋转数组查找数字
- 134.5 练习
- 145 千奇百怪的排序算法
- 155.2 快速选择
- 165.3 桶排序
- 175.4 练习
- 186 一切皆可搜索
- 196.3 回溯法
- 206.4 广度优先搜索
- 216.5 练习
- 227 深入浅出动态规划
- 237.3 基本动态规划:二维
- 247.4 分割类型题
- 257.5 子序列问题
- 267.6 背包问题
- 277.7 字符串编辑
- 287.8 股票交易
- 297.9 练习
- 308 化繁为简的分治法
- 318.3 练习
- 329 巧解数学问题
- 339.4 数字处理
- 349.5 随机与取样
- 359.6 练习
- 3610 神奇的位运算
- 3710.3 二进制特性
- 3810.4 练习
- 3911 妙用数据结构
- 4011.2 数组
- 4111.3 栈和队列
- 4211.4 单调栈
- 4311.5 优先队列
- 4411.6 双端队列
- 4511.7 哈希表
- 4611.8 多重集合和映射
- 4711.9 前缀和与积分图
- 4811.10 练习
- 11.10
- 566. Reshape the Matrix (Easy)
- 225. Implement Stack using Queues (Easy)
- 503. Next Greater Element II (Medium)
- 217. Contains Duplicate (Easy)
- 697. Degree of an Array (Easy)
- 594. Longest Harmonious Subsequence (Easy)
- 287. Find the Duplicate Number (Medium)
- 313. Super Ugly Number (Medium)
- 870. Advantage Shuffle (Medium)
- 307. Range Sum Query - Mutable (Medium)
- 4912 令人头大的字符串
- 5012.3 字符串理解
- 5112.4 字符串匹配
- 5212.5 练习
- 5313 指针三剑客之一:链表
- 5413.3 其它链表技巧
- 5513.4 练习
- 5614 指针三剑客之二:树
- 5714.3 层次遍历
- 5814.4 前中后序遍历
- 5914.5 二叉查找树
- 6014.6 字典树
- 6114.7 练习
- 14.7
- 226. Invert Binary Tree (Easy)
- 617. Merge Two Binary Trees (Easy)
- 572. Subtree of Another Tree (Easy)
- 404. Sum of Left Leaves (Easy)
- 513. Find Bottom Left Tree Value (Easy)
- 538. Convert BST to Greater Tree (Easy)
- 235. Lowest Common Ancestor of a Binary Search Tree (Easy)
- 530. Minimum Absolute Difference in BST (Easy)
- 889. Construct Binary Tree from Preorder and Postorder Traversal (Medium)
- 106. Construct Binary Tree from Inorder and Postorder Traversal (Medium)
- 94. Binary Tree Inorder Traversal (Medium)
- 6215 指针三剑客之三:图
- 6315.3 拓扑排序
- 6415.4 练习
- 6516 更加复杂的数据结构
- 6616.3 复合数据结构
- 6716.4 练习
- 6817 后记