leetcode 每日一题

发表于 更新于 分类于

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;

    }
};