(搜索) 剑指 Offer 13. 机器人的运动范围 ——【Leetcode每日一题】

news/2024/2/28 11:04:27

❓剑指 Offer 13. 机器人的运动范围

难度:中等

地上有一个 mn 列的方格,从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动,它每次可以向左、右、上、下移动一格(不能移动到方格外),也不能进入行坐标和列坐标的数位之和大于 k 的格子。例如,当 k 为18时,机器人能够进入方格 [35, 37] ,因为3+5+3+7=18。但它不能进入方格 [35, 38],因为 3+5+3+8=19。请问该机器人能够到达多少个格子?

示例 1:

输入:m = 2, n = 3, k = 1
输出:3

示例 2:

输入:m = 3, n = 1, k = 0
输出:1

提示

  • 1 <= n,m <= 100
  • 0 <= k <= 20

💡思路:广度优先搜索

我们将行坐标和列坐标数位之和大于 k 的格子看作障碍物,那么这道题就是一道很传统的搜索题目,我们可以使用广度优先搜索或者深度优先搜索来解决它,本文选择使用 广度优先搜索 的方法来讲解。

那么如何计算一个数的数位之和呢?

  • 我们只需要对数 x 每次对 10 取余,就能知道数 x 的个位数是多少,然后再将 x 除 10,这个操作等价于将 x 的十进制数向右移一位,删除个位数(类似于二进制中的 >> 右移运算符),不断重复直到 x 为 0 时结束。

🍁代码:(C++、Java)

C++

class Solution {
private:int getsum(int x){int ans = 0;while(x > 0 ){ans += x % 10;x /= 10;}return ans;}
public:int movingCount(int m, int n, int k) {if(k == 0) return 1;vector<pair<int, int>> dirs{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};queue<pair<int, int>> q;q.push(make_pair(0, 0));vector<vector<int>> visited(m, vector<int>(n));visited[0][0] = 1;int ans = 1;while(!q.empty()){auto [x, y] = q.front();q.pop();for(auto dir : dirs){int cur_x = x + dir.first, cur_y = y + dir.second;if(cur_x < 0 || cur_x >= m || cur_y < 0 || cur_y >= n || visited[cur_x][cur_y] || getsum(cur_x) + getsum(cur_y) > k) continue;q.push(make_pair(cur_x, cur_y));visited[cur_x][cur_y] = 1;ans++;}}return ans;}
};

Java

class Solution {private int getsum(int x){int ans = 0;while(x > 0 ){ans += x % 10;x /= 10;}return ans;}public int movingCount(int m, int n, int k) {if(k == 0) return 1;int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};Queue<int[]> q = new LinkedList<int[]>();q.offer(new int[]{0, 0});int[][]  visited = new int[m][n];visited[0][0] = 1;int ans = 1;while(!q.isEmpty()){int[] cell = q.poll();for(int[] dir : dirs){int cur_x = cell[0] + dir[0], cur_y = cell[1] + dir[1];if(cur_x < 0 || cur_x >= m || cur_y < 0 || cur_y >= n || visited[cur_x][cur_y] == 1 || getsum(cur_x) + getsum(cur_y) > k) continue;q.offer(new int[]{cur_x, cur_y});visited[cur_x][cur_y] = 1;ans++;}}return ans;}
}

🚀 运行结果:

在这里插入图片描述

🕔 复杂度分析:

  • 时间复杂度 O ( m n ) O(mn) O(mn),其中 m 为方格的行数,n 为方格的列数。考虑所有格子都能进入,那么搜索的时候一个格子最多会被访问的次数为常数,所以时间复杂度为 O ( 4 m n ) = O ( m n ) O(4mn) = O(mn) O(4mn)=O(mn)
  • 空间复杂度 O ( m n ) O(mn) O(mn),搜索的时候需要一个大小为 O ( m n ) O(mn) O(mn), 的标记结构用来标记每个格子是否被走过。

题目来源:力扣。

放弃一件事很容易,每天能坚持一件事一定很酷,一起每日一题吧!
关注我LeetCode主页 / CSDN—力扣专栏,每日更新!

