# # Leetcode 第33场双周赛题解

## # Problem A - 千位分隔数 (opens new window)

class Solution {
public:
string thousandSeparator(int n) {
string s = to_string(n);
string ans;
int k = s.size();
for (int i = 0; i < k; ++i) {
ans.push_back(s[i]);
if ((k - i - 1) % 3 == 0 && i != k - 1)
ans.push_back('.');
}
return ans;
}
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14

## # Problem B - 可以到达所有点的最少点数目 (opens new window)

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

1
2
3
4
5
6
7
8
9
10
11
12
13

## # Problem C - 得到目标数组的最少函数调用次数 (opens new window)

class Solution {
public:
int minOperations(vector<int>& nums) {
int ans = 0;
bool nonzero = true;
while (nonzero) {
nonzero = false;
for (int &num : nums)
if (num & 1)
num--, ans++;
bool d = false;
for (int &num : nums) {
if (num > 0)
num >>= 1, d = true;
if (num)
nonzero = true;
}
ans += d;
}
return ans;
}
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

## # Problem D - 二维网格图中探测环 (opens new window)

DFS实现无向图找环，遍历过程中记录深度，检查环的长度是否满足要求。实际上，因为本题的特殊性，不可能存在长度为$3$的环，所以只要能成环（有反向边），长度至少为$4$，因此即使不加对深度的判断，只根据是否已经访问过来进行判断，也是OK的。

const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, -1, 0, 1};

class Solution {
bool ans = false;
vector<vector<char>> grid;
vector<vector<int>> depth;
int n, m;
void dfs(int i, int j, int pi, int pj) {
if (ans)
return;
for (int k = 0; k < 4; ++k) {
int ci = i + dy[k], cj = j + dx[k];
if (ci < 0 || ci >= n || cj < 0 || cj >= m || grid[ci][cj] != grid[i][j] || (ci == pi && cj == pj))
continue;
if (depth[ci][cj] == -1) {
depth[ci][cj] = depth[i][j] + 1;
dfs(ci, cj, i, j);
} else if (depth[i][j] - depth[ci][cj] >= 3) {
ans = true;
return;
}
}
}
public:
bool containsCycle(vector<vector<char>>& grid) {
this->grid = grid;
n = grid.size(), m = grid[0].size();
depth = vector<vector<int>>(n, vector<int>(m, -1));
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j) {
if (ans)
return ans;
if (depth[i][j] == -1) {
depth[i][j] = 0;
dfs(i, j, -1, -1);
}
}
return ans;
}
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40