剑指 Offer 46. 把数字翻译成字符串

题目：给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。

示例 1:
           输入: 12258
           输出: 5
           解释: 12258有5种不同的翻译，分别是"bccfi", “bwfi”, “bczi”, “mcfi"和"mzi”
提示：
           0 <= num < 2^31

方法一：动态规划

/*方法一：动态规划 思路和算法: 首先我们来通过一个例子理解一下这里[翻译]的过程：我们来尝试翻译[1402]。 分成两种情况： 首先我们可以把每一位单独翻译，即[1,4,0,2]，翻译的结果是 beac 然后我们考虑组合某些连续的两位： [14,0,2]，翻译的结果是 oac。 [1,40,2]，这种情况是不合法的，因为40不能翻译成任何字母。 [1,4,02]，这种情况也是不合法的，含有前导零的两位数不在题目规定的翻译规则中，那么[14,02]显然也是不合法的。 那么我们可以归纳出翻译的规则，字符串的第i位置： 可以单独作为一位来翻译 如果第i−1位和第i位组成的数字在10到25之间，可以把这两位连起来翻译 到这里，我们发现它和[第198题.打家劫舍]非常相似。我们可以用f(i)表示以第i位结尾的前缀串翻译的方案数，考虑第i位单独翻译和与前一位连接起来再翻译对f(i)的贡献。单独翻译对f(i)的贡献为f(i−1)；如果第i−1位存在，并且第i−1位和第i位形成的数字x满足10≤x≤25，那么就可以把第i−1 位和第i位连起来一起翻译，对f(i)的贡献为f(i−2)，否则为0。我们可以列出这样的动态规划转移方程： f(i)=f(i−1)+f(i−2)[i−1≥0,10≤x≤25] 边界条件是f(−1)=0，f(0)=1。方程中[c]的意思是c为真的时候[c]=1，否则[c]=0。 有了这个方程我们不难给出一个时间复杂度为O(n)，空间复杂度为O(n)的实现。考虑优化空间复杂度：这里的f(i)只和它的前两项f(i−1)和f(i−2) 相关，我们可以运用「滚动数组」思想把f数组压缩成三个变量，这样空间复杂度就变成了O(1)。 复杂度分析: 记num=n。 时间复杂度：循环的次数是n的位数，故渐进时间复杂度为O(logn)。 空间复杂度：虽然这里用了滚动数组，动态规划部分的空间代价是O(1)的，但是这里用了一个临时变量把数字转化成了字符串，故渐进空间复杂度 也是 O(logn)。 */ class Method1{ 
    public int translateNum(int num) { 
    String src = String.valueOf(num); int p = 0, q = 0, r = 1; for (int i = 0; i < src.length(); ++i) { 
    p = q; q = r; r = 0; r += q; if (i == 0) { 
    continue; } String pre = src.substring(i - 1, i + 1); if (pre.compareTo("25") <= 0 && pre.compareTo("10") >= 0) { 
    r += p; } } return r; } } 

讯享网/*解题思路： 根据题意，可按照下图的思路，总结出 “递推公式” （即转移方程）。 因此，此题可用动态规划解决，以下按照流程解题。 动态规划解析： 记数字num第i位数字为xi，数字num的位数为n； 例如：num=12258的n=5,x1=1。 状态定义：设动态规划列表dp,dp[i]代表xi为结尾的数字的翻译方案数量。 转移方程：若xi和xi−1组成的两位数字可以被翻译，则dp[i]=dp[i−1]+dp[i−2] ；否则dp[i]=dp[i−1] 。 可被翻译的两位数区间：xi−1=0 时，组成的两位数是无法被翻译的（例如:00,01,02,⋯），因此区间为[10,25]。 dp[i]=dp[i−1]+dp[i−2],10xi−1+xi∈[10,25] dp[i]=dp[i−1] ,10xi−1+xi∈[0,10)∪(25,99] 初始状态：dp[0]=dp[1]=1 ，即 “无数字” 和 “第1位数字” 的翻译方法数量均为1； 返回值：dp[n]，即此数字的翻译方案数量。 Q：无数字情况dp[0]=1从何而来？ A：当num第1,2位的组成的数字∈[10,25]时，显然应有2种翻译方法，即dp[2]=dp[1]+dp[0]=2，而显然dp[1]=1，因此推出dp[0]=1 。 */ 

