天天看點
傳回

2022/10 LeetCode練習

🔰🔰🔰:困難

🔰🔰:中等

🔰:簡單

文章目錄

  • ​​`🔰🔰🔰`927.三等分​​
  • ​​`🔰🔰`811.子域名通路計數​​
  • ​​`🔰🔰`921.使括号有效的最少添加​​
  • ​​`🔰🔰`287.尋找重複數​​
  • ​​法一: 原地哈希​​
  • ​​`🔰🔰`(貪心)870.優勢洗牌​​
  • ​​`🔰🔰`856.括号的分數​​
  • ​​`🔰🔰🔰`(狀壓DP)801.使序列遞增的最小交換次數​​
  • ​​`🔰🔰`53.最大子數組和​​
  • ​​`🔰`1790.僅執行一次字元串交換能否使兩個字元串相等​​
  • ​​`🔰🔰`131.分割回文串​​
  • ​​遞歸回溯​​
  • ​​通過dp預處理優化​​
  • ​​`🔰🔰`5.最長回文子串​​
  • ​​`🔰🔰`817.連結清單元件​​
  • ​​`🔰🔰`769.最多能完成排序的塊​​
  • ​​`🔰🔰🔰`940.不同的子序列 II​​
  • ​​初步優化​​
  • ​​`🔰🔰`1441.用棧操作建構數組​​
  • ​​`🔰🔰🔰`6207.統計定界子數組的數目​​
  • ​​`🔰🔰`886.可能的二分法​​
  • ​​dfs​​
  • ​​并查集​​
  • ​​`🔰🔰`904.水果成籃​​
  • ​​優化​​
  • ​​`🔰🔰🔰`902.最大為 N 的數字組合​​
  • ​​dfs, 逾時​​
  • ​​數位DP​​
  • ​​`🔰`1700.無法吃午餐的學生數量​​
  • ​​`🔰🔰`779.第K個文法符号​​
  • ​​遞歸模拟​​
  • ​​✨位運算, 奇偶校驗​​
  • ​​(單調棧)`🔰🔰`901.股票價格跨度​​
  • ​​`🔰🔰🔰`1235.規劃兼職工作​​
  • ​​動态規劃​​
  • ​​二分優化​​
  • ​​`🔰`1768.交替合并字元串​​
  • ​​`🔰🔰`915.分割數組​​
  • ​​bfs+dfs `🔰🔰`934.最短的橋​​
  • ​​`🔰🔰`560.和為 K 的子數組​​
  • ​​`🔰🔰🔰`862.和至少為 K 的最短子數組​​
  • ​​暴力解法, 逾時​​
  • ​​雙端隊列​​
  • ​​(單調棧)`🔰🔰`907.子數組的最小值之和​​
  • ​​🤙歡迎關注泥煙的客棧(常在這裡更新)​​

🔰🔰🔰927.三等分

​​https://leetcode.cn/problems/three-equal-parts/​​

class Solution {
public:
    vector<int> threeEqualParts(vector<int>& arr) {
        int total = 0, len = arr.size();
        for(int i = 0 ; i < len; i ++) {
            if(arr[i]) total ++;
        }

        if(total == 0) return {0, 2};
        if(total % 3 != 0) return {-1, -1};

        int avg = total / 3;
        int f[6] = {1, avg, avg + 1, 2*avg, 2*avg + 1, total};
        int site[6];

        int cnt1 = 0;
        for(int i = 0, j = 0 ; i < len; i ++) {
            if(!arr[i]) continue;
            cnt1 ++;
            while(j < 6 && cnt1 == f[j]) site[j ++] = i; //
        }

        int cnt0 = len - 1 - site[5];
        // 判斷前兩段尾部零是否夠用
        if(site[2]-site[1]-1 < cnt0 || site[4]-site[3]-1 < cnt0) return {-1, -1};

        // 判斷三段是否完全相同
        if(!judge(arr, site[0], site[1], site[2], site[3])) return {-1, -1};
        if(!judge(arr, site[0], site[1], site[4], site[5])) return {-1, -1};
        return {site[1]+cnt0, site[3]+cnt0+1};
    }

    bool judge(vector<int>& arr, int l1, int r1, int l2, int r2){
        for(int i = l1, j = l2; i <= r1; i ++, j ++)
            if(arr[i]^arr[j])
                return false;
        
        return true;
    }
};

🔰🔰811.子域名通路計數

​​https://leetcode.cn/problems/subdomain-visit-count/​​

