Leetcode 雙周賽 41 題解

1684. 統計一緻字元串的數目

簡單模拟

class Solution {
public:
    int countConsistentStrings(string allowed, vector<string>& words) {
            int n = words.size(),num = 0;
            int hash[30];
            memset(hash,0,sizeof hash);
            for(int i = 0;i < allowed.size(); i ++) hash[allowed[i] - 'a'] ++;
            for(int i = 0 ;i < n ;i ++){
                int flag = 0;
                for(int j = 0 ; j < words[i].size(); j++){
                    if(!hash[words[i][j] - 'a']){
                        flag = 1;
                        break;
                    }
                }
                if(!flag) num ++;
            }
            return num;
    }
};
           

1685. 有序數組中差絕對值之和

簡單思維

class Solution {
public:
    vector<int> getSumAbsoluteDifferences(vector<int>& nums) {
        int n = nums.size();
        vector<int> s(n + 1);
        vector<int> r(n);
        for(int i = 1; i <= n ;i ++) s[i] = s[i-1] + nums[i-1];
        for(int i = 0;i < n ;i ++){
            r[i] = (i - 0 - (n - 1 - i)) * nums[i] - s[i] + s[n] - s[i+1];
        }
        return r;
    }
};
           

1686. 石子遊戲 VI

貪心

class Solution {
public:
    struct nod{
        int a,b;
    }node[100000 + 10];
    static bool cmp(nod x,nod y){
        return x.a + x.b > y.a + y.b;
    }
    int stoneGameVI(vector<int>& x, vector<int>& y) {
        for(int i = 0; i < x.size(); i ++){
            node[i].a = x[i];
            node[i].b = y[i];
        }
        int flag,numa = 0,numb = 0;
        sort(node,node+x.size(),cmp);
        for(int i = 0;i < x.size(); i ++){
            if(i&1){
                numb += node[i].b;
            }else{
                numa += node[i].a;
            }
        }
        if(numa > numb) flag = 1;
        else if(numa == numb) flag = 0;
        else flag = -1;
        return flag;
    }
};
           

class Solution {
public:
    int n; // 總個數
    vector<int> s; // 字首和數組

    // 計算把(l, r]區間裡的貨物運出去所花費的段數
    int cost(int l, int r) {
        // 如果左端點l + 1是起始點的話，那麼段數是分界點數
        if (s[l + 1] != s[l])
            return s[r] - s[l];
        // 如果左端點不是分界點的話，那麼段數就是分界點數+1
        return s[r] - s[l] + 1;
    }

    int boxDelivering(vector<vector<int>>& boxes, int portsCount, int maxBoxes, int maxWeight) {
        n = boxes.size();
        s.resize(n + 2);
        // 求字首和數組
        for (int i = 1; i <= n; i ++ ) {
            s[i] = s[i - 1];
            // 這裡要看一下i是不是分界點，每到分界點就+1
            if (i == 1 || boxes[i - 1][0] != boxes[i - 2][0])
                s[i] ++ ;
        }

        // dp的數組
        vector<int> f(n + 1);
        // 雙端隊列
        deque<int> q;
        q.push_back(0);
        // 從前往後周遊每個位置i
        // j是滿足限制能裝填貨物的最靠前的位置（j-1到i就不能裝進去了）
        // w是目前貨物的總重量
        for (int i = 1, j = 1, w = 0; i <= n; i ++ ) {
            // 把第i個箱子的重量加進來
            w += boxes[i - 1][1];
            // 因為i往前移動了，如果不滿足限制就一直把j往前移動，前面的貨物滑動出去
            while (w > maxWeight || i - j + 1 > maxBoxes) {
                w -= boxes[j - 1][1];
                j ++ ;
            }
            // 同時在隊列裡把滑出隊列的删除掉
            while (q.front() < j - 1)
                q.pop_front();
            // 目前的k
            int k = q.front();
            // dp計算，注意要加上回程時候的1
            f[i] = f[k] + cost(k, i) + 1;
            // 單調隊列優化，當隊尾比隊頭還差的時候就不停删除隊尾
            while (
            q.size() &&
            f[q.back()] >= f[i] + cost(i, i + 1) - cost(q.back(), i + 1)
                  )
                q.pop_back();
            // 将目前的i入隊
            q.push_back(i);
        }
        return f[n];
    }
};