算法闭关修炼百题计划（五）
前进、进步
- 1.单词搜索
- 2.将有序数组转换为二叉搜索树
- 3.路径总和III
- 4.腐烂的橘子
- 5.课程表
- 6.实现简单Trie树
- 7.杨辉三角
1.单词搜索
dfs包超时的，要剪枝，也就是说要回溯
在寻找下一个节点的之前，将上一个节点标记一下，以免访问
class Solution {
public:
bool search(vector<vector<char>>& board, string word, int wordIndex, int i, int j, vector<vector<bool>>& visited) {
if (wordIndex == word.size()) return true;
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
int m = board.size();
int n = board[0].size();
for (int k = 0; k < 4; k++) {
int newI = i + dx[k];
int newJ = j + dy[k];
if (newI >= 0 && newI < m && newJ >= 0 && newJ < n &&!visited[newI][newJ] && board[newI][newJ] == word[wordIndex]) {
visited[newI][newJ] = true;
if (search(board, word, wordIndex + 1, newI, newJ, visited)) return true;
visited[newI][newJ] = false;
}
}
return false;
}
bool exist(vector<vector<char>>& board, string word) {
int m = board.size();
int n = board[0].size();
vector<vector<bool>> visited(m, vector<bool>(n, false));
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (board[i][j] == word[0]) {
visited[i][j] = true;
if (search(board, word, 1, i, j, visited)) return true;
visited[i][j] = false;
}
}
}
return false;
}
};
2.将有序数组转换为二叉搜索树
给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 平衡 二叉搜索树。
二叉树的构建问题遵循固定的套路，构造整棵树可以分解成：先构造根节点，然后构建左右子树。
一个有序数组对于 BST 来说就是中序遍历结果，根节点在数组中心，数组左侧是左子树元素，右侧是右子树元素。
class Solution {
public:
TreeNode* sortedArrayToBST(vector<int>& nums) {
return build(nums, 0, nums.size() - 1);
}
// 将闭区间 [left, right] 中的元素转化成 BST，返回根节点
TreeNode* build(vector<int>& nums, int left, int right) {
if (left > right) {
// 区间为空
return nullptr;
}
// 构造根节点
// BST 节点左小右大，中间的元素就是根节点
int mid = (left + right) / 2;
TreeNode* root = new TreeNode(nums[mid]);
// 递归构建左子树
root->left = build(nums, left, mid - 1);
// 递归构造右子树
root->right = build(nums, mid + 1, right);
return root;
}
};
3.路径总和III
给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。
路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
——————————————————————————————————
前缀和的技巧用到树上来，用preSumCount来记录路径和，以及该路径和出现的次数
假设我们有一条从根节点到当前节点的路径，其和为 currentPathSum。我们希望找到一些点 A，使得从 A 到当前节点的路径和为 targetSum。
这意味着我们需要从 currentPathSum 中减去某个值，使得结果为 targetSum。currentPathSum−prePathSum=targetSum
- 每当到达一个节点的时候，该节点的值就应该加入到currentPathSum中，并且相应地计算currentPathSum - targetSum在preSumCount中是否存在，如果存在可以将次数累加成路径数目，最后将该路径也记录在preSumCount中
currentPathSum += root->val;
res += preSumCount[currentPathSum - targetSum];
preSumCount[currentPathSum]++;
- 递归，不断遍历更新currentPathSum，检查通过当前节点的路径是否能构成 targetSum，在递归前增加当前路径总和的计数，在递归后减少，这是因为当返回到该节点的父节点时，当前节点的子树已经遍历完毕，其路径总和不应再影响其他路径。
traverse(root->left, currentPathSum, targetSum);
traverse(root->right, currentPathSum, targetSum);
preSumCount[currentPathSum]--; // 回溯
class Solution {
public:
unordered_map<long long, int> preSumCount;
int res = 0;
int pathSum(TreeNode* root, int targetSum) {
preSumCount[0] = 1; // 前缀和关键技巧
traverse(root, 0, targetSum);
return res;
}
void traverse(TreeNode* root, long long currentPathSum, int targetSum) {
if (!root) return;
currentPathSum += root->val; // 更新当前路径总和
res += preSumCount[currentPathSum - targetSum]; // 查找满足条件的路径
preSumCount[currentPathSum]++; // 前缀和计数
traverse(root->left, currentPathSum, targetSum);
traverse(root->right, currentPathSum, targetSum);
preSumCount[currentPathSum]--; // 回溯
currentPathSum -= root->val;
}
};
4.腐烂的橘子
BFS
class Solution {
public:
int orangesRotting(vector<vector<int>>& grid) {
queue<std::vector<int>> queue;
int m = grid.size(), n = grid[0].size();
// 把所有腐烂的橘子加入队列，作为 BFS 的起点
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 2) {
queue.push({i, j});
}
}
}
// 方向数组，方便计算上下左右的坐标
vector<vector<int>> dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
// BFS 算法框架
int step = 0;
while (!queue.empty()) {
int sz = queue.size();
// 取出当前层所有节点，往四周扩散一层
for (int i = 0; i < sz; i++) {
vector<int> point = queue.front();
queue.pop();
for (const auto& dir : dirs) {
int x = point[0] + dir[0];
int y = point[1] + dir[1];
if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1) {
grid[x][y] = 2;
queue.push({x, y});
}
}
}
// 扩散步数加一
step++;
}
// 检查是否还有新鲜橘子
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
// 有新鲜橘子，返回 -1
if (grid[i][j] == 1) {
return -1;
}
}
}
// 注意，BFS 扩散的步数需要减一才是最终结果，另外还有0不要忘记
// 你可以用最简单的情况，比方说只有一个腐烂橘子的情况验证一下
return step == 0 ? 0 : step - 1;
}
};
5.课程表
遍历图结构，就可以判断环了
利用布尔数组 onPath，如果遍历过程中发现下一个即将遍历的节点已经被标记为 true，说明遇到了环。
给出DFS实现方式
- 构建图：使用邻接表vector<list< int >>来表示图，每个节点代表一个课程，节点之间的有向边表示课程间的依赖关系，即修完课程 A 才能修课程 B。例如，如果课程 1 是课程 0 的先修课，则在邻接表中课程 1 的列表中加入课程 0。
- 环检测：traverse 函数通过深度优先搜索遍历图。遍历每个节点时，首先将其标记为已访问visited和当前路径onpath上，然后递归地访问其所有邻接节点。如果节点已访问过或已发现环，则直接返回。
注意两点
- visited[s]并不代表存在环，而是找到了重复访问过的节点，return访问下一个才对
- 传递的 graph 如果const vector<list< int>> graph是按值传递的，这意味着每次递归调用都会复制整个图结构，这会超时，应当将 graph 改为引用传递，即 const vector<list< int>>& graph
class Solution {
public:
vector<bool> onPath;
vector<bool> visited;
bool hasCycle = false;
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
//建立图
vector<list<int>> graph = buildGraph(numCourses, prerequisites);
visited.resize(numCourses, false);
onPath.resize(numCourses, false);
for(int i = 0; i < numCourses; i ++){
traverse(graph, i);
}
return !hasCycle;
}
void traverse(vector<list<int>>& graph, int s){
if(onPath[s]){
hasCycle = true;
return;
}
if(visited[s]) return;
if(hasCycle) return;
visited[s] = true;
onPath[s] = true;
for(int t : graph[s]){
traverse(graph, t);
}
onPath[s] = false;
}
vector<list<int>> buildGraph(int numCourses, vector<vector<int>>& prerequisites){
//图中共有numCourses个节点
vector<list<int>> graph(numCourses);
for(auto edge : prerequisites){
int from = edge[1];
int to = edge[0];
graph[from].push_back(to);
}
return graph;
}
};
6.实现简单Trie树
search和startswith的区别就是search必须是一个字符串结尾的，也就是要有结尾标记，而startswith可以没有
const int N = 1e5 + 10;
int idx;// 各个节点的编号，根节点编号为0
int son[N][26];//Trie 树本身
bool visited[N];//以 编号为 N 为结尾的字符串是否存在
class Trie {
public:
Trie() {
//必须初始化
memset(visited, false, sizeof(visited));
memset(son,0,sizeof(son));
idx = 0;
}
void insert(string word) {
int p = 0;//先指向根节点
for(int i = 0; i < word.size(); i ++){
int u = word[i] - 'a';//将当前字符转换成数字（a->0, b->1,...）
//如果数中不能走到当前字符
//为当前字符创建新的节点，保存该字符，更新idx就相当于创建
if(!son[p][u]) son[p][u] = ++idx;// 新节点编号为 idx + 1
p = son[p][u];
}
//这个时候，p 等于字符串 word 的尾字符所对应的 idx
//visited[p] 记录的是字符串 word 出现过
visited[p] = true;
}
bool search(string word) {
int p = 0;
for(int i = 0; i < word.size(); i ++){
int u = word[i] - 'a';
//如果走不通了，即树中没有保存当前字符
//则说明树中不存在该字符串
if(!son[p][u]) return false;
p = son[p][u];
}
return visited[p];
}
bool startsWith(string prefix) {
int p = 0;
for(int i = 0; i <prefix.size(); i ++){
int u = prefix[i] - 'a';
if(!son[p][u]) return false;
p = son[p][u];
}
return true;
}
};
7.杨辉三角
给行数，实现杨辉三角
输入: numRows = 5
输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
class Solution {
public:
vector<vector<int>> generate(int numRows) {
vector<vector<int>> res;
if (numRows < 1) {
return res;
}
// 先把第一层装进去作为 base case
vector<int> firstRow = {1};
res.push_back(firstRow);
// 开始一层一层生成，装入 res
for (int i = 2; i <= numRows; i++) {
vector<int> prevRow = res.back();
res.push_back(generateNextRow(prevRow));
}
return res;
}
private:
// 输入上一层的元素，生成并返回下一层的元素
vector<int> generateNextRow(const vector<int>& prevRow) {
vector<int> curRow;
curRow.push_back(1);
for (int i = 0; i < prevRow.size() - 1; i++) {
curRow.push_back(prevRow[i] + prevRow[i + 1]);
}
curRow.push_back(1);
return curRow;
}
};