第 209 场周赛回顾

前言

第一题：特殊数组的特征值

题解一：枚举

因为数组只有n个元素，因此可能的结果属于 [1,n] 。先对原数组排序，从n开始递减枚举，统计比x大的数的个数，直到找到符合答案。

import java.util.Arrays;
class Solution {
    public int specialArray(int[] nums) {
        final int n = nums.length;
        Arrays.sort(nums);
        int[] bigger = new int[n + 2];
        int index = n - 1;
        for (int i = n; i >= 0; --i) {
            bigger[i] = bigger[i + 1];
            while ((index >= 0) && (nums[index] >= i)) {
                ++bigger[i];
                --index;
            }
            if (i == bigger[i]) {
                return i;
            }
        }
        return -1;
    }
    public static void main(String[] args) {
        Solution s = new Solution();
        s.specialArray(new int[]{0, 0});
    }
}

第二题：奇偶树

题解一：广度优先遍历

广度优先遍历，判断每层结点是否符合要求。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode() {}
 * TreeNode(int val) { this.val = val; }
 * TreeNode(int val, TreeNode left, TreeNode right) {
 * this.val = val;
 * this.left = left;
 * this.right = right;
 * }
 * }
 */
class Solution {
    public boolean isEvenOddTree(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        if (root != null) {
            queue.offer(root);
        }
        int depth = -1;
        while (!queue.isEmpty()) {
            ++depth;
            int size = queue.size();
            int[] list = new int[size];
            int cur = -1;
            int last = -1;
            for (int i = 0; i < size; ++i) {
                TreeNode node = queue.poll();
                if (i > 0) {
                    last = cur;
                    cur = node.val;
                    if (depth % 2 == 0) { // 偶数层
                        if (cur % 2 == 0) {
                            return false;
                        }
                        if (cur <= last) {
                            return false;
                        }
                    } else { // 奇数层
                        if (cur % 2 == 1) {
                            return false;
                        }
                        if (cur >= last) {
                            return false;
                        }
                    }
                } else {
                    cur = node.val;
                    if (depth % 2 == 0) { // 偶数层
                        if (cur % 2 == 0) {
                            return false;
                        }
                    } else { // 奇数层
                        if (cur % 2 == 1) {
                            return false;
                        }
                    }
                }
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
        }
        return true;
    }
}

第三题：可见点的最大数目

题解一：滑动窗口法

计算每个点相对于观察者的角度，如果与观察者位置相等则一定可见，不再纳入后续的统计范围。对角度数组进行排序，每个角度加上360度并加入角度数组（因为观察角度一定小于360度），形成环。然后维护一个滑动窗口，首部和尾部的差距不大于观察角度，找出包含点数最多的窗口。（注意判断 double 类型变量相等的问题）

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
class Solution {
    public int visiblePoints(List<List<Integer>> points, int angle, List<Integer> location) {
        final int n = points.size();
        int base = 0;
        // 每个点相对于我的角度
        List<Double> angles = new ArrayList<>(n);
        for (List<Integer> p : points) {
            double tmp = getAngle(location, p);
            if (Double.isNaN(tmp)) {
                ++base;
            } else {
                angles.add(tmp);
            }
        }
        Comparator<Double> doubleComparator = new Comparator<Double>() {
            @Override
            public int compare(Double o1, Double o2) {
                return o1.compareTo(o2);
            }
        };
        angles.sort(doubleComparator);
        for (int i = 0, size = angles.size(); i < size; ++i) {
            angles.add(angles.get(i) + 360);
        }
        //System.out.println(angles);
        int begin = 0;
        double beginAngle = angles.get(begin);
        double endAngle = beginAngle + angle;
        int end = 0;
        while ((angles.get(end) < endAngle)||equal(angles.get(end), endAngle)) {
            ++end;
        }
        --end;
        int max = end - begin + 1;
        while (begin < angles.size() / 2) {
            while (equal(angles.get(begin + 1), angles.get(begin))) {
                ++begin;
            }
            ++begin;
            if ((begin >= angles.size() / 2)) {
                break;
            }
            beginAngle = angles.get(begin);
            endAngle = beginAngle + angle;
            // System.out.println(beginAngle + " " + endAngle);
            while ((angles.get(end) < endAngle)||equal(angles.get(end), endAngle)) {
                ++end;
            }
            --end;
            max = Math.max(end - begin + 1, max);
        }
        return max + base;
    }
    private boolean equal(double o1, double o2) {
        return Math.abs(o1 - o2) <= 1e-5;
    }
    private double getAngle(List<Integer> origin, List<Integer> p) {
        int deltaX = p.get(0) - origin.get(0);
        int deltaY = p.get(1) - origin.get(1);
        double r = Math.sqrt(Math.pow(deltaX, 2.0) + Math.pow(deltaY, 2.0));
        double angle = Math.acos(deltaX / r) / Math.PI * 180;
        if (deltaY < 0) {
            angle = 360 - angle;
        }
        return angle;
    }
}

第四题：使整数变为 0 的最少操作次数

题解一：

思路。