当前位置: 首页 > 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…...

网络编程(Modbus进阶)

思维导图 Modbus RTU&#xff08;先学一点理论&#xff09; 概念 Modbus RTU 是工业自动化领域 最广泛应用的串行通信协议&#xff0c;由 Modicon 公司&#xff08;现施耐德电气&#xff09;于 1979 年推出。它以 高效率、强健性、易实现的特点成为工业控制系统的通信标准。 包…...

XML Group端口详解

在XML数据映射过程中&#xff0c;经常需要对数据进行分组聚合操作。例如&#xff0c;当处理包含多个物料明细的XML文件时&#xff0c;可能需要将相同物料号的明细归为一组&#xff0c;或对相同物料号的数量进行求和计算。传统实现方式通常需要编写脚本代码&#xff0c;增加了开…...

树莓派超全系列教程文档--(62)使用rpicam-app通过网络流式传输视频

使用rpicam-app通过网络流式传输视频 使用 rpicam-app 通过网络流式传输视频UDPTCPRTSPlibavGStreamerRTPlibcamerasrc GStreamer 元素 文章来源&#xff1a; http://raspberry.dns8844.cn/documentation 原文网址 使用 rpicam-app 通过网络流式传输视频 本节介绍来自 rpica…...

边缘计算医疗风险自查APP开发方案

核心目标:在便携设备(智能手表/家用检测仪)部署轻量化疾病预测模型,实现低延迟、隐私安全的实时健康风险评估。 一、技术架构设计 #mermaid-svg-iuNaeeLK2YoFKfao {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg…...

关于 WASM:1. WASM 基础原理

一、WASM 简介 1.1 WebAssembly 是什么&#xff1f; WebAssembly&#xff08;WASM&#xff09; 是一种能在现代浏览器中高效运行的二进制指令格式&#xff0c;它不是传统的编程语言&#xff0c;而是一种 低级字节码格式&#xff0c;可由高级语言&#xff08;如 C、C、Rust&am…...

全志A40i android7.1 调试信息打印串口由uart0改为uart3

一&#xff0c;概述 1. 目的 将调试信息打印串口由uart0改为uart3。 2. 版本信息 Uboot版本&#xff1a;2014.07&#xff1b; Kernel版本&#xff1a;Linux-3.10&#xff1b; 二&#xff0c;Uboot 1. sys_config.fex改动 使能uart3(TX:PH00 RX:PH01)&#xff0c;并让boo…...

CMake控制VS2022项目文件分组

我们可以通过 CMake 控制源文件的组织结构,使它们在 VS 解决方案资源管理器中以“组”(Filter)的形式进行分类展示。 🎯 目标 通过 CMake 脚本将 .cpp、.h 等源文件分组显示在 Visual Studio 2022 的解决方案资源管理器中。 ✅ 支持的方法汇总(共4种) 方法描述是否推荐…...

有限自动机到正规文法转换器v1.0

1 项目简介 这是一个功能强大的有限自动机&#xff08;Finite Automaton, FA&#xff09;到正规文法&#xff08;Regular Grammar&#xff09;转换器&#xff0c;它配备了一个直观且完整的图形用户界面&#xff0c;使用户能够轻松地进行操作和观察。该程序基于编译原理中的经典…...

Xen Server服务器释放磁盘空间

disk.sh #!/bin/bashcd /run/sr-mount/e54f0646-ae11-0457-b64f-eba4673b824c # 全部虚拟机物理磁盘文件存储 a$(ls -l | awk {print $NF} | cut -d. -f1) # 使用中的虚拟机物理磁盘文件 b$(xe vm-disk-list --multiple | grep uuid | awk {print $NF})printf "%s\n"…...

中医有效性探讨

文章目录 西医是如何发展到以生物化学为药理基础的现代医学&#xff1f;传统医学奠基期&#xff08;远古 - 17 世纪&#xff09;近代医学转型期&#xff08;17 世纪 - 19 世纪末&#xff09;​现代医学成熟期&#xff08;20世纪至今&#xff09; 中医的源远流长和一脉相承远古至…...