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

数据结构刷题(三十):96不同的二叉搜索树、01背包问题理论、416分割等和子集

一、96. 不同的二叉搜索树

1.这个题比较难想递推公式,

dp[3],就是元素1为头结点搜索树的数量 + 元素2为头结点BFS的数量 + 元素3为头结点BFS的数量

元素1为头结点搜索树的数量 = 右子树有2个元素的搜索树数量 * 左子树有0个元素的搜索树数量

元素2为头结点搜索树的数量 = 右子树有1个元素的搜索树数量 * 左子树有1个元素的搜索树数量

元素3为头结点搜索树的数量 = 右子树有0个元素的搜索树数量 * 左子树有2个元素的搜索树数量

用公式来说明就是

i>= 2, dp[i] += dp[p - 1] + dp[i - p]

2.需要注意dp数组的初始化

代码:

class Solution {public int numTrees(int n) {// 初始化int[] dp = new int[n + 1];// 分别初始化节点为0和1时的情况dp[0] = 1;dp[1] = 1;// 讨论j作为根结点时的情况 从左侧dp[0]到右侧dp[0]for (int i = 2; i <= n; i++) {for (int j = 1; j <= i; j++){//对于第i个节点,需要考虑1作为根节点直到i作为根节点的情况,所以需要累加dp[i] += dp[j - 1] * dp[i - j] ;}}return dp[n];}
}

二、01背包问题理论

 

dp[i][j]是在背包达到j重量时,任取0-i中任意多个物品,所达到的最大价值, 其中i代表物品,j代表背包容量; 现在需要放入i物品到背包中,需要对比不放物品i和放入物品i两种情况。

  • 不放物品i:直接就是dp[i-1][j]的最有情况
  • 放入物品i:确定放入i时,则整个物品集就被分成两部分,1到i-1和第i个,同时物品i会把j空间里的wi给占据了,只剩下j-wi的空间给前面i-1, 所以dp[i-1][j-weight[i]]的意思就是还没加上物品i的重量(weight[i])时的最大价值, 最后再加上i物品的价值

细节:1.当 j-weight【i】<0 时,数组会越界,要加个if j<weight【i】则 dp【i】【j】=dp【i-1】【j】;

2.初始化时,当背包容量j=0时,不论i等于几,都默认为0;而i=0时,可以根据物品i=0的重量设定初始值。

3.当dp是二维数组时,双层for循环是可以颠倒顺序的

三、01背包问题理论(二)

1.将二维数组转换成一维的滚动数组

2.dp[j]指的是容量为j时的最大价值

3.列表后面的值需要通过与前面的值(可能在第一次循环中就确定了dp[1]的值,只能使用倒序才能获取到最开始的dp[1],而不是使用正序去更新dp[1])比较确定,因此要先处理,所以在嵌套for循环需要使用倒序

四、416. 分割等和子集

1.使用01背包思想,以下四点是使用01背包解决这个题的要求:

  • 背包的体积为sum / 2。(已知体积)
  • 背包要放入的商品(集合里的元素)重量为元素的数值,价值也为元素的数值
  • 背包如果正好装满,说明找到了总和为 sum / 2 的子集。
  • 背包中每一个元素是不可重复放入。(满足01背包要求)

2.需要注意本题中的重量也就是价值这一说法

(1)01背包的递推公式为:dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

