2021-03-10:一个数组上共有 N 个点,序号为0的点是起点位置,序号为N-1 的点是终点位置。现在需要依次的从 0 号点走到 N-1 号点。但是除了 0 号点和 N-1 号点,他可以在其...

福大大架构师每日一题 · · 348 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

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 main

import "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
    }
}

执行结果如下:


在这里插入图片描述

评论


有疑问加站长微信联系(非本文作者)

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:701969077

348 次点击  
加入收藏 微博
下一篇:Go-Zap
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传