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代码