动态规划思路图【核心思想：递归】：

讯享网

方法二：字符串遍历

/*方法二：字符串遍历 为方便获取数字的各位xi，考虑先将数字num转化为字符串s，通过遍历s实现动态规划。 通过字符串切片s[i−2:i]获取数字组合10xi−1+xi，通过对比字符串ASCII码判断字符串对应的数字区间。 空间使用优化：由于dp[i]只与dp[i−1]有关，因此可使用两个变量a,b分别记录dp[i],dp[i−1]，两变量交替前进即可。此方法可省去dp列表使用的O(N)的额外空间。 复杂度分析： 时间复杂度O(N)：N为字符串s的长度（即数字num的位数log(num)），其决定了循环次数。 空间复杂度O(N)：字符串s使用O(N)大小的额外空间。 */ class Method2{ 
    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; } } //此题的动态规划计算是对称的，即从左向右遍历（从第dp[2]计算至dp[n]）和从右向左遍历（从第dp[n−2]计算至dp[0]）所得方案数一致。 //从右向左遍历的代码如下所示 class Method2{ 
    public int translateNum(int num) { 
    String s = String.valueOf(num); int a = 1, b = 1; for(int i = s.length() - 2; i > -1; i--) { 
    String tmp = s.substring(i, i + 2); int c = tmp.compareTo("10") >= 0 && tmp.compareTo("25") <= 0 ? a + b : a; b = a; a = c; } return a; } } 

方法三：数字求余

讯享网/*方法三：数字求余 上述方法虽然已经节省了dp列表的空间占用，但字符串s仍使用了O(N)大小的额外空间。 空间复杂度优化： 利用求余运算num%10和求整运算num//10，可获取数字num的各位数字（获取顺序为个位、十位、百位…）。 因此，可通过求余和求整运算实现从右向左的遍历计算。而根据上述动态规划“对称性”，可知从右向左的计算是正确的。 自此，字符串s的空间占用也被省去，空间复杂度从O(N)降至O(1)。 复杂度分析： 时间复杂度O(N)：N为字符串s的长度（即数字num的位数log(num)），其决定了循环次数。 空间复杂度O(1)：几个变量使用常数大小的额外空间。 */ class Method3{ 
    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; } } 

剑指 Offer 47. 礼物的最大价值

题目：在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？

示例 1:
         输入:
                  [
                     [1,3,1],
                     [1,5,1],
                     [4,2,1]
                   ]
         输出: 12
         解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物
提示：
         0 < grid.length <= 200
         0 < grid[0].length <= 200

