weekly-contest-209

Weekly-contest-209

第一次进前一百五，主要是最后一题强行找规律，WA多次之后终于做出来，算是占了放假后大佬都不见了的便宜

1/5531. 特殊数组的特征值

• 特征值不大于数组长度，遍历所有特征值判断，答案唯一。

class Solution {
    public int specialArray(int[] nums) {
        int len = nums.length;
        int result = -1;
        for(int i=0; i<=len; i++){
            int count = 0;
            for(int num:nums){
                if(num>=i)count++;
            }
            if(count==i){
                result=i;
                break;
            }
        }
        return result;
    }
}

2/5532. 奇偶树

• 没有什么好说的，树的层次遍历，加上层数和层内数字奇偶性的判断以及层内单调性的判断。需要注意的是在遍历一层的时候，for循环中使用的条件判断不能直接使用queue.size()，因为队列在循环中入队出队，大小会变化，需要在外界用一个int储存初始大小。

class Solution {
    //层次遍历
    public boolean isEvenOddTree(TreeNode root) {
        if(root==null)return true;
        Queue<TreeNode> queue = new LinkedList<>();
        TreeNode cur = root;
        queue.offer(root);
        
        int level = 0;
        while(!queue.isEmpty() && cur!=null){
            List<TreeNode> nums = new ArrayList<>();
            TreeNode p;
            int size = queue.size();
            for(int i=0; i<size; i++){
                cur = queue.poll();
                nums.add(cur);
                if(cur.left!=null)queue.offer(cur.left);
                if(cur.right!=null)queue.offer(cur.right);
            }
            //判断递增或是递减
            if(!judge(nums, level))return false;
            level++;
        }
        return true;
    }
    
    public boolean judge(List<TreeNode> nums, int level){
        if(level%2==0){
            for(int i=0; i<nums.size()-1; i++){
                if(nums.get(i).val%2!=1)return false;
                if(nums.get(i).val>=nums.get(i+1).val)return false;
            }
            if(nums.get(nums.size()-1).val%2!=1)return false;
        }
        if(level%2==1){
            for(int i=0; i<nums.size()-1; i++){
                if(nums.get(nums.size()-1).val%2!=0)return false;
                if(nums.get(i).val<=nums.get(i+1).val)return false;
            }
            if(nums.get(nums.size()-1).val%2!=0)return false;
        }
        return true;
    }
}

3/5534. 可见点的最大数目

• 因为斜率转换角度的方法不太清楚，所以直接跳过这题了
• 贴个其他人的题解

class Solution {
public int visiblePoints(List<List<Integer>> points, int angle, List<Integer> location) {
        double[] angles = new double[points.size()];
        int index = 0, count = 0;   // 自己所在的位置有多少个点
        for(List<Integer> point : points) {
            if(point.get(0).equals(location.get(0)) && point.get(1).equals(location.get(1))) {
                count++;
                continue;
            }
            // 得到[0,360)范围的角度
            double theta = Math.atan2(point.get(1) - location.get(1), point.get(0) - location.get(0)) / Math.PI * 180;
            if(theta < 0) theta += 360;
            angles[index++] = theta;
        }
        Arrays.sort(angles, 0, index);
        double[] nums = new double[index * 2];
        System.arraycopy(angles, 0, nums, 0, index);
        for(int i = 0; i < index; i++) {
            angles[i] += 360;
        }
        System.arraycopy(angles, 0, nums, index, index);

        // 双指针法找angle覆盖下的最长的子数组
        int left = 0, res = 0;
        for(int i = 0; i < nums.length; i++) {
            double diff = nums[i] - nums[left];
            while(left <= i && diff > angle) {
                left++;
                diff = nums[i] - nums[left];
            }
            res = Math.max(res, i - left + 1);
        }
        return res + count;
    }
}

4/5533. 使整数变为 0 的最少操作次数

• 题目描述的与格雷码相关，但是做的时候没有考虑这么多，找到规律，即操作数 F(2^n) = 2^(n+1) -1，F(8) = F(1000)2 = 15
• 每个数字的二进制都是由多个1组成的，F(12) = F(1100)2 = F(8)-F(4) = F(1000)2 -F(100)2 = 15 -7 =8，即12要转换为0需要转换8次
• 根据上述规律写出下列代码

class Solution {
    int[] powOfTwo = new int[32];
    public int minimumOneBitOperations(int n) {
        //二次方表
        for(int i=0;i<32;i++){
            powOfTwo[i] = (int)Math.pow(2,i);
        }
        
        //key-value: 值-操作次数
        Map<Integer,Integer> map = new HashMap<>();
        //corner case
        map.put(0,0);
        map.put(1,1);

        //map初始化
        int pow = 2;
        for(int i=2;i<=n; i=(int)Math.pow(2,pow++)){
            //i为2的次方
            //df[2^n] =  = 2^n + df[2^(n-1)]
            map.put(i,i+map.get(i/2));
        }
        
        int result = cal(n, map, 31);
        
        return result;
    }
    
    // 递归计算操作数
    public int cal(int n, Map<Integer,Integer> map,int index){
        if(n==0)return 0;
        
        int shortcut = 0;
        int nextIndex=0;
        for(int i=index; i>=0;i--){
            if(powOfTwo[i]<=n){
                shortcut = powOfTwo[i];
                nextIndex = i-1;
                break;
            }
        }
        return map.get(shortcut) - cal(n-shortcut, map, nextIndex);
    }
}