代码随想录Day29
Day29
动态规划part02
LeetCode 62.不同路径
题目描述
一个机器人位于一个 m x n
网格的左上角 (起始点在下图中标记为 “Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。
问总共有多少条不同的路径?
示例
输入:m = 3, n = 7
输出:28
题目链接
https://leetcode.cn/problems/unique-paths/
思路
- dp数组及下标含义
dp[i][j]
, 走到第i行第j列处的路径条数
- 递推公式
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
- 初始化
第一行和第一列都只有一种方式抵达
解决代码
class Solution {public int uniquePaths(int m, int n) {//dp[i][j] = dp[i - 1][j] + dp[i][j - 1]int[][] dp = new int[m][n];for (int i = 0; i < m; i++){dp[i][0] = 1;}for (int i = 0; i < n; i++) {dp[0][i] = 1;}for (int i = 1; i < m; i++) for (int j = 1; j < n; j++) {dp[i][j] = dp[i - 1][j] + dp[i][j - 1];}return dp[m - 1][n - 1];}
}
LeetCode 63. 不同路径 II
题目描述
给定一个 m x n
的整数数组 grid
。一个机器人初始位于 左上角(即 grid[0][0]
)。机器人尝试移动到 右下角(即 grid[m - 1][n - 1]
)。机器人每次只能向下或者向右移动一步。
网格中的障碍物和空位置分别用 1
和 0
来表示。机器人的移动路径中不能包含 任何 有障碍物的方格。
返回机器人能够到达右下角的不同路径数量。
测试用例保证答案小于等于 2 * 109
。
示例
输入:obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出:2
解释:3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径:
- 向右 -> 向右 -> 向下 -> 向下
- 向下 -> 向下 -> 向右 -> 向右
题目链接
https://leetcode.cn/problems/unique-paths-ii/description/
思路
- dp数组及下标含义
dp[i][j]
, 走到第i行第j列处的路径条数
- 递推公式
if (obstacleGrid[i][j] == 1)dp[i][j] = 0;
elsedp[i][j] = dp[i - 1][j] + dp[i][j - 1];
- 初始化
第一行和第一列都只有一种方式抵达且遇到有障碍, 之后的都无法抵达
解决代码
class Solution {public int uniquePathsWithObstacles(int[][] obstacleGrid) {int m = obstacleGrid.length, n = obstacleGrid[0].length;int[][] dp = new int[m][n];for (int i = 0; i < m; i++) {if (obstacleGrid[i][0] == 1)break;dp[i][0] = 1;}for (int j = 0; j < n; j++) {if (obstacleGrid[0][j] == 1)break;dp[0][j] = 1;}for (int i = 1; i < m; i++)for (int j = 1; j < n; j++) {if (obstacleGrid[i][j] == 1)dp[i][j] = 0;elsedp[i][j] = dp[i - 1][j] + dp[i][j - 1];}return dp[m - 1][n - 1];}
}
LeetCode 343.整数拆分
题目描述
给定一个正整数 n
,将其拆分为 k
个 正整数 的和( k >= 2
),并使这些整数的乘积最大化。
返回 你可以获得的最大乘积 。
示例
输入: n = 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
题目链接
https://leetcode.cn/problems/integer-break/
思路
- dp数组及下标含义
拆分n所能获得的最大乘积
- 递推公式
dp[i] = Math.max(dp[i], Math.max(j * dp[i - j], j * (i - j)))
//i为需要被拆分的数, j为当前拆分大小
- 初始化
2只能拆分为1 + 1, 所以dp[2] = 1; 小于2的情况没有意义
解决代码
class Solution {public int integerBreak(int n) {int[] dp = new int[n + 1];dp[2] = 1;for (int i = 3; i <= n; i++)for (int j = 1; j < i; j++) {dp[i] = Math.max(dp[i], Math.max(dp[i - j] * j, j * (i - j)));}return dp[n];}
}
LeetCode 96.不同的二叉搜索树
题目描述
给你一个整数 n
,求恰由 n
个节点组成且节点值从 1
到 n
互不相同的 二叉搜索树 有多少种?返回满足题意的二叉搜索树的种数。
示例
输入:n = 3
输出:5
题目链接
https://leetcode.cn/problems/unique-binary-search-trees/submissions/617446590/
思路
- dp数组及下标含义
节点值从 1
到 n
互不相同的 二叉搜索树的个数
- 递推公式
根节点为1, 则共有 dp[0] * dp[n - 1]种
根节点为2, 则有dp[1] * dp[n - 2]种
所以dp[n] += dp[j - 1] * dp[n - j];
n为总节点个数
j∈[1, n]
dp[j - 1] :左子树为j - 1个节点的二叉搜索树个数
dp[n - j]:右子树为n - j个节点的二叉搜索树个数
- 初始化
dp[0] = 1, dp[1] = 1
解决代码
class Solution {public int numTrees(int n) {int[] dp = new int[n + 1];dp[0] = 1;dp[1] = 1;for (int i = 2; i <= n; i++)for (int j = 1; j <= i; j++) {dp[i] += dp[i - j] * dp[j - 1];}return dp[n];}
}
相关文章:
代码随想录Day29
Day29 动态规划part02 LeetCode 62.不同路径 题目描述 一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” &…...
Python入门(3):语句
目录 1 基本语句 1.1 表达式语句 1.2 赋值语句 2 控制流语句 2.1 条件语句 2.2 循环语句 while循环: for循环: 2.3 流程控制语句 1. break语句:退出整个循环体 2. continue语句:只跳过本次循环,还会进…...
04_SQL概述及DDL
文章目录 一、关于SQL1.1、SQL概述1.2、SQL分类 二、数据库操作2.1、查看数据库2.2、切换数据库2.3、查询当前使用的数据库2.4、创建数据库2.5、查看数据库创建信息2.6、修改数据库2.7、删除数据库 三、表的操作3.1、数据类型3.1.1、数值类型3.1.2、字符串类型3.1.3、日期时间类…...
如何调整yarn.nodemanager.vmem-pmem-ratio参数?
调整 yarn.nodemanager.vmem - pmem - ratio 参数,可参考以下步骤: 打开YARN配置文件 找到 yarn - site.xml 文件,该文件通常位于Hadoop配置目录中,例如 /etc/hadoop/conf 或 /opt/module/hadoop - 3.1.3/etc/hadoop 。 找到并修改…...
【质量管理】质量的系统是预防,那以预防为主的质量管理系统包括什么?
“质量的系统是预防”这是克劳士比零缺陷管理四项基本原则的第二项基本原则。什么样的系统才是一个以预防为主的质量管理系统呢? 一个以预防为主的质量系统,必须包括三大方面:质量检验系统、质量保证系统、质量管理系统。 举个例子࿱…...
JavaScript 事件流与事件委托
目录 一、事件流、事件捕获与事件冒泡 1. 事件流(Event Flow) 2. 事件捕获(Event Capturing) 3. 事件冒泡(Event Bubbling) 4. 阻止事件冒泡 5. 事件解绑 6. 实际应用场景 二、事件委托 1. 什么是…...
RAG 优化 Embedding 模型或调整检索策略
在 RAG(Retrieval-Augmented Generation)系统中,优化 Embedding 模型和调整检索策略是提升检索质量的核心手段。以下是系统化的优化方法和实践指南: 一、优化 Embedding 模型 Embedding 模型的质量直接决定检索的召回率(Recall)和准确率(Precision)。优化方向包括: …...
Sentinel[超详细讲解]-3
主要讲解🚀 - 基于QPS/并发数的流量控制 1、流控规则 流量控制(Flow Control)用于限制某个资源的访问频率,防止系统被瞬时的流量高峰冲垮。流量控制规则可以针对不同的资源进行配置,例如接口、方法、类等。 流量规则的…...
vue3使用i18n$t()无法获取数组和对象
今天在使用i18n进行国际化时,定义了数组和对象节点,但是用$t()无法获取,只能返回字符串值,查询相关材料,解决方案如下: 使用新的api替换即可,$t > $tm 参考文章(深表谢意):vue -…...
机器学习的一百个概念(5)数据增强
前言 本文隶属于专栏《机器学习的一百个概念》,该专栏为笔者原创,引用请注明来源,不足和错误之处请在评论区帮忙指出,谢谢! 本专栏目录结构和参考文献请见[《机器学习的一百个概念》 ima 知识库 知识库广场搜索&…...
(Kotlin)Android 高效底部导航方案:基于预定义 Menu 和 ViewPager2 的 Fragment 动态绑定实现
支持预定义 Menu 并绑定 Fragment,同时保留动态添加 Tab 的能力 BottomTabHelper.kt package smartconnection.com.smartconnect.home.utilimport android.content.Context import android.util.SparseArray import androidx.annotation.IdRes import androidx.fra…...
零基础入门多媒体音频(4)-GENIVIProjectAudioManager总览
GENIVI Project的AudioManager是一个专门设计用于汽车信息娱乐系统的音频管理解决方案。它负责管理和控制车辆内的音频源和音频路径,确保各种音频信号能够正确、高效地在车辆的音响系统中传输和播放。 AudioManager的核心功能包括音频源的管理、音频路径的控制以及音…...
DeepSeek协助优化-GTX750Ti文物显卡0.65秒卷完400MB float 音频512阶时域FIR
文章目录 1. 学习目的2. 阶段成果2.1 NVVP 性能探查2.2 测试编译环境2.3 测试样例 3 学习过程3.1 提问DeepSeek3.2 最终代码 4. 体会 1. 学习目的 最近在学习cuda,准备给我的taskBus SDR添加CUDA的模块支持,以便可以用PC机压榨山寨 B210那56M的带宽。 因…...
Embedding原理
Embedding(嵌入)是将离散符号(如单词)映射到连续向量空间的核心技术,其本质是语义的数学化表示。以下是其核心原理详解: 一、基础概念图解 graph LRA[单词猫] --> B[索引5] --> C[向量[0.2, -1.3,…...
Spark,配置hadoop集群1
配置运行任务的历史服务器 1.配置mapred-site.xml 在hadoop的安装目录下,打开mapred-site.xml,并在该文件里面增加如下两条配置。 eg我的是在hadoop199上 <!-- 历史服务器端地址 --> <property><name>mapreduce.jobhistory.address…...
人工智能大模型-数据预处理-文本数据预处理-图像数据预处理
文本数据预处理 大模型常用的文本数据类型 通用文本数据:网页、对话和图书资料等专用文本数据:多语言文本、科学文本、代码和指令等 构造方法 指令数据:指令(instruction)、输入(input)、输出(output)3部分组成 如果在instruction部分已…...
怎么使用嵌套虚拟环境实现项目部署之virtualenv嵌套conda绕开安装环境检测实现.venv部署facefusion
#工作记录 一、前言 嵌套虚拟环境本来是不建议的一种方法,这种嵌套虚拟环境的使用有一定特殊性,但在一些特别的使用场景下,嵌套虚拟环境的使用非常有用。 二、嵌套虚拟环境: (一)conda嵌套virtualenv 该…...
ansible介绍以及安装
一.ansible介绍 实现对IT基础设施的批量管控,加快效率,节省工作时间。 1.ansible特性 1.基于python开发,开源, 2.基于ssh协议工作。只需要确保ansible机器,与被控制机器能连通就好了, 3.no server 无…...
GPT-4o图像生成功能:技术突破与隐忧并存
2025年3月25日,OpenAI正式推出GPT-4o原生图像生成功能,宣称其实现了“文本到图像的终极跨越”。然而,这一被市场追捧的技术在短短72小时内便因用户需求过载触发限流,暴露出算力瓶颈与商业化矛盾的尖锐性。这场技术狂欢的背后&…...
Java 时间处理:轻松掌握 java.time 包
前言 在 Java 开发中,日期和时间处理一直是令人头疼的问题。传统的 Date 和 Calendar 类不仅复杂,还充满了线程安全和时区处理的坑。Java 8 引入的 java.time 包彻底改变了这一局面,带来了现代化、直观且功能强大的日期时间 API。 本…...
Vue项目中Vuex在util引入,断点存在default
示例代码 // src/store/index.js import Vue from vue; import Vuex from vuex; ……Vue.use(Vuex); export default new Vuex.Store({…… })// src/utils/index.js import store from /store // 导入默认导出的 store export async function getDict() {store.state.userInf…...
2025宁德时代测评Verify考什么?网申测评如何通过SHL笔试|附真题线上笔试考点、高分攻略、CATL新能源科技SHL测评宁德社招题目、面试攻略、求职建议
——职小豚 带你拆解新能源巨头招聘密码 一、宁德时代:新能源赛道「超级独角兽」 作为全球动力电池龙头,宁德时代(CATL)的江湖地位无需多言: 技术硬实力:麒麟电池、钠离子电池、无钴电池等黑科技加持&…...
谈谈常见的数据结构(如数组、链表、栈、队列、哈希表、树、图)及其应用场景
一、数组(Array) 定义:连续存储相同类型数据的线性结构,支持随机访问。 应用场景:列表渲染、数据缓存、算法处理 代码示例: // 数组基本操作 const arr [1, 2, 3, 4]; arr.push(5); // O(1) 平均时间复杂…...
【 <二> 丹方改良:Spring 时代的 JavaWeb】之 Spring Boot 中的 AOP:实现日志记录与性能监控
答应我,这篇一定要看到最后~! <前文回顾> 点击此处查看 合集 https://blog.csdn.net/foyodesigner/category_12907601.html?fromshareblogcolumn&sharetypeblogcolumn&sharerId12907601&sharereferPC&sharesourceFoyoDesigner&a…...
【算法】快速幂
一、概念 快速幂是一种高效的指数运算,当指数范围过大时,通过位运算能够减少大量的计算次数 对于,我们通过将指数b转化为二进制数,就可以将分解为许多的(其中i是指数b中对应位为1的位数) 例如࿰…...
使用卷积神经网络识别MNIST数据集
卷积神经网络 卷积神经网络本质是共享权重稀疏链接的全连接网络 编写步骤 构建一个神经网络,步骤是几乎不变的,大概有以下几步 准备数据集 #更高级的CNN网络 import torch import torch.nn as nn import torch.nn.functional as F import torchvisi…...
JavaScript 中数组增删改查
在 JavaScript 中,数组是一种用来存储不同类型的值的数据结构。 增加数组元素: let arr = [1, 2, 3];// 在数组末尾添加元素 arr.push(4); console.log(arr); // [1, 2, 3, 4]// 在数组开头添加元素 arr.unshift(0); console.log(arr); // [0, 1, 2, 3, 4]// 在指定位置插…...
【Kettle安装】Kettle安装过程, 电脑已安装java23,安装Kettle 出现报错:尝试启动 Java 虚拟机(JVM)时失败解决方法
Kettle安装 Kettle 通常指的是 Pentaho Data Integration (PDI),这是一款开源的 ETL(Extract, Transform, Load)工具,用于数据集成、数据清洗和数据分析。它的核心工具名为 Spoon,但整个项目常被直接称为 Kettle 数据…...
Spring笔记04-注解注入
1.导入包 <dependency><groupId>org.springframework</groupId><artifactId>spring-beans</artifactId><version>5.2.7.RELEASE</version></dependency><dependency><groupId>org.springframework</groupId>…...
[动规19] 最大子数组和
目录 1. 题意 2. 思路 2.1. 状态表示 2.2. 状态转移方程 2.3. 初始化 2.4. 填表顺序 2.5. 返回值 3. 编码 1. 题意 链接: 53. 最大子数组和 - 力扣(LeetCode) 题目 给你一个整数数组 nums ,请你找出一个具有最大和的连续子数组&…...
2024年零知识证明(ZK)研究进展
Sumcheck 整个领域正在转向更多地依赖于 Sumcheck Protocol Sumcheck是用于验证多项式承诺的协议,常用于零知识证明(ZKP)中,尤其是在可验证计算和扩展性上。它的主要目的是通过对多项式进行分段检查,从而保证某个多项…...
1. 两数之和
leetcode Hot 100系列 文章目录 一、核心操作二、外层配合操作三、核心模式代码总结 一、核心操作 使用map,key作为数值,value作为下标先寻找对应的目标值,如果找到了则直接返回,否则在往map中插入 提示:小白个人理…...
【电动汽车再生制动控制技术(万字长文,图文并茂)】
电动汽车再生制动控制系统概述 电动汽车再生制动的基本原理是:通过具有可逆作用的电动机/发电机来实现电动汽车动能和电能的转化。在汽车减速或制动时,可逆电机以发电机形式工作,汽车行驶的动能带动发电机将汽车动能转化为电能并储存在储能器(蓄电池或超级电容器)中;在汽车…...
python实现股票数据可视化
最近在做一个涉及到股票数据清洗及预测的项目,项目中需要用到可视化股票数据这一功能,这里我与大家分享一下股票数据可视化的一些基本方法。 股票数据获取 目前,我已知的使用python来获取股票数据方式有以下三种: 爬虫获取,实现…...
2025年湖南建筑安全员 C1考证刷题题库
湖南建筑安全员 C1 类的练习题: 1、塔机的拆装作业必须在白天进行,不得在( )情况下进行。 A. 夜间 B. 大风 C. 浓雾 D. 以上都是 答案:D 2、采用钢筋混凝土灌注桩时,开挖标准是桩身混凝土达到&#…...
【Feign】⭐️使用 openFeign 时传递 MultipartFile 类型的参数参考
💥💥✈️✈️欢迎阅读本文章❤️❤️💥💥 🏆本篇文章阅读大约耗时三分钟。 ⛳️motto:不积跬步、无以千里 📋📋📋本文目录如下:🎁🎁&a…...
ToolsSet之:梯度色板
ToolsSet是微软商店中的一款包含数十种实用工具数百种细分功能的工具集合应用,应用基本功能介绍可以查看以下文章: Windows应用ToolsSet介绍https://blog.csdn.net/BinField/article/details/145898264 ToolsSet中Media菜单下的“Gradient Palette”工…...
Apache Hive和Snowflake的`CREATE VIEW`语法和功能特性整理的对比表
写一个Apache Hive中CREATE VIEW语句转换为对应Snowflake中CREATE VIEW语句的程序,现在需要一个根据功能的相似性对应的Apache HiveQL和Snowflake SQL的CREATE VIEW语句的表。 以下是基于Apache Hive的CREATE VIEW语法规则构造的所有可能合法语句实例及其功能说明&…...
【测试】每日3道面试题 3/31
长期更新,建议关注收藏点赞。 单元测试策略有哪些,主要内容。 白盒测试黑盒测试基于异常和边界的测试 主要内容:测试用例设计、执行、结果分析、自动化beta测试和alpha测试主要区别 主要区别:测试环境测试者 alphabeta时间先后测…...
用 Hugging Face Spaces 打造哪吒的 3D 模型:完整指南
引言: 哪吒,这位中国神话中的传奇人物,以其独特的形象和故事深受人们喜爱。如今,通过 Hugging Face Spaces 提供的 TripoSG 工具,我们可以轻松创建哪吒的 3D 模型。以下是详细步骤,帮助你将这个神话角色带入…...
鸿蒙应用元服务开发-Account Kit概述
Account Kit(华为账号服务)提供简单、快速、安全的登录功能,让用户快捷地使用华为账号登录元服务。用户授权后,Account Kit可提供头像、手机号码等信息,帮助元服务更了解用户。Account Kit提供的SampleCode示例工程体现…...
美团小程序 mtgsig1.2 拼好饭案例 分析 mtgsig
声明 本文章中所有内容仅供学习交流使用,不用于其他任何目的,抓包内容、敏感网址、数据接口等均已做脱敏处理,严禁用于商业用途和非法用途,否则由此产生的一切后果均与作者无关! 逆向分析 美团网页、小程序、app全是指…...
hadoop集群和常用命令
Hadoop集群的搭建与管理 1. HADOOP简介 Hadoop 是一种用于大规模数据处理的大数据框架,支持通过简单编程模型实现跨计算机集群的数据分布存储和计算3。 2. HADOOP集群部署过程 (1) 解压并安装HADOOP 在虚拟机环境中,可以通过解压缩方式完成Hadoop的安…...
爬虫:基本流程和robots协议
基本流程: 1.确认目标:url:www.baidu.com 2.发送请求:发送网络请求,获取到特定的服务端给你的响应 3.提取数据:从响应中提取特定的数据 4.保存数据:本地(html,json,txt),数据库 获取到的响应…...
python之三种去重方法
1. 数据读取与参数解析 代码片段 detail pd.read_csv(detail.csv, index_col0, encodinggbk)数据实例 参数详解 index_col0: 作用:将第1列设置为索引其他选项: None:不指定索引列(默认)列序号/列名&…...
QML输入控件: TextField(文本框)的样式定制
目录 引言示例简介示例代码与关键点示例1:基础样式定制示例2:添加图标示例3:交互式元素(清除按钮) 实现要点总结完整工程下载 引言 在Qt Quick应用程序开发中,文本输入是最常见的用户交互方式之一。TextFi…...
Visual Studio | 性能探测器
文章目录 一、性能探测器1、核心功能2、数据采集3、数据分析3.1、CPU分析 前言: Visual Studio(VS)提供的性能探测器(Performance Profiler)是一款强大的工具,它能够帮助开发者分析应用程序的性能ÿ…...
数据库中的函数:高效操作与灵活运用
数据库中的函数:高效操作与灵活运用 在数据库开发过程中,函数是常用的工具,可以帮助我们更高效地处理和操作数据。无论是对字符串、数值、日期还是流程控制,数据库函数都能够提供强大的支持。本文将深入探讨常见的数据库函数&…...
《非暴力沟通》第十二章 “重获生活的热情” 总结
《非暴力沟通》第十二章 “重获生活的热情” 的核心总结: 本章将非暴力沟通的核心理念延伸至生命意义的探索,提出通过觉察与满足内心深处的需要,打破“义务性生存”的桎梏,让生活回归由衷的喜悦与创造。作者强调,当行动…...
C++位运算精要:高效解题的利器
引言 在算法竞赛和底层开发中,位运算(Bit Manipulation)因其极高的执行效率而广受青睐。它能在O(1)时间复杂度内完成某些复杂操作,大幅优化程序性能。本文系统梳理C位运算的核心技巧,涵盖基础操作、经典应用、优化策略…...