1

class Solution {
public:
    int sign(int x){
        if(x > 0) return 1;
        if(x < 0) return -1;
        return 0;
    }
    int arraySign(vector<int>& nums) {
        int res = 1;
        for(int i = 0;i < nums.size();i ++ ){
            int num = nums[i];
            if(!sign(num)) return 0;
            else res *= sign(num);
        }
        return res;
    }
};

2 剑指offer原题 lc变都不带变得

class Solution {
public:
    int f(int n, int k){
        if(n == 1) return 0;
        return (f(n - 1, k) + k) % n;
    }
    int findTheWinner(int n, int k) {
        return f(n, k) + 1;
    }
};

3

刚开始走的模拟，发现行不通，走的dp
dp[i][j] 表示在 i 处的 j 个通道上 走到终点的最小步数
init：dp[n][1] = dp[n][2] = dp[n][3] = 0
ans：dp[0][2]

转移方程：
    cost = (j != k)
    dp[i][j] = dp[i + 1][k] + cost
如果 dp[i + 1][k] == INF 行不通 continue
如果 当前通道有石头 行不通 continue
如果 上一个位置有石头也不行 continue

const int N = 5e5 + 10;

int dp[N][4];

class Solution {
public:
    #define INF 0x3f3f3f3f
    int minSideJumps(vector<int>& obstacles) {
        int n = obstacles.size();
        memset(dp, 0x3f, sizeof dp);
        dp[n][1] = dp[n][2] = dp[n][3] = 0;

        for(int i = n - 1;i >= 0;i -- ){
            for(int j = 1;j <= 3;j ++ ){
                if(j == obstacles[i]) continue;
                for(int k = 1;k <= 3;k ++ ){
                    if(k == obstacles[i]) continue;
                    int cost = (k != j);
                    if(dp[i + 1][k] == INF) continue;
                    dp[i][j] = min(dp[i][j], dp[i + 1][k] + cost);
                }
            }
        }

        return dp[0][2];
    }
};

4

using LL = long long;

class MKAverage {
public:
    struct Node{
        LL sum = 0;
        multiset<int> s;
        void insert(int x){
            s.insert(x);
            sum += x;
        }
        void erase(int x){
            s.erase(s.find(x));
            sum -= x;
        }
    }L, M, R;
    int m, k;
    vector<int> q;

    MKAverage(int _m, int _k) {
        m = _m, k = _k;
    }

    void addElement(int num) {
        q.push_back(num);
        if(q.size() < m) return ;
        if(q.size() == m){
            auto w = q;
            sort(w.begin(), w.end());
            for(int i = 0;i < k;i ++ ) L.insert(w[i]);
            for(int i = k;i < m - k;i ++ ) M.insert(w[i]);
            for(int i = m - k;i < m;i ++ ) R.insert(w[i]);
        }else{
            M.insert(num);
            if(*M.s.begin() < *L.s.rbegin()){
                int x = *M.s.begin(), y = *L.s.rbegin();
                L.erase(y), L.insert(x);
                M.erase(x), M.insert(y);
            }
            if(*M.s.rbegin() > *R.s.begin()){
                int x = *M.s.rbegin(), y = *R.s.begin();
                R.erase(y), R.insert(x);
                M.erase(x), M.insert(y);
            }

            int t = q[q.size() - 1 - m];
            if(M.s.count(t)) M.erase(t);
            else if(L.s.count(t)){
                L.erase(t);
                int x = *M.s.begin();
                M.erase(x);
                L.insert(x);
            }else if(R.s.count(t)){
                R.erase(t);
                int x = *M.s.rbegin();
                M.erase(x);
                R.insert(x);
            }
        }
    }

    int calculateMKAverage() {
        if(q.size() < m) return -1;
        return M.sum / M.s.size();
    }
};

/**
 * Your MKAverage object will be instantiated and called as such:
 * MKAverage* obj = new MKAverage(m, k);
 * obj->addElement(num);
 * int param_2 = obj->calculateMKAverage();
 */