LeetCode 周赛 20201004 题解

• 1608. 特殊数组的特征值
• 1609. 奇偶树
• 1610. 可见点的最大数目
• 1611. 使整数变为0的最小操作次数

leetcode链接

给你一个非负整数数组 nums 。如果存在一个数 x ，使得 nums 中恰好有 x 个元素 大于或者等于 x ，那么就称 nums 是一个 特殊数组 ，而 x 是该数组的 特征值 。
注意： x 不必 是 nums 的中的元素。
如果数组 nums 是一个 特殊数组 ，请返回它的特征值 x 。否则，返回 -1 。可以证明的是，如果 nums 是特殊数组，那么其特征值 x 是 唯一的 。
示例 1：
输入：nums = [3,5]
输出：2
解释：有 2 个元素（3 和 5）大于或等于 2 。
示例 2：
输入：nums = [0,0]
输出：-1
解释：没有满足题目要求的特殊数组，故而也不存在特征值 x 。
如果 x = 0，应该有 0 个元素 >= x，但实际有 2 个。
如果 x = 1，应该有 1 个元素 >= x，但实际有 0 个。
如果 x = 2，应该有 2 个元素 >= x，但实际有 0 个。
x 不能取更大的值，因为 nums 中只有两个元素。
示例 3：
输入：nums = [0,4,3,0,4]
输出：3
解释：有 3 个元素大于或等于 3 。
示例 4：
输入：nums = [3,6,7,7,0]
输出：-1
提示：
1 <= nums.length <= 100
0 <= nums[i] <= 1000

Java代码

