# Leetcode 第209场周赛题解

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

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

枚举所有可能的特征值(最大为NN),判断是否成立。

时间复杂度O(N2)O(N^2)

参考代码(C++)
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

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

先排序,然后枚举特征值,这样可以快速找到符合每个特征值的元素个数。

时间复杂度O(NlogN)O(N\log N)

参考代码(C++)
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

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

我们可以首先进行计数(N\geq N的元素视为NN,因为特征值最大为NN),然后计算计数数组的后缀和,就可以直接得到不小于某一个数的元素个数。

时间复杂度O(N)O(N)

参考代码(C++)
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)

经典层次遍历。BFS后得到每一层的序列,然后逐层检查即可。

总时间复杂度O(N)O(N)

参考代码(C++)
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)

首先排除与人的位置重合的点,只考虑剩下的点。

计算每个点到人的位置的极角,然后按极角排序。因为可以循环,所以把整个数组加上360360^\circ再接到后面。

接下来双指针找出覆盖最多点的区间即可。

最后返回答案时,把与人的位置重合的点加上。

总时间复杂度O(NlogN)O(N\log N)

参考代码(C++)
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)

要注意到的是,因为必须首先将高位的11翻转为00,所以本题其实只存在一种合法的操作顺序,我们只要按照这一顺序进行操作即可。

# 方法一:递归

手算几个数,可以发现F(2n)=2n+11F(2^n)=2^{n+1}-1,因此我们可以将其作为一个捷径。

我们需要考虑两种情况:

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

实现这两个函数,递归计算即可。

参考代码(C++)
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

# 方法二:格雷码

如果进一步观察,可以发现,题目中给出的操作,实际上就是从Gray(n)变换为Gray(n-1)的操作。所以我们可以直接套用求逆格雷码的方法来进行求解。

时间复杂度O(logN)O(\log N)

参考代码(C++)
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