2021-03-10: There are N points in an array. The point 0 is the starting position and the point n-1 is the ending position. Now I have to go from zero to N minus one. But with the exception of zero and n-1, he can pick one of the n-2 positions, and just ignore it, and ask what is the minimum distance from the beginning to the end?

Answer 2021-03-10:

Array [1,4,-1,3], ignore 1, array becomes [1,-1,3], abs(-2)+4=6; Ignoring the ordinal number 2, the array becomes [1,4,3] and the distance is 3+1=4. I’m going to pick a point out of N minus 2 coordinates, and I’m going to ignore that point. Ignoring a point directly only affects the distance between the nodes before and after that node. This influence distance is named as the optimization distance for the moment, and all nodes are sequentially formed into a set of three nodes. In this way, the result can be obtained only through one cycle.The code is written in Golang, and the code is as follows:

package main

import "fmt"

func main(a) {
    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    // Maximum optimized distance
    ret := abs(i1) // Sum of distances on both sides

    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
    }
}
Copy the code

The result is as follows:

comments