网站注册主机,餐饮行业做网站的好处,石狮建设网站,做网站多少钱赚钱吗【每日刷题】Day155 #x1f955;个人主页#xff1a;开敲#x1f349; #x1f525;所属专栏#xff1a;每日刷题#x1f34d; #x1f33c;文章目录#x1f33c;
1. LCR 108. 单词接龙 - 力扣#xff08;LeetCode#xff09;
2. 675. 为高尔夫球比赛砍树 - 力扣(…【每日刷题】Day155 个人主页开敲 所属专栏每日刷题 文章目录
1. LCR 108. 单词接龙 - 力扣LeetCode
2. 675. 为高尔夫球比赛砍树 - 力扣(LeetCode)
3. LCR 107. 01矩阵 - 力扣(LeetCode) 1. LCR 108. 单词接龙 - 力扣LeetCode //思路本题与 Day154 中的 最小基因变化 完全一样 class Solution { public: string total abcdefghijklmnopqrstuvwxyz; int ladderLength(string beginWord, string endWord, vectorstring wordList) { unordered_setstring hash(wordList.begin(),wordList.end());//标记字典中的单词 unordered_setstring se;//标记已经出现过的单词 if(!hash.count(endWord)||beginWordendWord) return 0; queuestring qu; qu.push(beginWord); se.insert(beginWord); int ans 0; while(!qu.empty()) { ans; int size qu.size(); for(int i 0;isize;i) { string s qu.front(); for(int j 0;js.size();j) { for(int m 0;m26;m) { string tmp s; if(tmp[j]total[m]) continue; tmp[j] total[m]; if(tmpendWord) return ans1; if(se.count(tmp)) continue; se.insert(tmp); if(hash.count(tmp)) qu.push(tmp); } } qu.pop(); } } return 0; } }; 2. 675. 为高尔夫球比赛砍树 - 力扣(LeetCode) //思路BFS排序 //本题可以看作是 Day154 中 迷宫中离入口最近的出口 的升级版。 //仔细思考一下本题要求我们从 (0,0)位置开始砍树必须按照 由低到高 的顺序进行砍树那我们首先第一步一定是先把数组中的所有树的高度按照升序排序并且排序后我们还要保留其原本所在的坐标。 //排好序后我们要从最低的树开始砍砍完当前树需要去到下一个更高的树因此这里我们实际上可以将砍树的动作看作为从低的树的坐标去到下一个更高的树的坐标再从下一个更高的树的坐标去到下下一个更更高的树的坐标 ...... 以此类推。 //到这本题实际上就是多次 从一个坐标去到另一个坐标 的操作与 迷宫中离入口最近的出口 这题的思路就完全一样了。 class Solution { public: int n, m; int dx[4] { 1,-1,0,0 }; int dy[4] { 0,0,1,-1 }; int cutOffTree(vectorvectorint forest) { n forest.size(), m forest[0].size(); int ans 0; vectorvectorint hash;//这里也可以用 pair如果用pair后面 sort排序的时候就要自己写 lambda 表达式来排序这里偷懒的方法就是用二维数组。 for (int i 0; i n; i) for (int j 0; j m; j) if (forest[i][j] 1) hash.push_back({forest[i][j],i,j});//0位置放值也就是树的高度1、2位置放坐标 sort(hash.begin(), hash.end());//排序时默认会按照数组第一个元素进行排序这里刚好就是根据树的高度进行排序 int bx 0, by 0;//从 (0,0)位置开始 for (int i 0; i hash.size(); i) { auto a hash[i]; int ex a[1], ey a[2];//拿到下一个位置的坐标 int ret bfs(forest, bx, by, ex, ey);//获得从 bx、by初始位置到达ex、ey目标位置所需的最少步数 if (ret -1) return -1;//没法到达说明一定有至少一棵树没法砍掉返回-1 ans ret; bx ex, by ey;//更新初始位置 } return ans; } //下面的代码与 迷宫中离入口最近的出口 完全一样 int bfs(vectorvectorint forest, int bx, int by, int ex, int ey) { if(bxexbyey) return 0; vectorvectorbool hash(n, vectorbool(m)); queuepairint, int qu; qu.push({bx,by}); hash[bx][by] true; int ret 0; while (!qu.empty()) { ret; int size qu.size(); while(size--) { auto a qu.front(); qu.pop(); for (int j 0; j 4; j) { int x a.first dx[j], y a.second dy[j]; if (x 0 x n y 0 y m !hash[x][y] forest[x][y]) { if (x ex y ey) return ret; qu.push({ x,y }); hash[x][y] true; } } } } return -1; } }; 3. LCR 107. 01矩阵 - 力扣(LeetCode) //思路多源BFS //多源BFS问题相较于单源BFS问题而言区别仅仅在于单源BFS初始只将一个起点放入队列向外扩展多源BFS则是将所有起点同时放入队列进行向外扩展。 //本题我们要从逆向思维来考虑问题题目让我们找到矩阵中所有位置的 1 到它最近的 0 的距离并将距离与 1 替换。 //反向思考我们将所有的 0 看作一个起点向外扩展每次扩展到 1 时直接记录当前距离一定是最短距离因为每个 1 都一定有一个距离最近的 0 将所有 0 视为同一个起点同时向外扩展时距离 某个 1 的某个 0一定先扩展到因此每次的距离一定是最短的 class Solution { public: int n,m; int dx[4] {1,-1,0,0}; int dy[4] {0,0,1,-1}; vectorvectorint updateMatrix(vectorvectorint mat) { n mat.size(),m mat[0].size(); vectorvectorbool hash(n,vectorbool(m)); queuevectorint qu; for(int i 0;in;i) for(int j 0;jm;j) if(!mat[i][j]) { qu.push({i,j});//将所有 0 放入队列视为一个起点同时向外扩展 hash[i][j] true; } int ret 0; while(!qu.empty()) { ret; int size qu.size(); while(size--) { auto arr qu.front(); qu.pop(); for(int j 0;j4;j) { int x arr[0]dx[j],y arr[1]dy[j]; if(x0xny0ym!hash[x][y]) { if(mat[x][y]) mat[x][y] ret;//扩展到 1 时此时的距离一定是最短的因为此时一定是距离最近的 0 先扩展到 1 qu.push({x,y}); hash[x][y] true; } } } } return mat; } };
