当前位置: 首页 > news >正文

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

LeetCode/卡码网题目:

  • 46. 携带研究材料(第六期模拟笔试)
  • 416. 分割等和子集
  • 2962. 统计最大元素出现至少 K 次的子数组(每日一题4.29)

其他:

今日总结
往期打卡


46. 携带研究材料(第六期模拟笔试)

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

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

问题:

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

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

思路:

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

复杂度:

  • 时间复杂度: O ( n m ) O(nm) O(nm)
  • 空间复杂度: O ( n m ) 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 ( n m ) O(nm) O(nm)
  • 空间复杂度: O ( n ) O(n) 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^2) O(n2)
  • 空间复杂度: O ( n ) O(n) 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(n) O(n)
  • 空间复杂度: O ( 1 ) O(1) 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;}
}

总结

学习了动态规划背包问题

往期打卡

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

http://www.xdnf.cn/news/238411.html

相关文章:

  • 【mysql】执行过程,背诵版
  • 2025平航杯—团队赛
  • 企业的呼入语音智能体是什么样子?
  • 启动Hadoop集群及集群效果
  • 企业数字化转型新动向日渐明鲜,当以“AI为中心”而驱动
  • 分治算法求序列中第K小数
  • RAII 示例
  • 2025-03 机器人等级考试四级理论真题 4级
  • Dify添加ollama模型失败:NewConnectionError: Failed to establish a new connection
  • MCP与开源社区的共赢之道:携手推动技术创新
  • GRE隧道
  • Git Stash 详解
  • windows系统常用快捷键(CMD常用命令,DOS常用命令)
  • C++类和对象(中)
  • PostgreSQL中的SSL
  • 设备目录树--个人笔记
  • linux中sigint和sigterm的区别
  • react-11使用vscode开发react相关扩展插件(相关的快捷生成)
  • 开芯课堂丨视觉与4D毫米波前融合感知算法设计
  • [计算机科学#6]:从锁存器到内存,计算机存储的构建与原理
  • 航电系统之网络控制运动技术篇
  • C++Primerplus编程练习 第三章
  • Vue3源码学习-提交限制
  • 标准解读:数据要素安全可信流通技术标准【附全文阅读】
  • 驾驭音质,尽享四通道力量——AXPA17851
  • 若依定时任务
  • 【go】简单问答八股,go的理解,接口,锁,channel
  • 处理vue3热加载后axios的请求重复访问的问题
  • 深入理解C++17中的std::string_view
  • LibAI Lab走进西浦:重塑“AI+建筑”教育