Leetcode 【495、835】

问题描述:【Array】495. Teemo Attacking
解题思路:

读完题目,很容易想到要比较相邻两次攻击时间与中毒持续时间的关系:

  • 如果相邻两次攻击时间的间隔大于等于中毒持续时间,总中毒时间就要累加一个完整的中毒持续时间;
  • 如果相邻两次攻击时间的间隔小于中毒持续时间,那么艾希中毒还没结束就又中了一次毒,这样总中毒时间只需要累加这个间隔即可。
Python3 实现:
class Solution:
    def findPoisonedDuration(self, timeSeries: List[int], duration: int) -> int:
        if timeSeries == []:
            return 0
        time = duration
        for i in range(1, len(timeSeries)):
            if timeSeries[i] - timeSeries[i-1] >= duration:
                time += duration
            else:
                time += (timeSeries[i] - timeSeries[i-1])
        return time

问题描述:【Array】835. Image Overlap
解题思路:

方法1(时间复杂度 O(n^4),空间复杂度 O(1)):

抛开移动的过程只看移动完成的结果。记图片左上角为顶点 (0, 0),正方形边长为 N,要使得两张图片有重叠,那么其中一张图片移到的某一点 (x, y) 一定与另外一张图片的顶点 (0, 0) 重合。

假设移动图片 A,使其与图片 B 的顶点 (0, 0) 重合。设图片 A 移动到点 (x, y),那么 A 与 B 重叠的区域就是A:(x~N, yN),B:(0(N-x), 0~(N-y)) 。例如,A 最终移动到 (x=1, y=2),重叠区域如下图所示:

因此,我们只需要计算 A 与 B 的重叠部分中每个点都为 1 的个数,就是 A(x, y) 与 B(0, 0) 重叠时候能得到的 overlap。

注意:这样做我们的图片 A 是向右或者向下移动的,而图片 A 向左或者向上移动可以等价于图片 B 向右或者向下移动。因此,在对于每个位置 (x, y),还要计算出 B 中所有点与 A(0,0) 重叠的 overlap。每个位置,更新最大值即可。

Python3 实现:

class Solution:
    def largestOverlap(self, A: List[List[int]], B: List[List[int]]) -> int:
        max_ = 0
        N = len(A)
        for i in range(N):
            for j in range(N):
                max_ = max(max_, self.count(A, B, i, j))  # 向右或向下移动 A 到 (i, j),计算重叠区域 overlap
                max_ = max(max_, self.count(B, A, i, j))  # 向右或向下移动 B 到 (i, j)(相当于向左或向上移动 A 到 (-i, -j)),计算重叠区域的 overlap
        return max_
    
    def count(self, A, B, x, y):  # 计算重叠区域的 overlap
        cnt = 0
        N = len(A)
        for i in range(x, N):
            for j in range(y, N):
                if A[i][j] == B[i-x][j-y] == 1:
                    cnt += 1
        return cnt

方法2(时间复杂度 O(n^2),空间复杂度 O(n^2)):

参考这篇文章 leetcode835引发的位距离思考那么对于二维情况,我们同样去记录两幅图像1中的位置,然后A和B中1的位置的各个差值。差值出现次数最多的那个就是最大覆盖 overlap。

Python3 实现:

class Solution:
    def largestOverlap(self, A: List[List[int]], B: List[List[int]]) -> int:
        N = len(A)
        Apos = [(row, col) for row in range(N) for col in range(N) if A[row][col]]  # A中1的位置
        Bpos = [(row, col) for row in range(N) for col in range(N) if B[row][col]]  # B中1的位置
        sub = dict()  # 用字典对A和B中1的位置的差值计数
        max_ = 0
        for a in Apos:
            for b in Bpos:
                tem = (a[0]-b[0], a[1]-b[1])  # 计算A和B中1的位置的差值
                if tem not in sub:
                    sub[tem] = 1
                else:
                    sub[tem] += 1
                max_ = max(max_, sub[tem])  # overlap的最大值就是差值出现最多的次数
        return max_

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Pandas-32. transfrom 和fittransform

    在DataFrame自身调用一个函数,产生一个转变后的有着相同维度长度的新的DataFrame。

    悠扬前奏
  • Python爬虫——Scrapy简介

    Scrapy Engine(引擎):Scrapy框架的核心部分。负责在Spider和ItemPipeline、Downloader、Scheduler中间通信、...

    羊羽shine
  • Python基础(8)——内建函数

    Build-in Function,启动python解释器,输入dir(builtins), 可以看到很多python解释器启动后默认加载的属性和函数,这些函数...

    羊羽shine
  • 使用http-server搭建web服务器

    php命令可以用php -S 0.0.0.0:8080 python命令可以用 python -m SimpleHTTPServer 80

    lilugirl
  • Python基础(12)——装饰器

    python装饰器就是用于拓展原来函数功能的一种函数,这个函数的特殊之处在于它的返回值也是一个函数(函数的指针),使用python装饰器的好处就是在不用更改原函...

    羊羽shine
  • Python网络——Urllib&Requests

    Urllib 库,它是 Python 内置的 HTTP 请求库.不需要额外安装即可使用,在 Python中,有 Urllib 和 Urlib2 两个库可以用来实...

    羊羽shine
  • C#协程

    祝你万事顺利
  • Kafka Consumer重置Offset

    在Kafka Version为0.11.0.0之后,Consumer的Offset信息不再默认保存在Zookeeper上,而是选择用Topic的形式保存下来。

    迹_Jason
  • HBase Thrift with Python

    本文内容是基于 Centos 7、HDP 3.0.0、HBase 2.0.0、Python 2.7 环境下,其他环境的童鞋选择性进行参考。

    迹_Jason
  • Django——模型Model

    对象关系映射(Object Relation Mapping)实现了关系和数据库之间的映射,隐藏了关系数据访问的细节,不需要再编写SQL语句

    羊羽shine

扫码关注云+社区

领取腾讯云代金券