【代码随想录】刷题笔记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 中,常用来实现各种复杂…...

idea大量爆红问题解决
问题描述 在学习和工作中,idea是程序员不可缺少的一个工具,但是突然在有些时候就会出现大量爆红的问题,发现无法跳转,无论是关机重启或者是替换root都无法解决 就是如上所展示的问题,但是程序依然可以启动。 问题解决…...
在 Nginx Stream 层“改写”MQTT ngx_stream_mqtt_filter_module
1、为什么要修改 CONNECT 报文? 多租户隔离:自动为接入设备追加租户前缀,后端按 ClientID 拆分队列。零代码鉴权:将入站用户名替换为 OAuth Access-Token,后端 Broker 统一校验。灰度发布:根据 IP/地理位写…...

HBuilderX安装(uni-app和小程序开发)
下载HBuilderX 访问官方网站:https://www.dcloud.io/hbuilderx.html 根据您的操作系统选择合适版本: Windows版(推荐下载标准版) Windows系统安装步骤 运行安装程序: 双击下载的.exe安装文件 如果出现安全提示&…...
解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错
出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上,所以报错,到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本,cu、torch、cp 的版本一定要对…...

学习STC51单片机32(芯片为STC89C52RCRC)OLED显示屏2
每日一言 今天的每一份坚持,都是在为未来积攒底气。 案例:OLED显示一个A 这边观察到一个点,怎么雪花了就是都是乱七八糟的占满了屏幕。。 解释 : 如果代码里信号切换太快(比如 SDA 刚变,SCL 立刻变&#…...
Python ROS2【机器人中间件框架】 简介
销量过万TEEIS德国护膝夏天用薄款 优惠券冠生园 百花蜂蜜428g 挤压瓶纯蜂蜜巨奇严选 鞋子除臭剂360ml 多芬身体磨砂膏280g健70%-75%酒精消毒棉片湿巾1418cm 80片/袋3袋大包清洁食品用消毒 优惠券AIMORNY52朵红玫瑰永生香皂花同城配送非鲜花七夕情人节生日礼物送女友 热卖妙洁棉…...

Docker 本地安装 mysql 数据库
Docker: Accelerated Container Application Development 下载对应操作系统版本的 docker ;并安装。 基础操作不再赘述。 打开 macOS 终端,开始 docker 安装mysql之旅 第一步 docker search mysql 》〉docker search mysql NAME DE…...
iOS性能调优实战:借助克魔(KeyMob)与常用工具深度洞察App瓶颈
在日常iOS开发过程中,性能问题往往是最令人头疼的一类Bug。尤其是在App上线前的压测阶段或是处理用户反馈的高发期,开发者往往需要面对卡顿、崩溃、能耗异常、日志混乱等一系列问题。这些问题表面上看似偶发,但背后往往隐藏着系统资源调度不当…...

C++:多态机制详解
目录 一. 多态的概念 1.静态多态(编译时多态) 二.动态多态的定义及实现 1.多态的构成条件 2.虚函数 3.虚函数的重写/覆盖 4.虚函数重写的一些其他问题 1).协变 2).析构函数的重写 5.override 和 final关键字 1&#…...

基于SpringBoot在线拍卖系统的设计和实现
摘 要 随着社会的发展,社会的各行各业都在利用信息化时代的优势。计算机的优势和普及使得各种信息系统的开发成为必需。 在线拍卖系统,主要的模块包括管理员;首页、个人中心、用户管理、商品类型管理、拍卖商品管理、历史竞拍管理、竞拍订单…...