凡客包包,新野seo公司,惠普网站建设的目标,济南市住房与城乡建设厅网站《算法通关村——透彻理解动态规划》
91. 解码方法
一条包含字母 A-Z 的消息通过以下映射进行了 编码 #xff1a;
A - 1
B - 2
...
Z - 26要 解码 已编码的消息#xff0c;所有数字必须基于上述映射的方法#xff0c;反…《算法通关村——透彻理解动态规划》
91. 解码方法
一条包含字母 A-Z 的消息通过以下映射进行了 编码
A - 1
B - 2
...
Z - 26要 解码 已编码的消息所有数字必须基于上述映射的方法反向映射回字母可能有多种方法。例如11106 可以映射为
AAJF 将消息分组为 (1 1 10 6)KJF 将消息分组为 (11 10 6)
注意消息不能分组为 (1 11 06) 因为 06 不能映射为 F 这是由于 6 和 06 在映射中并不等价。
给你一个只含数字的 非空 字符串 s 请计算并返回 解码 方法的 总数 。
题目数据保证答案肯定是一个 32 位 的整数。
示例 1
输入s 12
输出2
解释它可以解码为 AB1 2或者 L12。示例 2
输入s 226
输出3
解释它可以解码为 BZ (2 26), VF (22 6), 或者 BBF (2 2 6) 。示例 3
输入s 06
输出0
解释06 无法映射到 F 因为存在前导零6 和 06 并不等价。提示
1 s.length 100s 只包含数字并且可能包含前导零。
class Solution {public int numDecodings(String s) {int[] dp new int[s.length() 1];dp[0] 1;for(int i 1 ;i s.length();i){if(s.charAt(i-1) ! 0){dp[i] dp[i-1];}if(i1 check(s,i)){dp[i] dp[i-2];}}return dp[s.length()];} public boolean check(String s,int i ){if(s.charAt(i-2) 0){return false;}if((s.charAt(i-2) - 0) * 10 (s.charAt(i-1) -0) 26){return false;}return true;}
}322. 零钱兑换
给你一个整数数组 coins 表示不同面额的硬币以及一个整数 amount 表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额返回 -1 。
你可以认为每种硬币的数量是无限的。
示例 1
输入coins [1, 2, 5], amount 11
输出3
解释11 5 5 1示例 2
输入coins [2], amount 3
输出-1示例 3
输入coins [1], amount 0
输出0提示
1 coins.length 121 coins[i] 231 - 10 amount 104
class Solution {public int coinChange(int[] coins, int amount) {int max amount 1;int [] dp new int[amount 1];Arrays.fill(dp,max);dp[0] 0;for (int i 1;iamount;i){for(int j 0; j coins.length;j){if(coins[j] i){dp[i] Math.min(dp[i],dp[i-coins[j]]1); }}}return dp[amount] amount? -1 : dp[amount];}
}
