python每日一题【剑指 Offer 13. 机器人的运动范围】

news/2024/3/29 0:41:18/文章来源:https://blog.csdn.net/qq_42896431/article/details/128104496

day23-2022.11.18

题目信息来源
作者:Krahets
链接:https://leetcode.cn/leetbook/read/illustration-of-algorithm
来源:力扣(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

题解:个人版

昨天做了一题,总之能照猫画虎做出来一题

  • 递归参数:行坐标i, 列坐标j

  • 终止条件:超出边界,不符合规则,已经看过的地方。用了一个二维列表来标记,还踩了雷。

  • 递推工作:标记已经选过的列表,搜索下一个单元格,计数

  • 返回值:无。选择了一个全局变量来计数,说实话,我没太想好怎么在递归中计数,这个尝试失败了

相关知识点

行坐标和列坐标的数位之和计算,设行坐标为i,列坐标为j,则计算行坐标数位之和为i//10+i%10,即整除和取余。我这里可能钻了测试题的漏洞,如果出现m,n=100,可能就bug了。

class Solution:def movingCount(self, m: int, n: int, k: int) -> int:# 递归参数:行坐标i, 列坐标j# 终止条件:超出边界,不符合规则# 递推工作:标记已经选过的列表,搜索下一个单元格,计数# 返回值self.m, self.n, self.k = m, n, kself.result = 0self.myset = [[0 for x in range(n)] for x in range(m)]self.move(0, 0)return self.resultdef move(self, i, j):if i>=self.m or j>=self.n:return#if i<0 or i>=self.m or j<0 or j>=self.n:returnif self.myset[i][j]==1:returnif self.myset[i][j]==0:self.myset[i][j] = 1if (i//10+i%10+j//10+j%10)>self.k:returnelse:self.result = self.result + 1# self.move(i-1, j)self.move(i+1, j)# self.move(i, j-1)self.move(i, j+1)return

题解:官方

官方题解知识点重点

  1. 数位增量和公式解释:若xx+1不超过两位数
  • x+1//10=0x+1//10=0x+1//10=0 时,xxx 的个位为9,x+1x+1x+1 的个位为0,比 xxx 小9,x+1x+1x+1 的十位比 xxx 的十位大1,整体就比 xxx 小8
  • x+1//10≠0x+1//10\neq0x+1//10=0 时,就比 xxx 大1
  1. 理解不可达解:有限制,机器人每次只能走一步。只有之前走过的连通了才可以。
  2. 剪枝:分析可知机器人可通过只往增序列处走就能访问所有可达解。(然后我偷偷注释了我代码里递归的两行,试了一下,确实不影响结果并且提升了速度减少了内存)
  3. 我也尝试用set()来标记走过的点,来剪枝,但是失败了,因为我的语法是set.add([i,j]),看了解析用的是set.add((i,j))
  4. 关于我没法把计数放到递归里的解决方案:解析里用的是+,如果不符合条件的直接会返回 0,所以会没有变化,其他情况都是被1+

but,官方解析里sisj的写法很容易混淆,其实就是 x 和 x+1 的数位之和

广度优先遍历 BFS

以平推的方式向前搜索,通常会利用队列实现。

  • 初始化:将初始点加入队列
  • 迭代终止条件:队列为空
  • 迭代工作:
    • 出队
    • 判断是否跳过
    • 标记
    • 入队

尝试复现官方题解的广度优先遍历

class Solution:def movingCount(self, m: int, n: int, k: int) -> int:# 初始化需要队列遍历存储遍历的列表,需要一个列表存储已经标记过的格子myqueue = [(0, 0, 0, 0)]choosed = set()while myqueue:x, y, sum_x, sum_y = myqueue.pop(0)if x>=m or y>=n or sum_x+sum_y>k or (x,y) in choosed:continuechoosed.add((x, y))myqueue.append((x+1, y, sum_x+1 if (x+1)%10!=0 else sum_x-8, sum_y))myqueue.append((x, y+1, sum_x, sum_y+1 if (y+1)%10!=0 else sum_y-8))return len(choosed)

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_39010.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

C++:STL之Vector实现

vector各函数 #include<iostream> #include<vector> using namespace std;namespace lz {//模拟实现vectortemplate<class T>class vector{public:typedef T* iterator;typedef const T* const_iterator;//默认成员函数vector(); …

Netty进阶——粘包与半包(代码示例)

目录一、消息粘包和消息半包的概述1.1、消息粘包1.2、消息半包二、粘包现象代码示例2.1、粘包现象服务端示例代码2.2、粘包现象客户端示例代码2.3、分别启动服务端&#xff0c;客户端&#xff0c;查看服务端结果输出三、半包现象代码示例3.1、半包现象服务端示例代码3.2、半包现…

【强化学习论文】小样本策略泛化的提示决策转换器

文献题目&#xff1a;Prompting Decision Transformer for Few-Shot Policy Generalization 摘要 人类可以利用先前的经验并从少量演示中学习新任务。与旨在通过更好的算法设计实现快速适应的离线元强化学习相比&#xff0c;我们研究了架构归纳偏差对少样本学习能力的影响。我…

不懂单链表? 这篇文章就帮你搞明白

坚持看完&#xff0c;结尾有思维导图总结 链表对指针的操作要求不低链表的概念链表的特性链表的功能(最重要)定义和初始化头插头删细节说明尾插尾删寻找链表元素与打印链表在 某位置后插入删除在某位置的插入删除销毁链表链表的概念 什么是链表 官方概念&#xff1a;链表是一种…

显卡---显卡驱动---CUDA---Cudnn

1. 背景 最近在follow百度的CAE这篇论文时&#xff0c;源码需要的环境为&#xff1a; python 3.7 cuda: 11.0 cudnn: 8.0.4 gcc 8.2 该版本要求与我目前使用的服务器上的CUDA版本不相符合。因此搜索了一篇国外小哥的文章&#xff0c;讲述了如何在一台服务器上安装多个CUDA和Cud…

Node之Express学习笔记

一.Express 1.1什么是Express Express的作用和Node.js内置的http模块类似 专门用来创建Web服务器的 本质&#xff1a;npm上的第三方包&#xff0c;提供快速创建Web服务器的便捷方法 1.2Express能做什么 Web网站服务器&#xff1a;专门提供Web网页资源的服务器 API接口服务器&…

FPGA----ZCU106基于axi-hp通道的pl与ps数据交互(全网唯一最详)

1、大家好&#xff0c;今天给大家带来的内容是&#xff0c;基于AXI4协议的采用AXI-HP通道完成PL侧数据发送至PS侧&#xff08;PS侧数据发送至PL侧并没有实现&#xff0c;但是保留了PL读取PS测数据的接口&#xff09; 2、如果大家用到SoC这种高级功能&#xff0c;那大家应该对于…

Linux进阶-进程间通信(ipc)

进程间通信&#xff1a;数据传输、资源共享、事件通知、进程控制。 Linux系统下的ipc 早期unix系统 ipc&#xff1a;管道&#xff08;数据传输&#xff09;、信号&#xff08;事件通知&#xff09;、fifo&#xff08;数据传输&#xff09;。 system-v ipc&#xff08;贝尔实…

Kubernetes之Pod初始化容器

Kubernetes之Pod初始化容器 概述 ​ 初始化是很多编程语言普遍关注的问题&#xff0c;甚至有些编程语言直接支持模式构造来生成初始化程序&#xff0c;这些用于进行初始化的程序结构称为初始化器或初始化列表。初始化代码要首先运行&#xff0c;且只能运行一次&#xff0c;它们…

CAPM资产定价模型

本文是Quantitative Methods and Analysis: Pairs Trading此书的读书笔记。 CAPM(Capital Asset Pricing Model)资产定价模型 这个模型在金融界的影响就是beta这个词的使用。CAPM模型用两个部分的回报之和来解释一个资产的回报。其中一个部分是指市场&#xff08;称为market)…

时间序列:时间序列模型---自回归过程(AutoRegressive Process)

本文是Quantitative Methods and Analysis: Pairs Trading此书的读书笔记。 这次我们构造一个由无限的白噪声实现&#xff08;white noise realization) 组成的时间序列&#xff0c;即。这个由无限数目的项组成的值却是一个有限的值&#xff0c;比如时刻的值为&#xff0c; 而…

Magic Leap 2设计和开发幕后花絮

Magic Leap今年发布新款AR头显Magic Leap 2&#xff0c;相比于上一代Magic Leap 1&#xff0c;新品更专注于B端场景&#xff0c;自公布以来&#xff0c;Magic Leap不仅对公司策略、理念更加透明&#xff0c;也不断公开ML2产品设计背后的思考。相比于ML1&#xff0c;ML2的设计有…

粒子群算法查找函数最小值

实现 函数 F01、F06 的优化测试 以下内容是现有算法的运行结果、调参分析、及代码实现&#xff0c;用于给其他人提供参考&#xff0c;懒得改了hh 1. 运行结果 参数 w 0.5 &#xff08;可更改&#xff09; c1 2.0 &#xff08;可更改&#xff09; c2 2.0 &#xff08;可更改&…

Echart 柱状图,X轴斜着展示

option { color: [‘#3398DB’], tooltip: { trigger: ‘axis’, axisPointer: { // 坐标轴指示器&#xff0c;坐标轴触发有效 type: ‘shadow’ // 默认为直线&#xff0c;可选为&#xff1a;‘line’ | ‘shadow’ } }, grid: { left: ‘3%’, right: ‘4%’, bottom: ‘3%’…

iPhone升级iOS 16后出现提示“面容ID不可用”怎么办?

最近&#xff0c;很多用户在苹果社区反馈&#xff0c;iPhone升级iOS 16后Face ID不能用了&#xff0c;尝试重置Face ID时&#xff0c;系统会弹窗提示“面容ID不可用&#xff0c;稍后尝试设置面容ID。” 如果你的iPhone在没有摔落手机或是手机进水的情况下出现这个弹窗&#xff…

【uniapp小程序】路由跳转navigator传参封装

文章目录&#x1f34d;前言&#x1f34b;正文1、看官网1.1 navigator API 介绍1.2、路由跳转参数传递1.3、五种常见的跳转方式1.3.1 uni.navigateTo(OBJECT)1.3.2 uni.redirectTo(OBJECT)1.3.3 uni.reLaunch(OBJECT)1.3.4 uni.switchTab(OBJECT)1.3.5 uni.navigateBack(OBJECT)…

图的初识·基本概念

文章目录基本概念图有两种基本形式无向图的表示有向图的表示基本概念 图结构也是数据结构的一部分。而且还有一点小难。图是由多个结点链接而成的&#xff0c;但是一个结点可以同时连接多个其他结点&#xff0c;多个节点也可以同时指向一个节点。【多对多的关系】 图结构是任意…

如何从报表控件FastReport .NET中连接到 PostgreSQL 数据库?

FastReport.NET官方版下载 Fastreport是目前世界上主流的图表控件&#xff0c;具有超高性价比&#xff0c;以更具成本优势的价格&#xff0c;便能提供功能齐全的报表解决方案&#xff0c;连续三年蝉联全球文档创建组件和库的“ Top 50 Publishers”奖。 慧都科技是Fast Repor…

mysql索引类别和失效场景

首先&#xff0c;我们为什么要使用索引&#xff0c;索引有什么作用呢&#xff1f; 索引可以用来快速查询数据表中有某一特定值的记录&#xff0c;大大加快数据的查询速度&#xff1b;在列上创建了索引之后&#xff0c;查找数据时可以直接根据该列上的索引找到对应记录行的位置…

YOLO X 改进详解

YOLO X 主要改进&#xff1a; Anchor-Free: FCOSDecoupled detection headAdvanced label assigning strategy Network structure improvement Decoupled detection head 对比于YOLO V5, YOLO X 在detection head上有了改进。YOLO V5中&#xff0c;检测头是通过卷积同时预…