class Solution {
public:
    vector<string> subdomainVisits(vector<string>& cpdomains) {
        unordered_map<string, int> cnt;
        for(auto& t : cpdomains)
        {
            int a = t.find(' ');
            int num = stoi(t.substr(0, a));
            t = t.substr(a + 1);
            while(1)
            {
                cnt[t] += num;
                a = t.find('.');
                if(a == -1) break;
                t = t.substr(a + 1);
            }
        }

        vector<string> res;
        for(auto& [str, n]:cnt)
        {
            res.push_back(to_string(n) + ' ' + str);
        }
        return res;
    }
};

🔰🔰921.使括号有效的最少添加

​​https://leetcode.cn/problems/minimum-add-to-make-parentheses-valid/​​

class Solution {
public:
    int minAddToMakeValid(string s) {
        int res = 0, v = 0;
        for(auto& t : s)
        {
            v += t == '(' ? 1 : -1;
            // 保持v為非負數
            if(v < 0) v = 0, res ++;
        }
        return res + v;
    }
};

🔰🔰287.尋找重複數

​​https://leetcode.cn/problems/find-the-duplicate-number​​

法一: 原地哈希

将​

​nums[i]​

​​存儲在​

​nums[nums[i]-1]​

​

  • 若i == nums[i]-1, 則遊标向後移動
  • 若​

    ​nums[i] = nums[nums[i]-1]​

     ​,則有重複
  • 若​

    ​nums[i] != nums[nums[i]-1]​

     ​,則交換 
class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int n = nums.size();
        for(int i = 0; i < n; )
        {
            int site = nums[i]-1;
            if(site == i) {
                i ++; 
                continue;
            }
            if(nums[site] == nums[i]) return nums[i];
            else swap(nums[site], nums[i]);
        }

        return -1;
    }
};

🔰🔰(貪心)870.優勢洗牌

​​https://leetcode.cn/problems/advantage-shuffle/​​

思路:

和田忌賽馬差不多, 這裡麻煩在于nums2保持不變

将nums1數組的最小值與nums2數組的最小值相比較

  • 如果前者更大, 則将該數放到nums2數組的最小值所處的位置
  • 如果後者更大, 則将該數放到nums2數組的最大值所處的位置(采用破罐子好摔的戰略,即我連 你小的數都比不過,那我臨走前要和你大的數比,而我的大數養精蓄銳) 
class Solution {
public:
    vector<int> advantageCount(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size();
        
        vector<int> res(n);
        vector<pair<int, int>> v2(n);
        for(int i = 0; i < n; i ++) v2[i] = {nums2[i], i};
        sort(v2.begin(), v2.end());
        sort(nums1.begin(), nums1.end());

        int l = 0, r = n-1;
        for(int i = 0; i < n ; i ++)
        {
            int site = nums1[i] > v2[l].first ? v2[l++].second : v2[r--].second;
            res[site] = nums1[i];
        }

        return res;
    }
};

🔰🔰856.括号的分數

​​https://leetcode.cn/problems/score-of-parentheses​​

class Solution {
public:
    int scoreOfParentheses(string s) {
        int res = 0, x = 0, len = s.size();
        for(int i = 0; i < len; i ++)
        {
            if(s[i] == '(') x ++;
            else{
                x --;
                res += (s[i-1] == '(') ? 1 << x : 0;
            }
        }

        return res;
    }
};

🔰🔰🔰(狀壓DP)801.使序列遞增的最小交換次數

​​https://leetcode.cn/problems/minimum-swaps-to-make-sequences-increasing/​​思路:

​​

​f[i][j]​

​​ => 在[0, i]區間内的最小交換次數, j=0/1表示第i個位置是否交換

f[0][0] = 0, f[0][1] = 1

可分為如下兩種情況更新f[][]

  • ​

    ​nums1[i]>nums1[i-1] && nums2[i]>nums2[i-1]​

     ​
  • ​

    ​f[i][0] = min{f[i][0], f[i-1][0]}​

     ​
  • ​

    ​f[i][1] = min{f[i][1], f[i-1][1]+1}​

     ​
  • ​

    ​nums1[i]>nums2[i-1] && nums2[i]>nums1[i-1]​

     ​
  • ​

    ​f[i][0] = min{f[i][0], f[i-1][1]}​

     ​
  • ​

    ​f[i][1] = min{f[i][1], f[i-1][0]+1}​

     ​ 
