leetcode-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

要完成的函数:

int maxDistToClosest(vector<int>& seats) 

说明:

1.这道题给了一个vector,里面存放着0和1,1表示这个位置有人,0表示没人。现在亚力克斯想坐在一个离最近的人距离最远的座位上,也就是“四周最空旷”的座位。

2.我们之前做过一道跟这道题类似的题目,我们只需做两次循环,一次把所有0的位置跟左边的1比较,得到跟左边的最近的1的位置距离。再跟右边的1比较,得到跟右边的最近的1的位置距离。

每个数都能得到两个位置距离,一个跟左边最近的1比较,一个跟右边最近的1比较,除了最开始的1的左边的数,比如[0,0,1,1]中第一个0和第二个0,只有跟右边的1比较得到的位置距离,还有最后面的1的右边的数,比如[1,1,0,0]中的两个0,只有跟左边的1比较得到的位置距离。

我们得到的两个位置距离,取小的那个。

把每个原本0值对应的得到的位置距离,存在vector中。

最后遍历一遍这个vector,得到最大的位置距离,返回。

在实际代码实现中,我们还可以简化步骤,降低时间复杂度和空间复杂度,代码如下:(附详解)

    int maxDistToClosest(vector<int>& seats) 
    {
        int left,right,s1=seats.size(),max1;
        for(left=0;left<s1;left++)//left表示最左边的第一个1的位置
        {
            if(seats[left]==1)
                break;
        }
        for(int i=left+1;i<s1;i++)//从left的下一位开始,逐个计算跟左边最近的1的距离
        {
            if(seats[i]==1)//不断更新左边最近的1的位置
                left=i;
            else//把距离存储在原本的vector中,为了避免混乱,以负数(相反数)的形式存储
                seats[i]=-(i-left);
        }
        for(right=s1-1;right>=0;right--)//right表示最右边的第一个1的位置
        {
            if(seats[right]==1)
                break;
        }
        if(right!=s1-1)//如果最右边的第一个1不是最后一位,也就是right的右边还有0
            max1=-seats[s1-1];//那么max1初始化为……
        else//如果右边的第一个1在最后一位,也就是right的右边没有0了
            max1=0;//那么max1初始化为0
        for(int i=right-1;i>=0;i--)//从right的前一位开始,逐个计算跟右边最近的1的距离
        {
            if(seats[i]==1)
                right=i;
            else if(seats[i]==0)//应对[0,0,1,1,0,0,0]这种情况中的前两个0
            {
                max1=max(max1,right-i);
            }
            else//正常情况下 夹在两个1中间的情况
            {
                seats[i]=max(-(right-i),seats[i]);
                max1=max(max1,-seats[i]);
            }
                
        }
        return max1;
    }

上述代码可能注释也还解释得不是十分清楚。

我们通过跟左边最近的1和右边最近的1的位置比较,得到位置距离,存储在原本的vector中。

存储的时候,为了避免跟原本的1混乱了,存储成负数(相反数)的形式。

我们最后还需要遍历一遍vector,得到最大的位置距离。

但笔者为了省时间,把最后这一步融合在代码中最后的for循环中了,跟右边最近的1比较完之后,得到的数值再跟vector中存储的数值比较,只剩下一个数,然后不断更新最大的位置距离。

为了实现这一点,我们需要考虑最开始max1要初始化为多少。

还不懂的同学自己手推一遍代码,理清过程就清楚啦!

上述代码实测12ms,beats 100% of cpp submission。

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏落影的专栏

程序员进阶之算法练习(十五)

前言 有朋友推荐一个新的算法练习网站leetcode,说北美的公司招人都是400题起步,国内公司招聘也经常用到,上海的尤其多。 很有意思,可以花点时间做做le...

3905
来自专栏机器之心

入门 | 一文介绍机器学习中基本的数学符号

选自Machine Learning Mastery 作者:Jason Brownlee 机器之心编译 参与:Edison Ke、黄小天 本文介绍了机器学习中的...

3519
来自专栏游戏开发那些事

【随笔】游戏程序开发必知的10大基础实用算法及其讲解

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(n logn)次比较。在最坏状况下则需要Ο(n2)次比较,但这种状况并不常见。事...

903
来自专栏ml

错排公式

错排公式 百科名片 pala提出的问题: 十本不同的书放在书架上。现重新摆放,使每本书都不在原来放的位置。有几种摆法? 这个问题推广一下,就是错排问题: n个有...

4039
来自专栏落影的专栏

程序员进阶之算法练习(二十三)

前言 7月,忙着学习ReactNative相关,这部分后续再详细介绍,先抽点时间补上算法文集的更新。 正文 1、Tennis Championship 题目链接...

2964
来自专栏Duncan's Blog

回溯法笔记

为了应用回溯法,所要求的解必须能表示成一个n-元组(x1,x2,…,xn),其中xi是取自某个有穷集Si。通常,所求解的问题需要求取一个使某一规范函数P(x1,...

1042
来自专栏逸鹏说道

码农眼中的数学之~数学基础

1维直线、2维平面(长宽)、3维空间(长宽高 | xyz轴)、4维时空(xyz轴+时间轴)

1233
来自专栏算法channel

LeetCode实战:动态规划算法是怎么一回事

主要推送关于对算法的思考以及应用的消息。培养思维能力,注重过程,挖掘背后的原理,刨根问底。本着严谨和准确的态度,目标是撰写实用和启发性的文章,欢迎您的关注。 0...

3217
来自专栏机器人网

机器学习中基本的数学符号是什么?

本文介绍了机器学习中的基本数学符号。具体来说有算数符号,包括各种乘法、指数、平方根以及对数;数列和集合符号,包括索引、累加以及集合关系。此外,本文还给出了 5 ...

7176
来自专栏程序员宝库

LCS 算法:Javascript 最长公共子序列

作者:司徒正美 链接:https://segmentfault.com/a/1190000012864957 最长公共子序列(Longest Common Su...

56210

扫码关注云+社区

领取腾讯云代金券