Golang面试的一道算法题

大家看下这道题到底要考察什么。

考解题算法，看解决方案的时间复杂度吧@pengwl

谢谢

示例第七步为什么不是直接把5移到队尾然后移除3，4，5呢。

应该是这样:

package main

import (
    "container/list"
    "fmt"
    "math/rand"
)

func dump(l *list.List) {
    ss := make([]string, 0, l.Len())
    for e := l.Front(); e != nil; e = e.Next() {
        s := fmt.Sprintf("%v", e.Value)
        ss = append(ss, s)
    }
    fmt.Println(ss)
}

func main() {
    l := list.New()
    for _, v := range rand.Perm(10) {
        l.PushBack(v)
    }

    min := 0
    for l.Len() > 0 {
        dump(l)

        elem := l.Remove(l.Back())
        if elem.(int) == min {
            min++
        } else {
            l.PushFront(elem)
        }
    }
}

问题没怎么搞懂要考察什么，问题是计算移除所有元素所需能量， 这移除方法就有很多，所需能量也不同，我想可能想问的是所需最少能量吧。如果按照这种思路来分析

• 1 队列中元素自身的值就代表能量，每次执行移除操作前都是前移或者后移一种，
• 2 由此可以选择二分法来计算
• 3 将队列中最小的数字找到，根据最小元素位置分为，前组 和 后组
• 4 计算（前组）和（自身 + 后组）的能量进行比较 若前组能量小，则选择后移；反之，则前移。
• 5 移动元素直到最小的元素达到移除位置，移除
• 6 若队列中还有元素，则回到 步骤3 ；若没有，则完成

没有搞明白 为什么示例里面是第 4 步 是要把4移动到队尾？之前和之后都是把最后一个移动到队头呀？为了移除2吗？哪移动2不是消耗2吗？同意6楼的计算方式。

不懂

题目都出错了，有啥意思了

如下，未优化，但是能够完成功能

package main

import (
    "fmt"
    "sort"
)

func main() {
    data := []int{5, 3, 1, 4, 2}
    fmt.Println("energy is:", getEnergy(data))
}

func getEnergy(data []int) (ret int) {
    if count := len(data); count > 1 {
        sorted := make([]int, len(data))
        buf := make([]int, len(data)-1)
        copy(sorted, data)
        sort.Ints(sorted)

        tailToHead := true
        sum := 0
        for _, v := range data {
            sum += v
        }

        for len(data) > 0 {
            var pos int
            minV := sorted[0]
            sumPrev := 0

            //find min value pos
            for i, v := range data {
                if v == minV {
                    pos = i
                    break
                } else {
                    sumPrev += v
                }
            }

            if pos == 0 {
                data = data[1:]
            } else {
                countNext := len(data) - pos - 1
                if tailToHead {
                    ret += sum - sumPrev
                } else {
                    ret += sumPrev
                }

                if countNext > 0 {
                    copy(buf, data[pos+1:])
                    copy(buf[countNext:], data[:pos])
                    buf, data = data, buf
                    data = data[:pos+countNext]
                } else {
                    data = data[:len(data)-1]
                }
            }

            tailToHead = !tailToHead
            sorted = sorted[1:]
            sum -= minV
        }
    }

    return
}

优化一下啊，供大家参考:

package main

import (
    "fmt"
)

func main() {
    data := []int{5, 3, 1, 4, 2}
    fmt.Println("energy is:", getEnergy(data))
    data = []int{9, 5, 2, 8, 3, 7, 1, 4, 6}
    fmt.Println("energy is:", getEnergy(data))
}

func getEnergy(data []int) (ret int) {
    if count := len(data); count > 1 {
        i := 0
        minV := 1
        tailToHead := true

        for count > 0 {
            if data[i] != minV {
                if tailToHead {
                    for {
                        if i == 0 {
                            i = count - 1
                        } else {
                            i--
                        }
                        ret += data[i]
                        if data[i] == minV {
                            break
                        }
                    }

                } else {
                    for {
                        ret += data[i]
                        if i++; i == count {
                            i = 0
                        }
                        if data[i] == minV {
                            break
                        }
                    }
                }
            }

            copy(data[i:], data[i+1:])
            if count--; i == count {
                i = 0
            }
            minV++
            tailToHead = !tailToHead
        }
    }

    return
}

语文不好，没读懂。疑问如下：

2 队尾移到队头，消耗能量2，

示例5： 4 队尾移到队头，消耗能量4

难道 队尾移到队头消耗的能量不应该一样吗，或者和队内元素数量有关系。 这个疑问不解决，后边的看不下去了。

和这个元素的值有关，移动2就是2，移动4就是4