[LeetCode Weekly Contest 88]849. 到最近的人的最大距离

第二道题目相对来说比较简单。

题目描述

849. 到最近的人的最大距离

在一排座位( seats)中,1 代表有人坐在座位上,0 代表座位上是空的。

至少有一个空座位,且至少有一人坐在座位上。

亚历克斯希望坐在一个能够使他与离他最近的人之间的距离达到最大化的座位上。

返回他到离他最近的人的最大距离。

示例 1:

输入:[1,0,0,0,1,0,1]
输出:2
解释:
如果亚历克斯坐在第二个空位(seats[2])上,他到离他最近的人的距离为 2 。
如果亚历克斯坐在其它任何一个空位上,他到离他最近的人的距离为 1 。
因此,他到离他最近的人的最大距离是 2 。 

示例 2:

输入:[1,0,0,0]
输出:3
解释: 
如果亚历克斯坐在最后一个座位上,他离最近的人有 3 个座位远。
这是可能的最大距离,所以答案是 3 。

提示:

  1. 1 <= seats.length <= 20000
  2. seats 中只含有 0 和 1,至少有一个 0,且至少有一个 1

分析

能看出来有三种情况:

  1. 左边有连续n个空位,坐最左边,最近的人距离为n
  2. 右边有连续n个空位,坐最右边,最近的人距离为n
  3. 中间有连续n个空位,n小于等于2,必须挨着人坐,最近距离为0,n为奇数最近距离为(n + 1)/ 2, n为偶数最近距离为n/2

选出最大的一个就可以。

代码

class Solution:
    def maxDistToClosest(self, seats):
        """
        :type seats: List[int]
        :rtype: int
        """
        width = 0
        
        
        left = 0
        while seats[left] == 0:
            left += 1
        width = max(left, width)
        
        
        right = len(seats) - 1
        zeros = 0
        while seats[right] == 0:
            right -= 1
            zeros += 1
        width = max(zeros, width)
        
        
        prev = False
        current = 0
        for index, value in enumerate(seats):
            if value == 0:
                if prev:
                    current += 1
                else:
                    prev = True
                    current = 1
            else:
                prev = False
                if current <= 2:
                    width = max(width, 1)
                elif current % 2:
                    width = max(width, current // 2 + 1)
                else:
                    width = max(width, current // 2)
                    
        return width
        

结语

这种简单的题目要考虑周全,最好一次通过,毕竟提交次数会影响到最后的评分。

最后祝大家享受生活, 享受代码。

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏利炳根的专栏

学习笔记DL001 : 数学符号、深度学习的概念

深度学习是机器学习拉出的分支,它试图使用包含复杂结构或由多重非线性变换构成的多个处理层对数据进行高层抽象的算法。本文主要介绍深度学习中的数学符号、数和数组。

4800
来自专栏小樱的经验随笔

利用向量积(叉积)计算三角形的面积和多边形的面积

利用向量积(叉积)计算三角形的面积和多边形的面积: 向量的数量积和向量积: (1)  向量的数量积 ? (1)  向量的向量积 两个向量a和b的叉积(向量积)可...

3909
来自专栏AI2ML人工智能to机器学习

决策树会有哪些特性?

决策树(Decision Tree)是机器学习中最常见的算法, 因为决策树的结果简单,容易理解, 因此应用超级广泛, 但是机器学习的专家们在设计决策树的时候会考...

1212
来自专栏封碎

当今世界最为经典的十大算法 博客分类: 经典文章转载 算法数据结构网络应用数据挖掘J#

本文转载自July CSDN博客:http://blog.csdn.net/v_JULY_v/archive/2011/03/07/6228235.aspx

1722
来自专栏ATYUN订阅号

利用统计方法,辨别和处理数据中的异常值

在建模时,清理数据样本非常重要,这样做可以确保观察结果充分代表问题。有时,数据集可能包含超出预期范围之外的极端值。这通常被称为异常值,通过理解甚至去除这些异常值...

1333
来自专栏小樱的经验随笔

模拟退火算法从原理到实战【基础篇】

  模拟退火算法来源于固体退火原理,将固体加温至充分高,再让其徐徐冷却,加温时,固体内部粒子随温升变为无序状,内能增大,而徐徐冷却时粒子渐趋有序,在每个温度都达...

3776
来自专栏数据结构与算法

P3819 松江1843路

题目描述 涞坊路是一条长L米的道路,道路上的坐标范围从0到L,路上有N座房子,第i座房子建在坐标为 的地方,其中住了 人。 松江1843路公交车要在这条路上...

3196
来自专栏小樱的经验随笔

【机器学习笔记之一】深入浅出学习K-Means算法

摘要:在数据挖掘中,K-Means算法是一种 cluster analysis 的算法,其主要是来计算数据聚集的算法,主要通过不断地取离种子点最近均值的算法。 ...

2929
来自专栏逍遥剑客的游戏开发

纹理投影测试

1887
来自专栏生信技能树

比较不同的对单细胞转录组数据聚类的方法

背景介绍 聚类之前必须要对表达矩阵进行normalization,而且要去除一些批次效应等外部因素。通过对表达矩阵的聚类,可以把细胞群体分成不同的状态,解释为什...

75712

扫码关注云+社区