【代码随想录】刷题笔记Day42
前言
- 这两天机器狗终于搞定了,一个控制ROS大佬,一个计院编程大佬,竟然真把创新点这个弄出来了,牛牛牛牛(菜鸡我只能负责在旁边喊加油)。下午翘了自辩课来刷题,这次应该是元旦前最后一刷了,下午尽量刷多点吧(活就是2024再说嘿嘿)~
96. 不同的二叉搜索树 - 力扣(LeetCode)
- 这一题最难的还是找规律,和整数拆分类似,DST定头节点后,左边是小的DST,右边是大的DST,所以可能数是左右可能数相乘
- dp含义:dp[i] : 1到i为节点组成的二叉搜索树的个数为dp[i]
- 递推公式:dp[i] += dp[j] * dp[i - j - 1](j从0开始)
- 初始化:dp[0] = dp[1] = 1,从前往后遍历

-
class Solution { public:int numTrees(int n) {vector<int> dp(20);dp[0] = 1;dp[1] = 1;for(int i = 2; i < dp.size(); i++){for(int j = 0; j < i; j++){dp[i] += dp[j] * dp[i - j - 1];}}return dp[n];} };
01背包问题理论基础(二维数组)
- 问题定义
- 有限个物体(都只有一个),有大小和价值,放进固定容量的背包里如何放是最大价值,暴力算的话时间复杂度为2^n(每件物品状态01),需要用动态规划,刚开始看有点懵,但是结合算法图解看很好懂

- dp数组含义
- dp[i][j] 表示从下标为[0-i]的物品里任意取,放进容量为j的背包,价值总和最大是多少

- 递推公式
- dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

- 初始化
- 第一行初始化从能装开始放value[0],第一列and其它全初始化为0

