LeetCode | 双周赛-85做题记录

status

Published

slug

leetcode-double-week-85-record

type

Post

第 85 场双周赛-链接

https://leetcode.cn/contest/biweekly-contest-85/

AC情况：

✅ ✅ ✅ ❌

1. 得到 K 个黑块的最少涂色次数

给你一个长度为 n 下标从 0 开始的字符串 blocks ，blocks[i] 要么是 'W' 要么是 'B' ，表示第 i 块的颜色。字符 'W' 和 'B' 分别表示白色和黑色。

给你一个整数 k ，表示想要连续黑色块的数目。

每一次操作中，你可以选择一个白色块将它涂成黑色块。

请你返回至少出现一次连续 k 个黑色块的最少操作次数。

解题思路：

这是一道简单题，最初的思路是通过递归或者是动态规划去做，明显把问题想复杂了，于是卡了一会儿，最后通过移动窗口的方式去解，实际上暴力应该也可以。

给出从下标0开始长度为k的窗口，统计其中'B' 的个数cntB，k-cntB就是该窗口内得到K个黑块的最少操作数，移动窗口并不断更新最小的k-cntB即得答案。

更新cntB时只需要判断窗口内移出和移入的字符状态。

移出字符为'B'，cntB--

移入字符为'B'，cntB++

复杂度：

AC代码：

2. 二进制字符串重新安排顺序需要的时间

给你一个二进制字符串 s 。在一秒之中，所有子字符串 "01" 同时被替换成 "10" 。这个过程持续进行到没有 "01" 存在。

请你返回完成这个过程所需要的秒数。

解题思路：

朴素的思路，按照题目模拟，每次都遍历查找出字符中的所有的"01"并替换为"10"，直到没有 "01" 存在

AC代码

3. 字母移位 II

给你一个小写英文字母组成的字符串 s 和一个二维整数数组 shifts ，其中 shifts[i] = [starti, endi, directioni] 。对于每个 i ，将 s 中从下标 starti 到下标 endi （两者都包含）所有字符都进行移位运算，如果 directioni = 1 将字符向后移位，如果 directioni = 0 将字符向前移位。

将一个字符向后移位的意思是将这个字符用字母表中 下一个 字母替换（字母表视为环绕的，所以 'z' 变成 'a'）。类似的，将一个字符向前移位的意思是将这个字符用字母表中 前一个 字母替换（字母表是环绕的，所以 'a' 变成 'z' ）。

请你返回对 s 进行所有移位操作以后得到的最终字符串。

解题思路

这道题又是一道模拟题，按照题目意思模拟即可。最朴素的写法就是定义出题中的shift方法，并不断按照shifts[i]处理字符串，这样的复杂度是

题目中 1 <= s.length, shifts.length <= 5 * 10^4，平方后大概在，不出所料的超时了。

于是想优化方法，题中字符的移位操作都是按照数组更新的，于是很容易就可以想到用差分来降低复杂度。

给定一个opV用来记录所有的移位操作，向前移位定义为-1，向后移位定义为+1，在所有移位操作记录完毕后，累加得到真正的移位数组，然后处理对应的移位操作，需要注意特殊情况和边界。

复杂度：

AC代码

4. 删除操作后的最大子段和

给你两个下标从 0 开始的整数数组 nums 和 removeQueries ，两者长度都为 n 。对于第 i 个查询，nums 中位于下标 removeQueries[i] 处的元素被删除，将 nums 分割成更小的子段。

一个子段是 nums 中连续正整数形成的序列。子段和 是子段中所有元素的和。

请你返回一个长度为 n 的整数数组 answer ，其中 answer[i]是第 i 次删除操作以后的最大子段和。

注意：一个下标至多只会被删除一次。

解题思路❌

这道题我的思路也是按照题意模拟，为了方便，逆向转换，把删除操作改为添加操作，使用node(val, ldx, rdx)来记录子数组的边界和子段和，遍历node的val，即可获得最大子段和，且每一次加入新节点后，都利用栈对相邻的子段进行合并，反转得到的最大子段和数组得到的就是每次删除操作的最大子段和。

复杂度：

代码

27 / 44 个通过测试用例

思路学习：

看了其他人的解法，思路也都是逆向增加+合并

合并操作使用并查集来简化，果然还是写的题太少，做题时完全没有想到这个方法