leetcode 每日一题

发表于 更新于 分类于


[TOC]

Leetcode 每日一题

3193. 统计逆序对的数目【dp】【滚动数组】【前缀和优化】（2024.10.17）

好题，题解传送门。 【dp】+【滚动数组】+【前缀和优化】

910. 最小差值 II【贪心】（2024.10.21）

【贪心】

分析：

  贪心。小的变大，大的变小。故先排序，之后的关键是确定一个位置i,把0~i-1之间的都变大k,i~n-1之间的都减小k。

  变化后的数组的mx = max(nums[i - 1] + k, nums[n - 1] - k),mi = min(nums[0] + k, nums[i] - k)。（这里有一个点，分段是0~i-1和i~n-1，而不是0~i和i+1~n-1好处是后续处理的时候，可以不同特判n=1的情况）。

AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int smallestRangeII(vector<int>& nums, int k) {
        
        int n = nums.size();
        sort(nums.begin(), nums.end());
        int ans = nums[n - 1] - nums[0], mx, mi;

        //0 ~ i-1: +k, i ~ n - 1: -k
        for(int i = 1; i < n; ++i)
        {
            mx = max(nums[i - 1] + k, nums[n - 1] - k);
            mi = min(nums[0] + k, nums[i] - k);
            ans = min(ans, mx - mi);
        }

        return ans;
    }
};

3175. 找到连续赢 K 场比赛的第一位玩家（2024.10.24）

分析：

  只要不是k>=n,遍历一遍就有答案了。但是自己sb了妹反应过来

AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    int findWinningPlayer(vector<int>& skills, int k) {
        
        int n = skills.size();
        if(k >= n) return max_element(skills.begin(), skills.end()) - skills.begin();
        int l = 0, r = 1, tmp, cnt = 0;
        while(r < n)
        {
            if(cnt == k) return l;
            if(skills[l] < skills[r]) 
            {
                tmp = r;
                l = r;
                r = tmp + 1;
                cnt = 1;
            }
            else
            {
                ++cnt;
                ++r;
            }
        }

        return l;

    }
};

3181. 执行操作可获得的最大总奖励 II【dp】【bitset】【位运算】（2024.10.26）

  很典型的一个dp优化。【dp】+【bitset】+【位运算】

AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int maxTotalReward(vector<int>& rewardValues) {
        
        sort(rewardValues.begin(), rewardValues.end());
        rewardValues.erase(unique(rewardValues.begin(), rewardValues.end()), rewardValues.end());
        const int maxn = 100010;
        bitset<maxn> dp(1);

        int shit;
        for(const int& x: rewardValues)
        {
            shit = maxn - x;
            dp |= dp << shit >> (shit - x);
        }

        for(int i = maxn - 1; ; --i) if(dp[i]) return i;

    }
};

2209. 用地毯覆盖后的最少白色砖块 (2025.02.21)

  官方难度标的是[hard],实际应该是个简单dp。

dp[i][j]:当前这块长为len的地毯的右界在i，且正好用了j块地毯的情况下，剩下的白色最少为多少。

转移方程:$dp[i][j] = min(dp[i-1][j], dp[i-len][j - 1] - (sum[i] - sum[i - len]))$，其中sum数组是前缀和数组。

AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    int minimumWhiteTiles(string floor, int numCarpets, int carpetLen) {
        
        int n = floor.size();
        int ans = 0;
        vector<int> sum(n + 5, 0);
        floor = '$' + floor;
        
        for(int i = 1; i <= n; ++i) ans += (floor[i] == '1'), sum[i] = ans;

        vector<vector<int> > dp(n + 5, vector<int>(numCarpets + 5, ans));
        for(int i = 1; i <= carpetLen; ++i) 
        {
            for(int j = 1; j <= numCarpets; ++j) dp[i][j] -= sum[i];
        }
        for(int i = carpetLen + 1; i <= n; ++i)
        {
            for(int j = 1; j <= numCarpets; ++j)
            {
                dp[i][j] = min(dp[i - carpetLen][j - 1] - (sum[i] - sum[i - carpetLen]), dp[i - 1][j]);
            }
        }

        return dp[n][numCarpets];
    }
};

