使用Python解题逻辑正确但是不AC
测试用例有错误(没有考虑int越界,计算出来错误结果作为测试答案)
题目链接
https://www.nowcoder.com/practice/592a069811044d3fadb94c6c55d7b4f2
以下是原题描述
题目描述
已知摩尔斯电码和字符映射关系如下:
-
A -> 0
-
B -> 1
-
C -> 10
-
D -> 11
-
E -> 100
-
F -> 101
-
G -> 110
-
H -> 111
当前我们获取到了一串01数字字符串,需要进行摩尔斯电码解码,请问共有多少种解码方法?
输入描述:
一行由0和1组成的字符串
输出描述:
一行一个数字表示答案,即解码方法数量
示例1
输入:
11
输出:
2
说明:
有D和BB两种解法
示例2
输入:
100
输出:
3
说明:
有E,BAA和CA三种解法
备注:
输入字符串长度范围为1~100
输出解码方法数不超过2147483647
使用Python解题如下:
thotext = input()
dp = [0 for i in text]
dp[0] = 1
for i in range(1, len(text)):
dp[i] += dp[i - 1]
if text[i - 1] == '1':
dp[i] += dp[i - 2] if i >= 2 else 1
if i >= 2 and text[i - 2] == '1':
dp[i] += dp[i - 3] if i >= 3 else 1
print(dp[-1])
上述代码并未通过
巨坑: 标准答案没有考虑32位Int的溢出
对比了Java答案和我的代码,经过多次测试发现,Java使用的是32位的int计算答案时会产生溢出。
将Java代码改成long后:
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String s = scanner.nextLine();
char[] chars = s.toCharArray();
long [] dp=new long[chars.length];
for (int i=0;i< chars.length;i++){
dp[i]=(i>=1?dp[i-1]:1)+(i>=2?dp[i-2]:1)*(i>=1?chars[i-1]-'0':0)+(i>=3?dp[i-3]:1)*(i>=2?chars[i-2]-'0':0);
}
System.out.println(dp[chars.length-1]);
}
}
输入
111101101001110110011111001010101100111101110010001111011110
输出
1520481317175
知识点: Python3的int是变长的
根据
官方文档
python的int类型可以理解为无限长,仅仅受虚拟内存大小的影响!
Integers (
int
)
These represent numbers in an unlimited range, subject to available (virtual) memory only. For the purpose of shift and mask operations, a binary representation is assumed, and negative numbers are represented in a variant of 2’s complement which gives the illusion of an infinite string of sign bits extending to the left.