【每日刷题】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;

    }

};