算法闭关修炼百题计划（五）

前进、进步

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++) {// 有新鲜橘子，返回 -1if (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 + 1p = 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 casevector<int> firstRow = {1};res.push_back(firstRow);// 开始一层一层生成，装入 resfor (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;}
};