LeetCode刷题 day20

目录1. 最低票价2.解码方法1. 最低票价在一个火车旅行很受欢迎的国度你提前一年计划了一些火车旅行。在接下来的一年里你要旅行的日子将以一个名为 days 的数组给出。每一项是一个从 1 到 365 的整数。火车票有 三种不同的销售方式 一张 为期一天 的通行证售价为 costs[0] 美元一张 为期七天 的通行证售价为 costs[1] 美元一张 为期三十天 的通行证售价为 costs[2] 美元。通行证允许数天无限制的旅行。 例如如果我们在第 2 天获得一张 为期 7 天 的通行证那么我们可以连着旅行 7 天第 2 天、第 3 天、第 4 天、第 5 天、第 6 天、第 7 天和第 8 天。返回 你想要完成在给定的列表 days 中列出的每一天的旅行所需要的最低消费 。示例 1输入days [1,4,6,7,8,20], costs [2,7,15]输出11解释例如这里有一种购买通行证的方法可以让你完成你的旅行计划在第 1 天你花了 costs[0] $2 买了一张为期 1 天的通行证它将在第 1 天生效。在第 3 天你花了 costs[1] $7 买了一张为期 7 天的通行证它将在第 3, 4, …, 9 天生效。在第 20 天你花了 costs[0] $2 买了一张为期 1 天的通行证它将在第 20 天生效。你总共花了 $11并完成了你计划的每一天旅行。示例 2输入days [1,2,3,4,5,6,7,8,9,10,30,31], costs [2,7,15]输出17解释例如这里有一种购买通行证的方法可以让你完成你的旅行计划在第 1 天你花了 costs[2] $15 买了一张为期 30 天的通行证它将在第 1, 2, …, 30 天生效。在第 31 天你花了 costs[0] $2 买了一张为期 1 天的通行证它将在第 31 天生效。你总共花了 $17并完成了你计划的每一天旅行。思路本题采用动态规划来解题。动态规划类题目一般都是从递归入手一步一步优化成严格位置依赖的动态规划解法。递归算法当来到days[i]时有三种选择可以选择1,7,30天的通行证那么只需求出每种情况的最小消费即可然后再从这三个选择最小值针对每张通行证需要覆盖尽可能多的旅游天数。代码如下classSolution{privatestaticint[]durations{1,7,30};publicintmincostTickets(int[]days,int[]costs){returnf1(days,costs,0);}publicintf1(int[]days,int[]costs,intstart){if(startdays.length){return0;}intminCostInteger.MAX_VALUE;//分三种情况1,7,30for(inti0;icosts.length;i){intdurationdurations[i];intjstart;while(jdays.lengthdays[j]-days[start]duration){j;}minCostMath.min(minCost,costs[i]f1(days,costs,j));}returnminCost;}}提交后通过37/70个测试用例说明递归思路没有问题代码需要继续优化记忆化搜索不难发现当选择1,7,30天的通行证后势必会在后面的某个时间点继续往后递归调用假如用一个缓存保存days[i]往后的最优方案那调用时只用计算一次即可不用反复计算这样会大大缩短时间复杂度因此得到记忆化搜索的算法classSolution{privatestaticint[]durations{1,7,30};intn;publicintmincostTickets(int[]days,int[]costs){ndays.length;int[]dpnewint[n1];Arrays.fill(dp,-1);returnf1(days,costs,0,dp);}publicintf1(int[]days,int[]costs,intstart,int[]dp){if(startn){return0;}if(dp[start]!-1){returndp[start];}intminCostInteger.MAX_VALUE;for(inti0;icosts.length;i){intdurationdurations[i];intjstart;while(jndays[j]-days[start]duration){j;}minCostMath.min(minCost,costs[i]f1(days,costs,j,dp));}dp[start]minCost;returnminCost;}}此时通过全部测试用例并且时间复杂度已最优但还不是动态规划解法。动态规划上述记忆化搜索过程是在递归中加入缓存需转化成严格位置依赖的动态规划。通过上述思考过程可知可以从后往前计算不用递归调用。classSolution{privatestaticint[]durations{1,7,30};publicintmincostTickets(int[]days,int[]costs){intndays.length;int[]dpnewint[n1];Arrays.fill(dp,0,n1,Integer.MAX_VALUE);dp[n]0;for(intkn-1;k0;k--){intjk;for(intl0;l3;l){while(jndays[j]-days[k]durations[l]){j;}dp[k]Math.min(dp[k],costs[l]dp[j]);}}returndp[0];}}时间复杂度O(n) n是数组长度空间复杂度O(n)2.解码方法一条包含字母 A-Z 的消息通过以下映射进行了 编码 “1” - ‘A’“2” - ‘B’…“25” - ‘Y’“26” - ‘Z’然而在 解码 已编码的消息时你意识到有许多不同的方式来解码因为有些编码被包含在其它编码当中“2” 和 “5” 与 “25”。例如“11106” 可以映射为“AAJF” 将消息分组为 (1, 1, 10, 6)“KJF” 将消息分组为 (11, 10, 6)消息不能分组为 (1, 11, 06) 因为 “06” 不是一个合法编码只有 “6” 是合法的。注意可能存在无法解码的字符串。给你一个只含数字的 非空 字符串 s 请计算并返回 解码 方法的 总数 。如果没有合法的方式解码整个字符串返回 0。题目数据保证答案肯定是一个 32 位 的整数。示例 1输入s “12”输出2解释它可以解码为 “AB”1 2或者 “L”12。示例 2输入s “226”输出3解释它可以解码为 “BZ” (2 26), “VF” (22 6), 或者 “BBF” (2 2 6) 。示例 3输入s “06”输出0解释“06” 无法映射到 “F” 因为存在前导零“6” 和 “06” 并不等价。思路递归算法先从递归入手当前数字分为可单独解码和不可单独解码两种情况若数字为0则不能单独解码从当前到最后解码情况为0种若数字为1则可单独解码也可与后面一位数字一起解码若数字为2则可单独解码若后一位数字小于7则可一起解码若数字大于2则只能单独解码classSolution{publicintnumDecodings(Strings){char[]s1s.toCharArray();returnf1(s1,0);}publicintf1(char[]s,intstart){if(starts.length){return1;}if(starts.length||s[start]0){return0;}intans0;if(start1s.length(s[start]-0)*10s[start1]-026){ansf1(s,start2);}ansf1(s,start1);returnans;}}测试用例通过23 / 269 最后一个超出时间限制表明当前递归算法思路正确时间复杂度需要优化记忆化搜索算法从递归往下推不难看出s[i,n-1]串的结果依赖s[i1,n-1]和s[i2,n-1]子串的解码结果因此用缓存保存后续子串解码方案则减少了重复计算过程classSolution{publicintnumDecodings(Strings){returnnumDecodings(s.toCharArray(),0);}privateintnumDecodings(char[]s,inti){intns.length;intcur0;intnext1;intnextnext0;for(intjn-1;j0;j--){if(s[j]0){cur0;}else{curnext;if(j1n(s[j]-0)*10s[j1]-026){curnextnext;}}nextnextnext;nextcur;cur0;}returnnext;}}严格位置依赖的动态规划classSolution{publicintnumDecodings(Strings){char[]s1s.toCharArray();intns1.length;int[]dpnewint[n1];dp[n]1;for(intin-1;i0;i--){if(s1[i]0){dp[i]0;continue;}dp[i]dp[i1];if(i1n(s1[i]-0)*10s1[i1]-026){dp[i]dp[i2];}}returndp[0];}}时间复杂度O(n) n是字符串长度空间复杂度O(n)当前算法还可以继续优化从动态规划解法可知dp[i]只依赖dp[i1]和dp[i2]因此可用两个局部变量代替dp数组此处不再给出具体解法