leetcode 每日一题

发表于 更新于 分类于

Leetcode 每日一题

3193. 统计逆序对的数目（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（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;

    }
};