class Solution {
public:
    int minSwap(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size();
        int f[n+5][2];
        memset(f, 0x3f, sizeof(f));

        f[0][0] = 0, f[0][1] = 1;
        for(int i = 1; i < n; i ++)
        {
            if(nums1[i]>nums1[i-1] && nums2[i]>nums2[i-1]){
                f[i][0] = min(f[i][0], f[i-1][0]);
                f[i][1] = min(f[i][1], f[i-1][1]+1);
            }
            if(nums1[i]>nums2[i-1] && nums2[i]>nums1[i-1]){
                f[i][0] = min(f[i][0], f[i-1][1]);
                f[i][1] = min(f[i][1], f[i-1][0]+1);
            }
        }

        return min(f[n-1][0], f[n-1][1]);
    }
};

🔰🔰53.最大子數組和

​​https://leetcode.cn/problems/maximum-subarray/​​

前面的累加若是大于零,則對最終的最大值是有貢獻的

若是小于零, 則可以不考慮, 從目前位置重新加起

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        int res = INT_MIN, t = -1;
        for(int i = 0; i < n; i ++)
        {
            t = (t < 0) ? nums[i] : nums[i]+t;
            res = (res > t) ? res : t;
        }
        return res;
    }
};

🔰1790.僅執行一次字元串交換能否使兩個字元串相等

​​https://leetcode.cn/problems/check-if-one-string-swap-can-make-strings-equal/​​ 逐個比對同一位置上的字元, 若不同, 記錄下目前位置. 并且cnt++

  • cnt > 2, ✖
  • cnt = 0, ✔
  • cnt = 1, ✖
  • cnt = 2
  • ​

    ​s1[ch[0]] == s2[ch[1]] && s1[ch[1]] == s2[ch[0]]​

     ​, ✔
  • ✖ 
class Solution {
public:
    bool areAlmostEqual(string s1, string s2) {
        int n = s1.size();
        int cnt = 0, ch[105];
        for(int i = 0; i < n; i ++)
        {
            if(s1[i]!=s2[i]) ch[cnt++] = i;
            if(cnt == 3) return false;
        }

        if(cnt == 0) return true;
        if(cnt == 1) return false;
        if(s1[ch[0]] == s2[ch[1]] && s1[ch[1]] == s2[ch[0]]) return true;

        return false;
    }
};

🔰🔰131.分割回文串

​​https://leetcode.cn/problems/palindrome-partitioning/​​

遞歸回溯 

class Solution {
public:
    int len;
    vector<string> path;
    vector<vector<string>> res;

    vector<vector<string>> partition(string s) {
        len = s.size();
        dfs(0, s);
        return res;
    }

    void dfs(int u, string s) {
        if(u == len){
            res.push_back(path);
            return ;
        }
        for(int i = u; i < len; i ++) {
            if(check(s, u, i)) {
                path.push_back(s.substr(u, i+1-u));
                dfs(i+1, s);
                path.pop_back();
            }
        }
    }
    //判斷從l到r是否為回文串
    bool check(string s, int l, int r) {
        while(l <= r) {
            if(s[l ++] != s[r --]) return false;
        }
        return true;
    }
};
2022/10 LeetCode練習

通過dp預處理優化 

class Solution {
public:
    int len;
    bool st[20][20];
    vector<string> path;
    vector<vector<string>> res;

    vector<vector<string>> partition(string s) {
        len = s.size();
        dp(s);
        dfs(0, s);
        return res;
    }

    void dfs(int u, string s) {
        if(u == len){
            res.push_back(path);
            return ;
        }
        for(int i = u; i < len; i ++) {
            if(st[u][i]) {
                path.push_back(s.substr(u, i+1-u));
                dfs(i+1, s);
                path.pop_back();
            }
        }
    }

    void dp(string s)
    {
        memset(st, false, sizeof st);
        for(int i = 0; i < len; i ++) st[i][i] = true;
        for(int i = 0; i < len-1; i ++) {
            if(s[i] == s[i+1]) st[i][i+1] = true;
        }
        for(int k = 3; k <= len; k ++) {
            for(int l = 0; l + k - 1 < len; l ++) {
                int r = l + k - 1;
                if(s[l] == s[r] && st[l+1][r-1]) st[l][r] = true;
            }
        }
    }
};
2022/10 LeetCode練習

🔰🔰5.最長回文子串

​​https://leetcode.cn/problems/longest-palindromic-substring/​​

🔰🔰817.連結清單元件

​​https://leetcode.cn/problems/linked-list-components/​​​

