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

LeetCode 面试题 08.02. 迷路的机器人

文章目录

  • 一、题目
  • 二、C# 题解

一、题目

  设想有个机器人坐在一个网格的左上角,网格 r 行 c 列。机器人只能向下或向右移动,但不能走到一些被禁止的网格(有障碍物)。设计一种算法,寻找机器人从左上角移动到右下角的路径。

在这里插入图片描述
  网格中的障碍物和空位置分别用 10 来表示。

  返回一条可行的路径,路径由经过的网格的行号和列号组成。左上角为 0 行 0 列。如果没有可行的路径,返回空数组。

示例 1:

输入:
[
[0,0,0],
[0,1,0],
[0,0,0]
]
输出: [[0,0],[0,1],[0,2],[1,2],[2,2]]
解释:
输入中标粗的位置即为输出表示的路径,即
0行0列(左上角) -> 0行1列 -> 0行2列 -> 1行2列 -> 2行2列(右下角)

说明:r 和 c 的值均不超过 100。

  点击此处跳转题目。

二、C# 题解

  可以使用回溯解,这里用动态规划好些。使用 path 记录当前位置是否能到达终点,因此从终点开始向起点方向进行判断,当前 path[i, j] 的值为 obstacleGrid[i][j] == 0 && (path[i + 1, j] || path[i, j + 1]),即当前无障碍物且后方有可到达路径。对于边界情况需要优先特殊处理,以免数组越界。

