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

相关文章

来自专栏Java Edge

利用 ChiMerge 分析鸢尾花数据集基本思想实战函数说明程序运行结果参考文献

3966
来自专栏zhisheng

学习算法之路

一个搞ACM的需要掌握的算法的sheet。 第一阶段:练经典常用算法,下面的每个算法给我打上十到二十遍,同时自己精简代码,因为太常用,所以要练到写时不用想,10...

3715
来自专栏悦思悦读

决策树告诉你Hello Kitty到底是人是猫

Hello Kitty,一只以无嘴造型40年来风靡全球的萌萌猫,在其40岁生日时,居然被其形象拥有者宣称:HelloKitty不是猫! 2014年八月,研究 H...

3187
来自专栏PPV课数据科学社区

非主流自然语言处理——遗忘算法系列(二):大规模语料词库生成

一、前言   本文介绍利用牛顿冷却模拟遗忘降噪,从大规模文本中无监督生成词库的方法。 二、词库生成     算法分析,先来考虑以下几个问题     问:目标是从...

34812
来自专栏大数据挖掘DT机器学习

R语言处理缺失数据的高级方法

主要用到VIM和mice包 [plain] view plain install.packages(c("VIM","mice")) 1.处理缺失值的步骤 ...

3217
来自专栏ml

由判断三一点是否在三角形内部而引发的思考.....

判断一个点是否在三角形里面(包括边界上),这个问题对于许多初学者来说,可谓是一头雾水,如何判断呢? 假如有四个点A(x0,y0),B(x1,y1),C(x2,y...

2798
来自专栏懒人开发

(4.7)James Stewart Calculus 5th Edition:Optimization Problems

根据下图,可以得到大体表达式: 已知 2x + y = 2400 求 A = xy = ? 的最大值

853
来自专栏窗户

平方根的C语言实现(二) —— 手算平方根的原理

  一个函数从数学上来说可以有无数个函数列收敛于这个函数,那么程序逼近实现来说可以有无数种算法,平方根自然也不例外。   不知道有多少人还记得手算平方根,那是满...

2019
来自专栏ACM算法日常

UVA297:黑白图像 Quadtrees(四分树)

四象树是每个内结点均有4个子结点的特殊四叉树,它可用于描述平面上黑白图像。平面上的黑白图像是32行×32列的正方形,每个格子称为1个象素,是最小的图像单位。正方...

1223
来自专栏大数据和云计算技术

最小生成树

本篇我们会聊聊最小生成树,最小生成树和之前的无向图最大的区别是这个每一条边都是带有权重的。在聊最小生成树之前 我们要先聊两个理念,因为最小生成树是基于这两...

711

扫码关注云+社区