186双周赛-①Q1-枚举②Q2-贪心/状态机DP③前缀和优化DP#

第 186 场双周赛 - 力扣（LeetCode）

https://www.wolai.com/bffX1CFhNVx9JdE1PHrb8g

Q2-枚举#

题意#

给你一个长度为 n 的整数数组 nums 和一个整数 k 。

如果满足以下条件，则下标对 (i, j) 被称为有效的：

0 <= i < j < n
j - i >= k

返回所有有效对中的 nums[i] + nums[j] 的最大值。

枚举#

枚举右，维护左，枚举的过程中维护nums[j-k]的最大值

1
class Solution:
2
    def maxValidPairSum(self, nums: list[int], k: int) -> int:
3
        ans = -inf
4
        pre = nums[0]
5
        for j in range(k,len(nums)):
6
            pre = max(pre,nums[j - k])
7
            ans = max(ans,pre + nums[j])
8
        return ans

1
class Solution {
2
public:
3
    int maxValidPairSum(vector<int>& nums, int k) {
4
        int ans = 0,mx = 0;
5
        for(int j = k;j < nums.size();j++){
6
            mx = max(mx,nums[j-k]);
7
            ans = max(ans,mx + nums[j]);
8
        }
9
        return ans;
10
    }
11
};

Q3-贪心/状态机DP#

题意#

给你两个长度同为 n 的二进制字符串 s1 和 s2 。

你可以对 s1以任意顺序执行以下操作任意次：

选择一个满足 s1[i] 为 '0' 的下标 i ，并将其更改为 '1' 。
选择一个满足 0 <= i < n - 1 且 s1[i] 和 s1[i + 1] 均为 '1' 的下标 i 。将这两个字符都更改为 '0' 。

返回使 s1 等于 s2 所需的最小操作次数。如果无法使 s1 等于 s2 ，则返回 -1 。

贪心#

灵神题解

1
class Solution:
2
    def minOperations(self, s1: str, t: str) -> int:
3
        n = len(s1)
4
        if n == 1 and s1[0] == '1' and t == '0':
5
            return -1
6
        s = list(s1)
7
        ans = 0
8
        for i in range(n):
9
            if s[i] == t[i]:
10
                continue
11
            if s[i] == '0':
12
                ans += 1
13
            elif i < n - 1 and s[i+1] == '1':
14
                ans += 1
15
                s[i+1] = '0'
16
            else:
17
                ans += 2
18
        return ans

1
class Solution {
2
public:
3
    int minOperations(string s, string t) {
4
        int n = s.size();
5
        if (n == 1 && s == "1" && t == "0") {
6
            return -1;
7
        }
8
        int ans = 0;
9
        for (int i = 0; i < n; i++) {
10
            if (s[i] == t[i]) {
11
                continue;
12
            }
13
            if (s[i] == '0') {
14
                ans++;
15
            } else if (i < n - 1 && s[i + 1] == '1') {
16
                ans++;
17
                s[i + 1] = '0';
18
            } else {
19
                ans += 2;
20
            }
21
        }
22
        return ans;
23
    }
24
};

状态机DP#

1
class Solution:
2
    def minOperations(self, s1: str, s2: str) -> int:
3
        n = len(s1)
4
        s1 = list(s1)
5
        s2 = list(s2)
6
        if n == 1:
7
            if s1 == s2:
8
                return 0
9
            return 1 if s1[0] == '0' and s2[0] == '1' else -1
10
        d = [int(s2[i]) - int(s1[i]) for i in range(n)]
11
        c2 = [0]*(n - 1)
12
        c2[-1] = max(0,-d[-1])
13
        for i in range(n-3,-1,-1):
14
            c2[i] = max(0,-d[i+1] - c2[i+1])
15
        c2[0] = max(c2[0],-d[0])
16
        return sum(d) + 3 * sum(c2)

音乐

音乐

186双周赛-①Q1-枚举②Q2-贪心/状态机DP③前缀和优化DP#

Q2-枚举#

题意#

枚举#

Q3-贪心/状态机DP#

题意#

贪心#

状态机DP#

Q4-前缀和优化DP#

音乐

目录