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

算法训练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. 不同路径 - 力扣&#xff08;LeetCode&#xff09; 1.思路 想象成矩阵填格子&#xff0c;两个关键点&#xff0c;初始化和递推公式。 初始化除点&#xff08;0&#xff0c;0&#xff09;第一行第一列均为1&#xff0c;递推公式推导dp[i][j] dp[i …...

react中hooks分享

一. HOOKS是什么 在计算机程序设计中&#xff0c;钩子一词涵盖了一系列技术&#xff0c;这些技术用来通过拦截函数调用、消息或在软件组件之间传递的事件来改变或增加操作系统、应用程序或其他软件组件的行为。处理这些被截获的函数调用、事件或消息的代码称为“hook”。 在r…...

LeetCode1207. 独一无二的出现次数

题干 给你一个整数数组 arr&#xff0c;请你帮忙统计数组中每个数的出现次数。 如果每个数的出现次数都是独一无二的&#xff0c;就返回 true&#xff1b;否则返回 false。 示例1&#xff1a; 输入&#xff1a;arr [1,2,2,1,1,3] 输出&#xff1a;true 解释&#xff1a;在该…...

【maven】构建项目前clean和不clean的区别

其实很简单&#xff0c;但是百度搜了一下&#xff0c;还是没人能简单说明白。 搬用之前做C项目时总结结论&#xff1a; 所以自己在IDE里一遍遍测试程序能否跑通的时候&#xff0c;不需要clean&#xff0c;因为反正还要改嘛。 但是这个项目测试好了&#xff0c;你要打成jar包给…...

Stable Diffusion 硬核生存指南:WebUI 中的 CodeFormer

本篇文章聊聊 Stable Diffusion WebUI 中的核心组件&#xff0c;强壮的人脸图像面部画面修复模型 CodeFormer 相关的事情。 写在前面 在 Stable Diffusion WebUI 项目中&#xff0c;源码 modules 目录中&#xff0c;有一个有趣的目录叫做 CodeFormer&#xff0c;它就是本文的…...

从零开始理解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 中的 目标状态&#xff0c;而 De…...

sk_buff操作函数学习

一. 前言 内核提供了大量实用的操作sk_buff的函数&#xff0c;在开发网络设备驱动程序和修改网络协议栈代码时需要用到。这些函数从功能上可以分为三类&#xff1a;创建&#xff0c;释放和复制socket buffer&#xff1b;操作sk_buff结构中的参数和指针&#xff1b;管理socket b…...

conda create时候出现JSONDecoderError解决方法

起因是我的conda出现了JSONDecoderError&#xff0c;这个我搜了一下是因为某些配置文件错误&#xff0c;所以让我update conda&#xff0c;于是我先用了下面的指令&#xff1a; conda update conda 但是在执行过程中依然会出现 JSONDecoderError的问题&#xff0c;后来参考了这…...

Electron 工具进程utilityProcess 使用中遇到的坑点汇集

简介 这是基于 node.js 中的子进程的概念推出来的&#xff0c;可参考链接&#xff1a;utilityProcess | Electron 官网有一句话非常重要&#xff0c;它提供一个相当于 Node.js 的 child_process.fork API&#xff0c;但使用 Chromium 的 Services API 代替来执行子进程。这句话…...

JdbcTemplate

目录 1、简介 2、开发步骤 2.1、导入坐标 2.2、创建表和类 2.3、创建JdbcTemplate对象 2.4、执行数据库操作 3、解耦 4、增删改查 ⭐作者介绍&#xff1a;大二本科网络工程专业在读&#xff0c;持续学习Java&#xff0c;努力输出优质文章 ⭐作者主页&#xff1a;逐梦苍穹…...

PROFINET转TCP/IP网关profinet网线接头接法

大家好&#xff0c;今天要和大家分享一款自主研发的通讯网关&#xff0c;捷米JM-PN-TCPIP。这款网关可是集多种功能于一身&#xff0c;PROFINET从站功能&#xff0c;让它在通讯领域独领风骚。想知道这款网关如何实现PROFINET和TCP/IP网络的连接吗&#xff1f;一起来看看吧&…...

【FPGA IP系列】FIFO的通俗理解

FPGA厂商提供了丰富的IP核&#xff0c;基础性IP核都是可以直接免费调用的&#xff0c;比如FIFO、RAM等等。 本文主要介绍FIFO的一些基础知识&#xff0c;帮助大家能够理解FIFO的基础概念。 一、FIFO介绍 FIFO全称是First In First Out&#xff0c;即先进先出。 FIFO是一个数…...

Kylin v10基于cephadm工具离线部署ceph分布式存储

1. 环境&#xff1a; ceph&#xff1a;octopus OS&#xff1a;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代码要经历的三个阶段 反射&#xff0c;程序框架设计的灵魂&#xff0c;将类的各个组成部分封装成其他对象&#xff0c;这就是反射机制。 框架&#xff1a;半成品的软件&#xff0c;在框架的基础上进行开发&#xff0c;可以简化编码 反射的好处&#xff1a; 可以在…...

【使用bat脚本实现批量创建文件夹、批量复制文件至对应文件夹中】

使用bat脚本实现批量创建文件夹、批量复制文件至对应文件夹中 常用cmd命令 场景一&#xff1a;在指定位置批量创建文件夹 在桌面创建一个txt文件编写创建目录代码 //在桌面"五保户结算单"的文件夹下创建名称为"1张三"的文件夹 md E:\桌面\五保户结算单\…...

