devbox
笔触狂放9
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

算法学习day32

作者：笔触狂放9 | 2024-08-14 05:44:13

赞

踩

算法学习day32

一、解码方法II（解码方法I的升级版）

在I的基础上增加了*，可以代替1-9中任意一个数字，求解码的方法有多少种

输入：s = "*"
输出：9
解释：这一条编码消息可以表示 "1"、"2"、"3"、"4"、"5"、"6"、"7"、"8" 或 "9" 中的任意一条。
可以分别解码成字符串 "A"、"B"、"C"、"D"、"E"、"F"、"G"、"H" 和 "I" 。
因此，"*" 总共有 9 种解码方法。
思路：

回顾一下上一题的思路：

1.如果遍历到的该位数字不是0，那么dp[i+1]=dp[i];

2.如果遍历到的数字可以和放一个数字构成一个有效的大写字母的ASCII值，是对dp[i+1]有用的，(这个有用是指多了dp[i-1]种分割方法）那么dp[i+1]+=dp[i-1];

那么这一道题的思路是？

1.如果遍历到的字符是*，

    1.1  那么不论上一个字符是什么，首先dp[i+1]=dp[i]*9;

    1.2  如果上一个字符是'1',那么dp[i+1]+=dp[i-1]*9

    1.3 如果上一个字符是'2',那么dp[i+1]+=dp[i-1]*6(1->6)

     1.4 其他情况均无法构成有效的大写字母

2.如果遍历到的字符不是'*'

      2.1 如果不是0,那么就可以切割。dp[i+1]=dp[i];

      2.2 如果上一个字符是'1',dp[i+1]+=dp[i-1]

      2.3 如果上一个字符是'1',且当前的字符是'0'->'7',dp[i+1]+=dp[i-1]

      2.4 如果上一个字符是'*',且当前字符是'0'->'7',dp[i+1]+=2*dp[i-1]

      2.5 如果上一个字符是'*',且当前字符不是'0'->'7',dp[i+1]+=dp[i-1]

 代码：
  1. /**
  2.  * 如果新加的一个字母是* 并且前一个数字是<=2的 直接+9
  3.  * 前一个数字是*,直接+16
  4.  * 解码方法I
  5.  * 如果新加的数字可以和前面数字组成一个有效的大写字母 那么dp[i+1]=dp[i]+dp[i-1]
  6.  * 如果不能组成dp[i+1]=dp[i]
  7.  */
  8. class Solution {
  9.     public int numDecodings(String s) {
  10.         int mod = 1000000007;
  11.         int size = s.length();
  12.         long[] dp = new long[size + 1];
  13.         dp[0] = 1;
  14.         dp[1] = (s.charAt(0) == '*') ? 9 : 1;
  15.         if (s.charAt(0) == '0')
  16.             return 0;
  17.         for (int i = 1; i < size; i++) {
  18.             // 开始分情况
  19.             if (s.charAt(i) == '*') {
  20.                 dp[i + 1] += dp[i] * 9;
  21.                 if (s.charAt(i - 1) == '1') {
  22.                     dp[i + 1] += dp[i - 1] * 9;
  23.                 } else if (s.charAt(i - 1) == '2') {
  24.                     dp[i + 1] += dp[i - 1] * 6;
  25.                 } else if (s.charAt(i - 1) == '*') {
  26.                     dp[i + 1] += dp[i - 1] * 15;
  27.                 }
  28.             } else {
  29.                 if (s.charAt(i) != '0')
  30.                     dp[i + 1] = dp[i];
  31.                 if (s.charAt(i - 1) == '1')
  32.                     dp[i + 1] += dp[i - 1];
  33.                 else if (s.charAt(i - 1) == '2' && s.charAt(i) < '7')
  34.                     dp[i + 1] += dp[i - 1];
  35.                 else if (s.charAt(i - 1) == '*') {
  36.                     if (s.charAt(i) < '7')
  37.                         dp[i + 1] += 2 * dp[i - 1];
  38.                     else
  39.                         dp[i + 1] += dp[i - 1];
  40.                 }
  41.             }
  42.             dp[i+1] %= mod;
  43.         }
  44.         return (int) dp[s.length()];
  45.     }
  46. }

二、丑数II

给你一个整数 n ，请你找出并返回第 n 个 丑数 。丑数 就是质因子只包含 2、3 和 5 的正整数。

输入：n = 10
输出：12
解释：[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 个丑数组成的序列。
思路：

首先明白丑数的概念，质因子只包括2、3、5的正整数。因此可以推断出一个丑数必定是由x个2、y个3，z个5组成的。即n=2*x+3*y+5*z

那么我们如何寻找第n个丑数，可以使用数组，把n个丑数都求出来，那么如何判断第a个丑数是什么？

根据题目可知，1也是一个丑数，那么arr[0]=1;然后开始遍历:

arr[i]的值就从Math.min(arr[i2]*2,Math.min(arr[i3]*3,arr[i5]*5))中取

帮助理解：

现在丑数中有{1，2}，在上一步中，1已经同2相乘过了，所以今后没必要再比较1×2了，我们说1失去了同2相乘的资格。

现在1有与3，5相乘的资格，2有与2，3，5相乘的资格，但是2×3和2×5是没必要比较的，因为有比它更小的1可以同3，5相乘，所以我们只需要比较1×3，1×5，2×2。

代码：
  1. class Solution {
  2.     public int nthUglyNumber(int n) {
  3.         int[] dp=new int[n];
  4.         dp[0]=1;
  5.         int i2=0,i3=0,i5=0;
  6.  
  7.         for(int i=1;i<n;i++){
  8.             dp[i]=Math.min(dp[i2]*2,Math.min(dp[i3]*3,dp[i5]*5));
  9.             if(dp[i]==dp[i2]*2)i2++;
  10.             if(dp[i]==dp[i3]*3)i3++;
  11.             if(dp[i]==dp[i5]*5)i5++;
  12.         }
  13.         return dp[n-1];
  14.     }
  15. }

三、超级丑数（类似于丑数II）

区别：

和丑数II的区别就是，丑数II的质因数只有2、3、5。而超级丑数的质因数的题目中给的。

思路：

使用一个map集合记录因数以及该因数参与的最近一次超级丑数的下标？

key:质因数

value:该因数参与的最近一次超级丑数的下标  类似于丑数II中的i2,i3,i5

dp[i]每次依然从dp[x]*primes[i]中选择一个最小的

代码:
  1. class Solution {
  2.     public int nthSuperUglyNumber(int n, int[] primes) {
  3.         Map<Integer,Integer> map=new HashMap<>();
  4.         for(int i:primes){
  5.             map.put(i,0);
  6.         }
  7.         long[] dp=new long[n];
  8.         dp[0]=1;
  9.         for(int i=1;i<n;i++){
  10.             Set<Integer> keys=map.keySet();
  11.             long min=Long.MAX_VALUE;
  12.             //找出最小值 也就是dp[i]放谁
  13.             for(Integer key:keys){
  14.                 int value=map.get(key);
  15.                 if(dp[value]*key<min)min=dp[value]*key;
  16.             }
  17.             //找出最小值是由哪一个质数得到的 value+1
  18.             for(Integer key:keys){
  19.                 int value=map.get(key);
  20.                 if(min/dp[value]==key)map.put(key,map.get(key)+1);
  21.             }
  22.             dp[i]=min;
  23.         }
  24.         return (int)dp[n-1];
  25.     }
  26. }

四、青蛙过河(dp)

题意：给定一个数组stones[],代表每个单元格之间的距离，青蛙每次跳跃的距离是上一次跳跃的距离-1->+1;也就是在k-1,k,k+1这个范围中选择。
思路：

如何定义dp数组的含义：dp[i][j]代表的是能否从某个单元格跳j步到达i单元格。因此某个单元格一定是i之前的。那么根据j的不同，跳到i有很多种方法。

递推公式:dp[i][distance]=dp[j][distance-1]||dp[j][distance]||dp[j][distance+1]

如何理解这个递推公式:首先j是i之前的一个单元格，从j跳到i,要看distance是否满足我们能跳的距离。

如果上一个单元是跳了distance-1到达的，那么+1后可以得到distance；

如果上一个单元是跳了distance到达的，那么不变可以得到distance;

如果上一个单元是跳了distance+1到达的，那么-1可以得到distance;

代码：
  1. class Solution {
  2.     public boolean canCross(int[] stones) {
  3.         int length=stones.length;
  4.         //1.定义dp数组
  5.         boolean[][] dp=new boolean[length][length];
  6.         //dp数组的含义
  7.         //初始化dp数组
  8.         dp[0][0]=true;
  9.         for(int i=1;i<length;i++){
  10.             for(int j=i-1;j>=0;j--){
  11.                 int distance=stones[i]-stones[j];
  12.                 //如果此时的j是无法跳过来的，那么j--之后，更无法跳过来，所以直接break
  13.                 if(distance>j+1)break;
  14.                 dp[i][distance]=dp[j][distance-1]||dp[j][distance]||dp[j][distance+1];
  15.                 if(i==length-1&&dp[i][distance])return true;
  16.             }
  17.         }
  18.         return false;
  19.     }
  20. }

五、等差数列划分（滑动窗口/dp）

如果一个数列 至少有三个元素 ，并且任意两个相邻元素之差相同，则称该数列为等差数列。

给你一个整数数组 nums ，返回数组 nums 中所有为等差数组的 子数组 个数。

子数组 是数组中的一个连续序列。

输入：nums = [1,2,3,4]
输出：3
解释：nums 中有三个子等差数组：[1, 2, 3]、[2, 3, 4] 和 [1,2,3,4] 自身。
解法一：滑动窗口
思路：

每次在数组中找一个最长等差数列，然后根据公式计算一下该等差数列中含有几个长度>=3的等差数列，如果len=5,长度为3的有3个，长度为4的有2个，长度为5的有1个。1+2+...+len-2 次数为：len-1 * len -2 /2

如果加上下一个元素 无法构成等差数列，那么就结算一下。然后继续重置数列长度。

代码：
  1. /**
  2. 滑动窗口
  3.  */
  4. class Solution {
  5.     public int numberOfArithmeticSlices(int[] nums) {
  6.         if(nums.length<3)return 0;
  7.         int right=2;
  8.         int count=0;
  9.         int len=2;
  10.         int preDiff=nums[1]-nums[0];
  11.         while(right<nums.length){
  12.             int curDiff=nums[right]-nums[right-1];
  13.             if(curDiff==preDiff)len++;
  14.             if(curDiff!=preDiff){
  15.                 count+=(len-1)*(len-2)/2;
  16.                 preDiff=curDiff;
  17.                 len=2;
  18.             }
  19.             right++;
  20.         }
  21.         count+=(len-1)*(len-2)/2;
  22.         return count;
  23.     }
  24. }
解法二：动态规划
思路:

dp[i]:代表以nums[i]为结尾的等差数列的个数。

如果nums[i]==nums[i-1]&&nums[i-1]==nums[i-2] 那么dp[i]+=dp[i-1]+1;

为什么dp[i]+=dp[i-1]+1,因为在原来的基础上延长到以nums[i]结尾的这个数列的长度是不变的，新加的+1是新组成的一个等差数列，由nums[i-2] nums[i-1] nums[i]组成

代码：
  1. class Solution {
  2.     public int numberOfArithmeticSlices(int[] nums) {
  3.         if(nums.length<3)return 0;
  4.         int[] dp=new int[nums.length];
  5.         int res=0;
  6.         for(int i=2;i<nums.length;i++){
  7.             if(nums[i]-nums[i-1]==nums[i-1]-nums[i-2]){
  8.                 dp[i]=dp[i-1]+1;
  9.                 res+=dp[i];
  10.             }
  11.         }
  12.         return res;
  13.     }
  14. }

 
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/笔触狂放9/article/detail/978250
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号