题目 给定一个数字,我们按照如下规则把它翻译为字符串:0 翻译成 “a” ,1 翻译成 “b”,……,11 翻译成 “l”,……,25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数,用来计算一个数字有多少种不同的翻译方法。
示例 1:输入: 12258
输出: 5
解释: 12258有5种不同的翻译,分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"
提示:0 <= num < 231
【Leetcode:面试题46. 把数字翻译成字符串 动态规划】链接:https://leetcode-cn.com/problems/ba-shu-zi-fan-yi-cheng-zi-fu-chuan-lcof
解题记录
- 首先通过num构建出数组nums,因为int类型最长也就是10,通过除10余数获取到数组倒叙,然后在翻转获得nums
- 状态方程要考虑两种情况,一种是i和i-1位组成数字大于25,这样的情况不会对整体产生新的组合因此顺延,dp[i] = dp[i-1]
- i和i-1位组成数字小于等于25,那么就是两个数可以组成一个新的数这个新的数可以和dp[i-2]中所有情况组合成新的组合,这时的状态方程为dp[i] = dp[i-1]+dp[i-2]
- 还有一种就是i-1为0,这种情况i和i-1组合虽然小于25但是数没有变,没有组成新的组合,因此也是dp[i] = dp[i-1]
- 本题为了计算方便初始状态给了dp[0] = 1, dp[1] = 1
/**
* @author ffzs
* @describe
* @date 2020/6/9
*/
public class Solution {
public static int translateNum(int num) {
int count = 0;
// int 最长 10
int[] tmp = new int[10];
while (num > 9) {
tmp[count] = num % 10;
count ++;
num /= 10;
}
int[] nums = new int[count+1];
nums[0] = num;
for (int i = 1;
i <= count;
i++) {
nums[i] = tmp[count-i];
}
int[] dp = new int[nums.length+1];
dp[0] = 1;
dp[1] = 1;
for (int i = 1;
i < nums.length;
i++) {
dp[i+1]= (nums[i-1]!=0 && (nums[i-1]*10+nums[i])<=25)?dp[i-1] + dp[i]:dp[i];
}
return dp[nums.length];
}public static void main(String[] args) {
System.out.println(translateNum(506));
}
}
文章图片
推荐阅读
- 人工智能|干货!人体姿态估计与运动预测
- 分析COMP122 The Caesar Cipher
- 技术|为参加2021年蓝桥杯Java软件开发大学B组细心整理常见基础知识、搜索和常用算法解析例题(持续更新...)
- C语言学习(bit)|16.C语言进阶——深度剖析数据在内存中的存储
- Python机器学习基础与进阶|Python机器学习--集成学习算法--XGBoost算法
- 数据结构与算法|【算法】力扣第 266场周赛
- 数据结构和算法|LeetCode 的正确使用方式
- leetcode|今天开始记录自己的力扣之路
- 人工智能|【机器学习】深度盘点(详细介绍 Python 中的 7 种交叉验证方法!)
- 网络|简单聊聊压缩网络