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

代码随想录算法训练营第二十九天| 62.不同路径、63. 不同路径 II

写代码的第二十九天
继续动归!!!

62.不同路径

思路

解决问题1:dp[i][j]的的含义是什么?本题给的是一个二维的表,判断从左上角走到右下角有多少种路径,所以dp应该是二维数组,dp[i][j]代表的是从起始点开始走到i,j位置时的路径数量。
解决问题2:递推公式是什么?也就是dp[i][j]=?本题中只能向右向下走,所以(i,j)位置的值只能由其上方或者左侧的dp值决定也就是(i-1,j)和(i,j-1)两个位置的值决定。dp[i-1][j]代表(i,j)位置上方的路径数量,dp[i][j-1]代表 (i,j)位置左侧的路径数量,所以dp[i][j]=dp[i-1][j]+dp[i][j-1]。
解决问题3:dp数组如何初始化?最开始的想法就是只对初始位置进行初始化,但是我们根据递推公式可以看见,如果我们想要第i位的值就需要i-1位的值,如果i=1,那么就需要i=0时的值,也就是第一行的全部值,所以初始化第一行也就是i=0这一行的所有值,同理也需要初始化j=0这一行的全部值。dp[0][j] = 1,dp[i][0]=1,为什么初始化为1,是因为在第一行中他只能向下走,只有一条路径,同理第一列中只能向右走,只有一条路径,所以初始化为1.
解决问题4:如何确定遍历顺序?我们是从左上到右下的路径,所以从左到右从上到下进行遍历。
解决问题5:输出搭配数组。为了判断是否和题意一致,方便后续改错。
正确代码:这个题中对我难度最大的是dp数组的初始化,笑死没想过该怎么初始化。最后需要注意输出的是dp[m-1][n-1],因为下标是从0开始的。第一行第一列已经处理完了,所以下面的range范围都是从1开始的。

class Solution:def uniquePaths(self, m: int, n: int) -> int:dp = [[0 for _ in range(n)] for _ in range(m)]for i in range(m):dp[i][0] = 1for j in range(n):dp[0][j] = 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[m-1][n-1]

63. 不同路径 II

思路

这个题和上一个题的区别在于在这个m*n的矩阵中是有障碍物的,也就是说遇到了障碍要直接越过,根据已经给出了二维数组,不是0的就是障碍物;如果障碍在第一行,那么遇到了障碍物之后的点都不能走了,因为只能向右向下,右侧遇到障碍物了只能向下走在向右走,不能向上走,所以当第一行有障碍物的时候,后面所有的点不会再走过,同理,当第一列有障碍物的时候只能向右走在向下,也就是当前障碍物下面的点都不会再走过。
根据上面的分析可以知道,本题的代码和上面题的代码区别在于,初始化第一行和第一列的dp数组,遇到障碍之前的都是1,从障碍开始的值都是零。如果在内部发现了障碍,那么当前这个障碍的点dp[i][j]就不应该存储任何数值,此路不通,所以应该将dp[i][j]赋值为0.
正确代码:m代表行,n代表列!

class Solution:def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:m = len(obstacleGrid)n = len(obstacleGrid[0])dp = [[0 for _ in range(n)] for _ in range(m)]for i in range(m):if obstacleGrid[i][0] == 0:dp[i][0] = 1else:breakfor j in range(n):if obstacleGrid[0][j] == 0:dp[0][j] = 1else:breakfor i in range(1,m):for j in range(1,n):if obstacleGrid[i][j] == 1:dp[i][j] = 0else:dp[i][j] = dp[i-1][j] + dp[i][j-1]return dp[m-1][n-1]

相关文章:

代码随想录算法训练营第二十九天| 62.不同路径、63. 不同路径 II

写代码的第二十九天 继续动归!!! 62.不同路径 思路 解决问题1:dp[i][j]的的含义是什么?本题给的是一个二维的表,判断从左上角走到右下角有多少种路径,所以dp应该是二维数组,dp[i]…...

Go+Redis零基础到用户管理系统API实战_20240730 课程笔记

概述 如果您没有Golang的基础,应该学习如下前置课程。 Golang零基础入门Golang面向对象编程Go Web 基础Go语言开发REST API接口_20240728Go语言操作MySQL开发用户管理系统API教程_20240729Redis零基础快速入门_20231227 基础不好的同学每节课的代码最好配合视频进…...

ScreenAgent:基于LVLM的计算机控制智能体

ScreenAgent : A Vision Language Model-driven Computer Control Agent 论文链接: https://arxiv.org/abs/2402.07945https://arxiv.org/abs/2402.07945IJCAI 2024 1.概述 大型语言模型(LLM),诸如ChatGPT与GPT-4,在自然语言处理领域(涵盖生成、理解及对话等任务)展现出…...