​解題思路​

​​ 模拟, 哈希

2022/10 LeetCode練習

大緻過程如下

左遊标pl, 右遊标pr

若pl所在的結點值存在,

res++

pr從pl開始向右移動直到​​

​為空或者值不存在​

 ​就停止 
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
 
class Solution {
public:
    int numComponents(ListNode* head, vector<int>& nums) {
        int n = nums.size(), res = 0;
        bool st[10010];
        memset(st, false, sizeof st);
        for(int i = 0; i < n; i ++) st[nums[i]] = true;
        
        for(ListNode* pl = head, *pr = nullptr; pl != nullptr; )
        {
            if(st[pl->val])
            {
                res ++;
                pr = pl->next;
                while(pr != nullptr && st[pr->val]) pr = pr->next;
                if(pr) pl = pr->next;
                else break;
            }
            else pl = pl->next;
        }
        return res;
    }
};

🔰🔰769.最多能完成排序的塊

​​https://leetcode.cn/problems/max-chunks-to-make-sorted/​​

class Solution {
public:
    int maxChunksToSorted(vector<int>& arr) {
        int n = arr.size();
        int res = 0, _max = -1, _min = 100;
        for(int i = 0, j = 0; i < n; )
        {
            _max = max(_max, arr[j]);
            _min = min(_min, arr[j]);
            if(_max == j && _min == i)
            {
                res ++;
                _max = -1, _min = 100;
                i = j + 1;
            }
            j ++;
        }
        return res;
    }
};

其實隻用最大值就可以

class Solution {
public:
    int maxChunksToSorted(vector<int>& arr) {
        int n = arr.size();
        int res = 0, _max = -1;
        for(int i = 0; i < n; i ++) {
            _max = max(_max, arr[i]);
            if(_max == i) {
                res ++;
                _max = -1;
            }
        }
        return res;
    }
};

🔰🔰🔰940.不同的子序列 II

f[i] : 以目前字母結尾的子序列數量

last[i] : 字母’a’+i 最後出現的位置

​​

​對于每一種字元，我們隻需要找到其最後一次出現的位置（并且在位置 i 之前），并将對應的 f 值累加進 f[i] 即可​

​

class Solution {
public:
    int distinctSubseqII(string s) {
        int n = s.size();
        int MOD = 1e9+7, res = 0;
        int last[26], f[2010];
        for(int i = 0; i < 26; i ++) last[i] = -1;
        for(int i = 0; i < n; i ++) f[i] = 1;

        for(int i = 0; i < n ; i ++)
        {
            for(int j = 0; j < 26; j ++)
                if(last[j] != -1) 
                    f[i] = (f[i] + f[last[j]])%MOD;
            last[s[i] - 'a'] = i;
        }

        for(int i = 0; i < 26; i ++)
            if(last[i] != -1)
                res = (res + f[last[i]]) % MOD;
        
        return res;
    }
};

初步優化

上面寫法中過程中的f[i]表示以目前字母結尾的子序列數量

​​

​不妨用g[i] 表示目前情況下, 以'a'+i 字母結尾的子序列數量總數​

​ 最後累加g[]即可

class Solution {
public:
    int distinctSubseqII(string s) {
        int n = s.size();
        int MOD = 1e9+7, res = 0;
        int g[26];
        for(int i = 0; i < 26; i ++) g[i] = 0;

        for(int i = 0; i < n ; i ++)
        {
            int sum = 1;
            for(int j = 0; j < 26; j ++)
                sum = (sum + g[j]) % MOD;
            g[s[i] - 'a'] = sum;
        }

        for(int i = 0; i < 26; i ++)
                res = (res + g[i]) % MOD;
        
        return res;
    }
};

🔰🔰1441.用棧操作建構數組

​​https://leetcode.cn/problems/build-an-array-with-stack-operations/​​ 模拟

class Solution {
public:
    vector<string> buildArray(vector<int>& target, int n) {
        int len = target.size();
        vector<string> res;
        if(target[0]==1) res.push_back("Push");
        else{
            for(int j = 0; j < target[0]-1; j ++){
                res.push_back("Push");
                res.push_back("Pop");
            }
            res.push_back("Push");
        }
        
        for(int i = 1; i < len; i ++)
        {
            if(target[i]-target[i-1] == 1) res.push_back("Push");
            else{
                int d = target[i]-target[i-1]-1;
                for(int j = 0; j < d; j ++){
                    res.push_back("Push");
                    res.push_back("Pop");
                }
                res.push_back("Push");
            }
        }
        
        return res;
    }
};

