算法训练Day39|62.不同路径 ● 63. 不同路径 II
LeetCode:62.不同路径
62. 不同路径 - 力扣(LeetCode)
1.思路
想象成矩阵填格子,两个关键点,初始化和递推公式。
初始化除点(0,0)第一行第一列均为1,递推公式推导dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
2.代码实现
1class Solution {2 public int uniquePaths(int m, int n) {3 // 二维数组4 int[][] dp = new int[m][n];56 // dp[m][n]:到达m,n位置,有dp[m][n]种路径7 // 初始化8 for (int i = 0; i < m; i++) {9 dp[i][0] = 1;
10 }
11 for (int i = 0; i < n; i++) {
12 dp[0][i] = 1;
13 }
14 for (int i = 1; i < m; i++) {
15 for (int j = 1; j < n; j++) {
16 dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
17 }
18 }
19 return dp[m - 1][n - 1];
20 }
21}
22
3.复杂度分析
时间复杂度:O(m * n).
空间复杂度:O(m * n).
LeetCode:63. 不同路径 II
63. 不同路径 II - 力扣(LeetCode)
1.思路
确定dp[][]数组,
条件排除,各种情况的考虑很关键,首尾节点和首行首列会影响初始化,当前节点影响dp[i][j]的值,
2.代码实现
1class Solution {2 public int uniquePathsWithObstacles(int[][] obstacleGrid) {3 // 求出总路径数 - 障碍位置路径数?45 int m = obstacleGrid.length; // 获取行数6 int n = obstacleGrid[0].length; // 获取列数7 // dp[m][n] 表示节点(m,n)处潜在路径数8 int[][] dp = new int[m][n];9 // 当起始节点和终止节点均有障碍时,无结果,直接返回0
10 if (obstacleGrid[m - 1][n - 1] == 1 || obstacleGrid[0][0] == 1) {
11 return 0;
12 }
13 // 每行的首位数字初始化(也即首列初始化),遇到障碍设置为0
14 for (int i = 0; i < m && obstacleGrid[i][0] == 0; i++) {
15 dp[i][0] = 1;
16 }
17 // 每列的首位数字初始化(也即首行初始化),遇到障碍设置为0
18 for (int j = 0; j < n && obstacleGrid[0][j] == 0; j++) {
19 dp[0][j] = 1;
20 }
21 // 遍历输出dp[][]数组值
22 for (int i = 1; i < m; i++) {
23 for (int j = 1; j < n; j++) [
24 if (obstacleGrid[i][j] == 0) { // 当前节点没有障碍时,正常执行
25 dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
26 } else {
27 dp[i][j] = 0; // 有障碍时直接赋值为0
28 }
29 ]
30 }
31 // 数组下标从0 开始,m - 1, n - 1也就代表(m,n)位置
32 return dp[m - 1][n - 1];
33
34 }
35}
36
3.复杂度分析
时间复杂度:O(m * n).
空间复杂度:O(m * n).
相关文章:
算法训练Day39|62.不同路径 ● 63. 不同路径 II
LeetCode:62.不同路径 62. 不同路径 - 力扣(LeetCode) 1.思路 想象成矩阵填格子,两个关键点,初始化和递推公式。 初始化除点(0,0)第一行第一列均为1,递推公式推导dp[i][j] dp[i …...
react中hooks分享
一. HOOKS是什么 在计算机程序设计中,钩子一词涵盖了一系列技术,这些技术用来通过拦截函数调用、消息或在软件组件之间传递的事件来改变或增加操作系统、应用程序或其他软件组件的行为。处理这些被截获的函数调用、事件或消息的代码称为“hook”。 在r…...
LeetCode1207. 独一无二的出现次数
题干 给你一个整数数组 arr,请你帮忙统计数组中每个数的出现次数。 如果每个数的出现次数都是独一无二的,就返回 true;否则返回 false。 示例1: 输入:arr [1,2,2,1,1,3] 输出:true 解释:在该…...
【maven】构建项目前clean和不clean的区别
其实很简单,但是百度搜了一下,还是没人能简单说明白。 搬用之前做C项目时总结结论: 所以自己在IDE里一遍遍测试程序能否跑通的时候,不需要clean,因为反正还要改嘛。 但是这个项目测试好了,你要打成jar包给…...
Stable Diffusion 硬核生存指南:WebUI 中的 CodeFormer
本篇文章聊聊 Stable Diffusion WebUI 中的核心组件,强壮的人脸图像面部画面修复模型 CodeFormer 相关的事情。 写在前面 在 Stable Diffusion WebUI 项目中,源码 modules 目录中,有一个有趣的目录叫做 CodeFormer,它就是本文的…...
从零开始理解Linux中断架构(24)软中断核心函数__do_softirq
1)概要 __do_softirq函数处理是总是尽可能的执行所有未决软中断。 (1)关闭软中断:在preempt_count设置软中断标志:SOFTIRQ_OFFSET 让in_interrupt检查条件为真,进入软中断处理临界区,后面进来的处理请求,需要检查in_interrupt(),从而达到禁止本cpu上的软中断嵌套的目…...
【云原生】Kubernetes中deployment是什么?
目录 Deployments 更新 Deployment 回滚 Deployment 缩放 Deployment Deployment 状态 清理策略 金丝雀部署 编写 Deployment 规约 Deployments 一个 Deployment 为 Pod 和 ReplicaSet 提供声明式的更新能力。 你负责描述 Deployment 中的 目标状态,而 De…...
sk_buff操作函数学习
一. 前言 内核提供了大量实用的操作sk_buff的函数,在开发网络设备驱动程序和修改网络协议栈代码时需要用到。这些函数从功能上可以分为三类:创建,释放和复制socket buffer;操作sk_buff结构中的参数和指针;管理socket b…...
conda create时候出现JSONDecoderError解决方法
起因是我的conda出现了JSONDecoderError,这个我搜了一下是因为某些配置文件错误,所以让我update conda,于是我先用了下面的指令: conda update conda 但是在执行过程中依然会出现 JSONDecoderError的问题,后来参考了这…...
Electron 工具进程utilityProcess 使用中遇到的坑点汇集
简介 这是基于 node.js 中的子进程的概念推出来的,可参考链接:utilityProcess | Electron 官网有一句话非常重要,它提供一个相当于 Node.js 的 child_process.fork API,但使用 Chromium 的 Services API 代替来执行子进程。这句话…...
JdbcTemplate
目录 1、简介 2、开发步骤 2.1、导入坐标 2.2、创建表和类 2.3、创建JdbcTemplate对象 2.4、执行数据库操作 3、解耦 4、增删改查 ⭐作者介绍:大二本科网络工程专业在读,持续学习Java,努力输出优质文章 ⭐作者主页:逐梦苍穹…...
PROFINET转TCP/IP网关profinet网线接头接法
大家好,今天要和大家分享一款自主研发的通讯网关,捷米JM-PN-TCPIP。这款网关可是集多种功能于一身,PROFINET从站功能,让它在通讯领域独领风骚。想知道这款网关如何实现PROFINET和TCP/IP网络的连接吗?一起来看看吧&…...
【FPGA IP系列】FIFO的通俗理解
FPGA厂商提供了丰富的IP核,基础性IP核都是可以直接免费调用的,比如FIFO、RAM等等。 本文主要介绍FIFO的一些基础知识,帮助大家能够理解FIFO的基础概念。 一、FIFO介绍 FIFO全称是First In First Out,即先进先出。 FIFO是一个数…...
Kylin v10基于cephadm工具离线部署ceph分布式存储
1. 环境: ceph:octopus OS:Kylin-Server-V10_U1-Release-Build02-20210824-GFB-x86_64、CentOS Linux release 7.9.2009 2. ceph和cephadm 2.1 ceph简介 Ceph可用于向云平台提供对象存储、块设备服务和文件系统。所有Ceph存储集群部署都从…...
框架的前置学习-反射
运行java代码要经历的三个阶段 反射,程序框架设计的灵魂,将类的各个组成部分封装成其他对象,这就是反射机制。 框架:半成品的软件,在框架的基础上进行开发,可以简化编码 反射的好处: 可以在…...
【使用bat脚本实现批量创建文件夹、批量复制文件至对应文件夹中】
使用bat脚本实现批量创建文件夹、批量复制文件至对应文件夹中 常用cmd命令 场景一:在指定位置批量创建文件夹 在桌面创建一个txt文件编写创建目录代码 //在桌面"五保户结算单"的文件夹下创建名称为"1张三"的文件夹 md E:\桌面\五保户结算单\…...
面向视频会议场景的 H.266/VVC 码率控制算法研究
文章目录 面向视频会议场景的 H.266/VVC 码率控制算法研究个人总结摘要为什么要码率控制码率控制的关键会议类视频码率控制研究背景视频会议系统研究现状目前基于 R-λ模型的码率控制算法的问题文章主要两大优化算法优化算法1:基于视频内容相关特征值的码率控制算法…...
【网络基础实战之路】设计网络划分的实战详解
系列文章传送门: 【网络基础实战之路】设计网络划分的实战详解 【网络基础实战之路】一文弄懂TCP的三次握手与四次断开 【网络基础实战之路】基于MGRE多点协议的实战详解 【网络基础实战之路】基于OSPF协议建立两个MGRE网络的实验详解 PS:本要求基于…...
MacBook触控板窗口管理 Swish for Mac
Swish for Mac是一款用于通过手势来控制mac应用窗口的软件,你可以通过这款软件在触控板上进行手势控制,你可以在使用前预设好不同手势的功能,然后就能直接通过这些手势让窗口按照你想要的方式进行变动了 Swish 支持 Haptick Feedback 震动反…...
VS开发Qt程序,无法打印QDebug调试信息,VS进行Qt开发时Qt Designer无法使用“转到槽”选项
VS开发Qt程序,无法打印QDebug调试信息,VS进行Qt开发时Qt Designer无法使用“转到槽”选项 VS开发Qt程序,无法打印QDebug调试信息VS进行Qt开发时Qt Designer无法使用“转到槽”选项 VS开发Qt程序,无法打印QDebug调试信息 解决方案…...
挑战杯推荐项目
“人工智能”创意赛 - 智能艺术创作助手:借助大模型技术,开发能根据用户输入的主题、风格等要求,生成绘画、音乐、文学作品等多种形式艺术创作灵感或初稿的应用,帮助艺术家和创意爱好者激发创意、提高创作效率。 - 个性化梦境…...
Spring Boot 实现流式响应(兼容 2.7.x)
在实际开发中,我们可能会遇到一些流式数据处理的场景,比如接收来自上游接口的 Server-Sent Events(SSE) 或 流式 JSON 内容,并将其原样中转给前端页面或客户端。这种情况下,传统的 RestTemplate 缓存机制会…...
《从零掌握MIPI CSI-2: 协议精解与FPGA摄像头开发实战》-- CSI-2 协议详细解析 (一)
CSI-2 协议详细解析 (一) 1. CSI-2层定义(CSI-2 Layer Definitions) 分层结构 :CSI-2协议分为6层: 物理层(PHY Layer) : 定义电气特性、时钟机制和传输介质(导线&#…...
(二)原型模式
原型的功能是将一个已经存在的对象作为源目标,其余对象都是通过这个源目标创建。发挥复制的作用就是原型模式的核心思想。 一、源型模式的定义 原型模式是指第二次创建对象可以通过复制已经存在的原型对象来实现,忽略对象创建过程中的其它细节。 📌 核心特点: 避免重复初…...
页面渲染流程与性能优化
页面渲染流程与性能优化详解(完整版) 一、现代浏览器渲染流程(详细说明) 1. 构建DOM树 浏览器接收到HTML文档后,会逐步解析并构建DOM(Document Object Model)树。具体过程如下: (…...
LLM基础1_语言模型如何处理文本
基于GitHub项目:https://github.com/datawhalechina/llms-from-scratch-cn 工具介绍 tiktoken:OpenAI开发的专业"分词器" torch:Facebook开发的强力计算引擎,相当于超级计算器 理解词嵌入:给词语画"…...
pikachu靶场通关笔记22-1 SQL注入05-1-insert注入(报错法)
目录 一、SQL注入 二、insert注入 三、报错型注入 四、updatexml函数 五、源码审计 六、insert渗透实战 1、渗透准备 2、获取数据库名database 3、获取表名table 4、获取列名column 5、获取字段 本系列为通过《pikachu靶场通关笔记》的SQL注入关卡(共10关࿰…...
Java多线程实现之Thread类深度解析
Java多线程实现之Thread类深度解析 一、多线程基础概念1.1 什么是线程1.2 多线程的优势1.3 Java多线程模型 二、Thread类的基本结构与构造函数2.1 Thread类的继承关系2.2 构造函数 三、创建和启动线程3.1 继承Thread类创建线程3.2 实现Runnable接口创建线程 四、Thread类的核心…...
OPENCV形态学基础之二腐蚀
一.腐蚀的原理 (图1) 数学表达式:dst(x,y) erode(src(x,y)) min(x,y)src(xx,yy) 腐蚀也是图像形态学的基本功能之一,腐蚀跟膨胀属于反向操作,膨胀是把图像图像变大,而腐蚀就是把图像变小。腐蚀后的图像变小变暗淡。 腐蚀…...
10-Oracle 23 ai Vector Search 概述和参数
一、Oracle AI Vector Search 概述 企业和个人都在尝试各种AI,使用客户端或是内部自己搭建集成大模型的终端,加速与大型语言模型(LLM)的结合,同时使用检索增强生成(Retrieval Augmented Generation &#…...
