力扣:63. 不同路径 II(Python3)

题目:

一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish”)。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径?

网格中的障碍物和空位置分别用 1 和 0 来表示。

来源:力扣(LeetCode)
链接:力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

示例:

示例 1:

 

输入:obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出:2
解释:3x3 网格的正中间有一个障碍物。 从左上角到右下角一共有 2 条不同的路径: 1. 向右 -> 向右 -> 向下 -> 向下 2. 向下 -> 向下 -> 向右 -> 向右


示例 2:

 

输入:obstacleGrid = [[0,1],[0,0]]
输出:1

解法:

创建m*n的表格,m是obstacleGrid的行数,n是obstacleGrid的列数。表格第1行、列初始化为1,如果第1行、列有障碍,那么从此位置开始及后面的所有位置都置为0,表示此路不通,其它位置初始化为-1。

然后遍历表格右下角区域(去除第1行、列),每个位置更新为上面和左边的和,障碍不更新,最后返回右下角值。

代码:

class Solution:def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:m = len(obstacleGrid)n = len(obstacleGrid[0])f = [[1] * n] + [[1] + [-1] * (n - 1) for _ in range(m - 1)]flag1 = flag2 = 0for index1, r in enumerate(obstacleGrid):for index2, c in enumerate(r):if index1 == 0:if flag1 == 1:f[index1][index2] = 0elif c == 1:flag1 = 1f[index1][index2] = 0flag2 = 1 if index2 == 0 else flag2else:if index2 == 0:if flag2 == 1:f[index1][index2] = 0elif c == 1:flag2 = 1f[index1][index2] = 0else:if c == 1:f[index1][index2] = 0for i in range(1, m):for j in range(1, n):if f[i][j] != 0:f[i][j] = f[i - 1][j] + f[i][j - 1]return f[m - 1][n - 1]

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/91273.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

淘宝搜索店铺列表API:关键字搜索店铺信息 获取店铺主页 店铺所在地 服务评级

接口名称:item_search_seller 基本功能介绍 该API可以通过传入关键字,获取到淘宝商城的店铺列表,支持翻页显示。指定参数page获取到指定页的数据。返回的店铺信息包括:店铺名、店铺ID、店铺主页、宝贝图片、掌柜名字、店铺所在地…

Python爬虫的应用场景与技术难点:如何提高数据抓取的效率与准确性

作为专业爬虫程序员,我们在数据抓取过程中常常面临效率低下和准确性不高的问题。但不用担心!本文将与大家分享Python爬虫的应用场景与技术难点,并提供一些实际操作价值的解决方案。让我们一起来探索如何提高数据抓取的效率与准确性吧&#xf…

【广州华锐互动】物联网工程VR虚拟课件有哪些特色?

物联网工程VR虚拟课件由广州华锐互动制作,是一种利用虚拟现实技术,将物联网的概念和应用场景通过模拟的方式呈现给学生的教学工具。相比传统的教学方式,物联网工程VR虚拟课件具有以下特色: 1.交互性强 物联网工程VR虚拟课件可以让…

选择最适合自己的NIO, 一探流技术

目录 一、Channel1、FileChannel代码示例2、DatagramChannel代码示例3、SocketChannel 和 ServerSocketChannel代码示例 二、Buffer1、ByteBuffer示例代码2、CharBuffer示例代码3、ShortBuffer、IntBuffer、LongBuffer、FloatBuffer、DoubleBuffer 等示例代码 三、Selector1、S…

转行软件测试四个月学习,第一次面试经过分享

我是去年上半年从销售行业转行到测试的,从销售公司辞职之后选择去培训班培训软件测试,经历了四个月左右的培训,在培训班结课前两周就开始投简历了,在结课的时候顺利拿到了offer。在新的公司从事软件测试工作已经将近半年有余&…

贝锐蒲公英:助力企业打造稳定高效的智能安防监控网络

随着技术的快速发展和物联网的普及,企业面临着许多安全威胁和风险,如盗窃、入侵、信息泄露等,企业需要建立安防监控系统来保护其资产、员工和业务运营的安全。 然而,企业在搭建安防监控系统的过程中,可能会面临一些难…

手机的发展历史

