代码随想录学习Day 34
62.不同路径
题目链接
讲解链接
动归五部曲:
1.确定dp数组及其下标的含义:dp[i][j]的含义是从(0, 0)走到(i, j)所需的步数;
2.确定递推公式:因为只能往右或者往下,所以dp[i][j] = dp[i - 1][j] + dp[i][j - 1]。
3.dp数组初始化:初始化为m * n的全1数组。
4.确定遍历顺序:因为递推公式为dp[i][j] = dp[i - 1][j] + dp[i][j - 1],dp[i][j]都是从其上方和左方推导而来,那么从左到右一层一层遍历就可以了。
5.举例推导dp数组:m = 3,n = 7时,dp = [[1, 1, 1, 1, 1, 1, 1], [1, 2, 3, 4, 5, 6, 7], [1, 3, 6, 10, 15, 21, 28]]
class Solution:def uniquePaths(self, m: int, n: int) -> int:dp = [[1] * n for _ in range(m)] # 初始化为全1数组,因为第一列和第一行一定都是1for i in range(1, m):for j in range(1, n):dp[i][j] = dp[i - 1][j] + dp[i][j - 1] # 递推公式return dp[-1][-1]
63.不同路径Ⅱ
题目链接
讲解链接
本题大体思路同上,只需要对障碍物处额外处理一下。
在初始化时,如果第一列或第一行有障碍物,则将该位置的dp至设为0;在后续遍历过程中若遇到障碍物,则同样将该位置设为0,之后按照与上一题同样的方法计算即可。
class Solution:def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:i, j = 0, 0m, n = len(obstacleGrid), len(obstacleGrid[0])dp = [[0] * n for _ in range(m)]while i < m and obstacleGrid[i][0] == 0: # 初始化列,第一列除了障碍物处均为1dp[i][0] = 1i += 1while j < n and obstacleGrid[0][j] == 0: # 同上,第一行除障碍均为1dp[0][j] = 1j += 1for i in range(1, m):for j in range(1, n):if obstacleGrid[i][j] == 1: # 若遇到障碍处则将该位置的dp置为0dp[i][j] = 0else:dp[i][j] = dp[i - 1][j] + dp[i][j - 1] # 递推公式return dp[-1][-1]
相关文章:
代码随想录学习Day 34
62.不同路径 题目链接 讲解链接 动归五部曲: 1.确定dp数组及其下标的含义:dp[i][j]的含义是从(0, 0)走到(i, j)所需的步数; 2.确定递推公式:因为只能往右或者往下,所以dp[i][j] dp[i - 1][j] dp[i][j - 1]。 3.…...

由于找不到MSVCP120D.dll,无法继续执行代码。重新安装程序可能会解决此问题
由于找不到MSVCP120D.dll,无法继续执行代码。重新安装程序可能会解决此问题 一、问题详细描述二、问题产生背景三、问题原因四、解决办法1、安装缺少的库2、直接更换更高版本的opencv 五、vs版本对应vc1、版本对应2、vs对应vc查看方法 一、问题详细描述 同样可能会报 ÿ…...

【前端】输入时字符跳动动画实现
输入时字符跳动动画实现 在前端开发中,为了提升用户体验,我们经常需要为用户的交互行为提供即时的反馈。这不仅让用户知道他们的操作有了响应,还可以让整个界面看起来更加生动、有趣。本文将通过一个简单的例子讲解如何实现在用户输入字符时…...
C语言面试重点问题
1. 冒泡排序法 2. strlen、strcpy、strcat、strcmp的用法和原理 3. 大小端的区分 3.1 主函数区分大小端 #include <stdio.h>int main(void) {int num 0x11223344;char *p (char *)#if (0x11 *p){printf("大端!\n");}else if (0x44 *p){printf(…...
antlr4略解
文章目录 1. antlr4是用来干什么的?2. 什么是lexer和parser?3. 使用antlr4生成某语言的lexer和parser的具体过程4. 其他 1. antlr4是用来干什么的? 是用来生成某语言lexer和parser的。 通俗点说,就是输入一个语言的规则描述文件&…...
超级好用的C++实用库之文件目录操作
💡 需要该C实用库源码的大佬们,可扫码关注文章末尾的微信公众号二维码,或搜索微信公众号“希望睿智”。添加关注后,输入消息“超级好用的C实用库”,即可获得源码的下载链接。 概述 文件和目录操作是操作系统层面上的基…...

