PHP 计算到最近的人最大距离

PHP 计算到最近的人最大距离

author: he xiaodong date: 2020-05-23
到最近的人最大距离

在一排座位( 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 <= seats.length <= 20000
  • seats 中只含有 01,至少有一个 0,且至少有一个 1

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/maximize-distance-to-closest-person

解题思路

将连续空座计算出来,然后不断的求最大值就行,最大的需要

PHP 实现

$seats = explode('1', implode('', $seats));

$res = 0;
foreach ($seats as $key => $val) {
    if ($key == 0 || $key == count($seats) - 1) {
        $res = max($res, strlen($val));
    } else {
        $res = max($res, ceil(strlen($val) / 2));
    }
}

return $res;

Go 实现 来源于 梦康群群友- 我要割麦子

func maxDistToClosest(seats []int) int {
    var (
        max1 int
        max2 int
        max3 int
    )

    dp := make([]int, len(seats))
    pre := 0
    diff := 0

    for i,v := range seats {
        if v == 1 {
            dp[i] = i - pre
            pre = i
        }else{
            dp[i] = i - pre
        }
        diff = max(dp[i], diff)
    }

    for i,v := range seats {
        if v == 1 {
            max1 = i
            break
        }
    }

    for i := len(seats) - 1;i >= 0;i--  {
        if seats[i] == 1 {
            max2 = len(seats) - i - 1
            break
        }
    }

    max3 = max(max1, max2)
    // fmt.Println(diff)
    max3 = max(max3, int(diff / 2))

    return max3

}

func max(a,b int) int {
    if a >= b {
        return a
    }

    return b
}

© 原创文章