2021-07-27：给定一个数组arr，长度为N，arr中的值只有1，2，3三种。arri == 1，代表汉诺塔问题中，从上往下第i个圆盘目前在左；arri == 2，代表汉诺塔问题中，从上往下第i个圆盘目前在中；arri == 3，代表汉诺塔问题中，从上往下第i个圆盘目前在右。那么arr整体就代表汉诺塔游戏过程中的一个状况。如果这个状况不是汉诺塔最优解运动过程中的状况，返回-1。如果这个状况是汉诺塔最优解运动过程中的状况，返回它是第几个状况。
福大大 答案2021-07-27：
1-7的汉诺塔问题。
- 1-6左→中。
- 7左→右。
- 1-6中→右。 单决策递归。 k层汉诺塔问题，是2的k次方-1步。 时间复杂度：O(N)。 空间复杂度：O(1)。
代码用golang编写。代码如下：
代码语言：txt复制package main
import "fmt"
func main() {
arr := []int{3, 3, 3}
if true {
ret := kth(arr)
fmt.Println("递归：", ret)
}
if true {
ret := kth2(arr)
fmt.Println("迭代：", ret)
}
}
func kth(arr []int) int {
N := len(arr)
return step(arr, N-1, 1, 3, 2)
}
// 0...index这些圆盘，arr[0..index] index 1层塔
// 在哪？from 去哪？to 另一个是啥？other
// arr[0..index]这些状态，是index 1层汉诺塔问题的，最优解第几步
func step(arr []int, index int, from int, to int, other int) int {
if index == -1 {
return 0
}
if arr[index] == other {
return -1
}
if arr[index] == from {
return step(arr, index-1, from, other, to)
} else {
p1 := (1 << index) - 1
p2 := 1
p3 := step(arr, index-1, other, to, from)
if p3 == -1 {
return -1
}
return p1 p2 p3
}
}
func kth2(arr []int) int {
if len(arr) == 0 {
return -1
}
from := 1
mid := 2
to := 3
i := len(arr) - 1
res := 0
tmp := 0
for i >= 0 {
if arr[i] != from && arr[i] != to {
return -1
}
if arr[i] == to {
res = 1 << i
tmp = from
from = mid
} else {
tmp = to
to = mid
}
mid = tmp
i--
}
return res
}执行结果如下：
在这里插入图片描述左神java代码
