字符解码问题 - 剑指46. 把数字翻译成字符串好 - 《LeetCode笔记》

剑指 Offer 46. 把数字翻译成字符串">剑指 Offer 46. 把数字翻译成字符串

剑指 Offer 46. 把数字翻译成字符串

贴一个答案：黑龙江大佬的:链接分为字符串遍历和求余数两个方法，分别是On，O1版本

方法1：字符串遍历
func translateNum(num int) int {
    bytes := []byte(strconv.Itoa(num))
    n := len(bytes)
    arr := make([]int, n)
    for i := 0; i < n; i++ {
        arr[i] = int(bytes[i] - '0')
    }
    dp := make([]int, n+1)
    dp[0] = 1
    dp[1] = 1
    for i := 2; i <= n; i++ {
        if arr[i-2] != 0 && (arr[i-2]*10+arr[i-1]) < 26 {
            dp[i] = dp[i-1] + dp[i-2]
        } else {
            dp[i] = dp[i-1]
        }
    }
    return dp[n]
}

方法2：数字求余
时间复杂度：On
空间复杂度：O1

func translateNum2(num int) int {
    a := 1
    b := 1
    x, y := num%10, num%10

    for num != 0 {
        num /= 10
        x = num % 10
        temp := 10*x + y
        c := a

        if 10 <= temp && temp <= 25 {
            c = a + b
        }
        b = a
        a = c
        y = x
    }
    return a
}

给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。

暴力 DFS
- time：O(2^n) 。每个节点都要遍历，栈的深度 n ，n 是数字字符个数
- space: O(n) 。栈的深度 n ，n 是数字字符个数

DFS + 备忘录

time：O(n) 。栈的深度 n ，n 是数字字符个数

space: O(n) 。栈的深度 n ，n 是数字字符个数

//自顶向下 == 递归 + 记忆化 ||  难点在处理字符串！
func translateNum(num int) int {
str := strconv.Itoa(num)        //变成“字符串1234”
n := len(str)                   //字符串长度 4， 不是原数组长度1000

dp := make([]int, n+1)
dp[0], dp[1] = 1, 1            //因为dp【2】= dp【0】+ dp【1】=2 ，所以dp【0】= 1

for i := 2; i <= n; i++ {
   dp[i] += dp[i-1]
   if str[i-2:i-1] == "0" {    //核心，判断条件，最优子结构 函数的分类
       continue
   }
   two_digit, _ := strconv.Atoi(str[i-2:i]) 
       if two_digit <= 25 {
           dp[i] += dp[i-2]
       }
}
return dp[n]
}

//1，自顶向下 == 递归 + 记忆化  ， 字符串的处理 稍有不同
func translateNum(num int) int {
tmp := num
nums := make([]int,0)
count := 0
for tmp > 0{
   nums = append(nums,tmp%10)
   tmp = tmp/10
   count++
}
if count <= 1{
   return 1
}
dp := make([]int,count+1)
dp[0] = 1
dp[1] = 1
for i:=2;i<=count;i++{
   tmp = nums[i-1]*10+nums[i-2]
   if tmp >= 10 && tmp <= 25{
       dp[i] = dp[i-1]+dp[i-2]
   }else{
       dp[i] = dp[i-1]
   }
}
return dp[count]
}

//2，自顶向下 == 递归 + 记忆化  ， 字符串的处理 稍有不同
func translateNum(num int) int {

    //此题如同跳楼梯 12258=abcde
    //如果de可以翻译，那么翻译方案是f(i-2),
    //否则是f(i-1)
    //可以递推公式: f(i) = f(i-1)+f(i-2)
    //否则递推公式: f(i) = f(i-1)

    s := fmt.Sprintf("%d", num)
    bs := []byte(s)
    matrix := make([]int, len(bs)+1)
    matrix[0] = 1
    matrix[1] = 1
    for i:=1;i<len(bs);i++{
        tmp := (bs[i-1]-'0') * 10 + (bs[i]-'0')
        if bs[i-1]!='0' && tmp<=25{
            //如果和前一个可以组成小于25的
            matrix[i+1] = matrix[i] + matrix[i-1]
        }else{
            matrix[i+1] = matrix[i]
        }
    }
    return matrix[len(matrix)-1]
}

时间复杂度：循环的次数是 n 的位数，故渐进时间复杂度为 O(logn)。
空间复杂度：虽然这里用了滚动数组，动态规划部分的空间代价是 O(1) 的，但是这里用了一个临时变量把数字转化成了字符串，故渐进空间复杂度也是 O(logn)

//自底向上，时On，空间O1；     但是有字符串处理，所以时空都变成logn。
//考点2：滚动数组优化空间！
func translateNum(num int) int {
    src := strconv.Itoa(num)
    p, q, res := 0, 0, 1

    for i := 0; i < len(src); i++ {
        p, q, res = q, res, 0           //dp【i】= dp【i-1】,res前进一位，p,q = dp[i-2],dp[i-1]
        res += q

        if i == 0 {
            continue
        }

        sum := src[i-1:i+1]   // 切片索引是左闭右开
        if sum <= "25" && sum >= "10" {   
            res += p  // 命中就加上前一次的,res = p+q
        }
    }
    return res
}

剑指46. 把数字翻译成字符串 好

剑指 Offer 46. 把数字翻译成字符串

剑指46. 把数字翻译成字符串好