关于福大大架构师每日一题:20210217规定1和A对应2和B对应3和C对应26和Z对应那么一个数字字符串比如11

24次阅读

共计 876 个字符，预计需要花费 3 分钟才能阅读完成。

2021-02-17：规定 1 和 A 对应、2 和 B 对应、3 和 C 对应 …26 和 Z 对应，那么一个数字字符串比方 ”111”就能够转化为:”AAA”、”KA” 和 ”AK”。给定一个只有数字字符组成的字符串 str，请问有多少种转化后果？

福哥答案 2021-02-17：

天然智慧即可。
1. 递归。有代码。
2. 动静布局。有代码。

代码用 golang 编写，代码如下：

package main

import "fmt"

func main() {
    str := "7210231231232031203123"
    fmt.Println("1. 递归：", number1(str))
    fmt.Println("2. 动静布局：", number2(str))
}
func number1(str string) int {if len(str) == 0 {return 0}
    return process1(str, 0)
}
func process1(str string, index int) int {strLen := len(str)
    if strLen == index { //1
        return 1
    }
    if str[index] == '0' {return 0}
    ret := process1(str, index+1)
    if index+1 < strLen && (str[index] == '1' || (str[index] == '2' && str[index+1] <= '6')) {ret += process1(str, index+2)
    }
    return ret
}

func number2(str string) int {strLen := len(str)
    if strLen == 0 {return 0}
    dp := make([]int, strLen+1)
    dp[strLen] = 1 //1
    for i := strLen - 1; i >= 0; i-- {if str[i] == '0' {continue}
        dp[i] = dp[i+1]
        if i+1 < strLen && (str[i] == '1' || (str[i] == '2' && str[i+1] <= '6')) {dp[i] += dp[i+2]
        }
    }
    return dp[0]
}

执行后果如下：

左神 java 代码
评论

正文完