Leetcode 【485、1004、1052】
Leetcode 【485、1004、1052】
问题描述：【Array】485. Max Consecutive Ones
解题思路：
因为要找最长连续 1 子数组的长度，所以我们只需要遍历一次，记录每段连续 1 的长度；如果遇到 0，就更新当前最大长度，然后当前长度清零，继续向后遍历。时间复杂度为 O(n)。
Python3 实现：
class Solution:
def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
max_ = tem = 0
for i in range(len(nums)):
if nums[i] == 0:
max_ = max(max_, tem) # 更新当前最大长度
tem = 0
else:
tem += 1
return max(max_, tem)问题描述：【Array】487. Max Consecutive Ones
收费暂时做不了 hhh~ 题目是最多改变其中 1 个 0 变成 1，然后求最长连续 1 子数组的长度。可以采用滑动窗口的做法，在下面的 1004 题有具体的解法，代码和 1004 完全一样。
问题描述：【Sliding Window】1004. Max Consecutive Ones III
解题思路：
这道题是最多改变 K 个 1 变成 0，然后求最长连续 1 子数组的长度。很容易想到滑动窗口的思路（487 做法和本题做法一致，只不过 487 中 K = 1）：
我们来定义本题的滑动窗口：因为肯定将所有 K 个 0 改成 1 才能获得最大长度，因此滑动窗口中记录包含 K 个 0 之后的最长连续 1 子数组。注意到这个滑动窗口的大小是不固定的，因此，我们在滑动的过程中，要记录滑动窗口的起始位置（终止位置不用记，因为终止位置就是当前遍历的位置）。
如何更新滑动窗口呢？如果我们的滑动窗口中已经有 K 个 0 了，后面又遇到一个 0，那么我们就要移动滑动窗口，根据滑动窗口的起始位置找到窗口中最前面的 0，然后这个 0 的下一个位置就是新滑动窗口的起始位置。注意，在这个过程中，还要减小滑动窗口的长度。
这样，我们只需要遍历 1 次，不断更新最大长度，就能得到结果。
注意：刚开始时滑动窗口中 0 的个数如果小于 K，我们只拓展窗口，不更新窗口的起始位置（最开始的起始位置为 0）。
Python3 实现：
class Solution:
def longestOnes(self, A: List[int], K: int) -> int:
sliding_window = 0 # 滑动窗口
begin = 0 # 滑动窗口的起始位置
nums0 = 0 # 滑动窗口中0的个数
max_ = 0
for i in range(len(A)):
sliding_window += 1 # 拓展窗口长度
if nums0 < K: # 滑动窗口中 0 的个数小于 K，只拓展窗口
if A[i] == 0:
nums0 += 1
elif nums0 == K:
if A[i] == 0: # 如果再有 0 出现，更新滑动窗口
while A[begin] == 1: # 找到滑动窗口中第1个0的位置
begin += 1
sliding_window -= 1
begin += 1 # 新滑动窗口的起始位置
sliding_window -= 1
max_ = max(max_, sliding_window) # 更新最大长度
return max_问题描述：【Sliding Window、DP、Array】1052. Grumpy Bookstore Owner
解题思路：
方法1（暴力 O(N^2)，TLE）：
- 根据 customers 和 grumpy 数组，可以统计出不使用 X 技巧能得到的一个初始的满意度总和；
- 再考虑使用 X 技巧，对于每个位置，将长度为 X 的窗口中 grupmy[i] == 1 的 custpmers[i] 也加入到初始满意度中，然后更新最大满意度。
这样，时间复杂度为 O(N*X)，由于 X 也可能达到 N 的长度级别，因此为 O(N^2)，超时。
方法2（DP O(N^2)，勉强 AC）：
尝试了一下动态规划，虽然时间复杂度还是 O(N^2)，但勉强 AC 了。DP 思路如下：
- 用 dp1[N] 记录不使用 X 技巧的累加初始满意度，dp2[N] 记录使用 X 技巧的最大满意度，最后 dp2[-1] 就是答案；
- dp1[N] 的状态转移方程很容易
dp1[i] = (dp1[i-1] + customers[i-1]) if grumpy[i-1] == 0 else dp1[i-1]； - dp2[N] 的状态转移方程为：
dp2[i] = (dp2[i-1] + customers[i-1]) if grumpy[i-1] == 0 else max(dp2[i-1], dp1[i-X] + sum(customers[i-X:i]))，含义是如果 grumpy[i-1] 为 0，则老板不会生气，dp[i] 直接在 dp2[i-1] 的基础上加上 customers[i-1] 就好；如果 grumpy[i-1] 为 1，则老板生气，dp2[i] 的值取决于 dp2[i-1] （前面已经生过气）和 dp1[i-X] + sum(customers[i-X:i]) （当前生气，最大满意度为前 dp1[i-X] 和这段 X 长度大小的窗口中的数字之和）的最大值。 - 初始时 dp[i] 中 i < X，无论生气与否，
dp2[i] = dp2[i-1] + customers[i-1]，因为 X 技巧可以充分展现。
但是，实际上这种做法还是 O(N*X) 的时间复杂度，但是竟然勉强 AC 了（可能脸好吧）。
Python3 实现（DP）：
class Solution:
def maxSatisfied(self, customers: List[int], grumpy: List[int], X: int) -> int:
N = len(customers)
dp1 = [0] * (N + 1) # 不使用 X 技巧的累加初始满意度
dp2 = [0] * (N + 1) # 使用 X 技巧的最大满意度
for i in range(1, N + 1):
if grumpy[i-1] == 0:
dp1[i] = dp1[i-1] + customers[i-1]
else:
dp1[i] = dp1[i-1]
for i in range(1, N + 1):
if grumpy[i-1] == 0 or i-X-1 < 0:
dp2[i] = dp2[i-1] + customers[i-1]
else:
dp2[i] = max(dp2[i-1], dp1[i-X] + sum(customers[i-X:i]))
return dp2[-1]方法3（Sliding Window O(N)，AC）：
这也是一道经典的利用滑动窗口解决问题的题目。
我们来定义本题的滑动窗口：因为肯定当技能 X 发挥时能获得的满意度最大，且这个窗口是连续的，因此窗口的大小是固定的。长度为 X 的滑动窗口中记录增加的满意度。
- 先求出不使用 X 技巧的初始满意度；
- 因为窗口中记录使用 X 技巧增加的满意度，所以它等于窗口中 grumpy[i] 为 1 的所有 customers[i] 之和；
- 窗口每次都向右移动一位，刚开始窗口大小小于 X，那么只要是 grumpy[i] == 1 就增加满意度（因为可以充分发挥 X 技巧）；当窗口大小等于 X 时，滑动过程中始终保持 X 长度；
- 当窗口大小等于 X，如果出现一个 grumpy[j] == 1，则窗口增加满意度 customers[j]；同时，如果移出去的 grumpy[j-X] == 1，那么滑动窗口的满意度要减去满意度 customers[j-X]；
- 每次移动窗口，都更新使用 X 技巧增加的满意度的最大值；
- 最后，初始满意度加上使用 X 技巧增加的满意度的最大值就是总的最大满意度。
这样，时间复杂度为 O(N)。
Python3 实现（Sliding Window）：
class Solution:
def maxSatisfied(self, customers: List[int], grumpy: List[int], X: int) -> int:
N = len(customers)
initial_satisfied = sum([customers[i] for i in range(N) if grumpy[i] == 0]) # 初始的满意度
sliding_window = 0 # 大小为X的滑动窗口中保存增加的满意度
add_satisfied = 0 # 大小为X的滑动窗口中增加的满意度的最大值
for i in range(N):
if i < X and grumpy[i] == 1: # 没有达到窗口大小
sliding_window += customers[i]
elif i >= X:
if grumpy[i] == 1:
sliding_window += customers[i] # 滑动窗口中增加当前满意度
if grumpy[i-X] == 1:
sliding_window -= customers[i-X] # 滑动窗口移除满意度
add_satisfied = max(add_satisfied, sliding_window)
return initial_satisfied + add_satisfied # 两者之和为最终满意度
腾讯云开发者