🔰🔰🔰6207.統計定界子數組的數目

​​https://leetcode.cn/problems/count-subarrays-with-fixed-bounds/​​

​

​滑動數組​

​​ 更新最大最小值所在的位置, 在該區間之前(直到不滿足條件的數值)的數的個數,

即為定界子數組的數量

class Solution {
public:
    long long countSubarrays(vector<int>& nums, int minK, int maxK) {
        int n = nums.size();
        int imin = -1, imax = -1, iout = -1;
        long long res = 0L;
        for(int i = 0; i < n; ++i)
        {
            if(nums[i] == minK) imin = i;
            if(nums[i] == maxK) imax = i;
            if(nums[i] < minK || nums[i] > maxK) iout = i;
            res += max(min(imin, imax)-iout, 0);
        }

        return res;
    }
};

🔰🔰886.可能的二分法

​​https://leetcode.cn/problems/possible-bipartition/​​

​

​二分圖, 染色法​

​

dfs

借助dislikes[]構造邊, 相鄰的兩點不應在同一集合, 若在染色的過程中出現沖突的情況, 則無法配置設定成功

class Solution {
public:
    vector<int> color;
    vector<vector<int>> g;

    bool dfs(int u, int cl) {
        color[u] = cl;
        for(int ne: g[u]) {
            if(color[ne] == cl) return false;
            // 如果未分組, 且被分到另一組後不合理
            if(color[ne] == 0 && !dfs(ne, 3-cl)) return false;
        }
        return true;
    }

    bool possibleBipartition(int n, vector<vector<int>>& dislikes) {
        color.resize(n);
        g.resize(n);

        for(auto& p: dislikes) {
            int a = p[0]-1, b = p[1]-1;
            g[a].push_back(b);
            g[b].push_back(a);
        }

        for(int i = 0; i < n; i ++)
        {
            if(!color[i] && !dfs(i, 1))
                return false;
        }

        return true;
    }
};

時間複雜度:​

​O(n+m)​

​​ 空間複雜度:​

​O(n+m)​

​

2022/10 LeetCode練習

并查集 

class Solution {
public:
    vector<int> p;

    void add(int a, int b) {
        p[find(a)] = p[find(b)];
    }

    int find(int x) {
        if(x != p[x]) p[x] = find(p[x]);
        return p[x];
    }

    bool query(int a, int b) {
        return find(a) == find(b);
    }

    bool possibleBipartition(int n, vector<vector<int>>& dislikes) {
        p.resize(n*2+10);
        for(int i = 1; i <= n*2; i ++) p[i] = i;
        for(auto& t : dislikes){
            int a = t[0], b = t[1];
            if(query(a, b)) return false;
            add(a, b+n);
            add(b, a+n);
        }
        return true;
    }
};

時間複雜度:​

​O(n+m)​

​​ 空間複雜度:​

​O(n)​

​

2022/10 LeetCode練習

🔰🔰904.水果成籃

​​https://leetcode.cn/problems/fruit-into-baskets/​​

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        int n = fruits.size();
        int res = 0;
        unordered_map<int, int> mp;
        for(int i = 0, j = 0; j < n; j ++)
        {
            ++mp[fruits[j]];
            while(mp.size() > 2){
                int x = fruits[i++];
                if(--mp[x] == 0) mp.erase(x);
            }
            res = max(res, j-i+1);
        }

        return res;
    }
};
2022/10 LeetCode練習

優化

🔰🔰🔰902.最大為 N 的數字組合

​​https://leetcode.cn/problems/numbers-at-most-n-given-digit-set/​​

dfs, 逾時 

class Solution {
public:
    int num;
    int atMostNGivenDigitSet(vector<string>& digits, int n) {
        num = 0;
        dfs(digits, 0, n, num);
        return num;
    }

    void dfs(vector<string>& digits, int u, int n, int num) {
        if(u > n) return ;
        if(u && u <= n) ++num;

        for(auto& d : digits) {
            dfs(digits, u*10+d[0]-'0', n, num);
        }
    }
};

數位DP

​​>>>靈茶山艾府 - 數位 DP 通用模闆

​

