Rank：389 / 4987，AC：3/4，Score：13/18

5185. 存在连续三个奇数的数组

比赛的时候写复杂了。。

class Solution {
public:
    bool threeConsecutiveOdds(vector<int>& arr) {
        vector<int> even;
        for(int i=0;i<arr.size();i++){
            if(arr[i]%2){
                even.push_back(i);
            }
        }
        if(even.size()<3) return false;
        for(int i=0;i<even.size();i++){
            int j=i;
            if(j+2>=even.size()) break;
            if(even[j]+1==even[j+1]&&even[j+1]+1==even[j+2]) return true;
        }
        return false;
    }
};

赛后看了别人的代码，自惭形愧…
其实这样写就行了..

class Solution {
public:
    bool threeConsecutiveOdds(vector<int>& arr) {
        for(int i=0;i+2<arr.size();i++){
            if(arr[i]%2&&arr[i+1]%2&&arr[i+2]%2) return true;
        }
        return false;
    }
};

5488. 使数组中所有元素相等的最小操作数

这个序列是 首项为1，尾项为(2*n-1)，公差为2的等差数列，然后我们可以算一下平均数为，按照平均数为对称轴从两边选就行，然后结果就是从1到n之前的数的差。
其实还可以继续推，当n为偶数时，；当n为奇数的时候 , ,当n为奇数的时候刚好截断,所以最后直接返回即可.

class Solution {
public:
    int minOperations(int n) {
        int  res = 0;
        for(int i=1;i<n;i=i+2){
            res += (n-i);
            cout << n-i << endl;
        }
        return res;
        // return n*n/4;
    }
};
// 推公式写法
class Solution {
public:
    int minOperations(int n) {
        return n*n/4;
    }
};

5489. 两球之间的磁力

任意两球间 最小磁力 最大, 根据题目的这种描述, 是要用二分,类似楼上扔鸡蛋的问题,将题目转换一下就是从n中选m个点让其间距尽可能的大.
时间复杂度:

class Solution {
public:
    int maxDistance(vector<int>& pos, int m) {
        sort(pos.begin(),pos.end());  // pos数组可能是无序的,需要排序
        int l = 0, r = 1e9;
        while(l<r){
            int mid = l+r+1 >>1;
            int count = 1,last = pos[0];
            for(int i=1;i<pos.size();i++){
                if(pos[i]-last>=mid) count ++,last = pos[i];
            }
            if(count>=m) l = mid;
            else r = mid-1;
        }
        return l;
    }
};

5490. 吃掉 N 个橘子的最少天数

DFS 记忆化写法

class Solution {
public:
    unordered_map<int,int> hash;
    int dfs(int n){
        if(n==1) return 1;
        if(hash[n]!=0) return hash[n];
        // 定义该子问题的结果
        int res = n; // 最坏情况是每天吃一个
        if(n%3==0)  res = min(res,dfs(n/3)+1);
        if(n%2==0) res = min(res,dfs(n/2)+1);
        // 如果能被6整除,就不尝试-1的情况,算是剪枝,不然会TLE
        if(n%6) res = min(res,dfs(n-1)+1);
        hash[n] = res;
        return res;
    }
    int minDays(int n) {
        return dfs(n);
    }
};

BFS写法

class Solution {
public:
    unordered_set<int> vis;
    int minDays(int n) {
        queue<int> qu,qu_next;
        qu.push(n); 
        vis.insert(n);
        int ans = 0;
        while(true){
            while(qu.size()){
                int e = qu.front(); qu.pop();
                if(!e) return ans;
                if(e%3==0&&vis.count(e/3)==0) {
                    qu_next.push(e/3), vis.insert(e/3);
                }
                if(e%2==0&&vis.count(e/2)==0) {
                    qu_next.push(e/2), vis.insert(e/2);
                }
                // 加个e%6的剪枝会快一点
                if(e%6&&vis.count(e-1)==0){
                    qu_next.push(e-1), vis.insert(e-1);
                }
            }
            ans++; qu = qu_next;
        }
        return n;
    }
};