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

代码随想录学习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.不同路径 题目链接 讲解链接 动归五部曲&#xff1a; 1.确定dp数组及其下标的含义&#xff1a;dp[i][j]的含义是从(0, 0)走到(i, j)所需的步数&#xff1b; 2.确定递推公式&#xff1a;因为只能往右或者往下&#xff0c;所以dp[i][j] dp[i - 1][j] dp[i][j - 1]。 3.…...

由于找不到MSVCP120D.dll,无法继续执行代码。重新安装程序可能会解决此问题

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

【前端】输入时字符跳动动画实现

输入时字符跳动动画实现 在前端开发中&#xff0c;为了提升用户体验&#xff0c;我们经常需要为用户的交互行为提供即时的反馈。这不仅让用户知道他们的操作有了响应&#xff0c;还可以让整个界面看起来更加生动、有趣。本文将通过一个简单的例子讲解如何实现在用户输入字符时…...

C语言面试重点问题

1. 冒泡排序法 2. strlen、strcpy、strcat、strcmp的用法和原理 3. 大小端的区分 3.1 主函数区分大小端 #include <stdio.h>int main(void) {int num 0x11223344;char *p (char *)&num;if (0x11 *p){printf("大端!\n");}else if (0x44 *p){printf(…...

antlr4略解

文章目录 1. antlr4是用来干什么的&#xff1f;2. 什么是lexer和parser&#xff1f;3. 使用antlr4生成某语言的lexer和parser的具体过程4. 其他 1. antlr4是用来干什么的&#xff1f; 是用来生成某语言lexer和parser的。 通俗点说&#xff0c;就是输入一个语言的规则描述文件&…...

超级好用的C++实用库之文件目录操作

&#x1f4a1; 需要该C实用库源码的大佬们&#xff0c;可扫码关注文章末尾的微信公众号二维码&#xff0c;或搜索微信公众号“希望睿智”。添加关注后&#xff0c;输入消息“超级好用的C实用库”&#xff0c;即可获得源码的下载链接。 概述 文件和目录操作是操作系统层面上的基…...

结合kimi chat的爬虫实战思路

背景 想钻研一下项目组件&#xff0c;找找之后的学习方向。不能自以为是&#xff0c;所以借着网开源项目网站上公布的项目内容看一下&#xff0c;那些是我可以努力去学习的&#xff08;入门的&#xff09;。首先需要获取相关内容&#xff0c;于是爬取整理。 任务1&#xff1a…...

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&#xff0c;但…...

LeetCode热题100|动态规划Part.1|70.爬楼梯、118.杨辉三角、198.打家劫舍

70.爬楼梯 代码随想录原题&#xff0c;看这篇文章&#xff1a;C动态规划Part.1|动态规划理论基础、509.斐波那契数、70.爬楼梯、746.使用最小花费爬楼梯 118.杨辉三角 题目链接&#xff1a;118.杨辉三角 一刷代码 时间复杂度和空间复杂度都造到 O ( n u m R o w s 2 ) O(num…...

python 根据网址和关键词批量下载影像

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

爬虫-无限debug场景 解决方式

解决无限debug 场景1 1. 鼠标右键 选择 continue to here&#xff08;此处不停留&#xff09;2. 鼠标右键 选择 edite breakpoint 设置 10 保证条件不成立 这行永远不执行3.方法置空 1. 方法调用加断点2. 控制台 setInterval function name() {}4. 替换文件 5. hoo…...

[链表专题]力扣206, 203, 19

1. 力扣206 : 反转链表 (1). 题 : 图略 给你单链表的头节点 head &#xff0c;请你反转链表&#xff0c;并返回反转后的链表。示例 1&#xff1a;输入&#xff1a;head [1,2,3,4,5] 输出&#xff1a;[5,4,3,2,1] 示例 2&#xff1a;输入&#xff1a;head [1,2] 输出&#x…...

秋招后端开发面试题 - MySQL基础

目录 MySQL基础前言面试题MySQL 基础篇Mysql 的基础架构&#xff1f;MySQL 的长连接和短连接长连接引起的异常重启问题&#xff1f;说一下 MySQL 执行一条查询语句的内部执行过程&#xff1f;MySQL 查询缓存的功能有何优缺点&#xff1f;MySQL 的常用引擎都有哪些&#xff1f;I…...

力扣每日一题113:路径总和||

题目 中等 给你二叉树的根节点 root 和一个整数目标和 targetSum &#xff0c;找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。 叶子节点 是指没有子节点的节点。 示例 1&#xff1a; 输入&#xff1a;root [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSu…...

Thinkphp5 中常见的session 操作方法