面向视频会议场景的 H.266/VVC 码率控制算法研究

文章目录 面向视频会议场景的 H.266/VVC 码率控制算法研究个人总结摘要为什么要码率控制码率控制的关键会议类视频码率控制研究背景视频会议系统研究现状目前基于 R-λ模型的码率控制算法的问题文章主要两大优化算法优化算法1&#xff1a;基于视频内容相关特征值的码率控制算法…...

【网络基础实战之路】设计网络划分的实战详解

系列文章传送门&#xff1a; 【网络基础实战之路】设计网络划分的实战详解 【网络基础实战之路】一文弄懂TCP的三次握手与四次断开 【网络基础实战之路】基于MGRE多点协议的实战详解 【网络基础实战之路】基于OSPF协议建立两个MGRE网络的实验详解 PS&#xff1a;本要求基于…...

MacBook触控板窗口管理 Swish for Mac

Swish for Mac是一款用于通过手势来控制mac应用窗口的软件&#xff0c;你可以通过这款软件在触控板上进行手势控制&#xff0c;你可以在使用前预设好不同手势的功能&#xff0c;然后就能直接通过这些手势让窗口按照你想要的方式进行变动了 Swish 支持 Haptick Feedback 震动反…...

VS开发Qt程序,无法打印QDebug调试信息,VS进行Qt开发时Qt Designer无法使用“转到槽”选项

VS开发Qt程序&#xff0c;无法打印QDebug调试信息&#xff0c;VS进行Qt开发时Qt Designer无法使用“转到槽”选项 VS开发Qt程序&#xff0c;无法打印QDebug调试信息VS进行Qt开发时Qt Designer无法使用“转到槽”选项 VS开发Qt程序&#xff0c;无法打印QDebug调试信息 解决方案…...

浏览器访问 AWS ECS 上部署的 Docker 容器(监听 80 端口)

✅ 一、ECS 服务配置 Dockerfile 确保监听 80 端口 EXPOSE 80 CMD ["nginx", "-g", "daemon off;"]或 EXPOSE 80 CMD ["python3", "-m", "http.server", "80"]任务定义&#xff08;Task Definition&…...

使用VSCode开发Django指南

使用VSCode开发Django指南 一、概述 Django 是一个高级 Python 框架&#xff0c;专为快速、安全和可扩展的 Web 开发而设计。Django 包含对 URL 路由、页面模板和数据处理的丰富支持。 本文将创建一个简单的 Django 应用&#xff0c;其中包含三个使用通用基本模板的页面。在此…...

YSYX学习记录(八)

C语言&#xff0c;练习0&#xff1a; 先创建一个文件夹&#xff0c;我用的是物理机&#xff1a; 安装build-essential 练习1&#xff1a; 我注释掉了 #include <stdio.h> 出现下面错误 在你的文本编辑器中打开ex1文件&#xff0c;随机修改或删除一部分&#xff0c;之后…...

企业如何增强终端安全?

在数字化转型加速的今天&#xff0c;企业的业务运行越来越依赖于终端设备。从员工的笔记本电脑、智能手机&#xff0c;到工厂里的物联网设备、智能传感器&#xff0c;这些终端构成了企业与外部世界连接的 “神经末梢”。然而&#xff0c;随着远程办公的常态化和设备接入的爆炸式…...

算法笔记2

1.字符串拼接最好用StringBuilder&#xff0c;不用String 2.创建List<>类型的数组并创建内存 List arr[] new ArrayList[26]; Arrays.setAll(arr, i -> new ArrayList<>()); 3.去掉首尾空格...

代码随想录刷题day30

1、零钱兑换II 给你一个整数数组 coins 表示不同面额的硬币&#xff0c;另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额&#xff0c;返回 0 。 假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带…...

springboot整合VUE之在线教育管理系统简介

可以学习到的技能 学会常用技术栈的使用 独立开发项目 学会前端的开发流程 学会后端的开发流程 学会数据库的设计 学会前后端接口调用方式 学会多模块之间的关联 学会数据的处理 适用人群 在校学生&#xff0c;小白用户&#xff0c;想学习知识的 有点基础&#xff0c;想要通过项…...

无人机侦测与反制技术的进展与应用

国家电网无人机侦测与反制技术的进展与应用 引言 随着无人机&#xff08;无人驾驶飞行器&#xff0c;UAV&#xff09;技术的快速发展&#xff0c;其在商业、娱乐和军事领域的广泛应用带来了新的安全挑战。特别是对于关键基础设施如电力系统&#xff0c;无人机的“黑飞”&…...

第7篇:中间件全链路监控与 SQL 性能分析实践

7.1 章节导读 在构建数据库中间件的过程中&#xff0c;可观测性 和 性能分析 是保障系统稳定性与可维护性的核心能力。 特别是在复杂分布式场景中&#xff0c;必须做到&#xff1a; &#x1f50d; 追踪每一条 SQL 的生命周期&#xff08;从入口到数据库执行&#xff09;&#…...

解析奥地利 XARION激光超声检测系统:无膜光学麦克风 + 无耦合剂的技术协同优势及多元应用

在工业制造领域&#xff0c;无损检测&#xff08;NDT)的精度与效率直接影响产品质量与生产安全。奥地利 XARION开发的激光超声精密检测系统&#xff0c;以非接触式光学麦克风技术为核心&#xff0c;打破传统检测瓶颈&#xff0c;为半导体、航空航天、汽车制造等行业提供了高灵敏…...