做最优秀的自己的视频网站,英文网站建设 深圳,帝国cms转wordpress,企业网站的设计原则322. 零钱兑换
给你一个整数数组 coins #xff0c;表示不同面额的硬币#xff1b;以及一个整数 amount #xff0c;表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额#xff0c;返回 -1 。
你可以认为每种硬币的数…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
class Solution {public int coinChange(int[] coins, int amount) {int max Integer.MAX_VALUE;int[] dp new int[amount 1];//初始化dp数组为最大值for (int j 0; j dp.length; j) {dp[j] max;}//当金额为0时需要的硬币数目为0dp[0] 0;for (int i 0; i coins.length; i) {//正序遍历完全背包每个硬币可以选择多次for (int j coins[i]; j amount; j) {//只有dp[j-coins[i]]不是初始最大值时该位才有选择的必要if (dp[j - coins[i]] ! max) {//选择硬币数目最小的情况dp[j] Math.min(dp[j], dp[j - coins[i]] 1);}}}return dp[amount] max ? -1 : dp[amount];}
}这段Java代码实现了一个经典的动态规划问题——“完全背包问题”的一个应用场景给定不同面额的硬币coins和一个总金额amount计算最少需要多少个硬币凑出这个金额如果不可能凑出则返回-1。这里是使用完全背包的思路即每种硬币可以无限使用。
代码解析 初始化首先定义一个dp数组长度为amount 1并将其所有值初始化为Integer.MAX_VALUE表示在没有计算之前达到每个金额所需的最小硬币数为正无穷大。例外的是dp[0]初始化为0因为当金额为0时不需要任何硬币。 双重循环 外层循环遍历硬币数组coins即遍历每一种硬币面额。内层循环从当前硬币的面额coins[i]开始遍历到总金额amount。这是因为在遍历到的金额j上只有当j至少为当前硬币面额时才有可能使用当前硬币去构成这个金额。 状态转移方程对于内层循环中的每个j如果dp[j - coins[i]]不是初始的最大值即存在一种方式可以构成j - coins[i]的金额则考虑使用一个面额为coins[i]的硬币更新dp[j]为dp[j]和dp[j - coins[i]] 1中的较小值。这里dp[j - coins[i]] 1表示在构成j - coins[i]的基础上再加一个面额为coins[i]的硬币。 返回结果最后检查dp[amount]是否仍为Integer.MAX_VALUE如果是则说明没有找到任何组合可以凑成总金额返回-1否则返回dp[amount]即最少需要的硬币数。
总结
这段代码通过动态规划的完全背包方法有效解决了最少硬币数量问题时间复杂度为O(coins.length * amount)空间复杂度为O(amount)。
279. 完全平方数
给你一个整数 n 返回 和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数其值等于另一个整数的平方换句话说其值等于一个整数自乘的积。例如1、4、9 和 16 都是完全平方数而 3 和 11 不是。
示例 1
输入n 12 输出3 解释12 4 4 4 示例 2
输入n 13 输出2 解释13 4 9
方法一
class Solution {// 版本一先遍历物品, 再遍历背包public int numSquares(int n) {int max Integer.MAX_VALUE;int[] dp new int[n 1];//初始化for (int j 0; j n; j) {dp[j] max;}//如果不想要寫for-loop填充數組的話也可以用JAVA內建的Arrays.fill()函數。//Arrays.fill(dp, Integer.MAX_VALUE);//当和为0时组合的个数为0dp[0] 0;// 遍历物品for (int i 1; i * i n; i) {// 遍历背包for (int j i * i; j n; j) {//if (dp[j - i * i] ! max) {dp[j] Math.min(dp[j], dp[j - i * i] 1);//}//不需要這個if statement因爲在完全平方數這一題不會有湊不成的狀況發生 一定可以用1來組成任何一個n故comment掉這個if statement。}}return dp[n];}
}这段Java代码是解决完全平方数问题的一个动态规划实现目标是找出最少数量的完全平方数例如1, 4, 9, 16…之和使其等于给定的正整数n。代码采用了“先遍历物品再遍历背包”的动态规划策略这里的“物品”指的是完全平方数而“背包”则是我们需要达到的目标和n。
代码解析 初始化dp数组首先创建一个长度为n1的数组dp其中dp[j]表示和为j时所需的最少完全平方数的个数。初始化所有dp[j]为Integer.MAX_VALUE表示初始时没有找到任何组合。但因为任何正整数都可以由无数个1^2组成所以实际上不需要初始化为Integer.MAX_VALUE直接初始化为一个较大的数即可或明确知道最小组合数为1当j 0时。注释中提到的Arrays.fill(dp, Integer.MAX_VALUE);是一种更简洁的初始化方式但在这个特定问题上下文里初始化为极大值然后在特定条件下更新的逻辑是多余的。 初始化dp[0]当和为0时不需要任何完全平方数所以dp[0]设置为0。 双重循环 外层循环遍历所有可能的完全平方数由1^2到√n的平方用i表示当前考虑的完全平方数的根。内层循环遍历从当前完全平方数i*i开始到目标和n的所有可能和j。对于每个j如果可以通过添加当前完全平方数i*i使得总和不超过n并且这样的操作能减少之前记录的最少完全平方数的个数就更新dp[j]的值为dp[j - i * i] 1。 返回结果最后返回dp[n]即和为n时所需的最少完全平方数的个数。
注意
代码注释中指出的“不需要这个if statement”是因为在找完全平方数之和的问题中任何正整数n都可以通过至少一个1^2即至少一个1来组合得到所以直接尝试更新dp[j]的值而不需检查之前是否达到过是不可能的状态即dp[j - i * i] ! max的检查没有必要。
综上这段代码通过动态规划方法有效地求解了最少完全平方数之和的问题。
方法二
class Solution {// 版本二 先遍历背包, 再遍历物品public int numSquares(int n) {int max Integer.MAX_VALUE;int[] dp new int[n 1];// 初始化for (int j 0; j n; j) {dp[j] max;}// 当和为0时组合的个数为0dp[0] 0;// 遍历背包for (int j 1; j n; j) {// 遍历物品for (int i 1; i * i j; i) {dp[j] Math.min(dp[j], dp[j - i * i] 1);}}return dp[n];}
}这段Java代码是解决“完全平方数”的另一个动态规划实现版本目标依然是找出最少数量的完全平方数如1, 4, 9, 16…之和使得这个和等于给定的正整数n。与第一个版本的主要区别在于遍历的顺序这里是“先遍历背包再遍历物品”。
代码解析 初始化与第一个版本相同首先创建一个长度为n1的数组dp其中dp[j]表示和为j时所需的最少完全平方数的个数。初始化所有dp[j]为Integer.MAX_VALUE然后设置dp[0]0表示和为0时不需要任何完全平方数。 遍历顺序改变 外层循环现在遍历背包容量从1到n用j表示当前考虑的总和。内层循环遍历所有可能的完全平方数从1^2到刚好不超过当前总和j的完全平方数用i表示当前完全平方数的根。这确保了每次内循环都是对一个有效的完全平方数进行操作不会超出背包容量。 状态转移对于每个背包容量j遍历所有小于等于它的完全平方数i*i并尝试将当前完全平方数加入组合中即从dp[j - i * i]转移而来然后通过Math.min()函数更新dp[j]为已知的最小组合数。 返回结果最后返回dp[n]即和为n时所需最少的完全平方数个数。
优缺点
优点这种“先遍历背包再遍历物品”的方式直接反映了背包问题的经典解法逻辑上清晰地表达了对于每个总和j尝试用所有可能的完全平方数去填充它寻找最小组合数。缺点在这个特定问题上两种遍历顺序先物品后背包 vs. 先背包后物品在逻辑复杂度和效率上并无本质区别主要取决于个人理解偏好。实际上由于完全平方数的特殊性连续的完全平方数之间差距增大遍历顺序对性能的影响相对较小。
总之这个版本提供了解决“完全平方数”问题的另一种动态规划实现思路关键在于遍历顺序的调整但核心的动态规划思想和状态转移方程保持一致。
139. 单词拆分
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。
注意不要求字典中出现的单词全部都使用并且字典中的单词可以重复使用。
示例 1
输入: s “leetcode”, wordDict [“leet”, “code”] 输出: true 解释: 返回 true 因为 “leetcode” 可以由 “leet” 和 “code” 拼接成。 示例 2
输入: s “applepenapple”, wordDict [“apple”, “pen”] 输出: true 解释: 返回 true 因为 “applepenapple” 可以由 “apple” “pen” “apple” 拼接成。 注意你可以重复使用字典中的单词。 示例 3
输入: s “catsandog”, wordDict [“cats”, “dog”, “sand”, “and”, “cat”] 输出: false
方法一
class Solution {public boolean wordBreak(String s, ListString wordDict) {HashSetString set new HashSet(wordDict);boolean[] valid new boolean[s.length() 1];valid[0] true;for (int i 1; i s.length(); i) {for (int j 0; j i !valid[i]; j) {if (set.contains(s.substring(j, i)) valid[j]) {valid[i] true;}}}return valid[s.length()];}
}这段Java代码是一个解决方案用于解决“单词拆分”问题。给定一个字符串s和一个字典wordDict单词列表判断字符串s是否可以被空格拆分成一个或多个字典中的单词。这是一个典型的动态规划问题。
代码解析 数据结构转换首先将wordDict转换为哈希集合HashSetString set这样可以以O(1)的时间复杂度查询一个字符串是否在字典中。 初始化定义一个布尔型数组valid长度为s.length() 1其中valid[i]表示字符串s的前i个字符组成的子串是否可以被拆分成字典中的单词。初始化valid[0]为true因为空字符串是可以“拆分”的。 动态规划填充外层循环从1遍历到s.length()代表当前正在检查的子串的结束位置。内层循环从0遍历到当前的结束位置i这是为了找到所有可能的前缀子串。如果存在某个前缀子串从索引j到i在字典集合中并且这个前缀子串的前一个位置即j的子串也是合法的valid[j]为true那么将当前位置i标记为合法valid[i] true。这里使用了!valid[i]作为提前终止的条件一旦找到一个合法的拆分方式就不再继续查找提高了效率。 返回结果最后返回valid[s.length()]即整个字符串s是否可以被成功拆分。
示例
假设s leetcodewordDict [leet, code]该函数将返回true因为可以将s拆分成leet和code这两个单词都在字典中。
这段代码通过动态规划有效地解决了单词拆分问题具有较好的时间和空间效率。
方法二
// 另一种思路的背包算法
class Solution {public boolean wordBreak(String s, ListString wordDict) {boolean[] dp new boolean[s.length() 1];dp[0] true;for (int i 1; i s.length(); i) {for (String word : wordDict) {int len word.length();if (i len dp[i - len] word.equals(s.substring(i - len, i))) {dp[i] true;break;}}}return dp[s.length()];}
}这段代码同样采用动态规划的思路来解决“单词拆分”问题但实现方式稍有不同具体解析如下
算法思路 初始化创建一个布尔型数组dp长度为s.length() 1其中dp[i]表示字符串s的前i个字符组成的子串是否能被字典中的单词组合覆盖。初始化dp[0] true表示空字符串是可以被任何词典中的单词组合覆盖的。 双重循环遍历 外层循环从1遍历到s.length()用i表示当前考虑的子串的结束位置。内层循环遍历字典wordDict中的每个单词word。 计算当前单词的长度len。判断当前子串的起始位置是否允许截取长度为len的子串即i len同时检查前len个字符组成的子串即s.substring(i - len, i)是否与当前单词相等并且这个子串的前一个位置的子串是否能被词典中的单词组合覆盖即dp[i - len]为true。如果上述条件满足说明找到了一个匹配的单词可以将当前位置i标记为true并跳出内层循环因为一旦找到一个合法的拆分方式就没有必要继续检查当前i的其他单词了利用了“一旦满足条件即可结束”的剪枝优化。 返回结果最后返回dp[s.length()]表示整个字符串s是否可以被字典中的单词组合覆盖。
优势与特点
剪枝优化通过在找到符合条件的单词后立即中断内层循环减少了不必要的循环次数提高了算法效率。直观易懂代码直接体现了对每个子串尝试匹配字典中单词的过程逻辑较为直观。空间效率此方法仅使用了一个长度等于字符串长度加一的布尔数组空间复杂度为O(n)其中n为字符串s的长度与题目给定的字典大小无关较为高效。
综上所述这是一种有效且易于理解的动态规划解法适用于解决给定字符串是否能被字典中的单词拆分的问题。
方法三
// 回溯法记忆化
class Solution {private SetString set;private int[] memo;public boolean wordBreak(String s, ListString wordDict) {memo new int[s.length()];set new HashSet(wordDict);return backtracking(s, 0);}public boolean backtracking(String s, int startIndex) {// System.out.println(startIndex);if (startIndex s.length()) {return true;}if (memo[startIndex] -1) {return false;}for (int i startIndex; i s.length(); i) {String sub s.substring(startIndex, i 1);// 拆分出来的单词无法匹配if (!set.contains(sub)) {continue; }boolean res backtracking(s, i 1);if (res) return true;}// 这里是关键找遍了startIndex~s.length()也没能完全匹配标记从startIndex开始不能找到memo[startIndex] -1;return false;}
}这段代码提供了一个使用回溯法加记忆化的解决方案来解决“单词拆分”问题。给定一个字符串s和一个单词字典wordDict判断字符串s是否可以被空格拆分成一个或多个字典中的单词。以下是代码的详细解析
类成员变量
set: 存储字典wordDict中的所有单词使用HashSet以支持快速查找。memo: 记忆化数组用于存储字符串s的各个起始位置是否能够被拆分成字典中的单词。初始化为整型数组长度与s相同初始值默认为0-1表示从该位置开始的子串不能被拆分。
方法解析
wordBreak 方法
初始化memo数组和set集合。调用backtracking方法从字符串的起始位置开始尝试拆分。
backtracking 方法 参数: s: 输入字符串。startIndex: 当前开始拆分的位置索引。 目的: 递归地尝试从startIndex开始的子串是否能被拆分成字典中的单词。 逻辑: 基础情况如果startIndex等于字符串长度说明已经成功拆分到末尾返回true。记忆化检查如果memo[startIndex]为-1说明从startIndex开始的子串已经被探索过且不可拆分直接返回false。遍历从startIndex到字符串结尾逐步尝试截取子串并检查该子串是否在字典中。 如果子串在字典中递归调用backtracking(s, i 1)尝试剩余部分能否拆分。如果剩余部分可以被拆分则当前子串也能被拆分返回true。 回溯如果所有尝试都无法成功拆分标记memo[startIndex] -1表示从这个位置开始的子串不能被拆分然后返回false。
关键点
记忆化搜索通过memo数组避免重复计算提高效率。回溯在尝试失败后记录失败信息防止同一子问题的重复探索。
这种方法在处理较长字符串和较大字典时相较于简单的递归或暴力搜索能显著提升效率但消耗的空间也会相应增加主要是由于记忆化数组的使用。