在 ThinkPHP 框架中&#xff0c;session 是用于在多个页面或请求之间存储用户信息的机制。以下是在 ThinkPHP 中进行 session 常见操作的一些示例&#xff1a; 启动 Session 在 ThinkPHP 中&#xff0c;通常不需要手动启动 Session&#xff0c;因为框架会在应用启动时自动处理…...

inBuilder 低代码平台新特性推荐 - 第十八期

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

部署xwiki服务需要配置 hibernate.cfg.xml如何配置?

1. 定位 hibernate.cfg.xml 文件 首先&#xff0c;确保您可以在 Tomcat 的 XWiki 部署目录中找到 hibernate.cfg.xml 文件&#xff1a; cd /opt/tomcat/latest/webapps/xwiki/WEB-INF ls -l hibernate.cfg.xml如果文件存在&#xff0c;您可以继续编辑它。如果不存在&#xff…...

1376:信使(msner)

【解题思路】 每个哨所是一个顶点&#xff0c;哨所与哨所之间的通信线路为边&#xff0c;两哨所间通讯花费的时间为边的权值。记第一个哨所为顶点s&#xff0c;信息从第一个哨所传递到表示为顶点x的某哨所可能有多条路径&#xff0c;每条传送路径有一个花费的时间&…...

Hadoop3:HDFS的架构组成

一、官方文档 我这里学习的是Hadoop3.1.3版本&#xff0c;所以&#xff0c;查看的也是3.1.3版本的文档 Architecture模块最下面 二、HDFS架构介绍 HDFS架构的主要组成部分&#xff0c;是一下四个部分 1、NameNode(NN) 就是Master节点&#xff0c;它是集群管理者。 1、管…...

P2910 [USACO08OPEN] Clear And Present Danger S

Problem: P2910 [USACO08OPEN] Clear And Present Danger S 文章目录 思路解题方法复杂度Code 思路 这是一个图论问题&#xff0c;我们需要找到从一个城市到另一个城市的最短路径。我们可以使用Floyd-Warshall算法来解决这个问题。首先&#xff0c;我们需要构建一个距离矩阵&am…...

网络编程(Modbus进阶)

思维导图 Modbus RTU&#xff08;先学一点理论&#xff09; 概念 Modbus RTU 是工业自动化领域 最广泛应用的串行通信协议&#xff0c;由 Modicon 公司&#xff08;现施耐德电气&#xff09;于 1979 年推出。它以 高效率、强健性、易实现的特点成为工业控制系统的通信标准。 包…...

【根据当天日期输出明天的日期(需对闰年做判定)。】2022-5-15

缘由根据当天日期输出明天的日期(需对闰年做判定)。日期类型结构体如下&#xff1a; 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 发行版&#xff…...

相机从app启动流程

一、流程框架图 二、具体流程分析 1、得到cameralist和对应的静态信息 目录如下: 重点代码分析: 启动相机前,先要通过getCameraIdList获取camera的个数以及id,然后可以通过getCameraCharacteristics获取对应id camera的capabilities(静态信息)进行一些openCamera前的…...

【HTML-16】深入理解HTML中的块元素与行内元素

HTML元素根据其显示特性可以分为两大类&#xff1a;块元素(Block-level Elements)和行内元素(Inline Elements)。理解这两者的区别对于构建良好的网页布局至关重要。本文将全面解析这两种元素的特性、区别以及实际应用场景。 1. 块元素(Block-level Elements) 1.1 基本特性 …...

c#开发AI模型对话

AI模型 前面已经介绍了一般AI模型本地部署&#xff0c;直接调用现成的模型数据。这里主要讲述讲接口集成到我们自己的程序中使用方式。 微软提供了ML.NET来开发和使用AI模型&#xff0c;但是目前国内可能使用不多&#xff0c;至少实践例子很少看见。开发训练模型就不介绍了&am…...

[Java恶补day16] 238.除自身以外数组的乘积

给你一个整数数组 nums&#xff0c;返回 数组 answer &#xff0c;其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法&#xff0c;且在 O(n) 时间复杂度…...

Java线上CPU飙高问题排查全指南

一、引言 在Java应用的线上运行环境中&#xff0c;CPU飙高是一个常见且棘手的性能问题。当系统出现CPU飙高时&#xff0c;通常会导致应用响应缓慢&#xff0c;甚至服务不可用&#xff0c;严重影响用户体验和业务运行。因此&#xff0c;掌握一套科学有效的CPU飙高问题排查方法&…...

Linux 内存管理实战精讲:核心原理与面试常考点全解析

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

免费PDF转图片工具

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