public class Solution {public IList<IList<int>> PathWithObstacles(int[][] obstacleGrid) {int r = obstacleGrid.Length, c = obstacleGrid[0].Length;IList<IList<int>> ans = new List<IList<int>>();bool[,] path = new bool[r, c]; // 记录可到达路径if (obstacleGrid[r - 1][c - 1] == 1) return ans; // 如果终点有障碍物,直接返回空/* 动态规划求解可到达路径 */path[r - 1, c - 1] = true;// 最右方边界判断for (int j = c - 2; j >= 0; j--)if (path[r - 1, j + 1] && obstacleGrid[r - 1][j] == 0)path[r - 1, j] = true;// 最下方边界判断for (int i = r - 2; i >= 0; i--)if (path[i + 1, c - 1] && obstacleGrid[i][c - 1] == 0)path[i, c - 1] = true;// 中间判断for (int i = r - 2; i >= 0; i--)for (int j = c - 2; j >= 0; j--)if (obstacleGrid[i][j] == 0 && (path[i + 1, j] || path[i, j + 1]))path[i, j] = true;if (!path[0, 0]) return ans; // 如果起点没有可到达路径,返回空/* 求解一条可到达路径 */int x = 0, y = 0;while (x != r - 1 || y != c - 1) {ans.Add(new List<int> { x, y });      // 添加路径if (y + 1 < c && path[x, y + 1]) y++; // 优先向右走else x++;                             // 右方堵住则向下走}ans.Add(new List<int> { r - 1, c - 1 });  // 添加终点return ans;}
}
  • 时间:132 ms,击败 100.00% 使用 C# 的用户
  • 内存:42.62 MB,击败 100.00% 使用 C# 的用户

相关文章:

LeetCode 面试题 08.02. 迷路的机器人

文章目录 一、题目二、C# 题解 一、题目 设想有个机器人坐在一个网格的左上角&#xff0c;网格 r 行 c 列。机器人只能向下或向右移动&#xff0c;但不能走到一些被禁止的网格&#xff08;有障碍物&#xff09;。设计一种算法&#xff0c;寻找机器人从左上角移动到右下角的路径…...

画CMB天图使用Planck配色方案

使用Planck的配色方案&#xff1a; 全天图&#xff1a; 或者方形图&#xff1a; 使用下面设置即可&#xff1a; import pspy, pixell from pspy.so_config import DEFAULT_DATA_DIR pixell.colorize.mpl_setdefault("planck")此方法不会改变matplotlib默认配色方案…...

成都瀚网科技有限公司:抖店精选联盟怎么用?

抖音精选联盟是抖音电商平台提供的一项服务&#xff0c;旨在为商家提供更多的推广机会和销售渠道。然而&#xff0c;很多人对于如何使用抖店精选联盟以及如何开通这项服务不太了解。本文将为您详细介绍抖店精选联盟的使用和激活流程。 第一节&#xff1a;如何使用抖店精选联盟 …...

第二章:最新版零基础学习 PYTHON 教程(第五节 - Python 输入/输出–如何在Python中打印而不换行?)

一般来说,从 C/C++ 切换到 Python 的人想知道如何在 python 中打印两个或多个变量或语句而不进入新行。由于Python print() 函数默认以换行符结尾。Python 有一个预定义的格式,如果你使用 print(a_variable) 那么它会自动转到下一行。 例子: # 输入:[csdn, csdnforcsdn] …...

C++实现集群聊天服务器

C实现集群聊天服务器 JSON Json是一种轻量级的数据交换模式&#xff08;也叫做数据序列化方式&#xff09;。Json采用完全独立于编程语言的文本格式来存储和表示数据。见解和清晰的层次结构使得Json称为理想的数据交换语言。易于阅读和编写。同时也易于支持机器解析和生成&am…...

40 二叉树的直径

二叉树的直径 总结&#xff1a;两个节点之间最长路径 路径的结点数 - 1题解1 递归——DFS 给你一棵二叉树的根节点&#xff0c;返回该树的 直径。 二叉树的直径是指树中任意两个节点之间最长路径的长度。这条路径可能经过也可能不经过根节点 root 。 两节点之间路径的长度由…...

Thread.sleep(0)的作用是什么?

Thread.sleep(0) 的作用是让当前线程放弃剩余的时间片&#xff0c;允许其他具有相同优先级的线程运行。这种操作有时被称为“主动让出CPU时间片”或“线程主动让步”。 通常情况下&#xff0c;当一个线程执行到一段代码时&#xff0c;它会占用CPU的时间片&#xff0c;直到时间…...

浏览器指定DNS

edge--设置 https://dns.alidns.com/dns-query...

虚拟机安装 centos

title: 虚拟机安装 centos createTime: 2020-12-13 12:00:27 updateTime: 2020-12-13 12:00:27 categories: linux tags: 虚拟机安装 centos 路线图 主机(宿主机) —> centos --> docker --> docker 镜像 --> docker 容器 — docker 服务 1.前期准备 一台 主机 或…...

【计算机网络笔记九】I/O 多路复用

阻塞 IO 和 非阻塞 IO 阻塞 I/O 和 非阻塞 I/O 的主要区别&#xff1a; 阻塞 I/O 执行用户程序操作是同步的&#xff0c;调用线程会被阻塞挂起&#xff0c;会一直等待内核的 I/O 操作完成才返回用户进程&#xff0c;唤醒挂起线程非阻塞 I/O 执行用户程序操作是异步的&#xf…...

踩坑日记 《正确的使用Vuex》基于 uniapp Vue3 setup 语法糖 vuex4 项目 太多坑了要吐了

踩坑日记 《正确的使用Vuex》基于 uniapp Vue3 setup 语法糖 vuex4 项目 太多坑了要吐了 完美解决页面数据不刷新 或者数据慢一步刷新 页面使用html <template><view><template v-if"cartData.data.length>0"><!-- 自定义导航栏 --><…...

Python无废话-办公自动化Excel修改数据

如何修改Excel 符合条件的数据&#xff1f;用Python 几行代码搞定。 需求&#xff1a;将销售明细表的产品名称为PG手机、HW手机、HW电脑的零售价格分别修改为4500、5500、7500&#xff0c;并保存Excel文件。如下图 Python 修改Excel 数据&#xff0c;常见步骤&#xff1a; 1&…...

MySQL系统架构设计

MySQL 一、MySQL整体架构1.1 SQL接口1.2 解析器 Parser1.3 查询优化器 Optimizer1.3.1 逻辑优化1.3.2 物理优化1.3.3 explain1.4 缓存 Cache1.5 存储引擎 Stroage Management1.6 一条查询SQL的执行流程二、缓存池(Buffer Pool)2.1 Buffer Pool 预读机制2.2 Buffer Pool free链…...

Google vs IBM vs Microsoft: 哪个在线数据分析师证书最好

Google vs IBM vs Microsoft: 哪个在线数据分析师证书最好&#xff1f; 对目前市场上前三个数据分析师证书进行审查和比较|Madison Hunter 似乎每个重要的公司都推出了自己版本的同一事物&#xff1a;专业数据分析师认证&#xff0c;旨在使您成为雇主的下一个热门商品。 随着…...

数据链路层 MTU 对 IP 协议的影响

在介绍主要内容之前&#xff0c;我们先来了解一下数据链路层中的"以太网" 。 “以太网”不是一种具体的网络&#xff0c;而是一种技术标准&#xff1b;既包含了数据链路层的内容&#xff0c;也包含了一些物理层的内容。 下面我们再来了解一下以太网数据帧&#xff…...

一文拿捏基于redis的分布式锁、lua、分布式性能提升

1.分布式锁 jdk的锁&#xff1a; 1、显示锁&#xff1a;Lock 2、隐式锁&#xff1a;synchronized 使用jdk锁保证线程的安全性要求&#xff1a;要求多个线程必须运行在同一个jvm中 但现在的系统基本都是分布式部署的&#xff0c;一个应用会被部署到多台服务器上&#xff0c;s…...

机器学习必修课 - 如何处理缺失数据

运行环境&#xff1a;Google Colab 处理缺失数据可简单分为两种方法&#xff1a;1. 删除具有缺失值的列 2. 填充 !git clone https://github.com/JeffereyWu/Housing-prices-data.git下载数据集 import pandas as pd from sklearn.model_selection import train_test_split导…...

阿里云服务器方升架构、自研硬件、AliFlash技术创新

阿里云服务器技术创新&#xff1a;服务器方升架构及自研硬件、自研存储硬件AliFlash和阿里云异构计算加速平台&#xff0c;阿里云百科分享阿里云服务器有哪些技术创新&#xff1a; 目录 服务器技术创新 服务器方升架构及自研硬件 自研存储硬件AliFlash 阿里云异构计算加速…...

知识工程---neo4j 5.12.0+GDS2.4.6安装

&#xff08;已安装好neo4j community 5.12.0&#xff09; 一. GDS下载 jar包下载地址&#xff1a;https://neo4j.com/graph-data-science-software/ 下载得到一个zip压缩包&#xff0c;解压后得到jar包。 二. GDS安装及配置 将解压得到的jar包放入neo4j安装目录下的plugi…...

BUUCTF reverse wp 81 - 85

[SCTF2019]babyre 反编译失败, 有花指令 有一个无用字节, 阻止反编译, patch成0x90 所有标红的地方nop掉之后按p重申函数main和loc_C22, F5成功 int __cdecl main(int argc, const char **argv, const char **envp) {char v4; // [rspFh] [rbp-151h]int v5; // [rsp10h] [rb…...

linux之kylin系统nginx的安装

一、nginx的作用 1.可做高性能的web服务器 直接处理静态资源&#xff08;HTML/CSS/图片等&#xff09;&#xff0c;响应速度远超传统服务器类似apache支持高并发连接 2.反向代理服务器 隐藏后端服务器IP地址&#xff0c;提高安全性 3.负载均衡服务器 支持多种策略分发流量…...

Redis相关知识总结(缓存雪崩,缓存穿透,缓存击穿,Redis实现分布式锁,如何保持数据库和缓存一致)

文章目录 1.什么是Redis&#xff1f;2.为什么要使用redis作为mysql的缓存&#xff1f;3.什么是缓存雪崩、缓存穿透、缓存击穿&#xff1f;3.1缓存雪崩3.1.1 大量缓存同时过期3.1.2 Redis宕机 3.2 缓存击穿3.3 缓存穿透3.4 总结 4. 数据库和缓存如何保持一致性5. Redis实现分布式…...

可靠性+灵活性:电力载波技术在楼宇自控中的核心价值

可靠性灵活性&#xff1a;电力载波技术在楼宇自控中的核心价值 在智能楼宇的自动化控制中&#xff0c;电力载波技术&#xff08;PLC&#xff09;凭借其独特的优势&#xff0c;正成为构建高效、稳定、灵活系统的核心解决方案。它利用现有电力线路传输数据&#xff0c;无需额外布…...

Linux简单的操作

ls ls 查看当前目录 ll 查看详细内容 ls -a 查看所有的内容 ls --help 查看方法文档 pwd pwd 查看当前路径 cd cd 转路径 cd .. 转上一级路径 cd 名 转换路径 …...

c++ 面试题(1)-----深度优先搜索(DFS)实现

操作系统&#xff1a;ubuntu22.04 IDE:Visual Studio Code 编程语言&#xff1a;C11 题目描述 地上有一个 m 行 n 列的方格&#xff0c;从坐标 [0,0] 起始。一个机器人可以从某一格移动到上下左右四个格子&#xff0c;但不能进入行坐标和列坐标的数位之和大于 k 的格子。 例…...

微信小程序 - 手机震动

一、界面 <button type"primary" bindtap"shortVibrate">短震动</button> <button type"primary" bindtap"longVibrate">长震动</button> 二、js逻辑代码 注&#xff1a;文档 https://developers.weixin.qq…...

基础测试工具使用经验

背景 vtune&#xff0c;perf, nsight system等基础测试工具&#xff0c;都是用过的&#xff0c;但是没有记录&#xff0c;都逐渐忘了。所以写这篇博客总结记录一下&#xff0c;只要以后发现新的用法&#xff0c;就记得来编辑补充一下 perf 比较基础的用法&#xff1a; 先改这…...

华为OD机试-食堂供餐-二分法

import java.util.Arrays; import java.util.Scanner;public class DemoTest3 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseint a in.nextIn…...

视频字幕质量评估的大规模细粒度基准

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 摘要 视频字幕在文本到视频生成任务中起着至关重要的作用&#xff0c;因为它们的质量直接影响所生成视频的语义连贯性和视觉保真度。尽管大型视觉-语言模型&#xff08;VLMs&#xff09;在字幕生成方面…...

unix/linux,sudo,其发展历程详细时间线、由来、历史背景

sudo 的诞生和演化,本身就是一部 Unix/Linux 系统管理哲学变迁的微缩史。来,让我们拨开时间的迷雾,一同探寻 sudo 那波澜壮阔(也颇为实用主义)的发展历程。 历史背景:su的时代与困境 ( 20 世纪 70 年代 - 80 年代初) 在 sudo 出现之前,Unix 系统管理员和需要特权操作的…...