注: 如有不足,欢迎指正!


http://www.ppmy.cn/news/1042700.html

相关文章

【Docker环境部署及基础命令操作】

CentOS7安装Docker&#xff08;使用yum安装&#xff09; 参考链接&#xff1a;https://developer.aliyun.com/mirror/docker-ce?spma2c6h.13651102.0.0.1ec41b11RJ4PKS #step 1:安装安装必要的一些系统工具 [rootnode1 ~]# yum install -y yum-utils device-mapper-persiste…

windows上的docker自动化部署到服务器脚本

1、mvn install后&#xff0c;双击这个bat&#xff0c;实现docker build后上传到124服务器&#xff0c;并且重启124服务器 **echo offsetlocal:: 定义镜像名称和版本变量 set IMAGE_NAMEweb set IMAGE_VERSION1.3.1:: 清理本地文件 echo Cleaning up... del service-%IMAGE_N…

【LeetCode75】第三十二题 链表最大孪生和

目录 题目: 示例: 分析: 代码: 题目: 示例: 分析: 题目让我们求出链表的最大孪生和&#xff0c;那么什么是孪生和呢&#xff0c;就是对称的节点就是孪生节点&#xff0c;他们的和就是孪生和。 比如第一个节点的孪生节点就是最后一个节点&#xff0c;第二个节点的孪生节点…

二、OpenLayer创建地图

//头部定义 const Map ol.Map; const View ol.View; const defaultControls ol.control.defaults.defaults;//绑定的元素盒子 <div id"mapDiv" class"map"></div>//高德底图 const baseVecLayer new TileLayer({visible: true,source: new…

【卡码网】31. 字符串的最大价值 <贪心>

【卡码网】31. 字符串的最大价值 给定一个字符串 S S S&#xff08;S.lenth < 5000&#xff09;&#xff0c;只包含 0 和 1 两个数字&#xff0c;下标从 1 开始&#xff0c;设第 i i i 位的价值为 v a l i val_i vali​&#xff0c;则 v a l i val_i vali​的定义如下&a…

安全(权限)框架Shiro概述及原理

1.1 Shiro是什么 Apache Shiro是一个功能强大且易于使用的Java安全&#xff08;权限&#xff09;框架。Shiro可以完成&#xff1a;认证、授权、加密、会话管理、与Web集成、缓存 等。借助Shiro您可以快速轻松地保护任何应用程序——从最小的移动应用程序到最大的Web和企业应用…

注解@JsonInclude

注解JsonInclude 1. 注解由来 JsonInclude是一个用于Java类中字段或方法的注解&#xff0c;它来自于Jackson库。Jackson库是一个用于处理JSON数据的流行开源库&#xff0c;在Java对象和JSON之间进行序列化和反序列化时经常被使用。 2. 注解示例 下面是JsonInclude注解的一个…

thinkphp 5 实现UNION ALL 3个联表查询,并且带上搜索条件,名称,时间,手机号

在ThinkPHP 5中实现带有搜索条件、名称、时间和手机号的3个联表查询&#xff08;UNION ALL&#xff09;&#xff0c;您可以按照以下步骤进行操作&#xff1a; 确保已经配置好数据库连接信息和相关的模型。 使用union()方法来构建3个联表查询&#xff0c;同时在每个查询中添加所…

Python土力学与基础工程计算.PDF-钻探泥浆制备

Python 求解代码如下&#xff1a; 1. rho1 2.5 # 黏土密度&#xff0c;单位&#xff1a;t/m 2. rho2 1.0 # 泥浆密度&#xff0c;单位&#xff1a;t/m 3. rho3 1.0 # 水的密度&#xff0c;单位&#xff1a;t/m 4. V 1.0 # 泥浆容积&#xff0c;单位&#xff1a;…

arm:day6

实现UART通信&#xff1a; 1.键盘输入一个字符a,串口工具显示b 2.键盘输入一个字符串"nihao",串口工具显示"nihao" uart.h #ifndef __UART4_H__ #define __UART4_H__#include "stm32mp1xx_uart.h" #include "stm32mp1xx_gpio.h" #in…

