前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Leetcode 【485、1004、1052】

Leetcode 【485、1004、1052】

作者头像
echobingo
发布2019-06-18 18:49:45
6860
发布2019-06-18 18:49:45
举报
文章被收录于专栏:Bingo的深度学习杂货店
问题描述:【Array】485. Max Consecutive Ones
解题思路:

因为要找最长连续 1 子数组的长度,所以我们只需要遍历一次,记录每段连续 1 的长度;如果遇到 0,就更新当前最大长度,然后当前长度清零,继续向后遍历。时间复杂度为 O(n)。

Python3 实现:
代码语言:javascript
复制
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 实现:
代码语言:javascript
复制
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):

代码语言:javascript
复制
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):

代码语言:javascript
复制
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  # 两者之和为最终满意度
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2019.06.17 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 问题描述:【Array】485. Max Consecutive Ones
  • 解题思路:
  • Python3 实现:
  • 问题描述:【Array】487. Max Consecutive Ones
  • 问题描述:【Sliding Window】1004. Max Consecutive Ones III
  • 解题思路:
  • Python3 实现:
  • 问题描述:【Sliding Window、DP、Array】1052. Grumpy Bookstore Owner
  • 解题思路:
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档