这次只能做出前面三题，而且第三题用时过长，导致这次排名只有505。

第一题Special Array With X Elements Greater Than or Equal X

给定一个数组，找出 x 使得恰有 x 个数不小于 x。

暴力枚举所有可能的 x。

class Solution:
    def specialArray(self, nums: List[int]) -> int:
        for n in range(len(nums) + 1):
            if sum(1 for v in nums if v >= n) == n:
                return n
        return -1

第二题Even Odd Tree

判断一颗二叉树（根节点为第 0 层）是否满足
1. 奇数层的数字为偶数，而且从左到右严格递减；
2. 偶数层的数字为奇数，而且从左到右严格递增。

BFS找出每一层来判断是否满足条件。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isEvenOddTree(self, root: TreeNode) -> bool:
        level = 0
        cur = [root]
        while cur:
            next = []
            nums = []
            for node in cur:
                if node is None:
                    continue
                nums.append(node.val)
                next.append(node.left)
                next.append(node.right)
            if level % 2 == 1:
                if any(a % 2 == 1 for a in nums) or any(a <= b for a, b in zip(nums, nums[1:])):
                    return False
            else:
                if any(a % 2 == 0 for a in nums) or any(a >= b for a, b in zip(nums, nums[1:])):
                    return False
            cur = next
            level += 1
        return True

第三题Maximum Number of Visible Points

假设有一个圆心固定，半径无限，角度为 angle 的扇形，它可以任意旋转。给定一些点，问这个扇形最多能盖住多少个点。

首先根据圆心算出所有点的角度（x轴正方向为 0 度），然后按照大小排序。然后用 two pointers 来找出角度差为 angle 的最大长度。需要注意的是如果两个角度的差大于 180 度，那么我们要将这个角度差调整成 360 - 角度差。为了方便，我将所有的角度每个加上 360 也考虑进来，这样就不用调整了。

class Solution:
    def visiblePoints(self, points: List[List[int]], angle: int, location: List[int]) -> int:
        x, y = location 
        base = 0
        degrees = []
        for a, b in points:
            if a == x and b == y:
                base += 1
                continue
            degrees.append(math.degrees(math.atan2(b - y, a - x)))
            degrees.append(degrees[-1] + 360)
        degrees.sort()
        ans = i = j = 0
        while i < len(degrees):
            while i < len(degrees) and degrees[i] - degrees[j] <= angle:
                i += 1
            ans = max(ans, i - j)
            j += 1
        return ans + base

第四题Minimum One Bit Operations to Make Integers Zero

对于一个数 n 的二进制，我们可以进行以下两种操作：
1. 改变最低位；
2. 如果第 (i + 1) 位是 1，第 (i + 2) 到最后的最低位都是 0，那么改变第 i 位。

问至少操作几次能将 n 变成 0。

一开始的时候假设 n 的二进制是 1x...x，长度为 l。为了将最高位的 1 变成 0，我们必须要将 1x...x 变成 110...0。而110...0 变成0的操作次数是 2l，所以我们只需要求出将 x...x 变成 10...0 的最小步数。x...x 的长度为 l - 1，但是我们希望将其变成 10..0，而不是 0。总结以下，我们将原来的问题转化成：给定一个长度是 l 的 01 序列 x...x， 将其变成 c0...0 至少需要 f(x...x, c0...0) 步，求 f(x...x, c0...0)。c 是 0 或 1。这个想法让我有了以下的算法：

为了方便讨论，我们将 01 序列的最左那位用 y 表示。假设当前 01 序列是 yx...x， 长度为l，我们需要将其变成 c0...0。

（1）如果 y = c，那么

f(yx...x, c0...0) = f(x...x, 0...0)。

（2）如果 y != c，那么有两种情况 (y, c) = (1, 0) 或者 (0, 1)。

（2.1）(y, c) = (1, 0)。这种情况在前面已经讨论过，

f(1x...x, 00...0) = 2l + f(x...x, 10...0)

（2.2）(y, c) = (0, 1)。这种情况下，0x...x -> 10...0 的最优方案是

0x...x -> 010...0 -> 10...0

不难看出，010...0 -> 10...0 需要 2l 步，所以

f(0x...x, 10...0) = 2l + f(x...x, 10...0)

因此，在 y != c 的情况下

f(yx...x, c0...0) = 2l + f(x...x, 10...0)

比赛的时候 (2.2) 的分析一直没有弄对，有点可惜了。

class Solution:
    def minimumOneBitOperations(self, n: int) -> int:
        bit = []
        while n:
            bit.append(n & 1)
            n //= 2
        ans = c = 0
        for i in range(len(bit) - 1, -1, -1):
            if c != bit[i]:
                ans += 2 ** i
                c = 1
            else:
                c = 0
        return ans
leetcode contest