# # Leetcode 第209场周赛题解

## # Problem A - 特殊数组的特征值 (opens new window)

### # 方法一：暴力枚举特征值

class Solution {
public:
int specialArray(vector<int>& nums) {
int n = nums.size();
for (int i = 0; i <= n; ++i) {
int cnt = 0;
for (int num : nums)
if (num >= i)
cnt++;
if (cnt == i)
return i;
}
return -1;
}
};

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

### # 方法二：排序+枚举特征值

class Solution {
public:
int specialArray(vector<int>& nums) {
int n = nums.size();
sort(nums.begin(), nums.end());
for (int i = 0; i <= n; ++i) {
int d = nums.end() - lower_bound(nums.begin(), nums.end(), i);
if (d == i)
return i;
}
return -1;
}
};

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

### # 方法三：计数数组后缀和

class Solution {
public:
int specialArray(vector<int>& nums) {
int n = nums.size();
vector<int> cnt(n + 1);
for (int num : nums)
cnt[min(num, n)]++;
for (int i = n; i >= 0; --i) {
if (i < n)
cnt[i] += cnt[i + 1];
if (cnt[i] == i)
return i;
}
return -1;
}
};

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

## # Problem B - 奇偶树 (opens new window)

class Solution {
public:
bool isEvenOddTree(TreeNode* root) {
vector<vector<int>> v;
queue<pair<TreeNode*, int>> q;
q.emplace(root, 0);
while (!q.empty()) {
TreeNode *u = q.front().first;
int lev = q.front().second;
q.pop();
if (!u)
continue;
if (lev >= v.size())
v.push_back({});
v[lev].emplace_back(u->val);
q.emplace(u->left, lev + 1);
q.emplace(u->right, lev + 1);
}
for (int i = 0; i < v.size(); ++i) {
if (i % 2 == 0) {
for (int j = 0; j < v[i].size(); ++j) {
if (v[i][j] % 2 == 0 || (j + 1 < v[i].size() && v[i][j] >= v[i][j + 1]))
return false;
}
} else {
for (int j = 0; j < v[i].size(); ++j) {
if (v[i][j] % 2 == 1 || (j + 1 < v[i].size() && v[i][j] <= v[i][j + 1]))
return false;
}
}
}
return true;
}
};

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

## # Problem C - 可见点的最大数目 (opens new window)

const double eps = 1e-8;

class Solution {
public:
int visiblePoints(vector<vector<int>>& points, int angle, vector<int>& location) {
int x = location[0], y = location[1];
int same = 0;
vector<double> v;
for (auto p : points) {
int px = p[0], py = p[1];
if (px == x && py == y)
same++;
else
v.emplace_back(atan2(py - y, px - x) * 180 / M_PI);
}
sort(v.begin(), v.end());
int m = v.size();
for (int i = 0; i < m; ++i)
v.emplace_back(v[i] + 360);
int r = 0, hi = 0;
for (int l = 0; l < m; ++l) {
while (r + 1 < v.size() && v[r + 1] - v[l] <= (double)angle + eps)
r++;
hi = max(hi, r - l + 1);
}
return hi + same;
}
};

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

## # Problem D - 使整数变为 0 的最少操作次数 (opens new window)

### # 方法一：递归

1. 把当前数变为$0$。我们首先要找到最高位的$1$，找到之后，我们需要的翻转次数，就是将之后的位置变为$10\dots0$，再将最高位翻转，然后将剩下的数变为$0$。因为剩下的数必然是$2$的幂次，就可以使用上面的捷径。
2. 把当前数变为$10\dots 0$。如果$1$对应的位置已经是$1$，我们只需要将后面的数变为$0$；否则，我们需要先把后面变为$10\dots0$，将最高位翻转，再将剩下的数变为$0$

class Solution {
int f(int n) {
if (n <= 1)
return n;
int t = 32 - __builtin_clz(n) - 1;
return (1 << t) + g(n ^ (1 << t), t - 1);
}

int g(int n, int t) {
if (t == 0)
return 1 - n;
if (n & (1 << t))
return f(n ^ (1 << t));
return (1 << t) + g(n, t - 1);
}
public:
int minimumOneBitOperations(int n) {
return f(n);
}
};

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

### # 方法二：格雷码

class Solution {
public:
int minimumOneBitOperations(int n) {
int ans = 0;
while (n) {
ans ^= n;
n >>= 1;
}
return ans;
}
};

1
2
3
4
5
6
7
8
9
10
11