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

LeetCode 2596. 检查骑士巡视方案

【LetMeFly】2596.检查骑士巡视方案

力扣题目链接:https://leetcode.cn/problems/check-knight-tour-configuration/

骑士在一张 n x n 的棋盘上巡视。在有效的巡视方案中,骑士会从棋盘的 左上角 出发,并且访问棋盘上的每个格子 恰好一次

给你一个 n x n 的整数矩阵 grid ,由范围 [0, n * n - 1] 内的不同整数组成,其中 grid[row][col] 表示单元格 (row, col) 是骑士访问的第 grid[row][col] 个单元格。骑士的行动是从下标 0 开始的。

如果 grid 表示了骑士的有效巡视方案,返回 true;否则返回 false

注意,骑士行动时可以垂直移动两个格子且水平移动一个格子,或水平移动两个格子且垂直移动一个格子。下图展示了骑士从某个格子出发可能的八种行动路线。

 

示例 1:

输入:grid = [[0,11,16,5,20],[17,4,19,10,15],[12,1,8,21,6],[3,18,23,14,9],[24,13,2,7,22]]
输出:true
解释:grid 如上图所示,可以证明这是一个有效的巡视方案。

示例 2:

输入:grid = [[0,3,6],[5,8,1],[2,7,4]]
输出:false
解释:grid 如上图所示,考虑到骑士第 7 次行动后的位置,第 8 次行动是无效的。

 

提示:

  • n == grid.length == grid[i].length
  • 3 <= n <= 7
  • 0 <= grid[row][col] < n * n
  • grid 中的所有整数 互不相同

方法一:排序 + 模拟

创建一个indices数组,indices[i]代表第i步要跳到的位置(只需要遍历一遍grid数组即可完成indices数组)。

使用两个变量 n o w X nowX nowX n o w Y nowY nowY,代表当前的位置。

遍历indices数组,如果下一个位置 和 当前位置不是“日”字型,则返回false。

最终返回true。

细节描述:

Q1: 如何确定相邻两个位置是否是日字型?

A1: 看“横坐标之差×纵坐标之差”是否等于2。

Q2: 如何优雅地判断骑士是否由“左上角”出发?特判grid[0][0]是否为0不够优雅。

A2: 初始位置可以设置为(-2, -1),这样首个位置必须是(0, 0)才满足日字型。

  • 时间复杂度 O ( n 2 ) O(n^2) O(n2),其中 s i z e ( g i r d ) = n × n size(gird) = n\times n size(gird)=n×n
  • 空间复杂度 O ( n 2 ) O(n^2) O(n2)

AC代码

C++
typedef pair<int, int> pii;
class Solution {
public:bool checkValidGrid(vector<vector<int>>& grid) {int n = grid.size();vector<pii> indices(n * n);for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {indices[grid[i][j]] = {i, j};}}int nowX = -2, nowY = -1;for (int i = 0; i < n * n; i++) {int nextX =indices[i].first, nextY = indices[i].second;if (abs(nowX - nextX) * abs(nowY - nextY) != 2) {return false;}nowX = nextX, nowY = nextY;}return true;}
};
Python
# from typing import Listclass Solution:def checkValidGrid(self, grid: List[List[int]]) -> bool:n = len(grid)indices = [0] * n ** 2for i in range(n):for j in range(n):indices[grid[i][j]] = [i, j]nowX, nowY = -2, -1for i in range(n * n):nextX, nextY = indices[i]if abs(nextX - nowX) * abs(nextY - nowY) != 2:return FalsenowX, nowY = indices[i]return True

同步发文于CSDN,原创不易,转载经作者同意后请附上原文链接哦~
Tisfy:https://letmefly.blog.csdn.net/article/details/132847346

相关文章:

LeetCode 2596. 检查骑士巡视方案

【LetMeFly】2596.检查骑士巡视方案 力扣题目链接&#xff1a;https://leetcode.cn/problems/check-knight-tour-configuration/ 骑士在一张 n x n 的棋盘上巡视。在有效的巡视方案中&#xff0c;骑士会从棋盘的 左上角 出发&#xff0c;并且访问棋盘上的每个格子 恰好一次 。…...

