leetcode 63. 不同路径 II
2023.8.9
这题是不同路径I的升级版,在路径上增加了障碍物,有障碍物的地方无法通过。
我的思路依然还是使用动态规划,dp[i][j]的含义依然是到(i,j)这个位置的路径个数。只需要在dp数组中将有障碍物的地方赋为0。大致步骤如下:
- 先进行极端情况判断:当起始位置为障碍物时,无法到达终点,直接返回0。
- 然后对第一行和第一列进行初始化,有障碍物的地方赋为0,无障碍物的地方赋为其左方或者上方的值。
- 用两个for循环递推赋值,递推公式和不同路径I 一样,当前位置的路径个数 = 上方位置路径个数 + 左方位置的路径个数。
代码如下:
class Solution {
public:int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {if(obstacleGrid[0][0] == 1) return 0; //起点就是障碍物int m = obstacleGrid.size();int n = obstacleGrid[0].size();vector<vector<int>> dp(m , vector<int>(n));dp[0][0] = 1;//第一行初始化赋值for(int i=1; i<n; i++){//有障碍物if(obstacleGrid[0][i] == 1) dp[0][i] = 0;//无障碍物else dp[0][i] = dp[0][i-1];}//第一列初始化赋值for(int i=1; i<m; i++){if(obstacleGrid[i][0] == 1) dp[i][0] = 0;else dp[i][0] = dp[i-1][0];}//遍历递推赋值for(int i=1; i<m; i++){for(int j=1; j<n; j++){if(obstacleGrid[i][j] == 1) dp[i][j] = 0; //有障碍物就不用赋值了else dp[i][j] = dp[i-1][j] + dp[i][j-1]; }}return dp[m-1][n-1];}
};
相关文章:
leetcode 63. 不同路径 II
2023.8.9 这题是不同路径I的升级版,在路径上增加了障碍物,有障碍物的地方无法通过。 我的思路依然还是使用动态规划,dp[i][j]的含义依然是到(i,j)这个位置的路径个数。只需要在dp数组中将有障碍物的地方赋为…...
c语言每日一练(5)
前言:每日一练系列,每一期都包含5道选择题,2道编程题,博主会尽可能详细地进行讲解,令初学者也能听的清晰。每日一练系列会持续更新,暑假时三天之内必有一更,到了开学之后,将看学业情…...
pycharm配置conda虚拟环境
📕作者简介:热编程的贝贝,致力于C/C、Java、Python等多编程语言,热爱跑步健身,喜爱音乐的一位博主。 📗本文收录于贝贝的日常汇报系列,大家有兴趣的可以看一看 📘相关专栏深度学习、…...
ubuntu 如何命令行打开系统设置(Wifi,网络,应用程序...)
关于GNOME GNOME 是一个自由、开放源代码的桌面环境,它运行在 Linux 和其他类 UNIX 操作系统上。它是 GNU 项目的一部分,旨在为 Linux 操作系统提供一个现代化、易于使用的用户界面。 GNOME 桌面环境包括许多应用程序,例如文件管理器、文本编…...
MySQL DQL 数据查询
文章目录 1.SELECT 语句2.SELECT 子句3.FROM 子句4.WHERE 子句5.GROUP BY 子句6.HAVING 子句7.ORDER BY 子句8.LIMIT 子句9.DISTINCT 子句10.JOIN 子句11.UNION 子句12.查看数据表记录数13.检查查询语句的执行效率14.查看 SQL 执行时的警告参考文献 1.SELECT 语句 MySQL 的 SE…...
深度学习基础知识笔记
深度学习要解决的问题 1 深度学习要解决的问题2 应用领域3 计算机视觉任务4 视觉任务中遇到的问题5 得分函数6 损失函数7 前向传播整体流程8 返向传播计算方法1 梯度下降 9 神经网络整体架构11 神经元个数对结果的影响12 正则化和激活函数1 正则化2 激活函数 13 神经网络过拟合…...
怎么系统的学习机器学习、深度学习?当然是看书了
目录 前言 内容简介 学完本书,你将能够 作者简介 本书目录 京东自购链接 前言 近年来,机器学习方法凭借其理解海量数据和自主决策的能力,已在医疗保健、 机器人、生物学、物理学、大众消费和互联网服务等行业得到了广泛的应用。自从Ale…...
无涯教程-Perl - binmode函数
描述 此函数设置在区分两者的操作系统上以二进制形式读取和写入FILEHANDLE的格式。非二进制文件的CR LF序列在输入时转换为LF,在LF时在输出时转换为CR LF。这对于使用两个字符分隔文本文件中的行的操作系统(MS-DOS)至关重要,但对使用单个字符的操作系统(Unix,Mac OS,QNX)没有影…...
Spring Boot Maven package时显式的跳过test内容
在pom.xml的编译插件部分显式的增加一段内容: <plugin> <!-- maven打包时,显式的跳过test部分 --><groupId>org.apache.maven.plugins</groupId><artifactId>maven-surefire-plugin</artifactId><version>3.…...
排序算法————基数排序(RadixSort)
基数排序的概念: 什么是基数排序???基数排序是一种和快排、归并、希尔等等不一样的排序...它不需要比较和移动就可以完成整型的排序。它是时间复杂度是O(K*N),空间复杂度是O(KM&…...
leetcode做题笔记75颜色分类
给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。 我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。 必须在不使用库内置的 sort 函数的情况下解决…...
聊一下互联网开源变现
(点击即可收听) 互联网开源变现其实是指通过开源软件或者开放源代码的方式,实现收益或盈利。这种方式越来越被广泛应用于互联网行业 在互联网开源变现的模式中,最常见的方式是通过捐款、广告、付费支持或者授权等方式获利。 例如,有些开源软件…...
PHP日期差计算器,计算两个时间相差 年/月/日
1. 计算两个日期相隔多少年,多少月,多少天示例:laravel框架实现 /*** 天数计算* return \Illuminate\Http\JsonResponse*/public function loveDateCal(){$start_date $this->request(start_date);$end_date $this->request(end_date…...
20230812在WIN10下使用python3将SRT格式的字幕转换为SSA格式
20230812在WIN10下使用python3将SRT格式的字幕转换为SSA格式 2023/8/12 20:58 本文的SSA格式以【Batch Subtitles Converter(批量字幕转换) v1.23】的格式为准! 1、 缘起:网上找到的各种各样的字幕转换软件/小工具都不是让自己完全满意! 【都…...
matlab使用教程(13)—稀疏矩阵创建和使用
使用稀疏矩阵存储包含众多零值元素的数据,可以节省大量内存并加快该数据的处理速度。sparse 是一种属性,可以将该属性分配给由 double 或 logical 元素组成的任何二维 MATLAB 矩阵。通过 sparse 属性,MATLAB 可以: • 仅存储矩…...
UI美工设计的主要职责(合集)
UI美工设计的主要职责1 职责: 1、执行公司的规章制度及专业管理办法; 2、 负责重点项目的原型设计和产品流程设计、视觉设计,优化网站和移动端的设计流程和规范,制定产品 UI/UE规范及文档编写; 3、负责使用PS、AI、illustrator、MarkMan、…...
【前端二次开发框架关于关闭eslint】
前端二次开发框架关于关闭eslint 方法一方法二方法三方法四:以下是若想要关闭项目中的部分代码时: 方法一 在vue.config.js里面进行配置: module.exports {lintOnSave:false,//是否开启eslint保存检测 ,它的有效值为 true || false || err…...
Scractch3.0_Arduino_ESP32_学习随记_蓝牙键盘(三)
C02蓝牙键盘 目的器材程序联系我们 目的 通过C02实现蓝牙键盘 器材 硬件: 齐护机器人C02 购买地址 软件: scratch3.0 下载地址:官网下载 程序 在P5口连接按钮模块。 蓝牙键盘组合按键动作的实现。 当对应按键按下时模拟键盘动作,先按下ctrl然后按下对应组合键…...
Spark2.2出现异常:ERROR SparkUI: Failed to bind SparkUI
详细错误信息如下: 复制代码 19/03/19 11:04:18 INFO util.log: Logging initialized 5402ms 19/03/19 11:04:18 INFO server.Server: jetty-9.3.z-SNAPSHOT 19/03/19 11:04:18 INFO server.Server: Started 5604ms 19/03/19 11:04:18 WARN util.Utils: Service ‘S…...
LeetCode 2811. Check if it is Possible to Split Array【脑筋急转弯;前缀和+动态规划或记忆化DFS】中等
本文属于「征服LeetCode」系列文章之一,这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁,本系列将至少持续到刷完所有无锁题之日为止;由于LeetCode还在不断地创建新题,本系列的终止日期可能是永远。在这一系列刷题文章…...
SpringBoot-17-MyBatis动态SQL标签之常用标签
文章目录 1 代码1.1 实体User.java1.2 接口UserMapper.java1.3 映射UserMapper.xml1.3.1 标签if1.3.2 标签if和where1.3.3 标签choose和when和otherwise1.4 UserController.java2 常用动态SQL标签2.1 标签set2.1.1 UserMapper.java2.1.2 UserMapper.xml2.1.3 UserController.ja…...
Spring Boot面试题精选汇总
🤟致敬读者 🟩感谢阅读🟦笑口常开🟪生日快乐⬛早点睡觉 📘博主相关 🟧博主信息🟨博客首页🟫专栏推荐🟥活动信息 文章目录 Spring Boot面试题精选汇总⚙️ **一、核心概…...
解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错
出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上,所以报错,到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本,cu、torch、cp 的版本一定要对…...
今日科技热点速览
🔥 今日科技热点速览 🎮 任天堂Switch 2 正式发售 任天堂新一代游戏主机 Switch 2 今日正式上线发售,主打更强图形性能与沉浸式体验,支持多模态交互,受到全球玩家热捧 。 🤖 人工智能持续突破 DeepSeek-R1&…...
JVM暂停(Stop-The-World,STW)的原因分类及对应排查方案
JVM暂停(Stop-The-World,STW)的完整原因分类及对应排查方案,结合JVM运行机制和常见故障场景整理而成: 一、GC相关暂停 1. 安全点(Safepoint)阻塞 现象:JVM暂停但无GC日志,日志显示No GCs detected。原因:JVM等待所有线程进入安全点(如…...
C++八股 —— 单例模式
文章目录 1. 基本概念2. 设计要点3. 实现方式4. 详解懒汉模式 1. 基本概念 线程安全(Thread Safety) 线程安全是指在多线程环境下,某个函数、类或代码片段能够被多个线程同时调用时,仍能保证数据的一致性和逻辑的正确性…...
C++.OpenGL (14/64)多光源(Multiple Lights)
多光源(Multiple Lights) 多光源渲染技术概览 #mermaid-svg-3L5e5gGn76TNh7Lq {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-3L5e5gGn76TNh7Lq .error-icon{fill:#552222;}#mermaid-svg-3L5e5gGn76TNh7Lq .erro…...
Docker 本地安装 mysql 数据库
Docker: Accelerated Container Application Development 下载对应操作系统版本的 docker ;并安装。 基础操作不再赘述。 打开 macOS 终端,开始 docker 安装mysql之旅 第一步 docker search mysql 》〉docker search mysql NAME DE…...
vulnyx Blogger writeup
信息收集 arp-scan nmap 获取userFlag 上web看看 一个默认的页面,gobuster扫一下目录 可以看到扫出的目录中得到了一个有价值的目录/wordpress,说明目标所使用的cms是wordpress,访问http://192.168.43.213/wordpress/然后查看源码能看到 这…...
Rust 开发环境搭建
环境搭建 1、开发工具RustRover 或者vs code 2、Cygwin64 安装 https://cygwin.com/install.html 在工具终端执行: rustup toolchain install stable-x86_64-pc-windows-gnu rustup default stable-x86_64-pc-windows-gnu 2、Hello World fn main() { println…...