2353. 设计食物评分系统【有序集合set】【懒删除堆】（2025.02.28）

  我真是个笨比。

分析：

法一：有序集合（set）

  思路很简单，就是两个unordered_map，一个是food→{rating,cuisine},另一个是cuisine→set{rating,food}。但是自己写的太蠢了，很多细节不到位，常熟也比较大，T了。

法二：懒删除堆（priority_queue）

  就是第二个数据结构改成一个堆，但是只插入不删除，只有在查询的时候，获取堆顶元素的时候，判断当前元素是否已经被删除，所以叫懒删除堆，很形象。

AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class FoodRatings {
private:
    unordered_map<string, pair<int, string>> food_mp;
    unordered_map<string, set<pair<int, string>>> cuisine_mp; 
public:
    FoodRatings(vector<string>& foods, vector<string>& cuisines, vector<int>& ratings) {
        int n = foods.size();
        for(int i = 0; i < n; ++i)
        {
            auto& food = foods[i];
            auto& cuisine = cuisines[i];
            int rating = ratings[i];
            food_mp[food] = {rating, cuisine};
            cuisine_mp[cuisine].emplace(-rating, food);
        }
    }
    
    void changeRating(string food, int newRating) {
        auto& [rating, cuisine] = food_mp[food];
        auto& st = cuisine_mp[cuisine];
        st.erase({-rating, food});
        st.emplace(-newRating, food);
        rating = newRating;
    }
    
    string highestRated(string cuisine) {
        
        return cuisine_mp[cuisine].begin()->second;
    }
};

/**
 * Your FoodRatings object will be instantiated and called as such:
 * FoodRatings* obj = new FoodRatings(foods, cuisines, ratings);
 * obj->changeRating(food,newRating);
 * string param_2 = obj->highestRated(cuisine);
 */
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class FoodRatings {
private:
    using pis = pair<int, string>;

    unordered_map<string, pis> food_mp;
    unordered_map<string, priority_queue<pis, vector<pis>, greater<>>> cuisine_mp;
public:
    FoodRatings(vector<string>& foods, vector<string>& cuisines, vector<int>& ratings) {

        int n = foods.size();
        for(int i = 0; i < n; ++i)
        {
            auto& food = foods[i];
            auto& cuisine = cuisines[i];
            int rating = ratings[i];
            food_mp[food] = {rating, cuisine};
            cuisine_mp[cuisine].emplace(-rating, food);
        }
    }
    
    void changeRating(string food, int newRating) {
        auto& [rating, cuisine] = food_mp[food];
        
        cuisine_mp[cuisine].emplace(-newRating, food);
        rating = newRating;
    }
    
    string highestRated(string cuisine) {
        
        auto& pq = cuisine_mp[cuisine];
        while(-pq.top().first != food_mp[pq.top().second].first) pq.pop();
        return pq.top().second;
    }
};

/**
 * Your FoodRatings object will be instantiated and called as such:
 * FoodRatings* obj = new FoodRatings(foods, cuisines, ratings);
 * obj->changeRating(food,newRating);
 * string param_2 = obj->highestRated(cuisine);
 */