大数据学习1.0-目录

学习内容持续更新ing 1.大数据学习1.1-Centos8虚拟机安装 大数据学习1.0-Centos8虚拟机安装_汉卿HanQ的博客-CSDN博客 2.大数据学习1.2-yum配置 大数据学习1.2-yum配置_汉卿HanQ的博客-CSDN博客 3.大数据学习1.3-xShell配置jdk 大数据学习1.3-xShell配置jdk_汉卿HanQ的博客…...

无涯教程-JavaScript - POWER函数

描述 POWER函数返回加到幂的数字的输出。 语法 POWER (number, power)争论 Argument描述Required/OptionalNumber 基数。 它可以是任何实数。 RequiredPowerThe exponent to which the base number is raised.Required Notes 可以使用" ^"运算符代替POWER来指示…...

ChatGPT:解释Java中 ‘HttpResponse‘ 使用 ‘try-with-resources‘ 的警告和处理 ‘Throwable‘ 打印警告

ChatGPT&#xff1a;解释Java中 ‘HttpResponse’ 使用 ‘try-with-resources’ 的警告和处理 ‘Throwable’ 打印警告 我在IDEA中对一个函数的警告点击了ignore&#xff0c;怎么撤回这个呢 ChatGPT&#xff1a; 要撤回在IDEA中对一个函数的警告的忽略&#xff0c;您可以按照以…...

Linux编辑器-gcc的使用

一&#xff1a;背景知识 1.预处理&#xff08;头文件展开、去注释、宏替换、条件编译&#xff09; 2.编译&#xff08;由C生成汇编&#xff09; 3.汇编&#xff08;生成及其可识别代码&#xff09; 4.连接&#xff08;生成可执行文件或库文件&#xff09; 二&#xff1a;gcc…...

第16篇ESP32 platformio_arduino框架 wifi联网_连接WiFi热点并连接tcp server收发数据进行通讯

第1篇:Arduino与ESP32开发板的安装方法 第2篇:ESP32 helloword第一个程序示范点亮板载LED 第3篇:vscode搭建esp32 arduino开发环境 第4篇:vscodeplatformio搭建esp32 arduino开发环境 ​​​​​​第5篇:doit_esp32_devkit_v1使用pmw呼吸灯实验 第6篇:ESP32连接无源喇叭播…...

day1| 704. 二分查找、27. 移除元素

704. 二分查找 题目链接&#xff1a;https://leetcode.cn/problems/binary-search/ 文档讲解&#xff1a;https://programmercarl.com/0704.%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE.html 视频讲解&#xff1a;https://www.bilibili.com/video/BV1fA4y1o715 1、二分法的前提 这道…...

R绘制箱线图

代码大部分来自boxplot()函数的帮助文件&#xff0c;可以通过阅读帮助文件&#xff0c;调整代码中相应参数看下效果&#xff0c;进而可以理解相应的作用&#xff0c;帮助快速掌握barplot()函数的用法。 语法 Usage(来自帮助文件) barplot(height, ...)## Default S3 method: …...

利用Audit审计系统行为

标题利用Audit审计系统行为 Linux Audit守护进程是一个可以审计Linux系统事件的框架 这个框架本身有数个组件&#xff0c;包括内核、二进制文件及其他文件。 1.内核audit&#xff1a;钩在内核中来捕获事件并将它们发送到auditd。 2.二进制文件 auditd&#xff1a;捕捉事件并…...

uniapp:不同权限设置不同的tabBar

1、在pages.json里&#xff0c;将所有tabBar涉及的页面都加进来。 我这里使用username来动态显示tabBar。 jeecg用户显示&#xff1a;首页&#xff0c;订单&#xff0c;消息&#xff0c;发现&#xff0c;我的&#xff0c;一共5个tabBar。 admin用户显示&#xff1a;首页&…...

如何将本地的项目上传到Git

