[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 条评论
登录 后参与评论

相关文章

来自专栏技术之路

sqlserver 的事务和c#的事务

sql的事务 1 sql 2 create database model 3 go 4 use model 5 go 6 create table ...

1979
来自专栏跟着阿笨一起玩NET

treeview 绑定文件夹和文件

521
来自专栏xingoo, 一个梦想做发明家的程序员

【插件开发】—— 6 SWT 复杂控件使用以及布局

前文回顾: 1 插件学习篇 2 简单的建立插件工程以及模型文件分析 3 利用扩展点,开发透视图 4 SWT编程须知 5 SWT简单控件的使用与布局搭...

2499
来自专栏码匠的流水账

zuul自定义SimpleHostRoutingFilter

zuul的SimpleHostRoutingFilter主要用来转发不走eureka的proxy,里头是使用httpclient来转发请求的,但是有时候我们需要...

1502
来自专栏Golang语言社区

GO语言 TCP传输实例

package main import ( "net" "fmt" ) var ( maxRead = 1100 msgStop = []byt...

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

实现一个同步的RenderApplication

1414
来自专栏james大数据架构

CSS好看的按钮

好看的按钮 <style> .btn { BORDER-RIGHT: #7b9ebd 1px solid; PADDING-RIGHT: 2px; BORDE...

2057
来自专栏我和未来有约会

Silverlight制作逐帧动画 v2 - part2

Silverlight制作逐帧动画 v2 - part2 在这里完善了一下算法,加入了fps的机制进去。 private string[] ...

1956
来自专栏王磊的博客

MySQL数据库工具类之——DataTable批量加入MySQL数据库(Net版)

MySQL数据库工具类之——DataTable批量加入数据库(Net版),MySqlDbHelper通用类希望能对大家有用,代码如下: using MySql....

3709
来自专栏互联网开发者交流社区

STC-单片机控制系统

1163

扫码关注云+社区