第209场周赛

时隔两周再一次参加周赛，相对于上一次，这一次比赛成绩进步了一些，针对每一道题，能够有一些思路，但是实现方法上不够简洁，速度上还是太慢，一些效得细节还是把握不太好，后面针对这些问题还是得解决一下。本次记录代码有些参考前排大佬。

1608. 特殊数组的特征值（EASY）

题目描述：给你一个非负整数数组 nums 。如果存在一个数 x ，使得 nums 中恰好有 x 个元素 大于或者等于 x ，那么就称 nums 是一个 特殊数组 ，而 x 是该数组的 特征值 。

注意： x 不必 是 nums 的中的元素。

如果数组 nums 是一个 特殊数组 ，请返回它的特征值 x 。否则，返回 -1 。可以证明的是，如果 nums 是特殊数组，那么其特征值 x 是 唯一的 。

分析：最简单的就是暴力求解

class Solution {
public:
    int specialArray(vector<int>& nums) {
        int cnt = 0;
        for (int i=0;i<=nums.size();i++){
            for(int n:nums){
                if(n>=i) cnt++;
            }
            if(cnt == i) return i;
            cnt = 0;
            
        }
        
        return -1;
    }
};

1609. 奇偶树（MEDIUM）

题目描述：如果一棵二叉树满足下述几个条件，则可以称为 奇偶树 ：

二叉树根节点所在层下标为 0 ，根的子节点所在层下标为 1 ，根的孙节点所在层下标为 2 ，依此类推。
偶数下标 层上的所有节点的值都是 奇 整数，从左到右按顺序 严格递增
奇数下标 层上的所有节点的值都是 偶 整数，从左到右按顺序 严格递减
给你二叉树的根节点，如果二叉树为 奇偶树 ，则返回 true ，否则返回 false 。

分析：二叉树类型的题目，那么初步我上的思路就是如何进行遍历，后续读题，抓住几个重点：层数，对每一层每一个节点奇偶性判断，对每一个节点顺序判断。观察树的示意图，发现类似BFS的遍历方式，那么这题就大体上确定下来：使用BFS框架，中间针对情况进行判定。我的代码如下：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isEvenOddTree(TreeNode* root) {
        if(!root) return false;
        if(root->val % 2 == 0) return false;
        return bfs(root);
    }
    bool bfs(TreeNode* root){
        queue<TreeNode*> q;
        q.push(root);
        int cnt = 0;
        while(!q.empty()){
            int s = q.size();
            int n = -1;
            for(int i=0;i<s;i++){
                TreeNode* node = q.front();
                q.pop();
                if(i == 0){
                    n = node->val;
                    if((cnt%2) == 0){
                        if(n%2 == 0) return false;
                    }
                    else if((cnt % 2) != 0){
                        if((n%2) != 0) return false;
                    }
                    
                    if(node->left) q.push(node->left);
                    if(node->right) q.push(node->right);
                    
                    continue;
                }
                
                //
                if((cnt % 2) == 0){
                    if((node->val%2) == 0) return false;
                    if(node->val <= n) return false;
                    n = node->val;
                }
                else if((cnt % 2) != 0){
                    if((node->val%2) != 0) return false;
                    if(node->val >= n) return false;
                    n = node->val;
                }
                
                //
                if(node->left) q.push(node->left);
                if(node->right) q.push(node->right);
                
            }
            cnt++;
            
        }
        return true;
        
    }
    
};

思考：代码冗余不简洁，有很多重复性的语句，可读性很差。看了前排大佬的代码，多用的是dfs，先利用dfs遍历二叉树，同时记录每一层节点的值，后续再遍历节点值，不符合条件判定为false。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int ok = 1;
    vector<int> v[100005];
    void dfs(TreeNode *rt, int dep) {
        if(rt->val%2 != dep%2) ok = 0;
        v[dep].push_back(rt->val);
        if(rt->left) dfs(rt->left, dep+1);
        if(rt->right) dfs(rt->right, dep+1);
    }
    bool isEvenOddTree(TreeNode* root) {
        if(!root) return 1;
        dfs(root, 1);
        if(!ok) return 0;
        for(int i=1;;++i) {
            if(v[i].empty()) break;
            for(int j=1;j<v[i].size();++j) {
                if((i&1) && v[i][j] <= v[i][j-1]) return 0;
                if((i%2==0) && v[i][j] >= v[i][j-1]) return 0;
            }
        }
        return 1;
    }
};

1610. 可见点的最大数目

题目描述：给你一个点数组 points 和一个表示角度的整数 angle ，你的位置是 location ，其中 location = [posx, posy] 且 points[i] = [xi, yi] 都表示 X-Y 平面上的整数坐标。

最开始，你面向东方进行观测。你 不能 进行移动改变位置，但可以通过 自转 调整观测角度。换句话说，posx 和 posy 不能改变。你的视野范围的角度用 angle 表示， 这决定了你观测任意方向时可以多宽。设 d 为逆时针旋转的度数，那么你的视野就是角度范围 [d - angle/2, d + angle/2] 所指示的那片区域。

分许：题目比较长，初一看容易头晕，问题关键主要有：自己所在的位置和点集的位置确定了，及相对位置已经定死，感受野的范围也是确定好的，那这里唯一能变化的就是旋转的角度，还有一个关键性的问题就是如何判定点是否在视野范围内。这里的一种解法是，首先检查点集中是否有和location重合的，然后计算每个点相对location的极坐标角度并进行排序，最后用双指针遍历所有点，看在视野范围内的最多能有几个点。这里一个新的函数是atan2（），可以计算极坐标角度。主要还是用到了数学知识，没有一些特殊的技巧。

class Solution {
public:
    int visiblePoints(vector<vector<int>>& ps, int angle, vector<int>& s) {
        int ans = 0;
        double pi = acos(-1.0);
        int x = s[0], y = s[1];
        vector<double> v;
        for(auto &p : ps) {
            if(x == p[0] && y == p[1]) {++ans;continue;}
            v.push_back(atan2(p[1]-y, p[0]-x));
        }
        sort(v.begin(), v.end());
        int n=v.size();
        for(int i=0;i<n;++i) v.push_back(v[i]+2*pi);
        int j=0;
        double g = 1.0 * angle * pi / 180;
        int tmp = 0;
        for(int i=0;i<n;++i) {
            while(j<i+n && (v[j]>=v[i]?v[j]-v[i]:v[j]+2*pi-v[i])<=g) ++j;
            tmp = max(tmp, j-i);
        }
        return ans + tmp;
    }
};

1611. 使整数变为 0 的最少操作次数

题目描述：给你一个整数 n，你需要重复执行多次下述操作将其转换为 0 ：

翻转 n 的二进制表示中最右侧位（第 0 位）。
如果第 (i-1) 位为 1 且从第 (i-2) 位到第 0 位都为 0，则翻转 n 的二进制表示中的第 i 位。
返回将 n 转换为 0 的最小操作次数。

分析：格雷码的运用，代码量并不是很大，但是思路很重要。

class Solution {
public:
    int minimumOneBitOperations(int n) {
        int ans = 0;
        while(n) {
            ans ^= n;
            n /= 2;
        }
        return ans;
    }
};

第209场周赛

原文：https://www.cnblogs.com/wushupei/p/13770241.html