怎么做优惠券网站seo还可以做哪些推广

怎么做优惠券网站,seo还可以做哪些推广,哪家公司做网站最好,创建公司网站 优帮云322.零钱兑换 文章讲解/视频讲解 题目描述#xff1a; 给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额#xff0c;返回 -1。 你可以认为每种硬币的数量是无限的。 示例 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示例 4输入coins [1], amount 1输出1示例 5输入coins [1], amount 2输出2提示1 coins.length 121 coins[i] 2^31 - 10 amount 10^4思路本题描述里提到了每种硬币都是无限的所以是典型的完全背包问题直接动规五部曲1.dp数组及其下标的含义dp[j]代表总金额j所需钱币最少数量为dp[j]2.确定递推公式凑足总额为j - coins[i]的最少个数为dp[j - coins[i]]那么只需要加上一个钱币coins[i]即dp[j - coins[i]] 1就是dp[j]所以递推公式就是dp[j] mindp[j - coins[i]] 1, dp[j]3.dp数组如何初始化首先dp[0]就得等于0其次就是其他非零下标都得赋值为正无穷因为dp公式是靠min不断更新正无穷是为了防止在比较的过程中dp[j]被初始值覆盖。4.确定遍历顺序昨天我们写了求组合的还写了求排列的这俩遍历顺序是有讲究的组合是外物品内背包排列是外背包内物品。但是本题只是求最少几枚币两个哪个都不算所以用哪个都可以都是对的5.举例推导dp数组以输入coins [1, 2, 5], amount 5为例dp[amount]为最终结果。代码示例function coinChange(coins: number[], amount: number): number { const dp:number[] new Array(amount 1).fill(Infinity) dp[0] 0 for(let i 0; i coins.length; i){ for(let j coins[i]; j amount; j){ if(dp[j - coins[i]] Infinity) continue dp[j] Math.min(dp[j], dp[j - coins[i]] 1) } } return dp[amount] Infinity ? -1 : dp[amount] };279.完全平方数文章讲解/视频讲解题目描述给定正整数 n找到若干个完全平方数比如 1, 4, 9, 16, ...使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。给你一个整数 n 返回和为 n 的完全平方数的 最少数量 。完全平方数 是一个整数其值等于另一个整数的平方换句话说其值等于一个整数自乘的积。例如1、4、9 和 16 都是完全平方数而 3 和 11 不是。示例 1输入n 12输出3解释12 4 4 4示例 2输入n 13输出2解释13 4 9提示1 n 10^4思路本题跟上题基本没啥区别乍看感觉挺麻烦的但是其实翻译一下完全平方数就是物品还是无限用的正整数n就是背包容量问凑满这个背包容量为n的背包需要多少个物品完全平方数。1.确定dp数组及其下标的含义dp[j]代表和为j的正整数最少需要dp[j]个完全平方数2.确定递推公式和上题保持一致dp[j] mindp[j - coins[i]] 1, dp[j]原因都是一样一样的把钱币替换成完全平方数就是了3.dp数组的初始化依旧是dp[0] 0其他非零下标要初始化为正无穷原因同上4.确定遍历顺序这个也是一样的本题求的只是最少用几个完全平方数没问有几种所以先遍历物品还是先遍历背包都是一样的上题先遍历物品这题就先遍历背包了5.举例推导dp数组已输入n为5例dp状态图如下dp[0] 0 dp[1] min(dp[0] 1) 1 dp[2] min(dp[1] 1) 2 dp[3] min(dp[2] 1) 3 dp[4] min(dp[3] 1, dp[0] 1) 1 dp[5] min(dp[4] 1, dp[1] 1) 2最后的dp[n]为最终结果。代码示例function numSquares(n: number): number { const dp:number[] new Array(n 1).fill(Infinity) dp[0] 0 for(let i 1; i n; i){ for(let j 1; j * j i; j){ dp[i] Math.min(dp[i], dp[i - j * j] 1) } } return dp[n] };139.单词拆分文章讲解/视频讲解题目描述给定一个非空字符串 s 和一个包含非空单词的列表 wordDict判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。说明拆分时可以重复使用字典中的单词。你可以假设字典中没有重复的单词。示例 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思路单词就是物品字符串s就是背包问我们能不能用物品单词装满背包字符串s单词是可以重复使用的毫无疑问的完全背包。1.dp数组及其下标含义dp[i]为true表示长度为i的字符串可以被拆封成一个或者多个单词换句话就说字符串s的前i个字符是否能被拆分2.确定递推公式切割的范围是[ji]我们要确保[j,i]切割出来是个单词还得确保dp[j] true字符串前j个字符可以被拆分成单词只有两个条件都满足我们才把当前dp[i]修改为true递推公式为if([j, i] 这个区间的子串出现在字典里 dp[j]是true) 那么 dp[i] true。3.dp数组如何初始化dp[0]是整个遍历过程的基石也是遍历的开始如果dp[0]为false后续所有的dp[i]都不可能为true因为满足不了“dp[j]是true”这个关键条件。所以dp[0]一定要初始化为true其他非零下标初始化为false即可4.确定遍历顺序又要开始讨论本题到底是组合还是排列问题了我们来回顾一下组合和排列以1,5和5,1为例这两个算一个组合但是算两种排列。而本题是排列问题拿 s applepenapple, wordDict [apple, pen] 举例。apple, pen 是物品那么我们要求 物品的组合一定是 apple pen apple 才能组成 applepenapple。apple apple pen 或者 pen apple apple 是不可以的那么我们就是强调物品之间顺序。强调物品顺序正是排列的重要特征所以本题的遍历顺序是外层遍历背包容量内层遍历物品5.举例推导dp[i]以输入: s leetcode, wordDict [leet, code]为例dp状态如图dp[s.size()]就是最终结果。代码示例function wordBreak(s: string, wordDict: string[]): boolean { const dp:boolean[] new Array(s.length 1).fill(false) dp[0] true for(let i 1; i s.length; i){ for(let j 0; j i; j){ let temp:string s.slice(j,i) if(wordDict.includes(temp) dp[j] true){ dp[i] true } } } return dp[s.length] };