6.3 回溯法
dfs(matrix, can_reach_p, i, 0);
dfs(matrix, can_reach_a, i, n - 1);
} for (int i = 0; i < n; ++i) {
dfs(matrix, can_reach_p, 0, i);
dfs(matrix, can_reach_a, m - 1, i);
} for (int i = 0; i < m; i++) {
for (int j = 0; j < n; ++j) { if (can_reach_p[i][j] && can_reach_a[i][j]) {
ans.push_back(vector<int>{i, j});
} }
} return ans;
}
// void dfs(const vector<vector<int>>& matrix, vector<vector<bool>>& can_reach,
int r, int c) { if (can_reach[r][c]) {
return;
} can_reach[r][c] = true;
int x, y;
for (int i = 0; i < 4; ++i) { x = r + direction[i], y = c + direction[i+1];
if (x >= 0 && x < matrix.size()
&& y >= 0 && y < matrix[0].size() && matrix[r][c] <= matrix[x][y]) {
dfs(matrix, can_reach, x, y);
} }
}
6.3
backtracking
[]![ ][]![]![
]
46. Permutations (Medium)
Input: [1,2,3] Output: [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]
i i+1
i
[1,2,3][[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]
// vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> ans;
backtracking(nums, 0, ans);
return ans;
}
// void backtracking(vector<int> &nums, int level, vector<vector<int>> &ans) {
if (level == nums.size() - 1) { ans.push_back(nums);
return;
} for (int i = level; i < nums.size(); i++) {
swap(nums[i], nums[level]); // backtracking(nums, level+1, ans); //
swap(nums[i], nums[level]); // }
}
77. Combinations (Medium)
nk1nk
nk
Input: n = 4, k = 2 Output: [[2,4], [3,4], [2,3], [1,2], [1,3], [1,4]]
// vector<vector<int>> combine(int n, int k) {
vector<vector<int>> ans;
vector<int> comb(k, 0);
int count = 0;
backtracking(ans, comb, count, 1, n, k);
return ans;
}
// void backtracking(vector<vector<int>>& ans, vector<int>& comb, int& count, int
pos, int n, int k) { if (count == k) {
ans.push_back(comb);
return;
} for (int i = pos; i <= n; ++i) {
comb[count++] = i; // backtracking(ans, comb, count, i + 1, n, k); //
--count; // }
}
79. Word Search (Medium)
Input: word = "ABCCED", board = [[’A’,’B’,’C’,’E’],
[’A’,’D’,’E’,’E’]] Output: true
’A’"ABCCED"
// bool exist(vector<vector<char>>& board, string word) {
if (board.empty()) return false;
int m = board.size(), n = board[0].size();
vector<vector<bool>> visited(m, vector<bool>(n, false));
bool find = false;
for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) {
backtracking(i, j, board, word, find, visited, 0);
} }
return find;
}
// void backtracking(int i, int j, vector<vector<char>>& board, string& word, bool
& find, vector<vector<bool>>& visited, int pos) { if (i < 0 || i >= board.size() || j < 0 || j >= board[0].size()) {
return;
} if (visited[i][j] || find || board[i][j] != word[pos]) {
return;
} if (pos == word.size() - 1) {
find = true;
return;
} visited[i][j] = true; //
// backtracking(i + 1, j, board, word, find, visited, pos + 1);
backtracking(i - 1, j, board, word, find, visited, pos + 1);
backtracking(i, j + 1, board, word, find, visited, pos + 1);
backtracking(i, j - 1, board, word, find, visited, pos + 1);
visited[i][j] = false; // }
51. N-Queens (Hard)
nn

6.1:51 -
n
Input: 4 Output: [
[".Q..", // Solution 1 "...Q",
"Q...", "..Q."],
["..Q.", // Solution 2 "Q...",
"...Q", ".Q.."]
]
Q
nn
// vector<vector<string>> solveNQueens(int n) {
vector<vector<string>> ans;
if (n == 0) { return ans;
全站分卷索引 · 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 后记