class Solution {
public:
    int atMostNGivenDigitSet(vector<string>& digits, int n) {
        string s = to_string(n);

        int len = s.size(), dp[len];
        memset(dp, -1, sizeof(dp));

        function<int(int, bool, bool)> f = [&](int u, bool is_limit, bool is_num) -> int {
            if(u == len) return is_num; //方案數, 0 or 1
            if(!is_limit && is_num && dp[u] >= 0) return dp[u];

            int res = 0;
            if(!is_num) res = f(u+1, false, false);
            char up = is_limit ? s[u] : '9';

            for(auto& d : digits) {
                if(d[0] > up) break;
                res += f(u+1, is_limit && d[0] == up, true);
            }
            if(!is_limit && is_num) dp[u] = res;
            return res;
        };

        return f(0, true, false);
    }
};

🔰1700.無法吃午餐的學生數量

​​https://leetcode.cn/problems/number-of-students-unable-to-eat-lunch/​​

class Solution {
public:
    int countStudents(vector<int>& students, vector<int>& sandwiches) {
        int n = students.size();

        int cnt[2] = {0, 0};
        for(int i = 0; i < n; i ++) cnt[students[i]] ++;
        for(int i = 0; i < n; i ++)
            if(cnt[sandwiches[i]]-- == 0)
                return cnt[1-sandwiches[i]]; //return cnt[sandwiches[i]^1];
        
        return 0;
    }
};

🔰🔰779.第K個文法符号

​​https://leetcode.cn/problems/k-th-symbol-in-grammar/​​

遞歸模拟 

class Solution {
public:
    int kthGrammar(int n, int k) {
        if(n == 1) return 0;
        if(k <= (1<<(n-2))) return kthGrammar(n-1, k);
        return kthGrammar(n-1, k-(1<<(n-2)))^1;
    }
};

✨位運算, 奇偶校驗

​​【位操作筆記】計算奇偶性 使用乘法​​ 
class Solution {
public:
    int kthGrammar(int N, unsigned int K) {
        K -= 1;
        K ^= K >> 1;
        K ^= K >> 2;
        K = (K & 0x11111111U) * 0x11111111U;
        return (K >> 28) & 1;
    }
};

(單調棧)🔰🔰901.股票價格跨度

​​https://leetcode.cn/problems/online-stock-span/​​

class StockSpanner {
public:
    StockSpanner() {

    }
    
    int next(int price) {
        int res = 1;
        while(!st.empty() && st.top().first <= price) {
            res += st.top().second;
            st.pop();
        }
        st.push({price, res});
        return res;
    }

private:
    stack<pair<int ,int>> st;
};

/**
 * Your StockSpanner object will be instantiated and called as such:
 * StockSpanner* obj = new StockSpanner();
 * int param_1 = obj->next(price);
 */

🔰🔰🔰1235.規劃兼職工作

​​https://leetcode.cn/problems/maximum-profit-in-job-scheduling/​​

動态規劃 

class Jobs{
public:
    int startTime;
    int endTime;
    int profit;

    Jobs(){
    }
    
    Jobs(int a, int b, int c):startTime(a), endTime(b), profit(c){
    }
};

class Solution {
public:
    int jobScheduling(vector<int>& startTime, vector<int>& endTime, vector<int>& profit) {
        int n = startTime.size();
        vector<Jobs> jobs(n);
        for(int i = 0; i <n; ++i)
            jobs[i] = Jobs(startTime[i], endTime[i], profit[i]);

        //按截止時間排序
        sort(jobs.begin(), jobs.end(), [](const Jobs& a, const Jobs& b) -> bool{
            return a.endTime < b.endTime;
        });

        for(int i = 0; i < n; ++i) {
            int maxProfit = jobs[i].profit;
            for(int j = i - 1; j >= 0; --j) {
                if(jobs[j].endTime <= jobs[i].startTime){
                    maxProfit = max(maxProfit, jobs[j].profit+jobs[i].profit);
                    break;
                }else{
                    maxProfit = max(maxProfit, jobs[j].profit);
                }
            }
            jobs[i].profit = maxProfit;
        }

        return jobs[n-1].profit;
    }
};

二分優化

🔰1768.交替合并字元串

​​https://leetcode.cn/problems/merge-strings-alternately/​​

class Solution {
public:
    string mergeAlternately(string word1, string word2) {
        int n = word1.size(), m = word2.size();
        int i = 0, j = 0;
        string res ;
        while(i < n && j < m)
        {
            if(i < n) res += word1[i++];
            if(j < m) res += word2[j++];
        }
        while(i < n) {
            res += word1[i++];
        }
        while(j < m) {
            res += word2[j++];
        }

        return res;
    }
};

