LeetCode笔记：Biweekly Contest 85

• LeetCode笔记：Biweekly Contest 85
  • 1. 题目一
    • 1. 解题思路
    • 2. 代码实现
  • 2. 题目二
    • 1. 解题思路
    • 2. 代码实现
  • 3. 题目三
    • 1. 解题思路
    • 2. 代码实现
  • 4. 题目四
    • 1. 解题思路
    • 2. 代码实现
    • 3. 算法优化

• 比赛链接：https://leetcode.com/contest/biweekly-contest-85/

1. 题目一

给出题目一的试题链接如下：

• 2379. Minimum Recolors to Get K Consecutive Black Blocks

1. 解题思路

这一题思路上是比较直接的，就是看连续的k个元素当中有多少个W的元素，遍历所有长度为k的窗口，找到其中的最小值即可。

2. 代码实现

给出python代码实现如下：

class Solution:
    def minimumRecolors(self, blocks: str, k: int) -> int:
        n = len(blocks)
        cnt = len([ch for ch in blocks[:k] if ch == "W"])
        res = cnt
        for i in range(n-k):
            if blocks[i] == "W":
                cnt -= 1
            if blocks[i+k] == "W":
                cnt += 1
            res = min(cnt, res)
        return res
1
2
3
4
5
6
7
8
9
10
11
12

提交代码评测得到：耗时38ms，占用内存13.8MB。

2. 题目二

给出题目二的试题链接如下：

• 2380. Time Needed to Rearrange a Binary String

1. 解题思路

这一题一开始觉得能够有什么直接的手段可以直接看出来答案，不过最终还是没有找到这样的方法，也许应该是有的，不过只能说能力限制吧。

所以最后这题也就是暴力地替换然后重复循环了，不过貌似耗时还能够接受……

2. 代码实现

给出python代码实现如下：

class Solution:
    def secondsToRemoveOccurrences(self, s: str) -> int:
        cnt = 0
        while s.find("01") != -1:
            s = s.replace("01", "10")
            cnt += 1
        return cnt
1
2
3
4
5
6
7

提交代码评测得到：耗时188ms，占用内存13.9MB。

3. 题目三

给出题目三的试题链接如下：

• 2381. Shifting Letters II

1. 解题思路

这一题的思路就是找到每一个元素在经过了一系列shift操作之后的最终移位距离，然后进行一次性变换。

而移位距离的计算，我们用一个累积数组就能够实现，倒是没啥太大的难度。

2. 代码实现

给出python代码实现如下：

class Solution:
    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:
        
        def move(ch, delta):
            a = ord('a')
            ch = (ord(ch) - a + delta) % 26 + a
            return chr(ch)
        
        n = len(s)
        delta = [0 for _ in range(n+1)]
        for st, ed, d in shifts:
            if d == 1:
                delta[st] +=1
                delta[ed+1] -= 1
            else:
                delta[st] -=1
                delta[ed+1] += 1
        delta = list(accumulate(delta))
        s = [move(ch, delta[i]) for i, ch in enumerate(s)]
        return "".join(s)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

提交代码评测得到：耗时2386ms，占用内存39.5MB。

4. 题目四

给出题目四的试题链接如下：

• 2382. Maximum Segment Sum After Removals

1. 解题思路

这一题我的思路还是比较直接的，就是仿照区间分割的方式。

每一次操作，都会将原先完整的某一个数拆分成两个数，因此，我们只需要在每次操作的时候找到这个数，然后将其进行拆分即可。

而如何找到这个数，我们只需要使用累积数组和二分搜索就能够大幅的优化执行效率，剩下来唯一的难点就在于边界条件的考察了。

2. 代码实现

给出python代码实现如下：

class Solution:
    def maximumSegmentSum(self, nums: List[int], removeQueries: List[int]) -> List[int]:
        n = len(nums)
        cumsum = [0] + list(accumulate(nums))
        s = []
        res = []
        _max = [cumsum[-1]]
        for idx in removeQueries:
            bisect.insort(s, idx)
            i = bisect.bisect_left(s, idx)
            if len(s) == 1:
                _max.pop()
                bisect.insort(_max, cumsum[idx]-cumsum[0])
                bisect.insort(_max, cumsum[-1]-cumsum[idx+1])
            elif i == 0:
                _max.pop(bisect.bisect_left(_max, cumsum[s[i+1]] - cumsum[0]))
                bisect.insort(_max, cumsum[idx]-cumsum[0])
                bisect.insort(_max, cumsum[s[i+1]]-cumsum[idx+1])
            elif i == len(s)-1:
                _max.pop(bisect.bisect_left(_max, cumsum[-1] - cumsum[s[i-1]+1]))
                bisect.insort(_max, cumsum[idx]-cumsum[s[i-1]+1])
                bisect.insort(_max, cumsum[-1]-cumsum[idx+1])
            else:
                _max.pop(bisect.bisect_left(_max, cumsum[s[i+1]] - cumsum[s[i-1]+1]))
                bisect.insort(_max, cumsum[idx]-cumsum[s[i-1]+1])
                bisect.insort(_max, cumsum[s[i+1]]-cumsum[idx+1])
            res.append(_max[-1])
        return res
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

提交代码评测得到：耗时9083ms，占用内存37.7MB。

3. 算法优化

可以看到，上述我们自己的算法耗时是非常恐怖的，基本就算是运气好刚刚通过了测评。

因此，我考察了一下其他大佬们的算法实现，其中有一位大佬时使用了union find的思路，算是目前执行效率最高的一个实现了。

我们将其算法实现摘录如下，供大家参考一下：

class Solution:
    def maximumSegmentSum(self, nums: List[int], queries: List[int]) -> List[int]:
        N = len(nums)
        tmp = 0
        s = defaultdict(int)
        p = defaultdict(int)
        p_sum = defaultdict(int)
        
        def ufind(x):
            if x not in s:
                p[x] = x
                p_sum[x] = nums[x]
                s[x] = 1
            if p[x] != x:
                p[x] = ufind(p[x])
                
            return p[x]
        
        def uunion(x, y):
            ux = ufind(x)
            uy = ufind(y)
            if s[ux] > s[uy]:
                ux, uy = uy, ux

            s[uy] += s[ux]
            p_sum[uy] += p_sum[ux]
            p[ux] = uy
        
        ans = [0 for x in range(N)]
        for i in range(N-1, -1, -1):
            ans[i] = tmp
            idx = queries[i]
            # need to add nums[queries[i]] and uunion it with its neighbors            
            if idx - 1 in s:
                uunion(idx, idx-1)
            if idx + 1 in s:
                uunion(idx, idx + 1)

            tmp = max(tmp, p_sum[ufind(idx)])
            
        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