    本题,相当于背包里放入数值,那么物品i的重量是nums[i],其价值也是nums[i]。

(2)如果dp[j] == j 说明,集合中的子集总和正好可以凑成总和j

class Solution {public boolean canPartition(int[] nums) {if (nums.length == 0 && nums == null)return false;int n = nums.length;int sum = 0;for (int num : nums) {sum += num;}// 判断和是否为奇数if (sum % 2 == 1) return false;int target = sum / 2;// dp[j]表示 当背包重量为j时,所具有的最大价值(这个题价值也就是重量)int[] dp = new int[target + 1];for (int i = 0; i < n; i++) {for (int j = target; j >= nums[i]; j--){//物品 i 的重量是 nums[i],其价值也是 nums[i]dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);}}// 只需要对两个子集中的一个进行判断即可,return dp[target] == target;}
}

相关文章:

数据结构刷题(三十):96不同的二叉搜索树、01背包问题理论、416分割等和子集

一、96. 不同的二叉搜索树 1.这个题比较难想递推公式&#xff0c; dp[3]&#xff0c;就是元素1为头结点搜索树的数量 元素2为头结点BFS的数量 元素3为头结点BFS的数量 元素1为头结点搜索树的数量 右子树有2个元素的搜索树数量 * 左子树有0个元素的搜索树数量 元素2为头结…...

bash的进程与欢迎讯息自定义

在bash shell中,可以通过多种方式自定义欢迎讯息和提示符。主要有: 修改/etc/profile文件: 该文件在用户登录后执行,定义了PROMPT_COMMAND和PS1提示符。可以修改其内容实现自定义欢迎讯息和提示符。 例如,修改为: bash PROMPT_COMMANDecho -e "\nWelcome to My Bash She…...

本周大新闻|苹果首款MR没有主打卖点;Meta认为AI是AR OS的基础

​本周XR大新闻&#xff0c;AR方面&#xff0c;苹果首款MR或没有主打卖点&#xff0c;反而尽可能支持更多App和服务&#xff1b;扎克伯格表示基于AI的AR眼镜操作系统是下一代计算平台的基础&#xff1b;微软芯片工程VP Jean Boufarhat加入Meta芯片团队&#xff1b;Humane展示了…...

Java中工具类Arrays、Collections、Objects

Arrays Arrays是Java中提供的一个针对数组操作的工具类&#xff0c;所有的方法都是静态的。 大致有这些常用的方法 sort()针对常用的基本数据类型&#xff0c;都能进行排序&#xff0c;byte、char、int、long、float、doubleparallelSort()并行排序&#xff0c;多线程排序&am…...

Docker安装Nginx/Python/Golang/Vscode【亲测可用】

一、docker安装nginx docker安装nginx&#xff0c;安装的是最新版本的&#xff1a;docker pull nginx:latest 创建一个容器&#xff1a;docker run --name my-nginx -p 80:80 -d nginx:latest 开启一个交互模式终端&#xff1a;docker exec -it my-nginx bash 创建django项…...

蓝桥杯2022年第十三届决赛真题-最大数字

蓝桥杯2022年第十三届决赛真题-最大数字 时间限制: 3s 内存限制: 320MB 题目描述 给定一个正整数 N。你可以对 N 的任意一位数字执行任意次以下 2 种操作&#xff1a; 将该位数字加 1。如果该位数字已经是 9&#xff0c;加 1 之后变成 0。 将该位数字减 1。如果该位数字已经…...

smbms项目搭建

目录 1.搭建一个maven web项目 2.配置Tomcat 3.测试项目是否能够跑起来 4.导入项目中会遇到的Jar包 5.项目结构搭建 6.项目实体类搭建 7.编写基础公共类 1.数据库配置文件 2.编写数据库的公共类 3.编写字符编码过滤器 3.1web配置注册 4.导入静态资源 1.搭建一个maven web项目 …...

进程/线程 状态模型详解

前言&#xff1a;最近操作系统复习到线程的状态模型&#xff08;也可以说进程的状态模型&#xff0c;本文直接用线程来说&#xff09;时候&#xff0c;网上查阅资料&#xff0c;发现很多文章都说的很不一样&#xff0c;有五状态模型、六状态模型、七状态模型.......虽然都是对的…...

数据结构与算法之队列: Leetcode 621. 任务调度器 (Typescript版)

任务调度器 https://leetcode.cn/problems/task-scheduler/ 描述 给你一个用字符数组 tasks 表示的 CPU 需要执行的任务列表。其中每个字母表示一种不同种类的任务。任务可以以任意顺序执行&#xff0c;并且每个任务都可以在 1 个单位时间内执行完。在任何一个单位时间&#…...

【报错】arXiv上传文章出现XXX.sty not found

笔者在overleaf上编译文章一切正常&#xff0c;但上传文章到arxiv时出现类似于如下报错&#xff1a; 一般情况下观察arxiv的编译log&#xff0c;不通过的原因&#xff0c;很多时候都是由于某一行导入了啥package&#xff0c;引起的报错&#xff1b;但是如果没有任何一个具体的…...

项目合同管理

项目合同管理的基本概念及分类、项目合同签订、项目合同管理以及项目合同索赔处理等内容 信息系统工程的建设过程实际上就是合同的执行和监控的过程 1、项目合同的概念及分类 合同法律关系&#xff1a;权力和义务关系 合同可以是书面形式、口头形式和其他形式 书面形式是指…...

聊聊ClickHouse向量化执行引擎-过滤操作

俄罗斯Yandex开发的ClickHouse是一款性能黑马的OLAP数据库&#xff0c;其对SIMD的灵活运用给其带来了难以置信的性能。本文我们聊聊它如何对过滤操作进行SIMD优化。 基本思想 1、有一个数组data&#xff0c;即ColumnVector::data&#xff0c;存放数据 2、使用uint8类型&#xf…...

数据可视化第二版-拓展-网约车分析案例

文章目录 数据可视化第二版-拓展-网约车分析案例竞赛介绍 1等奖作品-IT从业者张某某的作品结论过程数据和思考数据处理数据探索数据分析方法选择数据分析相关性分析转化率分析分析结论 完单数量分析分析结论 司机数量分析分析结论 时间分析每日订单分析 工作日各时段分析周六日…...

pytest - Getting Start

前言 项目开发中有很多的功能&#xff0c;通常开发人员需要对自己编写的代码进行自测&#xff0c;除了借助postman等工具进行测试外&#xff0c;还需要编写单元测试对开发的代码进行测试&#xff0c;通过单元测试来判断代码是否能够实现需求&#xff0c;本文介绍的pytest模块是…...

( 字符串) 205. 同构字符串 ——【Leetcode每日一题】

❓205. 同构字符串 难度&#xff1a;简单 给定两个字符串 s 和 t &#xff0c;判断它们是否是同构的。 如果 s 中的字符可以按某种映射关系替换得到 t &#xff0c;那么这两个字符串是同构的。 每个出现的字符都应当映射到另一个字符&#xff0c;同时不改变字符的顺序。不同…...

python+django+vue消防知识宣传网站

开发语言&#xff1a;Python 框架&#xff1a;django Python版本&#xff1a;python3.7.7 数据库&#xff1a;mysql 数据库工具&#xff1a;Navicat 开发软件&#xff1a;PyCharm 层随着移动应用技术的发展&#xff0c;越来越多的消防单位借助于移动手机、电脑完成生活中的事…...

彻底告别手动配置任务,魔改xxl-job!

分析 改造 1、接口调用 2、创建新注解 3、自动注册核心 4、自动装配 测试 测试后 XXL-Job是一款非常优秀的任务调度中间件&#xff0c;其轻量级、使用简单、支持分布式等优点&#xff0c;被广泛应用在我们的项目中&#xff0c;解决了不少定时任务的调度问题。不仅如此&a…...

【五一创作】Springboot+多环境+多数据源(MySQL+Phoenix)配置及查询(多知识点)

文章目录 1. 背景2. 技术点3 子模块依赖SpringBoot设置4. 多环境配置4.1 application.yml4.2 application-pro.yml 5. 多数据源配置5.1 yml配置5.2 自定义数据源在Java中配置5.2.1 PhoenixDataSourceConfig5.2.2 MysqlDataSourceConfig 6. 完整的Pom6. 测试6.1 Mapper配置6.2 方…...

Python小姿势 - 线程和进程:

线程和进程&#xff1a; Python里面线程是真正的并行执行&#xff0c;进程是可以并行执行的。 所谓进程&#xff0c;就是操作系统中执行一个程序的独立单元&#xff0c;它是系统进行资源分配和调度的基本单位。一个进程可以创建和撤销另一个进程&#xff0c;同一个进程内可以并…...

Mysql 锁

目录 0 课程视频 1 概述 1.1 多用户 并发访问 -> 为了数据一致性(多用户) 1.2 全局锁 数据库所有表 1.3 表级锁 每次操作 锁整张表 1.4 行级锁 每次操作 锁对应行 2 全局锁 ->锁后只读 -> 全库逻辑备份 2.1 阻塞DML /DDL 可DQL读 2.2 语法 2.2.1 加锁 flush…...

Vim 调用外部命令学习笔记

Vim 外部命令集成完全指南 文章目录 Vim 外部命令集成完全指南核心概念理解命令语法解析语法对比 常用外部命令详解文本排序与去重文本筛选与搜索高级 grep 搜索技巧文本替换与编辑字符处理高级文本处理编程语言处理其他实用命令 范围操作示例指定行范围处理复合命令示例 实用技…...

JavaSec-RCE

简介 RCE(Remote Code Execution)&#xff0c;可以分为:命令注入(Command Injection)、代码注入(Code Injection) 代码注入 1.漏洞场景&#xff1a;Groovy代码注入 Groovy是一种基于JVM的动态语言&#xff0c;语法简洁&#xff0c;支持闭包、动态类型和Java互操作性&#xff0c…...

CMake基础:构建流程详解

目录 1.CMake构建过程的基本流程 2.CMake构建的具体步骤 2.1.创建构建目录 2.2.使用 CMake 生成构建文件 2.3.编译和构建 2.4.清理构建文件 2.5.重新配置和构建 3.跨平台构建示例 4.工具链与交叉编译 5.CMake构建后的项目结构解析 5.1.CMake构建后的目录结构 5.2.构…...

苍穹外卖--缓存菜品

1.问题说明 用户端小程序展示的菜品数据都是通过查询数据库获得&#xff0c;如果用户端访问量比较大&#xff0c;数据库访问压力随之增大 2.实现思路 通过Redis来缓存菜品数据&#xff0c;减少数据库查询操作。 缓存逻辑分析&#xff1a; ①每个分类下的菜品保持一份缓存数据…...

sqlserver 根据指定字符 解析拼接字符串

DECLARE LotNo NVARCHAR(50)A,B,C DECLARE xml XML ( SELECT <x> REPLACE(LotNo, ,, </x><x>) </x> ) DECLARE ErrorCode NVARCHAR(50) -- 提取 XML 中的值 SELECT value x.value(., VARCHAR(MAX))…...

Python如何给视频添加音频和字幕

在Python中&#xff0c;给视频添加音频和字幕可以使用电影文件处理库MoviePy和字幕处理库Subtitles。下面将详细介绍如何使用这些库来实现视频的音频和字幕添加&#xff0c;包括必要的代码示例和详细解释。 环境准备 在开始之前&#xff0c;需要安装以下Python库&#xff1a;…...

C++.OpenGL (14/64)多光源(Multiple Lights)

多光源(Multiple Lights) 多光源渲染技术概览 #mermaid-svg-3L5e5gGn76TNh7Lq {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-3L5e5gGn76TNh7Lq .error-icon{fill:#552222;}#mermaid-svg-3L5e5gGn76TNh7Lq .erro…...

PAN/FPN

import torch import torch.nn as nn import torch.nn.functional as F import mathclass LowResQueryHighResKVAttention(nn.Module):"""方案 1: 低分辨率特征 (Query) 查询高分辨率特征 (Key, Value).输出分辨率与低分辨率输入相同。"""def __…...

Visual Studio Code 扩展

Visual Studio Code 扩展 change-case 大小写转换EmmyLua for VSCode 调试插件Bookmarks 书签 change-case 大小写转换 https://marketplace.visualstudio.com/items?itemNamewmaurer.change-case 选中单词后&#xff0c;命令 changeCase.commands 可预览转换效果 EmmyLua…...

Python学习(8) ----- Python的类与对象

Python 中的类&#xff08;Class&#xff09;与对象&#xff08;Object&#xff09;是面向对象编程&#xff08;OOP&#xff09;的核心。我们可以通过“类是模板&#xff0c;对象是实例”来理解它们的关系。 &#x1f9f1; 一句话理解&#xff1a; 类就像“图纸”&#xff0c;对…...