🔰🔰915.分割數組

​​https://leetcode.cn/problems/partition-array-into-disjoint-intervals/​​​ 從右往左初始化rightmin(目前位置右邊的最小值)數組

再從左往右掃描即可

class Solution {
public:
    int partitionDisjoint(vector<int>& nums) {
        int n = nums.size();
        int rightmin[n+5];
        int tmin = 1e6+10;
        for(int i = n - 2; i >= 0; --i){
            rightmin[i] = tmin < nums[i+1] ? tmin : nums[i+1];
            tmin = rightmin[i];
        }

        int res, tmax = -1;
        for(int i = 0; i < n; ++i){
            tmax = tmax > nums[i] ? tmax: nums[i];
            if(tmax <= rightmin[i]){
                res = i+1;
                break;
            }
        }
        return res;
    }
};

bfs+dfs 🔰🔰934.最短的橋

​​https://leetcode.cn/problems/shortest-bridge/​​

#define x first
#define y second

typedef pair<int ,int> PII;

class Solution {
public:
    int n, m;
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

    queue<PII> q;
    vector<vector<int>> g, dist;
    // 将一座島置為0, 并加入隊列
    void dfs(int x, int y) {
        g[x][y] = 0;
        dist[x][y] = 0;
        q.push({x, y});
        for(int i = 0; i < 4; ++i) {
            int nx = x + dx[i], ny = y + dy[i];
            if(nx < 0 || nx >= n || ny < 0 || ny >= m || !g[nx][ny]) continue;
            dfs(nx, ny);
        }
    }

    int bfs() {
        while(q.size()) {
            PII t = q.front();
            q.pop();
            for(int i = 0; i < 4; ++i){
                int nx = t.x + dx[i], ny = t.y + dy[i];
                if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
                // 待更新
                if(dist[t.x][t.y] + 1 >= dist[nx][ny]) continue;
                dist[nx][ny] = dist[t.x][t.y] + 1;
                if(g[nx][ny]) return dist[nx][ny]-1;
                q.push({nx, ny});
            }
        }
        return -1;
    }

    int shortestBridge(vector<vector<int>>& grid) {
        n = grid.size(), m = grid[0].size();
        g = grid;
        dist = vector<vector<int>>(n, vector<int>(m, 1e6));

        for(int i = 0; i < n; ++i)
            for(int j = 0; j < m; ++j)
                if(grid[i][j]){
                    dfs(i, j);
                    return bfs();
                }

        return -1;
    }
};

🔰🔰560.和為 K 的子數組

​​https://leetcode.cn/problems/subarray-sum-equals-k/​​

  • 如果利用字首和數組, 再二重循環暴力求解, 時間複雜度為O(n^2)
  • 優化寫法: 在每次累加字首和後, 判斷是否前面曾出現一個字首和​

    ​pre_sum = sum - k​

     ​, 即此時存在和為k的子數組在中間夾着. 時間複雜度為O(n) 
class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int n = nums.size();
        int cnt = 0, sum = 0;
        unordered_map<int, int> mp;
        mp[0] = 1;

        for(int i = 0; i < n; ++i) {
            sum += nums[i];
            cnt += mp[sum-k];
            ++mp[sum];
        }

        return cnt;
    }
};

🔰🔰🔰862.和至少為 K 的最短子數組

​​https://leetcode.cn/problems/shortest-subarray-with-sum-at-least-k/​​

暴力解法, 逾時

時間複雜度:O(n^2)

空間複雜度:O(n)

class Solution {
public:
    int shortestSubarray(vector<int>& nums, int k) {
        int n = nums.size();
        int sum[n+10];
        sum[0] = 0;
        for(int i = 0; i < n; ++i) {
            if(nums[i] >= k) return 1;
        }
        for(int i = 0; i < n; ++i) {
            sum[i+1] = sum[i]+nums[i];
        }
        int res = 1e5+10;
        for(int i = 1; i <= n; ++i) {
            for(int j = i+1; j <= n; ++j) {
                if(sum[j] - sum[i-1] >= k)
                    res = min(res, j-i+1);
            }
        }

        return res == 1e5+10 ? -1:res;
    }
};

雙端隊列

在上面的雙層循環中，還有一定的優化空間

比如當sum[x1] >= sum[x2]（x1 < x2）時，表明x1到x2之間的元素的和是負數或0，則sum[xn] - sum[x1] >= K時​

​必有sum[xn] - sum[x2] >= K​

 ​​，那麼這個時候我們隻計算xn - x2即可（​