金融语言模型:FinGPT

项目简介 FinGPT是一个开源的金融语言模型&#xff08;LLMs&#xff09;&#xff0c;由FinNLP项目提供。这个项目让对金融领域的自然语言处理&#xff08;NLP&#xff09;感兴趣的人们有了一个可以自由尝试的平台&#xff0c;并提供了一个与专有模型相比更容易获取的金融数据。…

2023/8/16 华为云OCR识别驾驶证、行驶证

目录 一、 注册华为云账号开通识别驾驶证、行驶证服务 二、编写配置文件 2.1、配置秘钥 2.2、 编写配置工具类 三、接口测试 3.1、测试接口 3.2、结果 四、实际工作中遇到的问题 4.1、前端传值问题 4.2、后端获取数据问题 4.3、使用openfeign调用接口报错 4.3、前端显示问题…

Element Plus el-table 数据为空时自定义内容【默认为 No Data】

1. 通过 Table 属性设置 <div class"el-plus-table"><el-table empty-text"暂无数据" :data"tableData" style"width: 100%"><el-table-column prop"date" label"Date" width"180" /&g…

C#反编译工具ILSPY

ILSPY ILSpy 是一个开源的.Net程序集浏览器和反编译工具。 Visual Studio 2022附带了默认情况下启用的F12反编译支持&#xff08;使用我们的引擎v7.1&#xff09;。 在Visual Studio 2019中&#xff0c;您必须手动启用F12支持。转到“工具”/“选项”/“文本编辑器”/C#/Adva…

vite初始化vue3项目(配置自动格式化工具与git提交规范工具)

初始化项目 vite构建vue项目还是比较简单的&#xff0c;简单配置选择一下就行了 初始化命令 npm init vuelatest初始化最新版本vue项目 2. 基本选项含义 Add TypeScript 是否添加TSADD JSX是否支持JSXADD Vue Router是否添加Vue Router路由管理工具ADD Pinia 是否添加pinia…

高斯消元——洛谷P3389题解

高斯消元模板题 链接&#xff1a;【模板】高斯消元法 - 洛谷 #include <algorithm> #include <complex> #include <deque> #include <iostream> #include <iterator> #include <list> #include <map> #include <queue> #inc…

python计算模板图像与原图像各区域的相似度

目录 1、解释说明&#xff1a; 2、使用示例&#xff1a; 3、注意事项&#xff1a; 1、解释说明&#xff1a; 在Python中&#xff0c;我们可以使用OpenCV库进行图像处理和计算机视觉任务。其中&#xff0c;模板匹配是一种常见的方法&#xff0c;用于在一幅图像中识别出与给定…

等保测评--安全物理环境--测评方法

安全子类--物理位置选择 a)机房场地应选择在具有防震、防风和防雨等能力的建筑内; 一、测评对象 记录类文档和机房 二、测评实施 1)检查机房所在建筑物是否具有建筑物抗震设防审批文档; 2)检查机房门窗是否不存在因风导致的尘土严重; 3)检查机房是否不存在雨水渗漏…

Matlab 频谱图中如何设置频率刻度

Matlab 频谱图中如何设置频率刻度&#xff08;横坐标&#xff09; 1、概述 时域信号经FFT 变换后得到了频谱&#xff0c;在作图时还必须设置正确的频率刻度&#xff0c;这样才能从图中得到正确的结果。下面来介绍如何设置正确的频率刻度。 2、案例分析 有一个余弦信号&#…

Java后端开发面试题篇——Redis

Redis的数据持久化策略有哪些 RDB的执行原理&#xff1f; bgsave开始时会fork主进程得到子进程&#xff0c;子进程共享主进程的内存数据。完成fork后读取内存数据并写入 RDB 文件。 fork采用的是copy-on-write技术&#xff1a; 当主进程执行读操作时&#xff0c;访问共享内存…
最新文章