谷粒商城实战笔记-129-商城业务-商品上架-nested数据类型场景

文章目录 扁平化处理扁平化处理导致的检索问题 解决方案:使用 nested 结构 在es的数据类型中有一个nested类型,本讲将重点讨论这个类型。 扁平化处理 PUT my_index/doc/1 {"group" : "fans","user" : [{"first&quo…...

axios请求响应拦截器

目录 axios-拦截器 拦截器的作用 请求拦截器-基本写法: axios请求拦截器-统一设置token 需求: 核心步骤: 关键代码: 响应拦截器-基本写法: axios响应拦截器-统一处理token失效 需求: 核心步骤: 关键代码: axios响应拦截器-数据剥离 需求: 核心步骤: 关键代码: ax…...

Python 中单例模式实现的几种方式

在设计模式中,单例模式是经常被提及和使用的一种模式。它保证一个类只有一个实例,并提供全局访问点。在Python中,有多种实现单例模式的方法。那么,如何选择合适的方法来实现单例模式呢? 单例模式在Python中的几种实现方…...

mysql数据库触发器同步数据

首先检查数据源库是否支持触发器,show ENGINES,如果FEDERATED是NO,表示未开启,如需开启,再mysql配置文件中,添加federated配置到mysqld下面。 一、同服务器不同库触发器同步,这里只举例插入数据…...

Prometheus-v2.45.0+Grafana+邮件告警

目录 普罗米修斯监控架构介绍 Prometheus 监控架构 1. 数据抓取(Scraping) 2. 时序数据库(TSDB) 3. 数据模型 4. PromQL 查询语言 5. 告警(Alerting) 6. Alertmanager 7. 可视化(Visu…...

LeetCode——572. 另一颗树的子树

通过万岁!!! 题目:给你两棵树,然后问subRoot是不是root的子树。也就是root某个节点的所有孩子节点在值和结构上完全与subRoot相同。思路:我的思路比较简单,就是遍历root,遇到root中…...

Spring Boot整合MyBatis-Flex

说明:MyBatis-Flex(官网地址:https://mybatis-flex.com/),是一款数据访问层框架,可实现项目中对数据库的访问,类比MyBatis-Plus。本文介绍,在Spring Boot项目整合MyBatis-Flex。 创…...

重塑未来体验:边缘计算与云原生的完美邂逅

🐇明明跟你说过:个人主页 🏅个人专栏:《未来已来:云原生之旅》🏅 🔖行路有良友,便是天堂🔖 目录 一、引言 1、云原生的兴起 2、边缘计算的兴起 二、边缘计算基础 …...

浅谈基础数论(c++)

目录 一些常见的符号表示阶乘定理 快速幂模板题代码扩展:矩阵快速幂主要作用 欧拉函数扩展积性函数 欧拉函数求法筛选法求欧拉函数(积性函数) 扩展欧几里得裴蜀定理问题分析代码 问题分析 同余与逆元如何求解逆元扩展欧几里得 例题讲解X-Magi…...

jdk 17新特性 sealed 关键字

通俗理解 sealed 关键字就是给对象继承加了权限控制一样,你必须在我的规则范围内才可以继承我的类 使用 permits 关键字控制允许哪些子类继承 子类必须加以下三个关键字: final 最终继承类(继承到这个类就不允许再往下继承了)n…...

在仪器计量校准中,无尘车间洁净室检测有哪些方法和流程?

仪器计量校准行业内,无尘车间洁净室检测可以说是较为热门的业务,因为其预算高,且检测流程不是太繁琐,很多仪器计量校准机构也是设立相关实验室,专门处理相关仪器的检测。不过虽然许多机构想要涉足该领域,但…...

【跨时代】第四次工业革命彻底来袭!什么是AI+

你有没有一种很割裂的感觉,就是在短视频里,AI已经要改变全世界了 但自己一用,却发现只能和AI聊聊天 画几张图 难道是姿势不对?但具体是哪里不对呢。 作为一个老牌程序员,我前面分享了很多计算机相关内容,总…...

前端性能优化-纲领篇

前端性能优化 本模块将梳理前端性能优化的相关知识点 从浏览器输入 URL 到页面展示发生了什么 完整版请查看[Browser_网络_安全]的部分,这里只是简单的梳理一下 DNS 解析TCP 连接浏览器发出 HTTP 请求服务器处理请求并返回 HTTP 报文浏览器解析渲染页面 性能优…...

深度学习-----------数值稳定性

目录 神经网络的梯度数值稳定性的常见两个问题例子:MLP 梯度爆炸梯度爆炸的问题 梯度消失梯度消失的问题 总结模型初始化和激活函数让训练更加稳定让每层的方差是一个常数 权重初始化正向均值和方差正向均值正向方差 反向均值和方差Xavier初始正向和反向的均值和方差…...

SpringBoot项目接口可以承受的调用次数

一个Spring Boot接口能够承受的调用次数主要取决于几个因素,包括但不限于: 服务器硬件:CPU、内存、硬盘I/O速度以及网络带宽都会直接影响接口的处理能力和并发量。操作系统和JVM配置:操作系统调度策略、JVM的内存分配、垃圾回收机…...

抽象代数精解【8】

文章目录 希尔密码矩阵矩阵基本概念行列式基本概念特殊矩阵关于乘法运算构成群 加解密原理密钥加密函数解密函数 Z 26 上的运算( Z 256 与此类似) Z_{26}上的运算(Z_{256}与此类似) Z26​上的运算(Z256​与此类似&…...

数据结构与算法 - 二叉树

1. 概述 二叉树是这么一种树状结构:每个节点最多有两个孩子,左孩子和右孩子 完全二叉树:是一种二叉树结构,除了最后一层以外,每一层都必须填满,填充时要遵循从左到右 平衡二叉树:是一种二叉树…...

Spring Cloud Gateway如何给一个请求加请求头

在Spring Cloud Gateway中,可以通过编写一个GlobalFilter来给所有请求加请求头,或者通过编写一个SpecificFilter来给特定路径的请求加请求头。 全局过滤器(GlobalFilter)的实现方式如下: Configuration public class…...

chromedriver版本下载地址汇总chromedriver所有版本下载地址汇总国内源下载

谷歌浏览器版本经常会升级,chromedriver 也得下载匹配的版本 chromedriver 114以前版本下载地址https://registry.npmmirror.com/binary.html?pathchromedriver/ windows版本请访问链接:https://blog.csdn.net/FL1768317420/article/details/139712108 …...

Go语言与Windows系统

1.获取屏幕尺寸 源自:Golang通过使用GetSystemMetrics获取系统的分辨率 - 完美代码 (perfcode.com) package mainimport ("syscall""fmt" )const (SM_CXSCREEN uintptr(0) // X Size of screenSM_CYSCREEN uintptr(1) // Y Size of screen …...

JAVA—面向对象编程高级

学习了一定基础后,开始更加深入的学习面向对象,包含static,final两个关键字,面向对象编程三大特征之继承和多态。以及对于抽象类,内部类,接口,枚举,泛型的学习。 目录 1.static (…...

[BJDCTF2020]Mark loves cat1

打开题目 发现这么多链接,以为要一点点去找功能上的漏洞。当你源代码,dirsearch,抓包等等操作之后,发现什么都没有。所以这题又是一道源码泄露题,上GItHack。扫描结果如下 http://63f29a80-e08b-43ae-a6d0-8e70fb02ea…...

微信答题小程序产品研发-用户操作流程设计

在答题小程序中,用户流程是指用户从进入小程序开始,到完成答题、查看结果、进行练习等一系列操作的步骤。 这里我画了一张用户流程图,展示用户在小程序中的主要操作流程。以及对每个步骤的详细说明。这里分两种角色,用户和管理员…...

目标检测——YOLOv10: Real-Time End-to-End Object Detection

YOLOv10是在YOLOv8的基础上,借鉴了RT-DETR的一些创新点改进出来的 标题:YOLOv10: Real-Time End-to-End Object Detection论文:https://arxiv.org/pdf/2405.14458源码:https://github.com/THU-MIG/yolov10 1. 论文介绍 在过去的几…...

堡垒机简单介绍

堡垒机(Bastion Host),也被称为跳板机、跳板服务器或堡垒服务器,是一种在网络安全中扮演重要角色的设备或服务。以下是关于堡垒机的详细介绍: 一、定义与功能 堡垒机是一种用于控制和管理网络安全的重要工具&#xf…...

【星闪开发连载】WS63E 星闪开发板和hi3861开发板的对比

此次星闪开发者体验官活动使用的开发板都是NearLink_DK_WS63E开发板,它和NearLink_DK_WS63开发板的区别在于具有雷达感知功能。从开发板的照片也可以看到WS63E有一个雷达天线接口。 我们把WS63E开发板和hi3861开发板的功能做了简单的对比,见下表。 参数…...

Python接口自动化测试框架(实战篇)-- Jenkins持续集成

文章目录 一、前言二、[Jenkins](https://www.jenkins.io/)2.1、环境搭建2.2、插件准备2.3、创建job2.4、小结2.5、构建策略2.6、报告展示2.7、扩展三、总结一、前言 温馨提示:在框架需要集成jenkins的时候,一定要注意环境切换问题,如果jenkins和开发环境是同样的系统且都有…...