文章目錄

• 題目描述
• 思路 && 代碼
• • • 1. 動態(tài)規(guī)劃做法
    • 2. DFS 做法
    • 二刷

打卡第六天~繼續(xù)加油！

題目描述

• 萬物皆可爬樓梯.…和爬樓梯原理很像，都是使用動態(tài)規(guī)劃的做法來做~
  

思路 && 代碼

1. 動態(tài)規(guī)劃做法

• 初始化：dp[0] = 1, dp[1] = 1。dp[i] 代表 [0, i - 1] 的數(shù)字可翻譯成的字符串種數(shù)，dp[0] 無實際意義，只是為了方便計算。
• 狀態(tài)轉(zhuǎn)移方程：第 i 個字符作為單個字符直接加到上一個字符的組合，有 dp[i - 1] 種結(jié)果。
  而和第 i - 1 個字符可組成字符，則再加上 dp[i - 2] 種結(jié)果。

class Solution {public int translateNum(int num) {// 先轉(zhuǎn)換成數(shù)組，方便操作char[] nums = String.valueOf(num).toCharArray();int count = 0;// dp 做法，類似跳臺階。// dp[i]：從[1, i]的子串，可行方法, dp[0] 不是實際值int[] dp = new int[nums.length + 1];dp[0] = 1;dp[1] = 1;for(int i = 2; i <= nums.length; i++) {// 1. 作為單個字符，直接加上的情況dp[i] = dp[i - 1];int temp = (nums[i - 1 - 1] - '0') * 10 + (nums[i - 1] - '0');// 2. 可以和前一個字符組合，變成兩個的情況if(temp >= 10 && temp <= 25) {dp[i] += dp[i - 2];}}return dp[nums.length];} }

2. DFS 做法

• 補一個當時的做法～
• 這道題用 DFS 的思路也很好理解，設定一個全局變量，在 DFS 的過程中不斷維護即可

class Solution {int count = 0;char[] nums;public int translateNum(int num) {// 先轉(zhuǎn)換成數(shù)組，方便操作nums = String.valueOf(num).toCharArray();dfs(0, nums.length - 1);return count;}public void dfs(int start, int end) {if(start > end) {count++;return;}dfs(start + 1, end);if(start + 1 < nums.length && (nums[start] - '0') * 10 + (nums[start + 1] - '0') < 26 && (nums[start] - '0') * 10 + (nums[start + 1] - '0') >= 10) {dfs(start + 2, end);}} }

二刷

class Solution {public int translateNum(int num) {char[] arr = ("" + num).toCharArray();int[] dp = new int[arr.length + 1];dp[0] = 1;dp[1] = 1;for(int i = 2; i <= arr.length; i++) {dp[i] = dp[i - 1];int temp = (arr[i - 2] - '0') * 10 + (arr[i - 1] - '0');if(temp > 9 && temp < 26) {dp[i] += dp[i - 2];}}return dp[arr.length];} }

總結(jié)

以上是生活随笔為你收集整理的【LeetCode笔记】剑指 Offer 46. 把数字翻译成字符串（Java、字符串、动态规划、DFS）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。