结合kimi chat的爬虫实战思路
背景 想钻研一下项目组件,找找之后的学习方向。不能自以为是,所以借着网开源项目网站上公布的项目内容看一下,那些是我可以努力去学习的(入门的)。首先需要获取相关内容,于是爬取整理。 任务1:…...

UnsupportedClassVersionError异常如何解决?
下面是异常报错的详细描述 java -version java version "17.0.11" 2024-04-16 LTS Java(TM) SE Runtime Environment (build 17.0.117-LTS-207) Java HotSpot(TM) 64-Bit Server VM (build 17.0.117-LTS-207, mixed mode, sharing) 环境变量已经是jdk17,但…...
LeetCode热题100|动态规划Part.1|70.爬楼梯、118.杨辉三角、198.打家劫舍
70.爬楼梯 代码随想录原题,看这篇文章:C动态规划Part.1|动态规划理论基础、509.斐波那契数、70.爬楼梯、746.使用最小花费爬楼梯 118.杨辉三角 题目链接:118.杨辉三角 一刷代码 时间复杂度和空间复杂度都造到 O ( n u m R o w s 2 ) O(num…...

python 根据网址和关键词批量下载影像
最近用到了GLASS的LAI产品,但这个产品的文件夹分得很细,我需要的影像又有8个瓦片,一个一个点击很麻烦,于是探索了批量下载的方法 一、下载1幅 import requests import re import os import requests import re# 网页URLurl &…...

爬虫-无限debug场景 解决方式
解决无限debug 场景1 1. 鼠标右键 选择 continue to here(此处不停留)2. 鼠标右键 选择 edite breakpoint 设置 10 保证条件不成立 这行永远不执行3.方法置空 1. 方法调用加断点2. 控制台 setInterval function name() {}4. 替换文件 5. hoo…...
[链表专题]力扣206, 203, 19
1. 力扣206 : 反转链表 (1). 题 : 图略 给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。示例 1:输入:head [1,2,3,4,5] 输出:[5,4,3,2,1] 示例 2:输入:head [1,2] 输出&#x…...
秋招后端开发面试题 - MySQL基础
目录 MySQL基础前言面试题MySQL 基础篇Mysql 的基础架构?MySQL 的长连接和短连接长连接引起的异常重启问题?说一下 MySQL 执行一条查询语句的内部执行过程?MySQL 查询缓存的功能有何优缺点?MySQL 的常用引擎都有哪些?I…...

力扣每日一题113:路径总和||
题目 中等 给你二叉树的根节点 root 和一个整数目标和 targetSum ,找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。 叶子节点 是指没有子节点的节点。 示例 1: 输入:root [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSu…...
Thinkphp5 中常见的session 操作方法
在 ThinkPHP 框架中,session 是用于在多个页面或请求之间存储用户信息的机制。以下是在 ThinkPHP 中进行 session 常见操作的一些示例: 启动 Session 在 ThinkPHP 中,通常不需要手动启动 Session,因为框架会在应用启动时自动处理…...

inBuilder 低代码平台新特性推荐 - 第十八期
今天来给大家带来的是inBuilder低代码平台特性推荐系列第十八期——表单设计器集成预约日历组件。 一、场景介绍 项目上希望用日历的形式展示某地点在一段时间内的预约记录,表单设计器新增支持创建日历预约视图,并配置预约属性。 二、运行效果 三、前…...

部署xwiki服务需要配置 hibernate.cfg.xml如何配置?
1. 定位 hibernate.cfg.xml 文件 首先,确保您可以在 Tomcat 的 XWiki 部署目录中找到 hibernate.cfg.xml 文件: cd /opt/tomcat/latest/webapps/xwiki/WEB-INF ls -l hibernate.cfg.xml如果文件存在,您可以继续编辑它。如果不存在ÿ…...
1376:信使(msner)
【解题思路】 每个哨所是一个顶点,哨所与哨所之间的通信线路为边,两哨所间通讯花费的时间为边的权值。记第一个哨所为顶点s,信息从第一个哨所传递到表示为顶点x的某哨所可能有多条路径,每条传送路径有一个花费的时间&…...

Hadoop3:HDFS的架构组成
一、官方文档 我这里学习的是Hadoop3.1.3版本,所以,查看的也是3.1.3版本的文档 Architecture模块最下面 二、HDFS架构介绍 HDFS架构的主要组成部分,是一下四个部分 1、NameNode(NN) 就是Master节点,它是集群管理者。 1、管…...
P2910 [USACO08OPEN] Clear And Present Danger S
Problem: P2910 [USACO08OPEN] Clear And Present Danger S 文章目录 思路解题方法复杂度Code 思路 这是一个图论问题,我们需要找到从一个城市到另一个城市的最短路径。我们可以使用Floyd-Warshall算法来解决这个问题。首先,我们需要构建一个距离矩阵&am…...

网络编程(Modbus进阶)
思维导图 Modbus RTU(先学一点理论) 概念 Modbus RTU 是工业自动化领域 最广泛应用的串行通信协议,由 Modicon 公司(现施耐德电气)于 1979 年推出。它以 高效率、强健性、易实现的特点成为工业控制系统的通信标准。 包…...
【根据当天日期输出明天的日期(需对闰年做判定)。】2022-5-15
缘由根据当天日期输出明天的日期(需对闰年做判定)。日期类型结构体如下: struct data{ int year; int month; int day;};-编程语言-CSDN问答 struct mdata{ int year; int month; int day; }mdata; int 天数(int year, int month) {switch (month){case 1: case 3:…...

Debian系统简介
目录 Debian系统介绍 Debian版本介绍 Debian软件源介绍 软件包管理工具dpkg dpkg核心指令详解 安装软件包 卸载软件包 查询软件包状态 验证软件包完整性 手动处理依赖关系 dpkg vs apt Debian系统介绍 Debian 和 Ubuntu 都是基于 Debian内核 的 Linux 发行版ÿ…...

相机从app启动流程
一、流程框架图 二、具体流程分析 1、得到cameralist和对应的静态信息 目录如下: 重点代码分析: 启动相机前,先要通过getCameraIdList获取camera的个数以及id,然后可以通过getCameraCharacteristics获取对应id camera的capabilities(静态信息)进行一些openCamera前的…...
【HTML-16】深入理解HTML中的块元素与行内元素
HTML元素根据其显示特性可以分为两大类:块元素(Block-level Elements)和行内元素(Inline Elements)。理解这两者的区别对于构建良好的网页布局至关重要。本文将全面解析这两种元素的特性、区别以及实际应用场景。 1. 块元素(Block-level Elements) 1.1 基本特性 …...

c#开发AI模型对话
AI模型 前面已经介绍了一般AI模型本地部署,直接调用现成的模型数据。这里主要讲述讲接口集成到我们自己的程序中使用方式。 微软提供了ML.NET来开发和使用AI模型,但是目前国内可能使用不多,至少实践例子很少看见。开发训练模型就不介绍了&am…...
[Java恶补day16] 238.除自身以外数组的乘积
给你一个整数数组 nums,返回 数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法,且在 O(n) 时间复杂度…...
Java线上CPU飙高问题排查全指南
一、引言 在Java应用的线上运行环境中,CPU飙高是一个常见且棘手的性能问题。当系统出现CPU飙高时,通常会导致应用响应缓慢,甚至服务不可用,严重影响用户体验和业务运行。因此,掌握一套科学有效的CPU飙高问题排查方法&…...

Linux 内存管理实战精讲:核心原理与面试常考点全解析
Linux 内存管理实战精讲:核心原理与面试常考点全解析 Linux 内核内存管理是系统设计中最复杂但也最核心的模块之一。它不仅支撑着虚拟内存机制、物理内存分配、进程隔离与资源复用,还直接决定系统运行的性能与稳定性。无论你是嵌入式开发者、内核调试工…...

免费PDF转图片工具
免费PDF转图片工具 一款简单易用的PDF转图片工具,可以将PDF文件快速转换为高质量PNG图片。无需安装复杂的软件,也不需要在线上传文件,保护您的隐私。 工具截图 主要特点 🚀 快速转换:本地转换,无需等待上…...