tips:

  1. unordered_map比map快，unordered_map比map快，unordered_map比map快。

  2. 对于字符串、容器等比较巨大的数据结构，以后直接用引用吧auto&。

  3. emplace是push_back和insert的上位替代。

  4. 对于那种，需要按第一关键字升序，第二关键字降序的那种，把另一关键字存成负的，这样对两个关键字的排序就统一了（方便set， priority_queue等容器）。

  5. erase有很多种用法。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    //删除指定值的元素
    std::set<int> st = {1, 2, 3, 4, 5};
    st.erase(3); // 删除值为 3 的元素
    //删除指定位置的元素
    std::set<int> st = {1, 2, 3, 4, 5};
    auto it = st.find(3); // 找到值为 3 的元素的迭代器
    if (it != st.end()) {
        st.erase(it); // 删除迭代器指向的元素
    }
    //删除一个范围内的元素
    std::set<int> st = {1, 2, 3, 4, 5};
    auto it1 = st.find(2); // 找到值为 2 的元素的迭代器
    auto it2 = st.find(4); // 找到值为 4 的元素的迭代器
    st.erase(it1, it2); // 删除 [2, 4) 范围内的元素

  6. priority_queue相关。

    1
    2
    priority_queue<int> pq; //默认大根堆
    priority_queue<int, vector<int>, greater<>> pq; //小根堆这么写

  7. 懒删除堆。很形象的名字，对于那些有删除需求，但又是弱删除的数据结构很有意义。

2179. 统计数组中好三元组数目【置换】【转换递增子序列】【枚举中间】【树状数组】(2025.04.15)

分析：

  置换：一个排列到另一个排列的双射。

  定义一个置换$P(x)$，将$nums_1$转化为一个递增的排列，$nums_2$同样需要通过$P(x)$映射。

  置换不是排序，是映射（可以理解成重命名），原来的公共子序列在映射后，子序列元素的位置没变，只是数值变了，仍然是公共子序列。所以置换不会改变公共子序列的个数。

  此时，只需要枚举三元组中间的元素$y$即可。而$nums_1$是递增的，所以问题转化为求$nums_2$中长度为3，中间元素为$y$的递增子序列的数量$num_y$。假设元素$y$位于位置$i$，左侧小于$y$的元素数量为$less_y$，而右侧大于$y$的元素数量为$more_y$。那么，$num_y = less_y * more_y$，而$more_y = n - 1 - y - (i - less_y)$。

  求解$less_y$的过程利用值域树状数组非常方便（类似于求逆序对）。需要注意的是，这是的排列是从0开始的，而树状数组下标是从1开始的，要加1。

  思路来源。

AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
// s
template<typename T>
class FenwickTree {
    vector<T> tree;

public:
    FenwickTree(int n) : tree(n + 1) {}

    void update(int i, T val) {
        for (; i < tree.size(); i += i & -i) {
            tree[i] += val;
        }
    }

    T pre(int i) const {
        T res = 0;
        for (; i > 0; i &= i - 1) {
            res += tree[i];
        }
        return res;
    }
};


class Solution {
public:

    long long goodTriplets(vector<int>& nums1, vector<int>& nums2) {
        
        int n = nums1.size();
        vector<int> p(n + 5, 0);

        for(int i = 0; i < n; ++i) p[nums1[i]] = i + 1;

        long long ans = 0;
        FenwickTree<int> t(n);

        for (int i = 0; i < n - 1; i++) 
        {
            int y = p[nums2[i]];
            int less = t.pre(y - 1);
            ans += 1LL * less * (n - y - (i - less));
            t.update(y, 1);
        }


        return ans;

    }
};

2799. 统计完全子数组的数目【滑动窗口】【双指针】（2025.04.24）

分析：

  子数组越长，越能满足题意。枚举子数组右端点r，当子数组满足条件时，不停的将nums[l]从子数组中移除，即++l。

  属于是「越长越合法」型滑动窗口，存在一个一般模板：

  • 维护一个有条件的滑动窗口
  • 右端点右移，导致窗口扩大，满足条件
  • 左端点右移，缩小窗口，找到右端点固定情况下，左端点的最右值（窗口大小的最小值）。

AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    int countCompleteSubarrays(vector<int>& nums) {
        
        unordered_set<int> st(nums.begin(), nums.end());
        int n = st.size();
        unordered_map<int, int> mp;
        int ans = 0;
        int l = 0;

        for(const auto& x : nums)
        {
            ++mp[x];
            while(mp.size() == n)
            {
                int y = nums[l];
                if(--mp[y] == 0) mp.erase(y);
                ++l;
            }
            ans += l;
        }

        return ans;
    }
};

