【每日刷题】Day155
【每日刷题】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, vector<string>& wordList)
{
unordered_set<string> hash(wordList.begin(),wordList.end());//标记字典中的单词
unordered_set<string> se;//标记已经出现过的单词
if(!hash.count(endWord)||beginWord==endWord) return 0;
queue<string> qu;
qu.push(beginWord);
se.insert(beginWord);
int ans = 0;
while(!qu.empty())
{
ans++;
int size = qu.size();
for(int i = 0;i<size;i++)
{
string s = qu.front();
for(int j = 0;j<s.size();j++)
{
for(int m = 0;m<26;m++)
{
string tmp = s;
if(tmp[j]==total[m]) continue;
tmp[j] = total[m];
if(tmp==endWord) return ans+1;
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(vector<vector<int>>& forest)
{
n = forest.size(), m = forest[0].size();
int ans = 0;
vector<vector<int>> 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(vector<vector<int>>& forest, int bx, int by, int ex, int ey)
{
if(bx==ex&&by==ey) return 0;
vector<vector<bool>> hash(n, vector<bool>(m));
queue<pair<int, 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};
vector<vector<int>> updateMatrix(vector<vector<int>>& mat)
{
n = mat.size(),m = mat[0].size();
vector<vector<bool>> hash(n,vector<bool>(m));
queue<vector<int>> qu;
for(int i = 0;i<n;i++)
for(int j = 0;j<m;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;j<4;j++)
{
int x = arr[0]+dx[j],y = arr[1]+dy[j];
if(x>=0&&x<n&&y>=0&&y<m&&!hash[x][y])
{
if(mat[x][y]) mat[x][y] = ret;//扩展到 1 时，此时的距离一定是最短的（因为此时一定是距离最近的 0 先扩展到 1）
qu.push({x,y});
hash[x][y] = true;
}
}
}
}
return mat;
}
};