万网网站域名,wordpress关键词内链,wordpress接erp,重庆周边游景点推荐一、解码方法II#xff08;解码方法I的升级版#xff09;
在I的基础上增加了*#xff0c;可以代替1-9中任意一个数字#xff0c;求解码的方法有多少种
输入#xff1a;s *
输出#xff1a;9
解释#xff1a;这一条编码消息可以表示 1、解码方法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[i1]dp[i];
2.如果遍历到的数字可以和放一个数字构成一个有效的大写字母的ASCII值是对dp[i1]有用的(这个有用是指多了dp[i-1]种分割方法那么dp[i1]dp[i-1];
那么这一道题的思路是
1.如果遍历到的字符是* 1.1 那么不论上一个字符是什么首先dp[i1]dp[i]*9; 1.2 如果上一个字符是1,那么dp[i1]dp[i-1]*9 1.3 如果上一个字符是2,那么dp[i1]dp[i-1]*6(1-6) 1.4 其他情况均无法构成有效的大写字母
2.如果遍历到的字符不是* 2.1 如果不是0,那么就可以切割。dp[i1]dp[i]; 2.2 如果上一个字符是1,dp[i1]dp[i-1] 2.3 如果上一个字符是1,且当前的字符是0-7,dp[i1]dp[i-1] 2.4 如果上一个字符是*,且当前字符是0-7,dp[i1]2*dp[i-1] 2.5 如果上一个字符是*,且当前字符不是0-7,dp[i1]dp[i-1] 代码
/*** 如果新加的一个字母是* 并且前一个数字是2的 直接9* 前一个数字是*,直接16* 解码方法I* 如果新加的数字可以和前面数字组成一个有效的大写字母 那么dp[i1]dp[i]dp[i-1]* 如果不能组成dp[i1]dp[i]*/
class Solution {public int numDecodings(String s) {int mod 1000000007;int size s.length();long[] dp new long[size 1];dp[0] 1;dp[1] (s.charAt(0) *) ? 9 : 1;if (s.charAt(0) 0)return 0;for (int i 1; i size; i) {// 开始分情况if (s.charAt(i) *) {dp[i 1] dp[i] * 9;if (s.charAt(i - 1) 1) {dp[i 1] dp[i - 1] * 9;} else if (s.charAt(i - 1) 2) {dp[i 1] dp[i - 1] * 6;} else if (s.charAt(i - 1) *) {dp[i 1] dp[i - 1] * 15;}} else {if (s.charAt(i) ! 0)dp[i 1] dp[i];if (s.charAt(i - 1) 1)dp[i 1] dp[i - 1];else if (s.charAt(i - 1) 2 s.charAt(i) 7)dp[i 1] dp[i - 1];else if (s.charAt(i - 1) *) {if (s.charAt(i) 7)dp[i 1] 2 * dp[i - 1];elsedp[i 1] dp[i - 1];}}dp[i1] % mod;}return (int) dp[s.length()];}
}
二、丑数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个3z个5组成的。即n2*x3*y5*z
那么我们如何寻找第n个丑数可以使用数组把n个丑数都求出来那么如何判断第a个丑数是什么
根据题目可知1也是一个丑数那么arr[0]1;然后开始遍历:
arr[i]的值就从Math.min(arr[i2]*2,Math.min(arr[i3]*3,arr[i5]*5))中取
帮助理解
现在丑数中有{12}在上一步中1已经同2相乘过了所以今后没必要再比较1×2了我们说1失去了同2相乘的资格。
现在1有与35相乘的资格2有与235相乘的资格但是2×3和2×5是没必要比较的因为有比它更小的1可以同35相乘所以我们只需要比较1×31×52×2。
代码
class Solution {public int nthUglyNumber(int n) {int[] dpnew int[n];dp[0]1;int i20,i30,i50;for(int i1;in;i){dp[i]Math.min(dp[i2]*2,Math.min(dp[i3]*3,dp[i5]*5));if(dp[i]dp[i2]*2)i2;if(dp[i]dp[i3]*3)i3;if(dp[i]dp[i5]*5)i5;}return dp[n-1];}
}
三、超级丑数类似于丑数II
区别
和丑数II的区别就是丑数II的质因数只有2、3、5。而超级丑数的质因数的题目中给的。
思路
使用一个map集合记录因数以及该因数参与的最近一次超级丑数的下标
key:质因数
value:该因数参与的最近一次超级丑数的下标 类似于丑数II中的i2,i3,i5
dp[i]每次依然从dp[x]*primes[i]中选择一个最小的
代码:
class Solution {public int nthSuperUglyNumber(int n, int[] primes) {MapInteger,Integer mapnew HashMap();for(int i:primes){map.put(i,0);}long[] dpnew long[n];dp[0]1;for(int i1;in;i){SetInteger keysmap.keySet();long minLong.MAX_VALUE;//找出最小值 也就是dp[i]放谁for(Integer key:keys){int valuemap.get(key);if(dp[value]*keymin)mindp[value]*key;}//找出最小值是由哪一个质数得到的 value1for(Integer key:keys){int valuemap.get(key);if(min/dp[value]key)map.put(key,map.get(key)1);}dp[i]min;}return (int)dp[n-1];}
}
四、青蛙过河(dp)
题意给定一个数组stones[],代表每个单元格之间的距离青蛙每次跳跃的距离是上一次跳跃的距离-1-1;也就是在k-1,k,k1这个范围中选择。
思路
如何定义dp数组的含义dp[i][j]代表的是能否从某个单元格跳j步到达i单元格。因此某个单元格一定是i之前的。那么根据j的不同跳到i有很多种方法。
递推公式:dp[i][distance]dp[j][distance-1]||dp[j][distance]||dp[j][distance1]
如何理解这个递推公式:首先j是i之前的一个单元格从j跳到i,要看distance是否满足我们能跳的距离。
如果上一个单元是跳了distance-1到达的那么1后可以得到distance
如果上一个单元是跳了distance到达的那么不变可以得到distance;
如果上一个单元是跳了distance1到达的那么-1可以得到distance;
代码
class Solution {public boolean canCross(int[] stones) {int lengthstones.length;//1.定义dp数组boolean[][] dpnew boolean[length][length];//dp数组的含义//初始化dp数组dp[0][0]true;for(int i1;ilength;i){for(int ji-1;j0;j--){int distancestones[i]-stones[j];//如果此时的j是无法跳过来的那么j--之后更无法跳过来所以直接breakif(distancej1)break;dp[i][distance]dp[j][distance-1]||dp[j][distance]||dp[j][distance1];if(ilength-1dp[i][distance])return true;}}return false;}
}
五、等差数列划分滑动窗口/dp
如果一个数列 至少有三个元素 并且任意两个相邻元素之差相同则称该数列为等差数列。
给你一个整数数组 nums 返回数组 nums 中所有为等差数组的 子数组 个数。
子数组 是数组中的一个连续序列。
输入nums [1,2,3,4]
输出3
解释nums 中有三个子等差数组[1, 2, 3]、[2, 3, 4] 和 [1,2,3,4] 自身。
解法一滑动窗口
思路
每次在数组中找一个最长等差数列然后根据公式计算一下该等差数列中含有几个长度3的等差数列如果len5,长度为3的有3个长度为4的有2个长度为5的有1个。12...len-2 次数为len-1 * len -2 /2
如果加上下一个元素 无法构成等差数列那么就结算一下。然后继续重置数列长度。
代码
/**
滑动窗口*/
class Solution {public int numberOfArithmeticSlices(int[] nums) {if(nums.length3)return 0;int right2;int count0;int len2;int preDiffnums[1]-nums[0];while(rightnums.length){int curDiffnums[right]-nums[right-1];if(curDiffpreDiff)len;if(curDiff!preDiff){count(len-1)*(len-2)/2;preDiffcurDiff;len2;}right;}count(len-1)*(len-2)/2;return count;}
}
解法二动态规划
思路: 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]组成
代码
class Solution {public int numberOfArithmeticSlices(int[] nums) {if(nums.length3)return 0;int[] dpnew int[nums.length];int res0;for(int i2;inums.length;i){if(nums[i]-nums[i-1]nums[i-1]-nums[i-2]){dp[i]dp[i-1]1;resdp[i];}}return res;}
}