838. 推多米诺【分类讨论】【bfs】（2024.05.02）

分析：

  • 方法1：分类讨论

    我的分类讨论水平好差。

    可能会出现4种情况：

    • L…L: 中间的.全变L。
    • R…R: 全变R。
    • R…L: 前一半变R，后一半变L。
    • L…R: 不变。

    为了方便处理，可以在字符串前后各加一个哨兵，即定义s = 'L' + dominoes + 'R'。

  • 方法2：bfs模拟

    挺容易看出适合bfs的，我当时没想明白的是在同一个时刻同时受左右力导致平衡时怎么处理。其实是可以通过维护一个force数组结果的，并且弄清楚队列q中存的是受力的节点，而不是确定会被推倒的节点，是否被推倒是当前节点从队列中取出时，根据force数组判断的。

    • time: 记录被推翻的时间。-1表示未推翻。
    • force: 记录骨牌受到的力，形状是vector<string>。

AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// 方法1
class Solution {
public:
    string pushDominoes(string dominoes) {
        
        int n = dominoes.size();
        int pre = -1;
        char ch;
        for(int i = 0; i <= n; ++i)
        {
            ch = i < n ? dominoes[i] : 'R';
            if(ch == '.') continue;
            if(ch == (pre < 0 ? 'L' : dominoes[pre])) fill(dominoes.begin() + pre + 1, dominoes.begin() + i, ch);
            else if(ch == 'L')
            {
                fill(dominoes.begin() + pre + 1, dominoes.begin() + (pre + i + 1) / 2, 'R');
                fill(dominoes.begin() + (pre + i) / 2 + 1, dominoes.begin() + i, 'L');
            }
            pre = i;
        }

        return dominoes;
        
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
// 方法2
class Solution {
public:
    string pushDominoes(string dominoes) {
        
        int n = dominoes.size();
        queue<int> q;
        vector<int> time(n, -1);
        vector<string> force(n);

        for(int i = 0; i < n; ++i) 
        {
            if(dominoes[i] != '.')
            {
                q.emplace(i);
                time[i] = 0;
                force[i].push_back(dominoes[i]);
            }
        } 

        string res(n, '.');
        int id, nxt, t;
        char ch;
        while(!q.empty())
        {
            id = q.front();
            q.pop();
            if(force[id].size() == 1)
            {
                ch = force[id][0];
                res[id] = ch;
                nxt = (ch == 'L') ? (id - 1) : (id + 1);
                if(nxt >= 0 && nxt < n)
                {
                    t = time[id];
                    if(time[nxt] == -1)
                    {
                        q.emplace(nxt);
                        time[nxt] = t + 1;
                        force[nxt].push_back(ch);
                    }
                    else if(time[nxt] == t + 1) force[nxt].push_back(ch);
                }
            }
        }

        return res;
    }
};

790. 多米诺和托米诺平铺【分类讨论】【推公式】【动态规划】【矩阵快速幂】（2024.05.05）

分析：

  dp[i][j]为前i-1列铺满，i列为状态j的情况下，一共有多少种方法。图片来源

image-20250505174956479

image-20250505175008585

  还可以用矩阵快速幂加速，初始时dp[0]对应的列向量为$x = [0 \ 0 \ 0 \ 1]^T$,n次转移后，dp[n]对应的$A^nx$。由此需要确定$A$，根据转移方程易得：

AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
const long long mod = 1e9 + 7;
class Solution {
public:
    int numTilings(int n) {
        
        vector<vector<long long>> dp(n + 5, vector<long long>(4, 0));
        
        dp[0][3] = 1;
        for(int i = 1; i <= n; ++i)
        {
            dp[i][0] = dp[i - 1][3];
            dp[i][1] = (dp[i - 1][0] + dp[i - 1][2]) % mod;
            dp[i][2] = (dp[i - 1][0] + dp[i - 1][1]) % mod;
            dp[i][3] = (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2] + dp[i - 1][3]) % mod;
        }

        return dp[n][3];
        
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
const long long mod = 1e9 + 7;
class Solution {
public:
    vector<vector<long long>> mulMatrix(const vector<vector<long long>> &a, const vector<vector<long long>> &b)
    {
        int m = a.size(), k = b.size(), n = b[0].size();
        vector<vector<long long>> res(m, vector<long long>(n));

        for(int i = 0; i < m; ++i)
        {
            for(int j = 0; j < n; ++j)
            {
                for(int kk = 0; kk < k; ++kk)
                {
                    res[i][j] = (res[i][j] + a[i][kk] * b[kk][j]) % mod;
                }
            }
        }

        return res;
    }

    int numTilings(int n) {
        
        vector<vector<long long>> mat = {
            {0, 0, 0, 1},
            {1, 0, 1, 0},
            {1, 1, 0, 0},
            {1, 1, 1, 1}
        };

        vector<vector<long long>> matn = {
            {1, 0, 0, 0},
            {0, 1, 0, 0},
            {0, 0, 1, 0},
            {0, 0, 0, 1}
        };

        while(n)
        {
            if(n & 1) matn = mulMatrix(matn, mat);
            mat = mulMatrix(mat, mat);
            n >>= 1;
        }

        return matn[3][3];
        
    }
};

3335. 字符串转换后的长度 I【动态规划】【矩阵快速幂】

分析：

img

img

  I不用矩阵快速幂也可, II需要。
AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// I
class Solution {
public:
    const long long mod = 1e9 + 7;
    int lengthAfterTransformations(string s, int t) {
        
        vector<vector<long long>> dp(t + 5, vector<long long>(26, 0));
        vector<int> nums = {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2};
        vector<long long> cnt(26, 0);

        //cout << nums.size() ;
        for(int i = 0; i < 26; ++i) dp[0][i] = 1;
        for(int i = 1; i <= t; ++i)
        {
            for(int j = 0; j < 26; ++j)
            {
                for(int k = 1; k <= nums[j]; ++k) dp[i][j] = (dp[i][j] + dp[i - 1][(j + k) % 26]) % mod;
            }
        }

        for(const auto& x : s) ++cnt[x - 'a'];
        int ans = 0;
        for(int i = 0; i < 26; ++i) ans = (ans + (dp[t][i] * cnt[i]) % mod) % mod;

        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
// II
const long long mod = 1e9 + 7;
class Solution {
public:

    vector<vector<long long>> mulMatrix(const vector<vector<long long>> &a, const vector<vector<long long>> &b)
    {
        int m = a.size(), k = b.size(), n = b[0].size();
        vector<vector<long long>> res(m, vector<long long>(n, 0));

        for(int i = 0; i < m; ++i)
            for(int j = 0; j < n; ++j)
                for(int kk = 0; kk < k; ++kk)
                    res[i][j] = (res[i][j] + a[i][kk] * b[kk][j]) % mod;

        return res;
    }

    int lengthAfterTransformations(string s, int t, vector<int>& nums) {
        
        vector<vector<long long>> matn(26, vector<long long>(26, 0));
        vector<vector<long long>> mat(26, vector<long long>(26, 0));
        vector<long long> dp(26, 0);
        vector<long long> cnt(26, 0);

        for(int i = 0; i < 26; ++i)
        {
            matn[i][i] = 1;
            for(int k = 1; k <= nums[i]; ++k) mat[i][(i + k) % 26] = 1;
        }

        while(t)
        {
            if(t & 1) matn = mulMatrix(matn, mat);
            mat = mulMatrix(mat, mat);
            t >>= 1;
        }

        for(int i = 0; i < 26; ++i)
            for(int j = 0; j < 26; ++j) 
                dp[i] = (dp[i] + matn[i][j]) % mod;
        
        for(const auto& x : s) ++cnt[x - 'a'];

        long long ans = 0;
        for(int i = 0; i < 26; ++i) ans = (ans + dp[i] * cnt[i]) % mod;;

        return ans;
    }
};