一、GitHub or GitLab or Gitee创建一个新的仓库 二、仓库路径创建成功后&#xff0c;将本地项目上传到git 1. 进入本地项目所在文件夹位置&#xff0c;右击 2.出现git命令框 输入git init 在当前项目的目录中生成本地的git管理&#xff08;会发现在当前目录下多了一个.git文件…...

[php] 文件上传的一个项目emmm

项目完整地址 <!DOCTYPE html> <html lang"zh"> <head><meta charset"UTF-8"><title>上传文件</title><link href"./css/bootstrap.min.css" rel"stylesheet"><style>font-face {fo…...

uniapp-时间格式和距离格式的转换

时间格式的转换 第一种是把 YYYY-MM-DD hh:mm:ss 转换成 MM月DD日 第二种是把 hh:mm:ss 转换成 hh:mm /*** 格式化时间 1* 把传入的完整时间分为 MM月DD日 的格式* returns*/ export function formatDate(timeStr) {const date new Date(timeStr);const month (date.ge…...

【卖出备兑看涨期权策略(Covered_call)】

卖出备兑看涨期权策略&#xff08;Covered_call&#xff09; 卖出备兑看涨期权策略是一种最基本的收入策略&#xff0c;该策略主要操作就是在持有标的资产的同时卖出对应的看涨期权合约&#xff0c;以此来作为从持有的标的资产中获取租金的一种方法。如果标的资产的价格上涨到…...

【校招VIP】测试算法考点之智力分析

考点介绍&#xff1a; 智力题(逻辑分析题&#xff09;准备校招的同学们好好准备下,测试笔试中经常遇到。 测试算法考点之智力分析-相关题目及解析内容可点击文章末尾链接查看&#xff01; 一、考点试题 1.5个囚犯在装有100颗豆子的袋子里摸,他们谁的存活几率大? 5个囚犯,分…...

【Linux 服务器运维】定时任务 crontab 详解 | 文末送书

文章目录 前言一、crontab 介绍1.1 什么是 crontab1.2 crontab 命令工作流程1.3 Linux 定时任务分类 二、crontab 用法详解2.1 crond 服务安装2.2 crontab 文件内容分析2.3 crontab 命令用法2.3.1 查看定时任务列表2.3.2 编辑/创建定时任务2.3.3 删除定时任务2.3.4 其他 cronta…...

Vue系列之入门篇

前言&#xff1a; 目录 一&#xff0c;关于Vue的简介 1.什么是Vue&#xff1f; 2.使用Vue框架的好处&#xff1f; 3. 库和框架的区别&#xff1a; 4. MVVM的介绍 5.Vue的入门案例 二&#xff0c;Vue的生命周期 一&#xff0c;关于Vue的简介 1.什么是Vue&#xff1f; Vu…...

【遥感卫星数据】Landsat数据Collection1和Collection2区别

文章目录 1 总体介绍2 Landsat Collection 13 Landsat Collection 23.1 Collection 2 Level-1产品3.2 Collection 2 Level-2产品参考资料1 总体介绍 Landsat卫星的产品数据每经过几年就会有一次改进,主要改进几何校正精度和辐射纠正精度。而且NASA/USGS每次更新产品都会把存档…...

socket() failed (24: Too many open files) while connecting to upstream, client

一、这个错误通常是因为文件句柄数目超过系统限制导致的。要解决这个问题&#xff0c;您可以尝试以下几个步骤&#xff1a; 调整系统文件句柄限制&#xff1a;您可以通过修改/etc/security/limits.conf文件中的nofile参数来增加系统文件句柄的最大数目。将nofile的值增加到更高…...

认识单链表

-之前我们学过储存数据的一种表——顺序表&#xff0c;那么为什么还有链表呢 首先我们回顾一下顺序表 顺序表是物理地址连续的一段内存空间&#xff08;数组&#xff09;&#xff0c;我们通过动态内存开辟的&#xff0c; 那么&#xff1a; 顺序表也有自己的一些优点&#xff0c…...

React Native 导航系统实战(React Navigation)

导航系统实战&#xff08;React Navigation&#xff09; React Navigation 是 React Native 应用中最常用的导航库之一&#xff0c;它提供了多种导航模式&#xff0c;如堆栈导航&#xff08;Stack Navigator&#xff09;、标签导航&#xff08;Tab Navigator&#xff09;和抽屉…...

Vue3 + Element Plus + TypeScript中el-transfer穿梭框组件使用详解及示例

使用详解 Element Plus 的 el-transfer 组件是一个强大的穿梭框组件&#xff0c;常用于在两个集合之间进行数据转移&#xff0c;如权限分配、数据选择等场景。下面我将详细介绍其用法并提供一个完整示例。 核心特性与用法 基本属性 v-model&#xff1a;绑定右侧列表的值&…...

基于uniapp+WebSocket实现聊天对话、消息监听、消息推送、聊天室等功能,多端兼容

基于 ​UniApp + WebSocket​实现多端兼容的实时通讯系统,涵盖WebSocket连接建立、消息收发机制、多端兼容性配置、消息实时监听等功能,适配​微信小程序、H5、Android、iOS等终端 目录 技术选型分析WebSocket协议优势UniApp跨平台特性WebSocket 基础实现连接管理消息收发连接…...

理解 MCP 工作流:使用 Ollama 和 LangChain 构建本地 MCP 客户端

&#x1f31f; 什么是 MCP&#xff1f; 模型控制协议 (MCP) 是一种创新的协议&#xff0c;旨在无缝连接 AI 模型与应用程序。 MCP 是一个开源协议&#xff0c;它标准化了我们的 LLM 应用程序连接所需工具和数据源并与之协作的方式。 可以把它想象成你的 AI 模型 和想要使用它…...

【快手拥抱开源】通过快手团队开源的 KwaiCoder-AutoThink-preview 解锁大语言模型的潜力

引言&#xff1a; 在人工智能快速发展的浪潮中&#xff0c;快手Kwaipilot团队推出的 KwaiCoder-AutoThink-preview 具有里程碑意义——这是首个公开的AutoThink大语言模型&#xff08;LLM&#xff09;。该模型代表着该领域的重大突破&#xff0c;通过独特方式融合思考与非思考…...

对WWDC 2025 Keynote 内容的预测

借助我们以往对苹果公司发展路径的深入研究经验&#xff0c;以及大语言模型的分析能力&#xff0c;我们系统梳理了多年来苹果 WWDC 主题演讲的规律。在 WWDC 2025 即将揭幕之际&#xff0c;我们让 ChatGPT 对今年的 Keynote 内容进行了一个初步预测&#xff0c;聊作存档。等到明…...

CocosCreator 之 JavaScript/TypeScript和Java的相互交互

引擎版本&#xff1a; 3.8.1 语言&#xff1a; JavaScript/TypeScript、C、Java 环境&#xff1a;Window 参考&#xff1a;Java原生反射机制 您好&#xff0c;我是鹤九日&#xff01; 回顾 在上篇文章中&#xff1a;CocosCreator Android项目接入UnityAds 广告SDK。 我们简单讲…...

相机从app启动流程

一、流程框架图 二、具体流程分析 1、得到cameralist和对应的静态信息 目录如下: 重点代码分析: 启动相机前,先要通过getCameraIdList获取camera的个数以及id,然后可以通过getCameraCharacteristics获取对应id camera的capabilities(静态信息)进行一些openCamera前的…...

什么是Ansible Jinja2

理解 Ansible Jinja2 模板 Ansible 是一款功能强大的开源自动化工具&#xff0c;可让您无缝地管理和配置系统。Ansible 的一大亮点是它使用 Jinja2 模板&#xff0c;允许您根据变量数据动态生成文件、配置设置和脚本。本文将向您介绍 Ansible 中的 Jinja2 模板&#xff0c;并通…...

Pinocchio 库详解及其在足式机器人上的应用

Pinocchio 库详解及其在足式机器人上的应用 Pinocchio (Pinocchio is not only a nose) 是一个开源的 C 库&#xff0c;专门用于快速计算机器人模型的正向运动学、逆向运动学、雅可比矩阵、动力学和动力学导数。它主要关注效率和准确性&#xff0c;并提供了一个通用的框架&…...