自动生成网页的工具_电气网站模板_网络营销师官网_自己怎么做网址开网站

其他:

今日总结
往期打卡

---

46. 携带研究材料（第六期模拟笔试）

跳转: 46. 携带研究材料（第六期模拟笔试）

学习: 代码随想录公开讲解

问题:

小明是一位科学家，他需要参加一场重要的国际科学大会，以展示自己的最新研究成果。他需要带一些研究材料，但是他的行李箱空间有限。这些研究材料包括实验设备、文献资料和实验样本等等，它们各自占据不同的空间，并且具有不同的价值。

小明的行李空间为 N，问小明应该如何抉择，才能携带最大价值的研究材料，每种研究材料只能选择一次，并且只有选与不选两种选择，不能进行切割。

思路:

01背包问题,一般是各个遍历物品,基于上一个物品各容量的最大价值以及当前物品的花费与价值进行更新.
递推公式 :
$f[第n次选择][容量x]=Math.max(f[n-1次选择][容量x-当前选择物品的花费]+当前物品价值,f[第n次选择][容量x])$
对各个物品的遍历顺序没有要求,所以直接写成递推即可.
遍历顺序:
如果用二维数组,那么无所谓.
因为是由上一个物品递推而来,可以优化成滚动数组,这时为了保证是根据上次选择更新,必须从大容量开始倒叙遍历背包容量.

复杂度:

• 时间复杂度: $O(nm)$
• 空间复杂度: $O(nm)$

代码(递推):

import java.util.Scanner;class Main{public static void main(String[] args) {Scanner sc = new Scanner(System.in);int m = sc.nextInt();int n = sc.nextInt();int[] w = new int[m];int[] v = new int[m];for(int i=0;i<m;i++){w[i] = sc.nextInt();}for(int i=0;i<m;i++){v[i] = sc.nextInt();}int[][] dp = new int[m][n+1];for(int i=w[0];i<=n;i++){dp[0][i] = v[0];}for(int i=1;i<m;i++){for(int j=n;j>=0;j--){if(j>=w[i])dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);else dp[i][j] = dp[i-1][j];}}System.out.println(dp[m-1][n]);}
}

复杂度:

• 时间复杂度: $O(nm)$
• 空间复杂度: $O(n)$

代码(滚动数组优化):

import java.util.Scanner;class Main{public static void main(String[] args) {Scanner sc = new Scanner(System.in);int m = sc.nextInt();int n = sc.nextInt();int[] w = new int[m];int[] v = new int[m];for(int i=0;i<m;i++){w[i] = sc.nextInt();}for(int i=0;i<m;i++){v[i] = sc.nextInt();}int[] dp = new int[n+1];for(int i=w[0];i<=n;i++){dp[i] = v[0];}for(int i=1;i<m;i++){for(int j=n;j>=0;j--){if(j>=w[i])dp[j] = Math.max(dp[j],dp[j-w[i]]+v[i]);else dp[j] = dp[j];}}System.out.println(dp[n]);}
}

---

416. 分割等和子集

跳转: 416. 分割等和子集

学习: 代码随想录公开讲解

问题:

给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

思路:

这题可以看作是n个物品,花费和重量相等
判断容量为sum/2的背包是否装满,只需要看最大价值是不是sum/2即可

复杂度:

• 时间复杂度: $O(n^2)$
• 空间复杂度: $O(n)$

代码:

class Solution {public boolean canPartition(int[] nums) {int sum = 0;for(int i:nums){sum+=i;}if(sum%2==1) return false;sum/=2;int n = nums.length;int[] dp = new int[sum+1];for(int i=nums[0];i<=sum;i++){dp[i] = nums[0];}for(int i=1;i<n;i++){for(int j=sum;j>=0;j--){if(j>=nums[i])dp[j] = Math.max(dp[j],dp[j-nums[i]]+nums[i]);else dp[j] = dp[j];}}if(dp[sum]==sum) return true;return false;}
}

---

2962. 统计最大元素出现至少 K 次的子数组(每日一题4.29)

跳转: 2962. 统计最大元素出现至少 K 次的子数组

问题:

给你一个整数数组 nums 和一个 正整数 k 。

请你统计有多少满足 「 nums 中的 最大 元素」至少出现 k 次的子数组，并返回满足这一条件的子数组的数目。

子数组是数组中的一个连续元素序列。

思路:

遍历尾部,滑动窗口,如果最大元素出现了k次,收缩滑块.
对于每个尾部的位置,加上正好k次的前缀数

复杂度:

• 时间复杂度: $O(n)$
• 空间复杂度: $O(1)$

代码:

class Solution {public long countSubarrays(int[] nums, int k) {int count = 0;long ans = 0; int i=0;int max = 0;for (int x : nums) {max = Math.max(max, x);}for(int j=0;j<nums.length;j++){if(nums[j]==max) count++;while(count==k){if(nums[i]==max)count--;i++;}ans+=i;}return ans;}
}

---

总结

学习了动态规划背包问题

往期打卡

代码随想录算法训练营第二十九天

代码随想录算法训练营第二十八天

代码随想录算法训练营第二十七天(补)

代码随想录算法训练营第二十六天

代码随想录算法训练营第二十五天

代码随想录算法训练营第二十四天

代码随想录算法训练营第二十三天

代码随想录算法训练营周末四

代码随想录算法训练营第二十二天(补)

代码随想录算法训练营第二十一天

代码随想录算法训练营第二十天

代码随想录算法训练营第十九天

代码随想录算法训练营第十八天

代码随想录算法训练营第十七天

代码随想录算法训练营周末三

代码随想录算法训练营第十六天

代码随想录算法训练营第十五天

代码随想录算法训练营第十四天

代码随想录算法训练营第十三天

代码随想录算法训练营第十二天

代码随想录算法训练营第十一天

代码随想录算法训练营周末二

代码随想录算法训练营第十天

代码随想录算法训练营第九天

代码随想录算法训练营第八天

代码随想录算法训练营第七天

代码随想录算法训练营第六天

代码随想录算法训练营第五天

代码随想录算法训练营周末一

代码随想录算法训练营第四天

代码随想录算法训练营第三天

代码随想录算法训练营第二天

代码随想录算法训练营第一天