class Solution {
    public int specialArray(int[] nums) {
         if (nums == null || nums.length == 0) {
            return -1;
        }
        Arrays.sort(nums);
        int length = nums.length;
        //x最大只能是数组最大值或者数组元素个数
        int max = Math.max(nums[length - 1],length);
        //处理边界特殊情况
        if(nums[0] >= length) return length;
        for(int i = nums[0]; i <= max; ++i){
            if(((length - i -1)>=0 )&&((length - i)= i)&& nums[length - i -1] 
1609. 奇偶树 
LeetCode链接
 
如果一棵二叉树满足下述几个条件，则可以称为 奇偶树 ：
二叉树根节点所在层下标为 0 ，根的子节点所在层下标为 1 ，根的孙节点所在层下标为 2 ，依此类推。
偶数下标 层上的所有节点的值都是 奇 整数，从左到右按顺序 严格递增
奇数下标 层上的所有节点的值都是 偶 整数，从左到右按顺序 严格递减
给你二叉树的根节点，如果二叉树为 奇偶树 ，则返回 true ，否则返回 false 。
示例 1：
 
 
输入：root = [1,10,4,3,null,7,9,12,8,6,null,null,2]
输出：true
解释：每一层的节点值分别是：
0 层：[1]
1 层：[10,4]
2 层：[3,7,9]
3 层：[12,8,6,2]
由于 0 层和 2 层上的节点值都是奇数且严格递增，而 1 层和 3 层上的节点值都是偶数且严格递减，
因此这是一棵奇偶树。
提示：
树中节点数在范围 [1, 105] 内
1 <= Node.val <= 106
 
BFS+每一层的奇偶标志level+pre值的设置
 
class Solution {
    public boolean isEvenOddTree(TreeNode root) {
        if (root == null) {
            return false;
        }
        Queue queue = new linkedList<>();
        queue.offer(root);
        int size = 0, pre = Integer.MIN_VALUE;
        boolean level = true;//偶数为true;boolean只占8bit
        TreeNode cur = null;
        while (!queue.isEmpty()) {
            size = queue.size();
            //偶数层递增，最开始的pre应该定为整数最小值
            if (level) pre = Integer.MIN_VALUE;
            //奇数层递减，最开始的pre应该定为整数最大值
            else pre = Integer.MAX_VALUE;
            for (int i = 0; i < size; ++i) {
                cur = queue.poll();
                //某一层不满足条件直接返回
                if ((level && ((cur.val & 1) == 0 || cur.val <= pre)) || (!level && ((cur.val & 1) != 0 || cur.val >= pre))) {
                    return false;
                }
                //更新pre
                pre = cur.val;
                if (cur.left != null) {
                    queue.offer(cur.left);
                }
                if (cur.right != null) {
                    queue.offer(cur.right);
                }
            }
            //跳到下一层之前更新level
            level = !level;
        }
        return true;
    }
}
 
1610. 可见点的最大数目 
LeetCode链接
 函数解释：
 atan2(y, x)是4象限反正切，它的取值不仅取决于正切值y/x，还取决于点 (x, y) 落入哪个象限【x可以为0，值域：(-π,π]】：
 
当点(x, y) 落入第一象限时，atan2(y, x)的范围是 0 ~ pi/2;
当点(x, y) 落入第二象限时，atan2(y, x)的范围是 pi/2 ~ pi;
当点(x, y) 落入第三象限时，atan2(y, x)的范围是 －pi～－pi/2;
当点(x, y) 落入第四象限时，atan2(y, x)的范围是 -pi/2～0.
 
而 atan(y/x) 仅仅根据正切值为y/x求出对应的角度 （可以看作仅仅是2象限反正切）：
 
当 y/x > 0 时，atan(y/x)取值范围是 0 ~ pi/2；
当 y/x < 0 时，atan(y/x)取值范围是 -pi/2～0.
 
故 atan2(y, x) = atan(y/x) 仅仅发生在 点 (x, y) 落入第一象限 （x>0, y>0）或 第四象限（x>0, y<0）。
 需要统计和location重合的点的个数
 计算出每个point所在点和location所在点的连线与location所在水平线之间的夹角，转换到[0,2π)，然后从小到大排列，再在此基础上加上360度加在后面，不然会有一片区域扫不到；扫描两圈也不要紧，但是不能有扫描不到的区域
 
 Java代码
 
class Solution {
      public int visiblePoints(List> points, int angle, List location) {
        double PRECISION = 1e-8;
        List angles = new ArrayList<>();
        int same = 0;
        int lx = location.get(0);
        int ly = location.get(1);
        for (List point : points) {
            int px = point.get(0);
            int py = point.get(1);
            //相同的点
            if (px == lx && py == ly) {
                same++;
                continue;
            }
            angles.add(getAngle(px, py, lx, ly));
        }
        //按自然序排序角度
        angles.sort(Comparator.naturalOrder());
        int length = angles.size();
        //这里需要加上360度再来一次，具体见图解
        for(int i = 0; i < length; ++i){
            angles.add(angles.get(i) + 360d);
        }
        int r = 0, max = 0;
        int size = angles.size();
        for (int l = 0; l < size; ++l) {
            while ((r + 1) < size && (angles.get(r + 1)-angles.get(l)) < (angle + PRECISION)){
                r++;
            }
            max = Math.max(max, r - l + 1);
        }
        return max + same;
    }

//计算point所在点和location所在点的连线与location所在水平线之间的夹角
    public double getAngle(int px, int py, int lx, int ly) {
        //直接算出度数，atan2值域(-π,π]
        double angle = Math.toDegrees(Math.atan2(py - ly, px - lx));
        //都转换到[0,2π)
        if (angle < 0) {
            angle += 360d;
        }
        return angle;
    }
}
 
1611. 使整数变为0的最小操作次数 
LeetCode链接
 
给你一个整数 n，你需要重复执行多次下述操作将其转换为 0 ：
翻转 n 的二进制表示中最右侧位（第 0 位）。
如果第 (i-1) 位为 1 且从第 (i-2) 位到第 0 位都为 0，则翻转 n 的二进制表示中的第 i 位。
返回将 n 转换为 0 的最小操作次数。
示例 1：
输入：n = 0
输出：0
示例 2：
输入：n = 3
输出：2
解释：3 的二进制表示为 "11"
"11" -> "01" ，执行的是第 2 种操作，因为第 0 位为 1 。
"01" -> "00" ，执行的是第 1 种操作。
示例 3：
输入：n = 6
输出：4
解释：6 的二进制表示为 "110".
"110" -> "010" ，执行的是第 2 种操作，因为第 1 位为 1 ，第 0 到 0 位为 0 。
"010" -> "011" ，执行的是第 1 种操作。
"011" -> "001" ，执行的是第 2 种操作，因为第 0 位为 1 。
"001" -> "000" ，执行的是第 1 种操作。
示例 4：
输入：n = 9
输出：14
示例 5：
输入：n = 333
输出：393
提示：
0 <= n <= 109
 
题目描述的是一次只改变n的二进制的其中一位，一步一步的改变直到变为0，就和逆序【从大到小】变化格雷码直到变为0所需要的操作次数是一样的，比如：格雷码1001，对应的二进制数是1110，那么将格雷码1001变成0000所需要的次数即为所求，这个次数就是它所对应的自然二进制数的大小，也就是说这道题其实就是一个格雷码的解码而已。
 想到和格雷码联系起来的大神实在太厉害了
 
 
 Java代码
 
class Solution {
    public int minimumOneBitOperations(int n) {
        int binary = n;
        while(n != 0){
            n >>= 1;
            binary ^= n;
        }
        return binary;
    }
}