2021-03-10：一个数组上共有 N 个点，序号为0的点是起点位置，序号为N-1 的点是终点位置

2021-03-10：一个数组上共有 N 个点，序号为0的点是起点位置，序号为N-1 的点是终点位置。现在需要依次的从 0 号点走到 N-1 号点。但是除了 0 号点和 N-1 号点，他可以在其余的 N-2 个位置中选出一个点，并直接将这个点忽略掉，问从起点到终点至少走多少距离？

福哥答案2021-03-10：

数组[1,4,-1,3]，忽略序号1，数组变成[1,-1,3],距离是abs(-2)+4=6；忽略序号2，数组变成[1,4,3]，距离是3+1=4。
N-2 个坐标中选出一个点，并直接将这个点忽略掉。直接忽略一个点只会直接影响到，这个节点前后节点的距离。这个影响的距离我们暂且命名为优化距离，将所有节点按顺序组成三个节点的集合，通过这种方式只需要通过一次循环便能得到结果。

代码用golang编写，代码如下：

package mainimport "fmt"func main() {    arr := []int{1, 4, -1, 3}    fmt.Println(shortDistance(arr))}func shortDistance(arr []int) int {    arrLen := len(arr)    if arrLen <= 1 {        return 0    }    if arrLen <= 3 {        return abs(arr[arrLen-1] - arr[0])    }    i1 := arr[1] - arr[0]    i2 := 0    maxval := 0    //最大优化距离    ret := abs(i1) //所有相邻两边距离之和    for i := 1; i < arrLen-1; i++ {        i2 = arr[i+1] - arr[i]        maxval = getMax(maxval, abs(i2)+abs(i1)-abs(i2+i1))        i1 = i2        ret += abs(i1)    }    return ret - maxval}func abs(a int) int {    if a < 0 {        return -a    } else {        return a    }}func getMax(a int, b int) int {    if a > b {        return a    } else {        return b    }}

执行结果如下：

©著作权归作者所有：来自51CTO博客作者福大大的原创作品，如需转载，请注明出处，否则将追究法律责任

每一份赞赏源于懂得

赞赏

0人进行了赞赏支持

每一份赞赏源于懂得

更多相关文章

随机推荐