制作网站花都,wordpress恢复老版本,搭建一个论坛网站,十大景观设计公司一、搜索二维矩阵
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性#xff1a;
每行的元素从左到右升序排列。每列的元素从上到下升序排列。 可以使用 从右上角开始搜索 的方法来有效地找到目标值。
选择起始位置#xff1a; 从矩…一、搜索二维矩阵
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性
每行的元素从左到右升序排列。每列的元素从上到下升序排列。 可以使用 从右上角开始搜索 的方法来有效地找到目标值。
选择起始位置 从矩阵的右上角开始。假设我们当前的位置是 matrix[0][n-1]其中 n 是列数。逐步搜索 如果当前元素等于目标值返回 true。如果当前元素大于目标值说明目标值可能出现在当前元素的左边因此我们向左移动一列。如果当前元素小于目标值说明目标值可能出现在当前元素的下方因此我们向下移动一行。结束条件 如果超出了矩阵的边界说明没有找到目标值返回 false。
class Solution {
public:bool searchMatrix(vectorvectorint matrix, int target) {if (matrix.empty() || matrix[0].empty()) return false;int m matrix.size(); // 行数int n matrix[0].size(); // 列数// 从右上角开始int row 0;int col n - 1;while (row m col 0) {if (matrix[row][col] target) {return true; // 找到目标值} else if (matrix[row][col] target) {col--; // 当前元素大于目标值向左移动} else {row; // 当前元素小于目标值向下移动}}return false; // 没有找到目标值}
};初始位置从矩阵的右上角 matrix[0][n-1] 开始。移动规则 如果当前元素等于目标值则返回 true。如果当前元素大于目标值则移动到左边一列。如果当前元素小于目标值则移动到下方一行。边界条件当行数或列数超出范围时结束搜索。 二、岛屿数量
给你一个由 1陆地和 0水组成的的二维网格请你计算网格中岛屿的数量。
岛屿总是被水包围并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外你可以假设该网格的四条边均被水包围。 DFS 遍历从每个尚未访问的陆地单元格开始使用 DFS 遍历其所有相邻的陆地单元格将它们标记为已访问。每次发现一个新的未被访问的陆地就说明发现了一个新的岛屿。 标记访问为了避免重复计算同一个岛屿需要在遍历过程中将已经访问过的陆地标记为水0这样就不会再次访问到它。 岛屿计数每当我们从一个未访问的陆地开始 DFS 时岛屿数加一。 对于每一个格子如果它是陆地 (1) 且未被访问则从该格子开始进行 DFS将与之相连的所有陆地格子标记为已访问并将岛屿数量加一。遍历所有格子最终得到岛屿的数量。对于一个陆地格子1递归地向上下左右四个方向扩展找到与它相连的所有陆地并将其标记为水0。这样做的目的是确保每个岛屿的陆地只被计数一次。
class Solution {
public:void dfs(vectorvectorchar grid, int i, int j) {// 边界条件如果当前格子越界或已经是水0则返回if (i 0 || i grid.size() || j 0 || j grid[0].size() || grid[i][j] 0) {return;}// 将当前陆地格子标记为水表示已访问grid[i][j] 0;// 递归四个方向dfs(grid, i 1, j); // 向下dfs(grid, i - 1, j); // 向上dfs(grid, i, j 1); // 向右dfs(grid, i, j - 1); // 向左}int numIslands(vectorvectorchar grid) {if (grid.empty()) return 0;int numIslands 0;// 遍历整个网格for (int i 0; i grid.size(); i) {for (int j 0; j grid[0].size(); j) {// 找到一个未访问的陆地启动 DFSif (grid[i][j] 1) {numIslands; // 发现新的岛屿dfs(grid, i, j); // 使用 DFS 标记整个岛屿}}}return numIslands;}
};DFS 函数dfs 用来递归访问与当前格子相连的所有陆地格子并将它们标记为水0。 参数 i, j 表示当前正在处理的格子坐标。在函数内部首先检查是否越界或是否已经是水0如果是则直接返回。然后标记当前格子为水并递归检查四个方向上下左右。 主函数numIslands 遍历整个二维网格发现每个未访问的陆地时调用 dfs 来标记所有相连的陆地从而确保每个岛屿只计算一次。 边界条件如果网格为空直接返回 0。 三、腐烂的橙子
在给定的 m x n 网格 grid 中每个单元格可以有以下三个值之一
值 0 代表空单元格值 1 代表新鲜橘子值 2 代表腐烂的橘子。
每分钟腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。
返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能返回 -1 。 class Solution {
public:int orangesRotting(vectorvectorint grid) {int m grid.size();int n grid[0].size();// 记录腐烂的橘子的位置queuepairint, int rotten;int freshCount 0; // 记录新鲜橘子的数量// 初始化队列和新鲜橘子数量for (int i 0; i m; i) {for (int j 0; j n; j) {if (grid[i][j] 2) {rotten.push({i, j});} else if (grid[i][j] 1) {freshCount;}}}// 如果没有新鲜橘子直接返回 0if (freshCount 0) return 0;// 四个方向vectorpairint, int directions {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};int minutes 0;// 开始 BFSwhile (!rotten.empty()) {int size rotten.size();bool rottedThisRound false; // 记录这一轮是否有橘子腐烂for (int i 0; i size; i) {auto [x, y] rotten.front();rotten.pop();// 四个方向扩展for (auto dir : directions) {int nx x dir.first;int ny y dir.second;// 如果新位置在网格内且是新鲜橘子if (nx 0 nx m ny 0 ny n grid[nx][ny] 1) {grid[nx][ny] 2; // 将新鲜橘子腐烂rotten.push({nx, ny}); // 加入队列freshCount--; // 减少新鲜橘子的数量rottedThisRound true;}}}// 如果这一轮有橘子腐烂时间增加if (rottedThisRound) {minutes;}}// 如果还有新鲜橘子返回 -1return freshCount 0 ? minutes : -1;}
};初始化 我们先遍历网格找到所有腐烂的橘子并将其加入队列。同时我们统计新鲜橘子的数量。BFS 过程 我们从腐烂的橘子开始逐层扩展检查每个腐烂橘子周围的四个方向。如果发现相邻位置是新鲜橘子值为 1我们就把它变成腐烂的橘子值改为 2并将其加入队列继续扩展。每次扩展都意味着时间增加一分钟。结束条件 如果在 BFS 完成后还有新鲜橘子freshCount 0说明不能完全腐烂所有橘子返回 -1。否则返回所需的分钟数。 四、课程表
你这个学期必须选修 numCourses 门课程记为 0 到 numCourses - 1 。
在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出其中 prerequisites[i] [ai, bi] 表示如果要学习课程 ai 则 必须 先学习课程 bi 。
例如先修课程对 [0, 1] 表示想要学习课程 0 你需要先完成课程 1 。
请你判断是否可能完成所有课程的学习如果可以返回 true 否则返回 false 。 class Solution {
public:bool canFinish(int numCourses, vectorvectorint prerequisites) {vectorint indegree(numCourses, 0); // 记录每个课程的入度vectorvectorint graph(numCourses); // 邻接表表示图// 构建图和入度数组for (const auto prereq : prerequisites) {int course prereq[0]; // 需要学习的课程int pre prereq[1]; // 先修课程graph[pre].push_back(course); // 将 course 加入 pre 的邻接表indegree[course]; // course 的入度加 1}// 使用队列存储入度为 0 的课程queueint q;for (int i 0; i numCourses; i) {if (indegree[i] 0) {q.push(i); // 将入度为 0 的课程加入队列}}int count 0; // 记录已修课程的数量while (!q.empty()) {int course q.front();q.pop();count;// 对当前课程的所有后续课程即它的邻接课程进行处理for (int nextCourse : graph[course]) {indegree[nextCourse]--; // 当前课程修完减去下一个课程的入度if (indegree[nextCourse] 0) {q.push(nextCourse); // 如果下一个课程的入度为 0加入队列}}}// 如果修完的课程数量等于总课程数则可以完成所有课程return count numCourses;}
};构建图和入度数组 我们首先创建一个 graph 数组来存储图的邻接表并创建一个 indegree 数组来记录每个课程的入度即每个课程有多少先修课程。然后我们根据 prerequisites 数组来构建图并更新每个课程的入度。拓扑排序 我们初始化一个队列 q将所有入度为 0 的课程加入队列。逐个从队列中取出课程修完后将它的邻接课程的入度减 1。如果某个邻接课程的入度变为 0则将它加入队列。判断是否完成所有课程 最后我们检查已修的课程数量 count 是否等于总课程数 numCourses。如果相等说明没有环路返回 true否则返回 false。 五、实现 Trie (前缀树)
Trie发音类似 try或者说 前缀树 是一种树形数据结构用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景例如自动补全和拼写检查。
请你实现 Trie 类
Trie() 初始化前缀树对象。void insert(String word) 向前缀树中插入字符串 word 。boolean search(String word) 如果字符串 word 在前缀树中返回 true即在检索之前已经插入否则返回 false 。boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix 返回 true 否则返回 false 。 class Trie {
private:struct TrieNode {unordered_mapchar, TrieNode* children;bool isWord;TrieNode() : isWord(false) {}};TrieNode* root;public:// 构造函数初始化 Trie 树Trie() {root new TrieNode();}// 向 Trie 插入一个字符串void insert(string word) {TrieNode* node root;for (char c : word) {// 如果当前字符的子节点不存在则创建一个新的节点if (node-children.find(c) node-children.end()) {node-children[c] new TrieNode();}node node-children[c];}// 标记字符串结束的节点node-isWord true;}// 查找字符串是否存在于 Trie 中bool search(string word) {TrieNode* node root;for (char c : word) {if (node-children.find(c) node-children.end()) {return false; // 如果有字符没有找到对应节点返回 false}node node-children[c];}// 如果到达字符串结尾并且是一个完整的单词返回 truereturn node-isWord;}// 检查是否有任何单词以 prefix 为前缀bool startsWith(string prefix) {TrieNode* node root;for (char c : prefix) {if (node-children.find(c) node-children.end()) {return false; // 如果有字符没有找到对应节点返回 false}node node-children[c];}// 如果遍历完整个前缀说明 Trie 中有以 prefix 为前缀的单词return true;}
};/*** Your Trie object will be instantiated and called as such:* Trie* obj new Trie();* obj-insert(word);* bool param_2 obj-search(word);* bool param_3 obj-startsWith(prefix);*/TrieNode 结构体每个 TrieNode 代表一个树节点包含 children一个哈希表键是字符值是指向子节点的指针。这个哈希表用于存储当前节点的所有子节点。isWord一个布尔值标记当前节点是否为一个单词的结束。 Trie 构造函数创建一个空的根节点 root。 insert(word) 从根节点开始逐个字符遍历 word。如果某个字符的子节点不存在则创建一个新的子节点。最后将最后一个字符的 isWord 标记为 true表示这是一个完整的单词。 search(word) 从根节点开始逐个字符遍历 word。如果在任何字符位置找不到对应的子节点则返回 false。如果遍历结束并且当前节点的 isWord 为 true说明找到了该单词返回 true。 startsWith(prefix) 从根节点开始逐个字符遍历 prefix。如果在某个字符位置找不到对应的子节点则返回 false。如果能够遍历完前缀的所有字符说明存在以该前缀为开始的单词返回 true。
