CS-Wiki CS-Wiki
Home
知识体系总览
  • 数据结构与算法
  • 计算机网络
  • 操作系统
  • MySQL
  • Redis
  • 设计模式
  • Java 基础
  • Java 集合
  • Java 并发
  • Java 虚拟机
  • Spring
  • Kafka
  • 校招扫盲
  • 项目推荐
  • 唠唠嗑儿
  • 读书笔记
归档
GitHub (opens new window)
Home
知识体系总览
  • 数据结构与算法
  • 计算机网络
  • 操作系统
  • MySQL
  • Redis
  • 设计模式
  • Java 基础
  • Java 集合
  • Java 并发
  • Java 虚拟机
  • Spring
  • Kafka
  • 校招扫盲
  • 项目推荐
  • 唠唠嗑儿
  • 读书笔记
归档
GitHub (opens new window)
  • 刷题模板汇总
  • 一些刷题小技巧
  • 整数 and 位运算

  • 数组

  • 链表

  • 哈希表

  • 字符串

  • 栈

  • 队列

  • 二叉树

  • 前缀树

  • 二分查找

  • 双指针法

  • 区间求和问题

  • 排序

  • 回溯算法

  • 贪心算法

  • 动态规划

    • 动态规划理论基础
    • Fibonacci 问题

    • 背包问题

    • 打家劫舍问题

    • 买卖股票问题

    • 子串和子序列问题

    • 矩阵路径问题

    • 其他

      • 剑指 Offer 14- I - 剪绳子
      • 不同的二叉搜索树
      • 把数字翻译成字符串
        • 📃 题目描述
        • 🔔 解题思路
        • 💥 复杂度分析
      • 粉刷房子
      • 翻转字符
      • 分割数组
      • 最大正方形
      • 统计全为 1 的正方形子矩阵
      • 最长有效括号
      • 剑指 Offer 19 - 正则表达式匹配
      • 剑指 Offer 49 - 丑数
  • 图

  • 数学

  • 自动机

  • 海量数据和空间限制

  • 05-数据结构与算法
  • 动态规划
  • 其他
小牛肉
2022-09-12
目录

把数字翻译成字符串

# 📃 题目描述

题目链接:

  • 剑指 Offer 46. 把数字翻译成字符串 (opens new window)
  • BM69 把数字翻译成字符串 (opens new window)

# 🔔 解题思路

dp[i] 表示字符串 nums 中以 i 个位置结尾的前缀字符串的解码种数,例如 nums = "123", 此时dp[0]=1,dp[1]=2,dp[2]=3

  • 当前字符不等于 0 的时候, dp[i] = dp[i-1], 此时将当前位置的一个字符译码
  • 当前字符+前一个字符,记为num, 如果 10<=num<=26,此时符合两个合并一起译码的条件,dp[i] = dp[i - 2]

总的来说,其实这道题目很像爬楼梯,一次能爬一层和爬两层,只是爬的过程中增加了一些限定条件,只要将这些限定条件屡清楚则可以完全搞懂这类题目~

import java.util.*;


public class Solution {
    /**
     * 解码
     * @param nums string字符串 数字串
     * @return int整型
     */
    public int solve (String nums) {
        if (nums == null || nums.length() == 0 || nums.charAt(0) == '0') {
            return 0;
        }
        
        int n = nums.length();
        // dp[i] 表示 nums[0...i] 有多少种译码结果
        int[] dp = new int[n];
        dp[0] = 1;
        
        for (int i = 1; i < n; i ++) {
            // 1. 最基本的, nums[i] 单独编码
            if (nums.charAt(i) != '0') {
                dp[i] = dp[i - 1];
            }
            
            // 2. nums[i] 和 nums[i - 1] 共同编码
            int num = (nums.charAt(i - 1) - '0') * 10 + (nums.charAt(i) - '0');
            if (num >= 10 && num <= 26) {
                // 处理下边界情况
                if (i == 1) {
                    dp[i] += 1;
                }
                else {
                    dp[i] += dp[i - 2];
                }
            }
        }
        
        return dp[n - 1];
    }
}

# 💥 复杂度分析

  • 空间复杂度:
  • 时间复杂度:

🎁 公众号

各位小伙伴大家好呀,叫我小牛肉就行,目前在读东南大学硕士,上方扫码关注公众号「飞天小牛肉」,与你分享我的成长历程与技术感悟~

帮助小牛肉改善此页面 (opens new window)
Last Updated: 2023/02/16, 11:27:10
不同的二叉搜索树
粉刷房子

← 不同的二叉搜索树 粉刷房子→

最近更新
01
02
线上环境 CPU 使用率飙升如何快速排查?
03-05
03
面试官再跟你说中国没有根服务器,雪人计划让他了解下
02-23
更多文章>
Theme by Vdoing | Copyright © 2019-2023 飞天小牛肉 | 皖ICP备2022008966号
  • 跟随系统
  • 浅色模式
  • 深色模式
  • 阅读模式