每天一道leetcode:剑指 Offer 13. 机器人的运动范围(中等广度优先遍历剪枝)
今日份题目:
地上有一个m行n列的方格,从坐标 [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
题目思路
由于机器人是从(0,0)开始走,并不一定能走过所有格子,甚至不一定能走到右下角,所以其实是个搜索过程,故使用广度优先遍历,将满足条件(坐标在格子内且位数和小于k)的点坐标放入队列,每次从队列中取出第一个点坐标判断向下向右两个点左边,然后继续,直到队列不为空。剪枝,只考虑向下向右两个方向即可,这是由本题规律得出的,随着k的增大,可行区域都是增加在右和下两个方向的:
补充:方向
代码
class Solution
{
public:int num(int x) //计算x的数位之和{string s=to_string(x);//将int型数据转换成字符串类型int res=0;for(int i=0;i<s.length();i++) {res+=s[i]-'0';//计算各位之和}return res;}int movingCount(int m, int n, int k) {if(k==0) return 1;queue<pair<int,int> > p;//向右和向下的方向数组int dx[2]={0,1};int dy[2]={1,0};int visited[200][200]={0};//用于标记是否到达过//从(0,0)开始p.push({0,0});visited[0][0]=1;int ans=1;//bfs广度优先遍历while(!p.empty()) {pair<int,int> xy=p.front();p.pop();for(int i=0;i<2;i++) //遍历两个方向{int tx=dx[i]+xy.first;int ty=dy[i]+xy.second;if(tx<0||tx>=m||ty<0||ty>=n||visited[tx][ty]==1||num(tx)+num(ty)>k) continue;//避免到方格外、被遍历过、数位之和大于kp.push({tx,ty});visited[tx][ty]=1;ans++;}}return ans;}
};
提交结果
欢迎大家在评论区讨论,如有不懂的代码部分,欢迎在评论区留言!
相关文章:
每天一道leetcode:剑指 Offer 13. 机器人的运动范围(中等广度优先遍历剪枝)
今日份题目: 地上有一个m行n列的方格,从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0]的格子开始移动,它每次可以向左、右、上、下移动一格(不能移动到方格外),也不能进入行坐标和列坐标的数位之…...
TypeError: a bytes-like object is required, not ‘str‘
raceback (most recent call last): File "D:\pycharmcode\client.py", line 12, in <module> tcp_socket.send(send_data) TypeError: a bytes-like object is required, not str 使用socket进行ubuntu与windows通信时,发送数据时报了以上错…...
题解 | #1005.List Reshape# 2023杭电暑期多校9
1005.List Reshape 签到题 题目大意 按一定格式给定一个纯数字一维数组,按给定格式输出成二维数组。 解题思路 读入初始数组字符串,将每个数字分离,按要求输出即可 参考代码 参考代码为已AC代码主干,其中部分功能需读者自行…...
会声会影2023旗舰版电脑端视频剪辑软件
随着短视频、vlog等媒体形式的兴起,视频剪辑已经成为了热门技能。甚至有人说,不会修图可以,但不能不会剪视频。实际上,随着各种智能软件的发展,视频剪辑已经变得越来越简单。功能最全的2023新版,全新视差转…...
【linux基础(四)】对Linux权限的理解
💓博主CSDN主页:杭电码农-NEO💓 ⏩专栏分类:Linux从入门到开通⏪ 🚚代码仓库:NEO的学习日记🚚 🌹关注我🫵带你学更多操作系统知识 🔝🔝 Linux权限 1. 前言2. shell命…...
maven项目指定数据源
springboot项目 直接在pom.xml文件中添加以下配置 <!--使用阿里云maven中央仓库--> <repositories><repository><id>aliyun-repos</id><url>http://maven.aliyun.com/nexus/content/groups/public/</url><snapshots><ena…...
web3:使用Docker-compose方式部署blockscout
最近做的项目,需要blockscout来部署一个区块链浏览器,至于blockscout是什么,咱们稍后出一篇文章专门介绍下,本次就先介绍一下如何使用Docker-compose方式部署blockscout,以及过程中遇到的种种坑 目录 先决条件我的环境准备工作Docker-compose1.安装方式一:下载 Docker Co…...
C++11实用技术(五)泛型编程加载dll接口函数
C11泛型编程简化加载dll代码 常见的加载dll方式: HMODULE m_hDataModule; m_hDataModule LoadLibrary("myDll.dll");typedef int (*PfunA)(int a, int b);//定义函数指针 PfunA fun (PfunA)(GetProcAddress(m_hDataModule , "funA"));//加载…...
使用wxPython和PyMuPDF提取PDF页面指定页数的内容的应用程序
在本篇博客中,我们将探讨如何使用wxPython和PyMuPDF库创建一个简单的Bokeh应用程序,用于选择PDF文件并提取指定页面的内容,并将提取的内容显示在文本框中。 C:\pythoncode\new\pdfgetcontent.py 准备工作 首先,确保你已经安装了…...
k8s的pv和pvc创建
//NFS使用PV和PVC 1、配置nfs存储 2、定义PV 实现 下图的pv和pvc测试 pv的定义 这里定义5个PV,并且定义挂载的路径以及访问模式,还有PV划分的大小 vim /pv.yamlapiVersion: v1 kind: PersistentVolume metadata:name: pv001 spec:capacity:storage: …...
记K8S集群工作节点,AnolisOS 8.6部署显卡驱动集成Containerd运行时
1、安装gcc #安装编译环境 yum -y install make gcc gcc-c2、下载显卡驱动 点击 直达连接 nvidia高级搜索下载历史版本驱动程序(下载历史版本驱动) https://www.nvidia.cn/Download/Find.aspx?langcn3、安装驱动 安装显卡驱动 ./NVIDIA-Linux-x86…...
JavaScript 性能优化
优化JavaScript代码的性能是开发过程中的一个关键任务,它可以显著提升网站或应用的用户体验。以下是一些优化技巧,涵盖了减少重绘、减少内存占用和合并网络请求等方面: 1. **减少重绘和重排:** - **使用 CSS3 动画:…...
架构演进及常用架构
1架构演进及常用架构 1.1单体分层架构 1.2 多应用微服务架构 1.3 分布式集群部署 部署 CDN 节点: 用户访问量的增加意味着用户地域的分散请求,如果所有请求都直接发送中心服务器的话,距离越远,响应速度越差,这时就需…...
WinCC V7.5 中的C脚本对话框不可见,将编辑窗口移动到可见区域的具体方法
WinCC V7.5 中的C脚本对话框不可见,将编辑窗口移动到可见区域的具体方法 由于 Windows 系统更新或使用不同的显示器,在配置C动作时,有可能会出现C脚本编辑窗口被移动到不可见区域的现象。 由于该窗口无法被关闭,故无法进行进一步…...
【实战】十一、看板页面及任务组页面开发(二) —— React17+React Hook+TS4 最佳实践,仿 Jira 企业级项目(二十四)
文章目录 一、项目起航:项目初始化与配置二、React 与 Hook 应用:实现项目列表三、TS 应用:JS神助攻 - 强类型四、JWT、用户认证与异步请求五、CSS 其实很简单 - 用 CSS-in-JS 添加样式六、用户体验优化 - 加载中和错误状态处理七、Hook&…...
Vue2.7.14、vuecli@5.0.8 升级 vite@4.4.8
项目背景 Vue2.7.14、vuecli5.0.8、element-ui2.15.13、node14.18.3 vite安装 pnpm add vite4.4.8 -D 入口文件index.html 文件位置修改 将pulic里的index.html移到根目录下 根目录/public/index.html 到 根目录/index.html 文件内容修改 <link rel"icon"…...
LeetCode[面试题04.12]求和路径
难度:Medium 题目: 给定一棵二叉树,其中每个节点都含有一个整数数值(该值或正或负)。设计一个算法,打印节点数值总和等于某个给定值的所有路径的数量。注意,路径不一定非得从二叉树的根节点或叶节点开始或结束&#x…...
骑行运动耳机哪款好?五年骑行爱好者给你分享分享
作为一名骑行达人,我尝试过多种骑行耳机,有入耳式、耳罩式、骨传导等等,但总有一款让我特别满意。直到我遇到了这几款耳机,它不仅音质出色,而且非常适合骑行,让我爱不释手。下面,我将分享一下这…...
SpringBoot3集成ElasticSearch
标签:ElasticSearch8.Kibana8; 一、简介 Elasticsearch是一个分布式、RESTful风格的搜索和数据分析引擎,适用于各种数据类型,数字、文本、地理位置、结构化数据、非结构化数据; 在实际的工作中,历经过Ela…...
详解23种设计模式优缺点以及解决方案
1. 单例模式(Singleton Pattern): 优点:确保一个类只有一个实例,提供全局访问点,节省资源。缺点:可能引入全局状态,难以扩展和测试。解决方法:使用依赖注入来替代直接访…...
Oracle 数据库中删除表空间的详细步骤与示例
系列文章目录 文章目录 系列文章目录前言一、查看表空间二、数据迁移和备份三、下线表空间中的对象四、删除表空间五、删除完成后的操作总结前言 在 Oracle 数据库中,表空间是存储数据的逻辑容器。有时候,我们可能需要删除不再使用的表空间以释放空间或进行数据库重组。本文…...
<kernel>kernel 6.4 笔记
<kernel>kernel 6.4 笔记 1、kernel 与用户层通信过程 (1) kernel 通过uevent事件 通知 用户层; 第一步:准备同事事件的参数键值对存到环境变量中; 第二步 :准备环境变量数据 ACTION、DEVPATH、SUBSYSTEM…...
介绍一些编程语言— Perl 语言
介绍一些编程语言— Perl 语言 Perl 语言 简介 Perl 是一种动态解释型的脚本语言。 最初的设计者为拉里・沃尔,它于 1987 1987 1987 年 12 12 12 月 18 18 18 日发表。Perl 借取了 C、sed、awk、shell scripting 以及很多其他编程语言的特性。其中最重要的特性…...
原型与继承
原型与继承 在 JavaScript 中,对象有一个特殊的隐藏属性 [[Prototype]](如规范中所命名的),它要么为 null,要么就是对另一个对象的引用。该对象被称为“原型。 当我们从 object 中读取一个缺失的属性时,Jav…...
Flink流批一体计算(14):PyFlink Tabel API之SQL查询
举个例子 查询 source 表,同时执行计算 # 通过 Table API 创建一张表: source_table table_env.from_path("datagen") # 或者通过 SQL 查询语句创建一张表: source_table table_env.sql_query("SELECT * FROM datagen&quo…...
JRebel插件扩展-mac版
前言 上一篇分享了mac开发环境的搭建,但是欠了博友几个优化的债,今天先还一个,那就是idea里jRebel插件的扩展。 一、场景回眸 这个如果在win环境那扩展是分分钟,一个exe文件点点就行。现在在mac环境就没有这样的dmg可以执行的&…...
C语言中常见的一些语法概念和功能
常用代码: 程序入口:int main() 函数用于定义程序的入口点。 输出:使用 printf() 函数可以在控制台打印输出。 输入:使用 scanf() 函数可以接收用户的输入。 条件判断:使用 if-else 语句可以根据条件执行不同的代码…...
Python土力学与基础工程计算.PDF-钻探泥浆制备
Python 求解代码如下: 1. rho1 2.5 # 黏土密度,单位:t/m 2. rho2 1.0 # 泥浆密度,单位:t/m 3. rho3 1.0 # 水的密度,单位:t/m 4. V 1.0 # 泥浆容积,单位:…...
【机器学习】— 2 图神经网络GNN
一、说明 在本文中,我们探讨了图神经网络(GNN)在推荐系统中的潜力,强调了它们相对于传统矩阵完成方法的优势。GNN为利用图论来改进推荐系统提供了一个强大的框架。在本文中,我们将在推荐系统的背景下概述图论和图神经网…...
QT的布局与间隔器介绍
布局与间隔器 1、概述 QT中使用绝对定位的布局方式,无法适用窗口的变化,但是,也可以通过尺寸策略来进行 调整,使得 可以适用窗口变化。 布局管理器作用最主要用来在qt设计师中进行控件的排列,另外,布局管理…...
深入浅出Pytorch函数——torch.nn.Linear
分类目录:《深入浅出Pytorch函数》总目录 对输入数据做线性变换 y x A T b yxA^Tb yxATb 语法 torch.nn.Linear(in_features, out_features, biasTrue, deviceNone, dtypeNone)参数 in_features:[int] 每个输入样本的大小out_features :…...
Vue3.2+TS的defineExpose的应用
defineExpose通俗来讲,其实就是讲子组件的方法或者数据,暴露给父组件进行使用,这样对组件的封装使用,有很大的帮助,那么defineExpose应该如何使用,下面我来用一些实际的代码,带大家快速学会defi…...
牛客网Python入门103题练习|【08--元组】
⭐NP62 运动会双人项目 描述 牛客运动会上有一项双人项目,因为报名成功以后双人成员不允许被修改,因此请使用元组(tuple)进行记录。先输入两个人的名字,请输出他们报名成功以后的元组。 输入描述: 第一…...
Jenkins改造—nginx配置鉴权
先kill掉8082的端口进程 netstat -natp | grep 8082 kill 10256 1、下载nginx nginx安装 EPEL 仓库中有 Nginx 的安装包。如果你还没有安装过 EPEL,可以通过运行下面的命令来完成安装 sudo yum install epel-release 输入以下命令来安装 Nginx sudo yum inst…...
(二)VisionOS平台概述
2.VisionOS平台概述 1. VisionOS平台概述 Unity 对VisionOS的支持将 Unity 编辑器和运行时引擎的全部功能与RealityKit提供的渲染功能结合起来。Unity 的核心功能(包括脚本、物理、动画混合、AI、场景管理等)无需修改即可支持。这允许游戏和应用程序逻…...
菜单中的类似iOS中开关的样式
背景是我们有需求,做类似ios中开关的按钮。github上有一些开源项目,比如 SwitchButton, 但是这个项目中提供了很多选项,并且实际使用中会出现一些奇怪的问题。 我调整了下代码,把无关的功能都给删了,保留核…...
Vue 2 动态组件和异步组件
先阅读 【Vue 2 组件基础】中的初步了解动态组件。 动态组件与keep-alive 我们知道动态组件使用is属性和component标签结合来切换不同组件。 下面给出一个示例: <!DOCTYPE html> <html><head><title>Vue 动态组件</title><scri…...
MongoDB升级经历(4.0.23至5.0.19)
MongoDB从4.0.23至5.0.19升级经历 引子:为了解决MongoDB的两个漏洞决定把MongoDB升级至最新版本,期间也踩了不少坑,在这里分享出来供大家学习与避坑~ 1、MongoDB的两个漏洞 漏洞1:MongoDB Server 安全漏洞(CVE-2021-20330) 漏洞2…...
iPhone上的个人热点丢失了怎么办?如何修复iPhone上不见的个人热点?
个人热点功能可将我们的iPhone手机转变为 Wi-Fi 热点,有了Wi-Fi 热点后就可以与附近的其他设备共享其互联网连接。 一般情况下,个人热点打开就可以使用,但也有部分用户在升级系统或越狱后发现 iPhone 的个人热点消失了。 iPhone上的个人热点…...
AI 媒人:为什么图形神经网络比 MLP 更好?
一、说明 G拉夫神经网络(GNN)!想象他们是人工智能世界的媒人,通过探索他们的联系,不知疲倦地帮助数据点找到朋友和人气。数字派对上的终极僚机。 现在,为什么这些GNN如此重要,你问?好…...
信息学奥赛一本通 1984:【19CSPJ普及组】纪念品 | 洛谷 P5662 [CSP-J2019] 纪念品
【题目链接】 ybt 1984:【19CSPJ普及组】纪念品 洛谷 P5662 [CSP-J2019] 纪念品 【题目考点】 1. 动态规划:完全背包 【解题思路】 由于小伟每天都可以买卖物品无限次,我们可以假想每天开始时,他把所有的商品都卖出ÿ…...
JVM——JVM参数指南
文章目录 1.概述2.堆内存相关2.1.显式指定堆内存–Xms和-Xmx2.2.显式新生代内存(Young Ceneration)2.3.显示指定永久代/元空间的大小 3.垃圾收集相关3.1.垃圾回收器3.2.GC记录 1.概述 在本篇文章中,你将掌握最常用的 JVM 参数配置。如果对于下面提到了一些概念比如…...
马上七夕到了,用各种编程语言实现10种浪漫表白方式
目录 1. 直接表白:2. 七夕节表白:3. 猜心游戏:4. 浪漫诗句:5. 爱的方程式:6. 爱心Python:7. 心形图案JavaScript 代码:8. 心形并显示表白信息HTML 页面:9. Java七夕快乐:…...
Spring Clould 注册中心 - Eureka,Nacos
视频地址:微服务(SpringCloudRabbitMQDockerRedis搜索分布式) Eureka 微服务技术栈导学(P1、P2) 微服务涉及的的知识 认识微服务-服务架构演变(P3、P4) 总结: 认识微服务-微服务技…...
使用appuploader工具发布证书和描述性文件教程
使用APPuploader工具发布证书和描述性文件教程 之前用AppCan平台开发了一个应用,平台可以同时生成安卓版和苹果版,想着也把这应用上架到App Store试试,于是找同学借了个苹果开发者账号,但没那么简单,还要用到Mac电脑的…...
【面试八股文】每日一题:谈谈你对IO的理解
谈谈你对IO的理解 每日一题-Java核心-谈谈你对对IO的理解【面试八股文】 1.Java基础知识 Java IO(Input/Output)是Java编程语言中用于处理输入和输出的一组类和接口。它提供了一种在Java程序中读取和写入数据的方法。 Java IO包括两个主要的部分&#x…...
200. 岛屿数量
思路:遍历整个矩阵,对每个格子执行以下操作: 如果格子是陆地(‘1’),则将其标记为已访问(‘0’),并从当前位置开始进行深度优先搜索,将与当前格子相邻的陆地都…...
【LeetCode】581.最短无序连续子数组
题目 给你一个整数数组 nums ,你需要找出一个 连续子数组 ,如果对这个子数组进行升序排序,那么整个数组都会变为升序排序。 请你找出符合题意的 最短 子数组,并输出它的长度。 示例 1: 输入:nums [2,6…...
曲面(弧面、柱面)展平(拉直)瓶子标签识别ocr
瓶子或者柱面在做字符识别的时候由于变形,识别效果是很不好的 或者是检测瓶子表面缺陷的时候效果也没有展平的好 下面介绍两个项目,关于曲面(弧面、柱面)展平(拉直) 项目一:通过识别曲面的6个点…...
知识继承概述
文章目录 知识继承第一章 知识继承概述1.背景介绍第一页 背景第二页 大模型训练成本示例第三页 知识继承的动机 2.知识继承的主要方法 第二章 基于知识蒸馏的知识继承预页 方法概览 1.知识蒸馏概述第一页 知识蒸馏概述第二页 知识蒸馏第三页 什么是知识第四页 知识蒸馏的核心目…...