status
Published
slug
leetcode-double-week-85-record
type
Post
category
Technology
date
Aug 21, 2022
tags
笔记
LeetCode
summary
Leetcode双周赛-85，做题记录和题解
第 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 个通过测试用例
思路学习：
看了其他人的解法，思路也都是逆向增加+合并
合并操作使用并查集来简化，果然还是写的题太少，做题时完全没有想到这个方法