这是悦乐书的第 328 次更新, 第 351 篇原创
01 看题和准备
今天介绍的是 LeetCode 算法题中 Easy 级别的第 198 题(顺位题号是 849). 在一排座位中, 1 表示一个人坐在该座位上, 0 表示座位是空的. 在这些座位中, 至少有一个空座位, 至少有一个人坐着. Alex 想坐在座位上, 以便他和离他最近的人之间的距离最远. 返回距离最近的人的最大距离. 例如:
输入:[1,0,0,0,1,0,1]
输出: 2
说明: 如果 Alex 坐在第二个空座位(seats[2]), 那么离最近的人距离为 2. 如果 Alex 坐在任何其他空座位上, 则离最近的人的距离为 1. 因此, 到最近的人的最大距离是 2.
输入:[1,0,0,0]
输出: 3
说明: 如果 Alex 坐在最后一个座位上, 那么离他最近的人距离为 3. 这是可能的最大距离, 所以答案是 3.
注意:
1 <= seats.length <= 20000
所有座位中仅包含 0 或 1, 至少一个 0, 至少一个 1.
本次解题使用的开发工具是 eclipse,jdk 使用的版本是 1.8, 环境是 win7 64 位系统, 使用 Java 语言编写和测试.
02 解题
在解题前, 先来看看题目的意思. Alex 想要在一排座位中, 找到一个离人最近但是距离最远的座位, 题目通过一个数组来表示一排座位, 元素值为 0 表示当前这个座位是空的, Alex 可以坐, 为 1 时表示当前这个座位有人坐了, Alex 不能坐, 也就是说, 在为 0 的座位中, 要找一个离最近的人距离越远越好的座位. 我们可以分三种情况来选座位:
(1)左边是墙时, 即数组中第一个元素是 0, 或者数组前部分是连续的 0, 如果往右, 至少会遇到一个座位上有人, 此时 Alex 离这个人是最近的, 距离也是最远的. 比如数组{0,0,0,1},Alex 坐在第一个座位上, 离他最近的人的最远距离是 3.
(2)左右两边都有人时, 即此时数组中出现了一段连续的 0, 也就是有连续好几个连着的空座位可以选, 此时 Alex 坐在这些连续空座位的中间是最好的, 离左右两边的人最近, 距离也是相等的. 比如数组 {1,0,0,0,1},Alex 坐在第三个座位上, 即坐在 seats[2] 上, 距离两边的人都是最近的, 且距离最大, 都为 2.
(3)右边是墙时, 即数组中最后一个元素是 0, 或者后部分是连续的 0, 如果往左, 至少会遇到一个座位上有人, 此时 Alex 离这个人是最近的, 距离也是最远的. 比如数组{1,0,0,0},Alex 坐在第四个座位上, 离他最近的人的最远距离是 3.
通过上面的分析, 我们可以使用一个变量记录前一个座位已经被坐的索引, 再根据当前座位来判断, 看属于上面三种情况中的哪一种, 计算距离, 比较最大值, 通过双指针来实现.
注意, 计算距离是计算索引之差.
- public int maxDistToClosest(int[] seats) {
- int left = -1, n = seats.length;
- int maxDistance = 0;
- for (int i=0; i<n; i++) {
- if (seats[i] == 0) {
- continue;
- }
- if (left == -1) {
- // 左边第一位是 1 或者连续的 0, 有可能左边靠墙
- maxDistance = Math.max(maxDistance, i);
- } else {
- // 中间部分连续的 0, 即中间
- maxDistance = Math.max(maxDistance, (i-left)/2);
- }
- left = i;
- }
- // 结束部分为连续的 0, 即右边靠墙
- if (seats[n-1] == 0) {
- maxDistance = Math.max(maxDistance, n-1-left);
- }
- return maxDistance;
- }
03 小结
算法专题目前已日更超过五个月, 算法题文章 198 + 篇, 公众号对话框回复[数据结构与算法] ,[算法] ,[数据结构] 中的任一关键词, 获取系列文章合集.
以上就是全部内容, 如果大家有什么好的解法思路, 建议或者其他问题, 可以下方留言交流, 点赞, 留言, 转发就是对我最大的回报和支持!
来源: http://www.jianshu.com/p/1627d7e2e2aa