文章目录

• 1. 比赛结果
• 2. 题目
• 1. LeetCode 5479. 千位分隔数 easy
• 2. LeetCode 5480. 可以到达所有点的最少点数目 medium
• 3. LeetCode 5481. 得到目标数组的最少函数调用次数 medium
• 4. LeetCode 5482. 二维网格图中探测环 hard

1. 比赛结果

题目比较简单，全部做出来了。继续加油！

全国排名： 511 / 3304，15.5%；全球排名： 1626 / 11366，14.3%

2. 题目

1. LeetCode 5479. 千位分隔数 easy

题目链接

给你一个整数 n，请你每隔三位添加点（即 "." 符号）作为千位分隔符，并将结果以字符串格式返回。

示例 1：
输入：n = 987
输出："987"

示例 2：
输入：n = 1234
输出："1.234"

示例 3：
输入：n = 123456789
输出："123.456.789"

示例 4：
输入：n = 0
输出："0"
 
提示：
0 <= n < 2^31

解题：

• 按题意模拟即可

class Solution {
public:
    string thousandSeparator(int n) {
    	string num = to_string(n), ans;
    	int k = 3;
    	for(int i = int(num.size())-1; i >= 0; i--)
    	{
    		if(k == 0)
    		{
    			ans = "." + ans;//3位到了，加点
    			k = 3;//重置3
    			i++;//该位还需要再次访问
    		}
    		else
    		{
    			ans = num[i] + ans;//没到三次，加字符
    			k--;
    		}
    	}
    	return ans;
    }
};

0 ms 5.9 MB

2. LeetCode 5480. 可以到达所有点的最少点数目 medium

题目链接

给你一个 有向无环图 ， n 个节点编号为 0 到 n-1 ，以及一个边数组 edges ，其中 edges[i] = [fromi, toi] 表示一条从点 fromi 到点 toi 的有向边。

找到最小的点集使得从这些点出发能到达图中所有点。题目保证解存在且唯一。

你可以以任意顺序返回这些节点编号。

示例 1：

输入：n = 6, edges = [[0,1],[0,2],[2,5],[3,4],[4,2]]
输出：[0,3]
解释：从单个节点出发无法到达所有节点。
从 0 出发我们可以到达 [0,1,2,5] 。
从 3 出发我们可以到达 [3,4,2,5] 。
所以我们输出 [0,3] 。

示例 2：

输入：n = 5, edges = [[0,1],[2,1],[3,1],[1,4],[2,4]]
输出：[0,2,3]
解释：注意到节点 0，3 和 2 无法从其他节点到达，
所以我们必须将它们包含在结果点集中，这些点都能到达节点 1 和 4 。
 
提示：
2 <= n <= 10^5
1 <= edges.length <= min(10^5, n * (n - 1) / 2)
edges[i].length == 2
0 <= fromi, toi < n
所有点对 (fromi, toi) 互不相同。

解题：

• 检查入度为0的节点

class Solution {
public:
    vector<int> findSmallestSetOfVertices(int n, vector<vector<int>>& edges) {
    	vector<int> indegree(n, 0), ans;
    	for(auto& e : edges) 
    	{
    		indegree[e[1]]++;
    	}
    	for(int i = 0; i < n; i++)
    	{
    		if(indegree[i] == 0)
    			ans.push_back(i);
    	}
    	return ans;
    }
};

696 ms 94.5 MB

3. LeetCode 5481. 得到目标数组的最少函数调用次数 medium

题目链接

给你一个与 nums 大小相同 且 初始值 全为 0 的数组 arr ，请你调用以上函数得到整数数组 nums 。

请你返回将 arr 变成 nums 的最少函数调用次数。

答案保证在 32 位有符号整数以内。

示例 1：
输入：nums = [1,5]
输出：5
解释：给第二个数加 1 ：[0, 0] 变成 [0, 1] （1 次操作）。
将所有数字乘以 2 ：[0, 1] -> [0, 2] -> [0, 4] （2 次操作）。
给两个数字都加 1 ：[0, 4] -> [1, 4] -> [1, 5] （2 次操作）。
总操作次数为：1 + 2 + 2 = 5 。

示例 2：
输入：nums = [2,2]
输出：3
解释：给两个数字都加 1 ：[0, 0] -> [0, 1] -> [1, 1] （2 次操作）。
将所有数字乘以 2 ： [1, 1] -> [2, 2] （1 次操作）。
总操作次数为： 2 + 1 = 3 。

