当前位置: 首页 > news >正文

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。

转载于:https://www.cnblogs.com/chenjx85/p/9265029.html

相关文章:

  • java中与运算,或运算,异或运算,取反运算
  • Windows后登陆没有图形界面只有cmd,explorer.exe不能启动
  • fastdfs添加新group注意事项
  • 关于自动驾驶等级划分
  • 数据仓库学习笔记
  • windows设置防火墙允许telnet
  • Hexo添加评论、阅读次数和分类/标签
  • 颜色的生成
  • 360首曝人工智能研发三大神秘成果
  • ThinkSNS+ 移动端1.8.2.0704 版本更新简要说明
  • js蛋疼的Class(获取class对象)
  • 【跃迁之路】【519天】程序员高效学习方法论探索系列(实验阶段276-2018.07.09)...
  • 大数据教程(2.5):Linux系统搭建本地YUM源服务器
  • 每天学点SpringCloud(一):使用SpringBoot2.0.3整合SpringCloud
  • @for /l %i in (1,1,10) do md %i 批处理自动建立目录
  • 时间复杂度分析经典问题——最大子序列和
  • [分享]iOS开发-关于在xcode中引用文件夹右边出现问号的解决办法
  • [原]深入对比数据科学工具箱:Python和R 非结构化数据的结构化
  • angular组件开发
  • css系列之关于字体的事
  • docker-consul
  • ES学习笔记(10)--ES6中的函数和数组补漏
  • Java知识点总结(JavaIO-打印流)
  • k8s 面向应用开发者的基础命令
  • SwizzleMethod 黑魔法
  • uva 10370 Above Average
  • 从零开始学习部署
  • 第三十一到第三十三天:我是精明的小卖家(一)
  • 它承受着该等级不该有的简单, leetcode 564 寻找最近的回文数
  • 为什么要用IPython/Jupyter?
  • ​【已解决】npm install​卡主不动的情况
  • ​软考-高级-信息系统项目管理师教程 第四版【第14章-项目沟通管理-思维导图】​
  • #快捷键# 大学四年我常用的软件快捷键大全,教你成为电脑高手!!
  • (04)odoo视图操作
  • (Spark3.2.0)Spark SQL 初探: 使用大数据分析2000万KF数据
  • (备忘)Java Map 遍历
  • (多级缓存)缓存同步
  • (附源码)ssm航空客运订票系统 毕业设计 141612
  • (附源码)ssm跨平台教学系统 毕业设计 280843
  • (亲测有效)解决windows11无法使用1500000波特率的问题
  • (四)模仿学习-完成后台管理页面查询
  • (算法设计与分析)第一章算法概述-习题
  • (转)微软牛津计划介绍——屌爆了的自然数据处理解决方案(人脸/语音识别,计算机视觉与语言理解)...
  • .net 4.0发布后不能正常显示图片问题
  • .net core IResultFilter 的 OnResultExecuted和OnResultExecuting的区别
  • .NET DataGridView数据绑定说明
  • .net 按比例显示图片的缩略图
  • .NET 设计一套高性能的弱事件机制
  • /proc/vmstat 详解
  • @ModelAttribute 注解
  • @RequestMapping-占位符映射
  • [ACL2022] Text Smoothing: 一种在文本分类任务上的数据增强方法
  • [AI]文心一言出圈的同时,NLP处理下的ChatGPT-4.5最新资讯
  • [BUUCTF]-Reverse:reverse3解析
  • [BZOJ1877][SDOI2009]晨跑[最大流+费用流]