目录 一.人类的通信方式变化 二.手机对人类通信的影响 三.手机的发展过程 四.手机对现代人的影响 一.人类的通信方式变化 人类通信方式的变化是一个非常广泛和复杂的话题,随着技术的进步和社会的发展,人类通信方式发生了许多重大的变化。下面是一些主…

python技术栈 之 单元测试中mock的使用

一、什么是mock? mock测试就是在测试过程中,对于某些不容易构造或者不容易获取的对象,用一个虚拟的对象来创建以便测试的测试方法。 二、mock的作用 特别是开发过程中上下游未完成的工序导致当前无法测试,需要虚拟某些特定对象…

fiddler抓包工具的用法以及抓取手机报文定位bug

前言: fiddler抓包工具是日常测试中常用的一种bug定位工具 一 抓取https报文步骤 使用方法: 1 首先打开fiddler工具将证书导出 点击TOOLS------Options------Https-----Actions---选中第二个选项 2 把证书导出到桌面后 打开谷歌浏览器 设置---高级…

数据结构算法--2 冒泡排序,选择排序,插入排序

基础排序算法 冒泡排序 思想就是将相邻元素两两比较,当一个元素大于右侧相邻元素时,交换他们的位置,小于右侧元素时,位置不变,最终序列中的最大元素,像气泡一样,到了最右侧。 这时冒泡排序第一…

分类预测 | MATLAB实现CNN-BiGRU-Attention多输入分类预测

分类预测 | MATLAB实现CNN-BiGRU-Attention多输入单输出分类预测 目录 分类预测 | MATLAB实现CNN-BiGRU-Attention多输入单输出分类预测预测效果基本介绍模型描述程序设计参考资料 预测效果 基本介绍 Matlab实现CNN-BiGRU-Attention多特征分类预测,卷积双向门控循环…

SpringBoot系列---【SpringBoot在多个profiles环境中自由切换】

SpringBoot在多个profiles环境中自由切换 1.在resource目录下新建dev,prod两个目录,并分别把dev环境的配置文件和prod环境的配置文件放到对应目录下,可以在配置文件中指定激活的配置文件,也可以默认不指定。 2.在pom.xml中最后位置…

解析TCP/IP协议的分层模型

了解ISO模型:构建通信的蓝图 为了促进网络应用的普及,国际标准化组织(ISO)引入了开放式系统互联(Open System Interconnect,OSI)模型。这个模型包括了七个层次,从底层的物理连接到顶…

SQL | 注释

2-注释 2.1-单行注释 select prod_name -- 这是一条行内注释 from products; 使用两个连字符(-- ) 放在行内,两个连字符后的内容即为注释内容。 # 这是一条注释 select prod_name from products; 这种注释方式可能有些数据库不支持,所以使用前应该…

Visual Studio 2022 如何关闭左侧绿色条的点击事件,避免误触?

如图,文本编辑器左侧的绿条,很容易误触,真是神烦!点一下就会弹出这个差异框。 我也不知道这个绿色的条叫什么,烦了好久都没有找到怎么关闭它! 是叫 git 状态条?git 差异条?git 更改…

面试热题(两数之和)

给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下标。 你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。 你可以按任意顺序返回答…

aspose 使用ftl模板生成word和pdf

1 先找到word模板,用${},替换变量,保存,然后另存为xml,最后把xml后缀改成ftl。 如下图: word 模板文件 ftl模板文件如下: 2 代码生成 下面函数将ftl填充数据,并生成word和pdf /*** * param dataMap 模板…

No view found for id 0x7f0901c3 for fragment解决以及线上bug排查技巧

情景再现 开发这么久,不知道你们是否也经历过这样的情况,测试或者用户,反馈app闪退,结果你自己打开开发工具,去调试,一切正常,然后闪退还是存在,只是在开发环境中不能重现。这种情况…

CentOS系统环境搭建(九)——centos系统下使用docker部署项目

centos系统环境搭建专栏🔗点击跳转 关于Docker-compose安装请看CentOS系统环境搭建(三)——Centos7安装Docker&Docker Compose,该文章同样收录于centos系统环境搭建专栏。 Centos7部署项目 采用前后端分离的形式部署。使用Do…

echarts多条折线图

代码 <template><div><!-- 折线图 --><div id"average-score1" class"risk-percent" /></div> </template><script> import * as echarts from "echarts";export default {name: "StrategicRis…