leetcode日记(51)不同路径Ⅱ

devtools/2024/11/15 8:11:58/

和上一道题(无障碍物的最短路径)很像,但事实上比上一题多了优化方法

根据上一题改的代码如下,添加了对障碍物的判定,如果有障碍物则将数组值设为0。

class Solution {
public:int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {int m=obstacleGrid.size();int n=obstacleGrid[0].size();int a[m][n];for(int i=0;i<m;i++) for(int j=0;j<n;j++) a[i][j]=0;for(int i=0;i<n&&obstacleGrid[0][i]==0;i++) a[0][i]=1;for(int i=0;i<m&&obstacleGrid[i][0]==0;i++) a[i][0]=1;for(int i=1;i<m;i++){for(int j=1;j<n;j++){if(obstacleGrid[i][j]==0) a[i][j]=a[i-1][j]+a[i][j-1];}}return a[m-1][n-1];}
};

然后看了答案,答案说可以使用滚动数组优化,就又去搜了一下滚动数组的使用方法。

参考了一下63. 不同路径 II(C++)---动态规划解题(并进行滚动数组思想优化),琢磨了一下代码,原理是将上面的二维数组优化成了一维,记录开始位置到达每一行末尾的路径数。如有障碍物则直接将数目设为0,然后继续遍历这一行;没有障碍物就将数目设为上一行路径数加上这一行路径数。

需要注意的是遍历方向,按照上面这种思路需要先遍历列再遍历行,如果先遍历行,如果上一行末尾有障碍物那么下一行就通过不了。

class Solution {
public:int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {int m=obstacleGrid.size();int n=obstacleGrid[0].size();vector<int> a(m);a[0]=!obstacleGrid[0][0];for(int j=0;j<n;j++){for(int i=0;i<m;i++){if(obstacleGrid[i][j]) a[i]=0;else if(i>0&&!obstacleGrid[i-1][j]) a[i]+=a[i-1];cout<<i<<" "<<j<<" "<<a[i]<<endl;}}return a[m-1];}
};

感觉这个方法很熟悉,前几天的一道题也用过这种思路(虽然也是看答案知道的就是了)


http://www.ppmy.cn/devtools/86434.html

相关文章

golang websocket 手写研究机制

// 处理ws请求 func WsHandler(w http.ResponseWriter, r *http.Request, id string) {var conn *websocket.Connvar err errorpingTicker : time.NewTicker(time.Second * 10)conn, err wsupgrader.Upgrade(w, r, nil)if err ! nil {log.Printf("Failed to set websocke…

CANoe在使用时碰到的一些很少见的Bug

CANoe作为一款成熟且稳定的总线仿真与测试工具&#xff0c;深受汽车工程师们的喜爱。CANoe虽然稳定&#xff0c;但作为一个软件来说&#xff0c;在使用中总会出现一些或大或小的Bug。最近全球范围内的大规模蓝屏事件&#xff0c;是由某个安全软件引起的。而很多CANoe使用者最近…

钉钉小程序内部跳转

1.跳转小程序携带参数 //触发跳转事件的方法 handleJump() {dd.navigateToMiniProgram({// 需要跳转的小程序的appIdappId: XXXXXXXXXXXXXXX,//需要跳转的小程序的页面path: pages/func/camera/camera,//参数extraData: {isOutSide: "1"},success: (res) > {cons…

ComfyUI插件:ComfyUI Impact 节点(四)

前言&#xff1a; 学习ComfyUI是一场持久战&#xff0c;而 ComfyUI Impact 是一个庞大的模块节点库&#xff0c;内置许多非常实用且强大的功能节点 &#xff0c;例如检测器、细节强化器、预览桥、通配符、Hook、图片发送器、图片接收器等等。通过这些节点的组合运用&#xff0…

昇思MindSpore 应用学习-基于MindSpore的GPT2文本摘要

基于MindSpore的GPT2文本摘要 --AI代码解析 数据集加载与处理 数据集加载 本次实验使用的是nlpcc2017摘要数据&#xff0c;内容为新闻正文及其摘要&#xff0c;总计50000个样本。 from mindnlp.utils import http_get # 导入http_get模块&#xff0c;用于下载数据集# downl…

使用Echarts来实现数据可视化

目录 一.什么是ECharts? 二.如何使用Springboot来从后端给Echarts返回响应的数据&#xff1f; eg:折线图&#xff1a; ①Controller层&#xff1a; ②service层&#xff1a; 一.什么是ECharts? ECharts是一款基于JavaScript的数据可视化图标库&#xff0c;提供直观&…

【echarts】 柱状图,最后带“竖线”

具体&#xff1a; https://echarts.zhangmuchen.top/#/detail?cid28ea6-0601-e9f5-9cc29-c022b758 let data [{value: 0,name: 数据格式一},{value: 55,name: 数据格式二},{value: 66,name: 数据格式三},{value: 75,name: 数据格式四},{value: 20,name: 数据格式五}];getAr…

FastAPI(七十八)实战开发《在线课程学习系统》接口开发-- 评论

源码见&#xff1a;"fastapi_study_road-learning_system_online_courses: fastapi框架实战之--在线课程学习系统" 梳理下思路 1.判断是否登录 2.课程是否存在 3.如果是回复&#xff0c;查看回复是否存在 4.是否有权限 5.发起评论 首先新增pydantic模型 class Cour…