Golang面试的一道算法题

pengwl · 2019-05-14 13:21:01 · 4563 次点击 · 大约8小时之前 开始浏览    置顶
这是一个创建于 2019-05-14 13:21:01 的主题,其中的信息可能已经有所发展或是发生改变。

题目如下

现有一个队列,共有N个数据(1-Nb不重复),排序随机,如: 5 3 1 4 2 。
需要做以下操作,
1、可以把队尾的数据移到头部(或者头部移到尾部),如把2移到头部,队列变成如下: 2 5 3 1 4。需要消耗能量为2。
2、一直移动队尾的数据到头部,如果该数据为剩余数据最小值,可以移除该数据,消耗能量为0.
3、一直重复上述步骤,直到数据全部移除为止。

问题

怎么计算一个随机队列全部移除需要消耗的能量值。

示例

队列5 3 1 4 2移除需要的能量一共为18:
1、把2移到头部,队列:2 5 3 1 4,消耗能量2。
2、把4移到头部,队列:4 2 5 3 1,消耗能量4。
3、把1移到头部,队列:1 4 2 5 3,消耗能量1。
4、移除1,消耗能量为0。队列:4 2 5 3.
5、把4移到尾部,队列:2 5 3 4 ,消耗能量4。
6、把2移除,消耗能量0。队列:5 3 4,
7、把4移到头部,队列:4 5 3 ,消耗能量4。
8、把3移到头部,队列:3 4 5,消耗能量3。
9、把3移除,消耗能量0。队列:4 5,
10、把4移除,消耗能量0。队列:5,
11、把5移除,消耗能量0。全部移除完毕。

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

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

4563 次点击  
加入收藏 微博
13 回复  |  直到 2019-10-21 14:12:51
pengwl
pengwl · #1 · 6年之前

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

hei6775
hei6775 · #2 · 6年之前

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

pengwl
pengwl · #3 · 6年之前
hei6775hei6775 #2 回复

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

谢谢

Liaomessi
Liaomessi · #4 · 6年之前

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

darklowly
darklowly · #5 · 6年之前

应该是这样:

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)
        }
    }
}
CppToGo
CppToGo · #6 · 6年之前

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

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

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

gikieng
gikieng · #8 · 6年之前

不懂

invictus090
invictus090 · #9 · 6年之前

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

licz
licz · #10 · 5年之前

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

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
}
licz
licz · #11 · 5年之前

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

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
}
jinyuyoulong
jinyuyoulong · #12 · 5年之前

语文不好,没读懂。疑问如下:

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

示例5: 4 队尾移到队头,消耗能量4

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

heyHui2018
heyHui2018 · #13 · 5年之前
jinyuyoulongjinyuyoulong #12 回复

语文不好,没读懂。疑问如下: 2 队尾移到队头,消耗能量2, 示例5: 4 队尾移到队头,消耗能量4 难道 队尾移到队头消耗的能量不应该一样吗,或者和队内元素数量有关系。 这个疑问不解决,后边的看不下去了。

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

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