原题: 一副从1到n的牌,每次从牌堆顶取一张放桌子上,再取一张放牌堆底,直到手机没牌,最后桌子上的牌是从1到n有序,设计程序,输入n,输出牌堆的顺序数组 。
微软君给的算法: 取一个1~n的数组,这里为了说明取n=5。按照题目中的规则变换,得到数组:[1 3 5 4 2],将该数组下标与值互换得到[1 5 2 4 3],即为答案。解释:[1 3 5 4 2]的意义是,经过变换,原数组中3号位置的数字现在2号槽,原数组中5号位置的数字现在3号槽... 现在已知变换后的槽存放的是1~n,故只需将下标与值互换即可得到待求数组。
// joseph
/*
# golang代码 变相约瑟夫环。知乎上一个小米面试题的微软解法(细节去知乎找找看)
#
# 原题: 一副从1到n的牌,每次从牌堆顶取一张放桌子上,再取一张放牌堆底,直到手机没牌,最后桌子上的牌是从1到n有序,设计程序,输入n,输出牌堆的顺序数组 。
#
# 微软君给的算法: 取一个1~n的数组,这里为了说明取n=5。按照题目中的规则变换,得到数组:[1 3 5 4 2],将该数组下标与值互换得到[1 5 2 4 3],即为答案。解释:[1 3 5 4 2]的意义是,经过变换,原数组中3号位置的数字现在2号槽,原数组中5号位置的数字现在3号槽... 现在已知变换后的槽存放的是1~n,故只需将下标与值互换即可得到待求数组。
#
*/
// 此代码用了list,肯定有效率问题。以后考虑改进。
// 我的golang技能生疏了不少
package main
import (
"container/list"
"fmt"
)
// 构成顺序数组
func make_array(n int) *list.List {
array := list.New()
for i := 1; i <= n; i++ {
array.PushBack(i)
}
return array
}
// 生成中间数组
func count_mid_array(array *list.List) *list.List {
mid_array := list.New()
for array.Len() > 1 {
t1 := array.Front()
mid_array.PushBack(t1.Value)
array.Remove(t1)
t2 := array.Front()
array.Remove(t2)
array.PushBack(t2.Value)
}
mid_array.PushBack(array.Front().Value)
return mid_array
}
// 转换中间组到最终结果
func trans_array(n int, new_array *list.List) *list.List {
fin_array := list.New()
for i := 1; i <= n; i++ {
idx := 0
for e := new_array.Front(); e != nil; e = e.Next() {
idx++
if e.Value == i {
fin_array.PushBack(idx)
}
}
}
return fin_array
}
// 打印list函数
func PrintList(l *list.List) {
if l != nil {
fmt.Printf("[")
for e := l.Front(); e != nil; e = e.Next() {
fmt.Printf("%d", e.Value)
if e.Next() != nil {
fmt.Print(", ")
}
}
fmt.Printf("]\n")
}
}
// 约瑟夫环入口
func joseph() {
fmt.Println("----====joseph run====----")
var n int = 12
array := make_array(n)
PrintList(array)
mid_array := count_mid_array(array)
PrintList(mid_array)
fin_array := trans_array(n, mid_array)
PrintList(fin_array)
}
有疑问加站长微信联系(非本文作者)