劍指Offer系列(java版,詳細解析)46.把數字翻譯成字符串

程序員社區 2022-01-08 02:31:27 阅读数:718

offer 系列 java 解析 字符串

題目描述

劍指 Offer 46. 把數字翻譯成字符串

難度中等213收藏分享切換為英文接收動態反饋

給定一個數字,我們按照如下規則把它翻譯為字符串:0 翻譯成 “a” ,1 翻譯成 “b”,……,11 翻譯成 “l”,……,25 翻譯成 “z”。一個數字可能有多個翻譯。請編程實現一個函數,用來計算一個數字有多少種不同的翻譯方法。

示例 1:

輸入: 12258輸出: 5解釋: 12258有5種不同的翻譯,分別是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"

提示:

  • 0 <= num < 231

測試用例

  • 功能測試(只有一比特數字;包含多比特數字)
  • 特殊輸入測試(輸入的數字字符串指針為空指針)

題目考點

  • 考察應聘者分析問題的能力。應聘者能够從問題中分析出遞歸的錶達式[f(i)=f(i-1) + g(i,i-1)f(i-2)]是解决這個問題的關鍵。
  • 考察應聘者對遞歸及時間效率的理解。面試官期待應聘者能够用基於循環的代碼(動態規劃)來避免不必要的重複計算。

解題思路

動態規劃

假設數組dp[i]錶示從頭到字符串的第i比特(不是字符串的下標),一共有多少種解碼方法的話

首先我們一定能從第i-1比特的解碼方法上繼續解碼。那麼就是dp[i] += dp[i-1];

除此之外如果字符串的第i-1比特和第i比特能組成一個10到25的數字,說明我們可以是在第i-2比特的解碼方法上繼續解碼。那麼就是dp[i] += dp[i-2];

參考解題

class Solution {
 public int translateNum(int num) {
 String s = String.valueOf(num); int a = 1, b = 1; for(int i = 2; i <= s.length(); i++) {
 String tmp = s.substring(i - 2, i); int c = tmp.compareTo("10") >= 0 && tmp.compareTo("25") <= 0 ? a + b : a; b = a; a = c; } return a; }}
class Solution {
 public int translateNum(int num) {
 int a = 1, b = 1, x, y = num % 10; while(num != 0) {
 num /= 10; x = num % 10; int tmp = 10 * x + y; int c = (tmp >= 10 && tmp <= 25) ? a + b : a; b = a; a = c; y = x; } return a; }}
版权声明:本文为[程序員社區]所创,转载请带上原文链接,感谢。 https://gsmany.com/2022/01/202201080231264944.html