示例 3：
输入：nums = [4,2,5]
输出：6
解释：（初始）[0,0,0] -> [1,0,0] -> [1,0,1] -> 
[2,0,2] -> [2,1,2] -> [4,2,4] -> [4,2,5] （nums 数组）。

示例 4：
输入：nums = [3,2,2,4]
输出：7

示例 5：
输入：nums = [2,4,8,16]
输出：8
 
提示：
1 <= nums.length <= 10^5
0 <= nums[i] <= 10^9

解题：

• 数组要乘以2的次数是最大的那个数，可以被2除的次数
• 然后每个数不能被2整除时，就 -1，调用次数 +1

class Solution {
public:
    int minOperations(vector<int>& nums) {
    	int s = 0, maxn = 0;
    	for(int i = 0; i < nums.size(); ++i)
    	{
    		maxn = max(maxn, nums[i]);
    	}
    	for(int i = 0; i < nums.size(); ++i)
    	{
            while(nums[i])
            {
                if(nums[i]&1)//不能整除
                {
                    s++;//调用
                    nums[i]--;
                }
                else
                {
                    nums[i] /= 2;
                }
            }
    	}
    	while(maxn>1)//大于1时
    	{
    		maxn /= 2;//最大的数能被2除的次数
    		s++;
    	}
    	return s;
    }
};

188 ms 25.5 MB

4. LeetCode 5482. 二维网格图中探测环 hard

题目链接

给你一个二维字符网格数组 grid ，大小为 m x n ，你需要检查 grid 中是否存在 相同值 形成的环。

一个环是一条开始和结束于同一个格子的长度 大于等于 4 的路径。对于一个给定的格子，你可以移动到它上、下、左、右四个方向相邻的格子之一，可以移动的前提是这两个格子有 相同的值 。

同时，你也不能回到上一次移动时所在的格子。比方说，环 (1, 1) -> (1, 2) -> (1, 1) 是不合法的，因为从 (1, 2) 移动到 (1, 1) 回到了上一次移动时的格子。

如果 grid 中有相同值形成的环，请你返回 true ，否则返回 false 。

示例 1：

输入：grid = [
["a","a","a","a"],
["a","b","b","a"],
["a","b","b","a"],
["a","a","a","a"]]
输出：true
解释：如下图所示，有 2 个用不同颜色标出来的环：

示例 2：

输入：grid = [
["c","c","c","a"],
["c","d","c","c"],
["c","c","e","c"],
["f","c","c","c"]]
输出：true
解释：如下图所示，只有高亮所示的一个合法环：

示例 3：

输入：grid = [
["a","b","b"],
["b","z","b"],
["b","b","a"]]
输出：false
 
提示：
m == grid.length
n == grid[i].length
1 <= m <= 500
1 <= n <= 500
grid 只包含小写英文字母。

解题：

• dfs 记录访问标记，以及走过的 steps

class Solution {
    vector<vector<int>> dir = {{1,0},{0,1},{-1,0},{0,-1}};
    bool found = false;
    int m, n;
public:
    bool containsCycle(vector<vector<char>>& grid) {
        m = grid.size(), n = grid[0].size();
        int i, j, k, x, y;
        vector<vector<bool>> visited(m, vector<bool>(n, false));
        vector<vector<int>> step(m, vector<int>(n, 0));
        for(i = 0; i < m; ++i) 
        {
            for(j = 0; j < n; ++j)
            {
                if(found) return found;
                if(visited[i][j])
                    continue;
                visited[i][j] = true;
                step[i][j] = 1;//走过的步数
                dfs(i,j,step,visited,grid);
            }
        }
        return found;
    }
    void dfs(int i, int j,vector<vector<int>> &step, vector<vector<bool>> &visited, vector<vector<char>>& grid)
    {
        int x,y,k;
        if(found) return;
        for(k = 0; k < 4; k++)
        {
            x = i + dir[k][0];
            y = j + dir[k][1];
            if(x >= 0 && x < m && y >= 0 && y < n)
            {
                if(grid[x][y] != grid[i][j])
                    continue;//不相同的值，不行
                if(!visited[x][y])//没有访问
                {
                    visited[x][y] = true;
                    step[x][y] = step[i][j]+1;//步数+1
                    dfs(x, y, step, visited, grid);
                }
                else
                {	//访问过了，且当前步数跟其步数差满足条件
                    if(step[i][j]-step[x][y]+1 >= 4)
                    {
                        found = true;
                        return;
                    }
                }
            }
        }
    }
};

724 ms 100.8 MB

我的CSDN博客地址 https://michael.blog.csdn.net/

长按或扫码关注我的公众号（Michael阿明），一起加油、一起学习进步！