原题: 一副从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)
}