哪个网站是专门做封面素材,网络公司网站asp,网站开发具体是干什么的,网站运营课程一、贪心算法理论基础
在问题的每个决策阶段#xff0c;都选择当前看起来最优的选择#xff0c;即贪心地做出局部最优的决策#xff0c;以期获得全局最优解。
最好用的策略就是举反例#xff0c;如果想不到反例#xff0c;那么就试一试贪心吧。
动态规划和贪心的区别
…一、贪心算法理论基础
在问题的每个决策阶段都选择当前看起来最优的选择即贪心地做出局部最优的决策以期获得全局最优解。
最好用的策略就是举反例如果想不到反例那么就试一试贪心吧。
动态规划和贪心的区别
动态规划会根据之前阶段的所有决策来考虑当前决策并使用过去子问题的解来构建当前子问题的解。贪心算法不会考虑过去的决策而是一路向前地进行贪心选择不断缩小问题范围直至问题被解决。
二、分发饼干
class Solution {public int findContentChildren(int[] g, int[] s) {//先排序形成升序数组Arrays.sort(g);Arrays.sort(s);int m g.length, n s.length;int count 0;for(int i 0, j 0; i m j n; i,j){//当前饼干无法满足孩子胃口饼干大小递增while(j n g[i] s[j]){j;}// g[i] s[j]表示饼干能满足孩子胃口if(j n){count;}}return count;}
}三、摆动序列
在循环遍历数组nums的过程中我们通过比较当前数字和前一个数字的大小关系来确定当前位置是上升摆动还是下降摆动。
如果当前数字大于前一个数字说明出现了上升摆动。我们更新up的值为down 1表示当前位置上升摆动序列的最大长度因为上升摆动的前一个数字应该是下降摆动序列的最大长度。如果当前数字小于前一个数字说明出现了下降摆动。我们更新down的值为up 1表示当前位置下降摆动序列的最大长度因为下降摆动的前一个数字应该是上升摆动序列的最大长度。
通过不断更新up和down我们可以找到整个数字序列中的最长摆动子序列的长度。
最后返回down和up中的最大值即为最长摆动子序列的长度。
ps这里的上升和下降其实针对的是序列的尾部两个元素来说的之前的元素一定都是摆动的序列
class Solution {public int wiggleMaxLength(int[] nums) {
//up 和 down 初始化为1因为一旦找到上升或下降序列一定是两个元素1刚好为2int down 1, up 1;
//for (int i 1; i nums.length; i) {if (nums[i] nums[i - 1])up down 1;else if (nums[i] nums[i - 1])down up 1;}return nums.length 0 ? 0 : Math.max(down, up);}
}四、最大子序和
public class Solution {public int maxSubArray(int[] nums) {int len nums.length;
// 1.dp[i] (对应子问题的解) 表示以 nums[i] 结尾的连续子数组的最大和int[] dp new int[len];dp[0] nums[0]; //2.初始状态for (int i 1; i len; i) {if (dp[i - 1] 0) {dp[i] dp[i - 1] nums[i];//3.状态转移方程} else {dp[i] nums[i];//3.状态转移方程}}// 也可以在上面遍历的同时求出 res 的最大值这里我们为了语义清晰分开写大家可以自行选择int res dp[0];for (int i 1; i len; i) {res Math.max(res, dp[i]);}return res;}
}五、零钱兑换(动态规划)
这个题在一定条件下可以使用贪心但是全部情况的还是要用动态规划做这个题体验动态规划和贪心算法的区别
只问最优值没要求最优解一般情况下可以使用动态规划解决
import java.util.Arrays;public class Solution {public int coinChange(int[] coins, int amount) {
// 给 0 占位因为索引从0开始所以dp[amount]对应长度为amount 1
//用于存储凑齐每个金额所需的最少硬币数量int[] dp new int[amount 1];// 注意因为要比较的是最小值这个不可能的值就得赋值成为一个最大值(amount 1)用于dp[i]表示无法凑齐对应金额。Arrays.fill(dp, amount 1);// 理解 dp[0] 0 的合理性单独一枚硬币如果能够凑出面值符合最优子结构
//将dp[0]初始化为0表示凑齐金额0所需的最少硬币数量为0。dp[0] 0;
//然后使用两个嵌套的循环进行动态规划计算。外层循环从1到amount遍历所有可能的金额。
//内层循环遍历硬币数组coins中的每个硬币判断是否可以使用当前硬币凑齐金额i。
//如果可以凑齐即i - coin 0并且凑齐i - coin金额所需的最少硬币数量不为amount 1表示可以凑齐则更新dp[i]为dp[i - coin]和dp[i]的较小值加1表示使用当前硬币后的最少硬币数量。通过上述循环我们得到了凑齐每个金额所需的最少硬币数量。for (int i 1; i amount; i) {for (int coin : coins) {if (i - coin 0 dp[i - coin] ! amount 1) {dp[i] Math.min(dp[i], 1 dp[i - coin]);}}}//最后判断dp[amount]是否等于amount 1如果等于则表示无法凑齐金额amount将其赋值为-1。if (dp[amount] amount 1) {dp[amount] -1;}
//返回dp[amount]作为结果即为凑齐金额amount所需的最少硬币数量如果无法凑齐则为-1。return dp[amount];}
}