- 遍历顺序
- 两层for循环,按行先遍历物品再遍历背包(反过来其实也行)
- →↓ 或 ↓→(前者好理解一些)
-
void test_2_wei_bag_problem1() {vector<int> weight = {1, 3, 4};vector<int> value = {15, 20, 30};int bagweight = 4;// 二维数组vector<vector<int>> dp(weight.size(), vector<int>(bagweight + 1, 0));// 初始化for (int j = weight[0]; j <= bagweight; j++) {dp[0][j] = value[0];}// weight数组的大小 就是物品个数for(int i = 1; i < weight.size(); i++) { // 遍历物品for(int j = 0; j <= bagweight; j++) { // 遍历背包容量if (j < weight[i]) dp[i][j] = dp[i - 1][j];else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);}}cout << dp[weight.size() - 1][bagweight] << endl; }int main() {test_2_wei_bag_problem1(); }
01背包问题理论基础(滚动数组)
- 和二维数组比,一维只要更新一行就行,但是遍历顺序要从后往前(用没更新d[j])
- dp数组含义
- dp[j]表示:容量为j的背包,所背的物品价值可以最大为dp[j]
- 递推公式
- dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
- 初始化
- 全初始为0,保证用没放物品的值进行更新最大值
- 遍历顺序
- 倒序遍历:本质上还是一个对二维数组的遍历,并且右下角的值依赖上一层左上角的值,因此需要保证左边的值仍然是上一层的,从右向左覆盖

-
void test_1_wei_bag_problem() {vector<int> weight = {1, 3, 4};vector<int> value = {15, 20, 30};int bagWeight = 4;// 初始化vector<int> dp(bagWeight + 1, 0);for(int i = 0; i < weight.size(); i++) { // 遍历物品for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);}}cout << dp[bagWeight] << endl; }int main() {test_1_wei_bag_problem(); }
后言
- 正式开始放假!有什么事2024再说!晚上看晚会去咯!看能不能抽到遥遥领先!

相关文章:
【代码随想录】刷题笔记Day42
前言 这两天机器狗终于搞定了,一个控制ROS大佬,一个计院编程大佬,竟然真把创新点这个弄出来了,牛牛牛牛(菜鸡我只能负责在旁边喊加油)。下午翘了自辩课来刷题,这次应该是元旦前最后一刷了&…...
数据库云平台新数科技完成B轮融资,打造全链路智能化数据库云平台
数据库云平台软件厂商「北京新数科技有限公司」(以下简称「新数科技」)已于2023年完成B1轮和B2轮融资,分别由渤海创富和彬复资本投资;义柏资本担任本轮融资独家财务顾问。 新数科技成立于2014年,当前产品矩阵包括数据库…...
【Linux 内核源码分析】Linux内核通知链机制
Linux内核通知链(notifier chain)是一种机制,用于实现内核中的事件通知和处理。它提供了一种灵活的方式,让不同的模块可以注册自己感兴趣的事件,并在事件发生时接收到通知。 通知链由一个或多个注册在其中的回调函数组…...
2023年度回顾:怿星科技的转型与创新
岁月不居,时节如流。随着2023年的落幕,怿星科技在这一年中不仅实现了自身的转型,还在技术创新、产品研发、行业合作和人才培养等方面取得了显著的成就。这一年,怿星科技正式完成了从服务型公司向产品型公司的战略转变,…...
STM32MP157D-DK1 Qt程序交叉编译与运行测试
上篇文章介绍了STM32MP157D-DK1开发板Qt镜像的构建,通过在Ubuntu中重新编译带有Qt功能的系统来实现。 本篇在上篇的基础上,继续搭建Qt的交叉编译环境,实现Qt程序在Ubuntu中编译,在STM32MP157板子中运行。 1 编译安装SDK 在上篇…...
Rancher 单节点 docker 部署备份与恢复
Rancher 单节点 docker 部署备份与恢复 1. 备份集群 获取 rancher server 容器名,本例为 angry_aryabhata docker ps | grep rancher/rancher6a27b8634c80 rancher/rancher:v2.5.14 xxx angry_aryabhata停止容器 docker stop angry_aryabhata创建备…...
WPF容器的背景对鼠标事件的影响
背景:在实现鼠标拖动窗口的过程中发现对父容器设置了鼠标拖动窗口的事件MouseLeftButtonDown private void DragWindow(object sender, MouseButtonEventArgs e) {if (e.LeftButton MouseButtonState.Pressed)DragMove(); } 问题:非常困惑的是&#x…...
pve虚拟机无法开机‘ha-manager set vm:101 --state started‘ failed: exit code 255
pve虚拟机无法开机,提示 ha-manager set vm:101 --state started failed: exit code 255 () Requesting HA start for VM 101 service vm:101 in error state, must be disabled and fixed first TASK ERROR: command ha-manager set vm:101 --state started fail…...
官宣!亚信安全TrustOne实力代言“中国新一代终端安全”
近日,IDC《中国新一代终端安全市场洞察,2023——安全防御的“最前线”》发布,正式定义了“中国新一代终端安全”的技术概念、技术演进和技术特点。该报告基于大量市场调研和数据分析,深入阐释了中国终端安全市场现状及面临的困局&…...
Text visualization : pipeline,wordle,phrase net,word tree
Text visualization(文本可视化)是一种将文本数据转换为可视形式的技术,以便更好地理解和分析文本内容。以下是可能会涉及的几个知识点: 1. Pipeline(流程图):Pipeline是指将文本可视化的过程划…...
C# WPF上位机开发(报表导出)
【 声明:版权所有,欢迎转载,请勿用于商业用途。 联系信箱:feixiaoxing 163.com】 对于在工厂上班的小伙伴来说,导出生产数据、生成报表,这是很习以为常的一个工作。之前的文章中,虽然我们也介绍…...
CentOS7安装部署Zookeeper
文章目录 CentOS7安装部署Zookeeper一、前言1.简介2.架构3.集群角色4.特点5.环境 二、正文1.部署服务器2.基础环境1)主机名2)Hosts文件3)关闭防火墙4)JDK 安装部署 3.单机部署1)下载和解压2)配置文件3&…...
OceanBase入选Gartner®云数据库管理系统魔力象限“荣誉提及”
近日,全球IT市场研究和咨询公司Gartner发布最新报告《Magic Quadrant™ for Cloud Database Management Systems》(全球云数据库管理系统魔力象限)。全自研分布式数据库 OceanBase 入选“荣誉提及”,2022 年推出的云数据库 OB Clo…...
Oracle 19C DBA管理常用命令
登入数据库主机,查看 CRS 资源状态: 集群资源启动完毕后,在任意一节点上利用crsctl查看集群状态。 查看:/u01/app/19c/grid/bin/crsctl status res -t 集群资源管理命令: 启动:/u01/app/19c/grid/bin/cr…...
BIO和NIO编程(待完善)
目录 IO模型 BIO NIO 常见问题 IO模型 Java共支持3种网络编程IO模式:BIO,NIO,AIO BIO 同步阻塞模型,一个客户端连接对应一个处理线程 代码示例: Server端: public class BioServer {private static …...
基于RocketMQ实现分布式事务
前言 在上一篇文章Spring Boot自动装配原理以及实践我们完成了服务通用日志监控组件的开发,确保每个服务都可以基于一个注解实现业务功能的监控。 而本文我们尝试基于RocketMQ实现下单的分布式的事务。可能会有读者会有疑问,之前我们不是基于Seata完成了…...
TikTok社会学:短视频如何塑造社会认知?
TikTok,作为一款全球性的短视频平台,正在深刻地影响着用户的社会认知。在这个数字时代,短视频不仅仅是娱乐的载体,更是塑造和反映社会认知的一面镜子。本文将深入探讨TikTok是如何通过短视频影响社会认知,以及这种影响…...
小秋SLAM入门实战深度学习所有文章汇总
如何用python代码实现虚拟拖拽 MediaPipe Losses 损失函数 深度学习激活函数Activation Functions 【深度学习Regularization正则化】 深度学习: 数据扩充 (Data Augmentation) 【keras-yolo3】 【YOLO源码解读】 caffe源码解读系列 Python中的异常处理 精确率、精度ÿ…...
linux搭建git仓库
git安装与配置 # git安装 yum install -y git# git配置(以下为root用户下配置) # 添加git组 groupadd git# 添加账号、密码(账号zdtest可根据自己需求修改) useradd zdtest -g git passwd zdtest创建远程仓库(linux端) 创建个人文件夹 mkdir -p /home/data/zdtestcd /home/d…...
19. Mysql 循环语句
文章目录 概念循环语句while 循环语句repeat 循环语句loop 循环语句iterate 和 leave 语句 精选示例总结参考资料 概念 循环结构是编程中常见的控制结构,它允许我们重复执行一段代码,直到满足特定条件为止。 在 Mysql 中,常用来实现各种复杂…...
论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(二)
HoST框架核心实现方法详解 - 论文深度解读(第二部分) 《Learning Humanoid Standing-up Control across Diverse Postures》 系列文章: 论文深度解读 + 算法与代码分析(二) 作者机构: 上海AI Lab, 上海交通大学, 香港大学, 浙江大学, 香港中文大学 论文主题: 人形机器人…...
日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする
日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする 1、前言(1)情况说明(2)工程师的信仰2、知识点(1) にする1,接续:名词+にする2,接续:疑问词+にする3,(A)は(B)にする。(2)復習:(1)复习句子(2)ために & ように(3)そう(4)にする3、…...
汽车生产虚拟实训中的技能提升与生产优化
在制造业蓬勃发展的大背景下,虚拟教学实训宛如一颗璀璨的新星,正发挥着不可或缺且日益凸显的关键作用,源源不断地为企业的稳健前行与创新发展注入磅礴强大的动力。就以汽车制造企业这一极具代表性的行业主体为例,汽车生产线上各类…...
(转)什么是DockerCompose?它有什么作用?
一、什么是DockerCompose? DockerCompose可以基于Compose文件帮我们快速的部署分布式应用,而无需手动一个个创建和运行容器。 Compose文件是一个文本文件,通过指令定义集群中的每个容器如何运行。 DockerCompose就是把DockerFile转换成指令去运行。 …...
GC1808高性能24位立体声音频ADC芯片解析
1. 芯片概述 GC1808是一款24位立体声音频模数转换器(ADC),支持8kHz~96kHz采样率,集成Δ-Σ调制器、数字抗混叠滤波器和高通滤波器,适用于高保真音频采集场景。 2. 核心特性 高精度:24位分辨率,…...
以光量子为例,详解量子获取方式
光量子技术获取量子比特可在室温下进行。该方式有望通过与名为硅光子学(silicon photonics)的光波导(optical waveguide)芯片制造技术和光纤等光通信技术相结合来实现量子计算机。量子力学中,光既是波又是粒子。光子本…...
用 Rust 重写 Linux 内核模块实战:迈向安全内核的新篇章
用 Rust 重写 Linux 内核模块实战:迈向安全内核的新篇章 摘要: 操作系统内核的安全性、稳定性至关重要。传统 Linux 内核模块开发长期依赖于 C 语言,受限于 C 语言本身的内存安全和并发安全问题,开发复杂模块极易引入难以…...
【动态规划】B4336 [中山市赛 2023] 永别|普及+
B4336 [中山市赛 2023] 永别 题目描述 你做了一个梦,梦里有一个字符串,这个字符串无论正着读还是倒着读都是一样的,例如: a b c b a \tt abcba abcba 就符合这个条件。 但是你醒来时不记得梦中的字符串是什么,只记得…...
Ubuntu 可执行程序自启动方法
使用 autostart(适用于桌面环境) 适用于 GNOME/KDE 桌面环境(如 Ubuntu 图形界面) 1. 创建 .desktop 文件 sudo vi ~/.config/autostart/my_laser.desktop[Desktop Entry] TypeApplication NameMy Laser Program Execbash -c &…...
Python[数据结构及算法 --- 栈]
一.栈的概念 在 Python 中,栈(Stack)是一种 “ 后进先出(LIFO)”的数据结构,仅允许在栈顶进行插入(push)和删除(pop)操作。 二.栈的抽象数据类型 1.抽象数…...
