【华为OD题库-090】找车位-java

题目

停车场有一横排车位，0代表没有停车，1代表有车。至少停了一辆车在车位上，也至少有一个空位没有停车。为了防剐蹭，需为停车人找到一个车位，使得距停车人的车最近的车辆的距离是最大的，返回此时的最大距离。
输入描述
1.一个用半角逗号分割的停车标识字符串，停车标识为0或1，0为空位，1为已停车。
2.停车位最多100个。
输出描述
输出一个整数记录最大距离
示例1:
输入∶
1,0,0,0,0,1,0,0,1,0,1
输出:
2

思路

找到两个1之间的范围，比如1,0,0,0,1，此范围的最小间距=(end-start)/2，现要求最大的距离，遍历一次即可。同时需要考虑两端不为1的情况。
使用lst记录上次为1的索引，初始值为-1，遍历nums：
如果nums[i]=1，lst为-1，说明i之前都为0，此时停靠在第0个位置即可，距离为：i
如果lst不为-1，那么停靠在lst和i的中间时，可以得到最大距离为：(i - lst) / 2
遍历完成后，lst为最后1个1的索引，还需要计算它到nums结尾的距离：nums.length-1-lst
在上述逻辑中，获取最终的最大值即可

题解

package hwod;

import java.util.Arrays;
import java.util.Scanner;

public class FindPark {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[] nums = Arrays.stream(sc.nextLine().split(",")).mapToInt(Integer::parseInt).toArray();
        System.out.println(findPark(nums));
    }

    private static int findPark(int[] nums) {
        int res = 0;
        int lst = -1;//上一个为1的位置
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0) continue;
            if (lst == -1) {
                res = Math.max(res, i);
            } else {
                res = Math.max(res, (i - lst) / 2);
            }
            lst = i;
        }
        return Math.max(res,nums.length-1-lst);
    }
}

推荐

如果你对本系列的其他题目感兴趣，可以参考华为OD机试真题及题解（JAVA），查看当前专栏更新的所有题目。