LeetCode 第 33 场双周赛（511/3304，前15.5%，第4次全部通过）

示例 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;
    }
};

输入：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] 。

输入：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) 互不相同。

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;
    }
};

示例 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

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;
    }
};

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

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

输入：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 只包含小写英文字母。

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;
                    }
                }
            }
        }
    }
};