/*解题思路： 题目说明：从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。 根据题目说明，易得某单元格只可能从上边单元格或左边单元格到达。 设f(i,j)为从棋盘左上角走至单元格(i,j)的礼物最大累计价值，易得到以下递推关系：f(i,j)等于f(i,j−1)和f(i−1,j)中的较大值加上当前单元格礼物价值grid(i,j) 。 f(i,j)=max[f(i,j−1),f(i−1,j)]+grid(i,j) 因此，可用动态规划解决此问题，以上公式便为转移方程。 动态规划解析： 状态定义： 设动态规划矩阵dp，dp(i,j)代表从棋盘的左上角开始，到达单元格(i,j)时能拿到礼物的最大累计价值。 转移方程： 当i=0且j=0时，为起始元素； 当i=0且j=0时，为矩阵第一行元素，只可从左边到达； 当i=0且j=0时，为矩阵第一列元素，只可从上边到达； 当i=0且j=0时，可从左边或上边到达； dp(i,j)=grid(i,j) ,i=0,j=0 dp(i,j)=grid(i,j)+dp(i,j−1) ,i=0,j!=0 dp(i,j)=grid(i,j)+dp(i−1,j) ,i!=0,j=0 dp(i,j)=grid(i,j)+max[dp(i−1,j),dp(i,j−1)] ,i!=0,j!=0 初始状态：dp[0][0]=grid[0][0]，即到达单元格(0,0)时能拿到礼物的最大累计价值为grid[0][0]； 返回值：dp[m−1][n−1],m,n分别为矩阵的行高和列宽，即返回dp矩阵右下角元素。 空间复杂度优化： 由于dp[i][j]只与dp[i−1][j],dp[i][j−1],grid[i][j]有关系，因此可以将原矩阵grid用作dp矩阵，即直接在grid上修改即可。 应用此方法可省去dp矩阵使用的额外空间，因此空间复杂度从O(MN)降至O(1)。 复杂度分析： 时间复杂度O(MN)：M,N分别为矩阵行高、列宽；动态规划需遍历整个grid矩阵，使用O(MN)时间。 空间复杂度O(1)：原地修改使用常数大小的额外空间。 */ class Method { 
    public int maxValue(int[][] grid) { 
    int m = grid.length, n = grid[0].length; for(int i = 0; i < m; i++) { 
    for(int j = 0; j < n; j++) { 
    if(i == 0 && j == 0) continue; if(i == 0) grid[i][j] += grid[i][j - 1] ; else if(j == 0) grid[i][j] += grid[i - 1][j]; else grid[i][j] += Math.max(grid[i][j - 1], grid[i - 1][j]); } } return grid[m - 1][n - 1]; } } //以上代码逻辑清晰，和转移方程直接对应，但仍可提升效率：当grid矩阵很大时,i=0或j=0的情况仅占极少数，相当循环每轮都冗余了一次判断。因此，可先初始化矩阵第一行和第一列，再开始遍历递推。 class Method { 
    public int maxValue(int[][] grid) { 
    int m = grid.length, n = grid[0].length; for(int j = 1; j < n; j++) // 初始化第一行 grid[0][j] += grid[0][j - 1]; for(int i = 1; i < m; i++) // 初始化第一列 grid[i][0] += grid[i - 1][0]; for(int i = 1; i < m; i++) for(int j = 1; j < n; j++) grid[i][j] += Math.max(grid[i][j - 1], grid[i - 1][j]); return grid[m - 1][n - 1]; } } 

总结：

不知不觉又已经是凌晨了，又是另一天的开始了，这几天思前想后，想了太多太多的东西！曾经在学校的时候，总觉得社会上应该比学校会好很多！能学习到很多学校里学不到的知识！的确！我也感受到了！是能学习很多的东西！但回过头来看看我们还是曾经在学校的那个自己吗？我们好像是实现我们当初想要的自由了！也实现了自身的财富自由以及人身自由！但回过头来想想！我们真的自由了吗？可能每天早上九点开始上班，晚上五六点下班，路上行程两三个小时，甚至有些可能还得加班……！
学校的生活：天真、单纯、美好！天天除了吃饭、睡觉、上课、干饭、谈个不分手的恋爱！
社会的生活：自由、复杂、现实！天天除了上班、干饭、加班、熬夜、为个不稳定的工作！
真心怀念学校的生活！可惜我们再也回不去了！话说回来了！曾经错过的学习的机会！现在就得加倍的补回来！毕竟昨天已经过去！我们还得继续向前看！且行且珍惜！
最后！我想给在学校的那些小伙伴们说：不要一天沉侵在恋爱的世界里，有时间尽可能的多学习些专业技能！恋爱既可以载舟也可以覆舟，希望你们能越来越好！
我想给已经走向社会的那些小伙伴们说：我们虽然已经步入社会了！说明我们已经从一个学生转变成一个真正的社会人了，我们需要做的就是做好我们自身的本职工作！然后利用平时的业余时间，多提升自身的技术栈！愿我们都能在各行各业中能够取得不同的成就！能够用自身的所学知识为国家贡献出自己的一份力量！加油！