​x1到x2之間的元素可以全部跳過​

​​），就不需要計算xn - x1了，因為後者一定是更大的，不滿足我們要選最小的條件。

另一個角度，當sum[x2] - sum[x1] >= K時，x1就可以跳過了，為什麼呢？因為x1到x2已經滿足了大于K，再繼續從x1開始向後再找，也不會再有比x2距離x1更近的了，畢竟我們要求的是最小的x2 - x1。

以上的兩種分析，情況1是把位于末尾沒用的x1扔掉，情況2是把指向前面的已經滿足條件的x1的指針向後移動1位，這是就需要比較目前最小值與此時剛符合條件的值的大小了。

class Solution {
public:
    int shortestSubarray(vector<int>& nums, int k) {
        int n = nums.size();
        long sum[n+10];
        sum[0] = 0;
        for(int i = 0; i < n; ++i) {
            if(nums[i] >= k) return 1;
        }
        for(int i = 0; i < n; ++i) {
            sum[i+1] = sum[i]+nums[i];
        }
        long res = 1e5+10;
        deque<int> dq;
        for(int i = 0; i <= n; ++i) {
            while(!dq.empty() && sum[i] <= sum[dq.back()]) {
                dq.pop_back();
            }

            while(!dq.empty() && sum[i] - sum[dq.front()] >= k) {
                int len = i - dq.front();
                dq.pop_front();
                res = res < len ? res : len;
            }
            dq.push_back(i);
        }

        return res == 1e5+10 ? -1:res;
    }
};

(單調棧)🔰🔰907.子數組的最小值之和

​​https://leetcode.cn/problems/sum-of-subarray-minimums/​​​ 參考: ​​0x3f 貢獻法+單調棧​​ 利用單調棧初始化left[]和right[]

class Solution {
    const int MOD = 1e9+7;
public:
    int sumSubarrayMins(vector<int>& arr) {
        int n = arr.size();
        vector<int> left(n, -1);
        vector<int> right(n, n);
        int stk[n], k = -1;
        for(int i = 0; i < n; ++i) {
            while(k != -1 && arr[stk[k]] >= arr[i]) --k;
            if(k != -1) left[i] = stk[k];
            stk[++k] = i;
        }
        
        k = -1;
        for(int i = n-1; i >= 0; --i) {
            while(k != -1 && arr[stk[k]] > arr[i]) --k;
            if(k != -1) right[i] = stk[k];
            stk[++k] = i;
        }

        long  res = 0L;
        for(int i = 0; i < n; ++i) {
            res += (long)arr[i]*(i-left[i])*(right[i]-i);
        }

        return res%MOD;
    }
};
2022/10 LeetCode練習

在更新left時,可以同時更新right

對于棧頂元素 t，如果 t 右側有多個小于或等于 t 的元素，那麼 t 隻會因為右側第一個小于或等于 t 的元素而出棧，這恰好符合右邊界的定義

class Solution {
    const int MOD = 1e9+7;
public:
    int sumSubarrayMins(vector<int>& arr) {
        int n = arr.size();
        vector<int> left(n, -1);
        vector<int> right(n, n);
        int stk[n], k = -1;
        for(int i = 0; i < n; ++i) {
            while(k != -1 && arr[stk[k]] >= arr[i]) {
                right[stk[k]] = i;
                --k;
            }
            if(k != -1) left[i] = stk[k];
            stk[++k] = i;
        }

        long  res = 0L;
        for(int i = 0; i < n; ++i) {
            res += (long)arr[i]*(i-left[i])*(right[i]-i);
        }

        return res%MOD;
    }
};
2022/10 LeetCode練習
class Solution {
    const int MOD = 1e9+7;
public:
    int sumSubarrayMins(vector<int>& arr) {
        arr.push_back(-1); //右哨兵
        int n = arr.size();
        int stk[n], k = -1;
        long res = 0L;
        stk[++k] = -1; //左哨兵
        for(int r = 0; r < n; ++r) {
            while(k > 0 && arr[stk[k]] >= arr[r]) {
                int t  = stk[k--];
                res += (long) arr[t]*(t - stk[k])*(r - t);
            }
            stk[++k] = r;
        }
        return res%MOD;
    }
};

🤙歡迎關注泥煙的客棧(常在這裡更新)

leetcode 算法 數組 字元串 最小值
上一篇: 音視訊名詞解釋
下一篇: 資料處理

繼續閱讀