2021-08-08：自由之路。电子游戏“辐射4”中，任务“通向自由”要求玩家到达名为“Freedom Trail Ring”的金属表盘，并使用表盘拼写特定关键词才能开门。给定一个字符串 ring，表示刻在外环上的编码；给定另一个字符串 key，表示需要拼写的关键词。您需要算出能够拼写关键词中所有字符的最少步数。最初，ring 的第一个字符与12:00方向对齐。您需要顺时针或逆时针旋转 ring 以使 key 的一个字符在 12:00 方向对齐，然后按下中心按钮，以此逐个拼写完 key 中的所有字符。旋转 ring 拼出 key 字符 key[i] 的阶段中：您可以将 ring 顺时针或逆时针旋转一个位置，计为1步。旋转的最终目的是将字符串 ring 的一个字符与 12:00 方向对齐，并且这个字符必须等于字符 key[i] 。如果字符 key[i] 已经对齐到12:00方向，您需要按下中心按钮进行拼写，这也将算作 1 步。按完之后，您可以开始拼写 key 的下一个字符（下一阶段）, 直至完成所有拼写。
福大大 答案2021-08-08：
递归。具体见代码。
代码用golang编写。代码如下：
package main
import (
"fmt"
"math"
)
func main() {
ring := "godding"
key := "gd"
ret := findRotateSteps(ring, key)
fmt.Println(ret)
}
func findRotateSteps(r string, k string) int {
N := len(r)
map0 := make(map[byte][]int)
for i := 0; i < N; i++ {
if _, ok := map0[r[i]]; !ok {
map0[r[i]] = make([]int, 0)
}
map0[r[i]] = append(map0[r[i]], i)
}
M := len(k)
dp := make([][]int, N)
for i := 0; i < N; i++ {
dp[i] = make([]int, M+1)
}
for i := 0; i < N; i++ {
for j := 0; j <= M; j++ {
dp[i][j] = -1
}
}
return process(0, 0, k, map0, N, dp)
}
// 电话里：指针指着的上一个按键preButton
// 目标里：此时要搞定哪个字符？keyIndex
// map : key 一种字符 value: 哪些位置拥有这个字符
// N: 电话大小
// f(0, 0, aim, map, N)
func process(preButton int, index int, str string, map0 map[byte][]int, N int, dp [][]int) int {
if dp[preButton][index] != -1 {
return dp[preButton][index]
}
ans := math.MaxInt64
if index == len(str) {
ans = 0
} else {
// 还有字符需要搞定呢！
cur := str[index]
nextPositions := map0[cur]
for _, next := range nextPositions {
cost := dial(preButton, next, N) + 1 + process(next, index+1, str, map0, N, dp)
ans = getMin(ans, cost)
}
}
dp[preButton][index] = ans
return ans
}
func dial(i1 int, i2 int, size int) int {
return getMin(Abs(i1-i2), getMin(i1, i2)+size-getMax(i1, i2))
}
func getMin(a int, b int) int {
if a < b {
return a
} else {
return b
}
}
func Abs(a int) int {
if a < 0 {
return -a
} else {
return a
}
}
func getMax(a int, b int) int {
if a > b {
return a
} else {
return b
}
}
执行结果如下：
左神java代码
