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

简易版抽奖活动的设计技术方案

1.前言 本技术方案旨在设计一套完整且可靠的抽奖活动逻辑,确保抽奖活动能够公平、公正、公开地进行,同时满足高并发访问、数据安全存储与高效处理等需求,为用户提供流畅的抽奖体验,助力业务顺利开展。本方案将涵盖抽奖活动的整体架构设计、核心流程逻辑、关键功能实现以及…...

Objective-C常用命名规范总结

【OC】常用命名规范总结 文章目录 【OC】常用命名规范总结1.类名&#xff08;Class Name)2.协议名&#xff08;Protocol Name)3.方法名&#xff08;Method Name)4.属性名&#xff08;Property Name&#xff09;5.局部变量/实例变量&#xff08;Local / Instance Variables&…...

《通信之道——从微积分到 5G》读书总结

第1章 绪 论 1.1 这是一本什么样的书 通信技术&#xff0c;说到底就是数学。 那些最基础、最本质的部分。 1.2 什么是通信 通信 发送方 接收方 承载信息的信号 解调出其中承载的信息 信息在发送方那里被加工成信号&#xff08;调制&#xff09; 把信息从信号中抽取出来&am…...

【Web 进阶篇】优雅的接口设计:统一响应、全局异常处理与参数校验

系列回顾&#xff1a; 在上一篇中&#xff0c;我们成功地为应用集成了数据库&#xff0c;并使用 Spring Data JPA 实现了基本的 CRUD API。我们的应用现在能“记忆”数据了&#xff01;但是&#xff0c;如果你仔细审视那些 API&#xff0c;会发现它们还很“粗糙”&#xff1a;有…...

使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台

🎯 使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台 📌 项目背景 随着大语言模型(LLM)的广泛应用,开发者常面临多个挑战: 各大模型(OpenAI、Claude、Gemini、Ollama)接口风格不统一;缺乏一个统一平台进行模型调用与测试;本地模型 Ollama 的集成与前…...

排序算法总结(C++)

目录 一、稳定性二、排序算法选择、冒泡、插入排序归并排序随机快速排序堆排序基数排序计数排序 三、总结 一、稳定性 排序算法的稳定性是指&#xff1a;同样大小的样本 **&#xff08;同样大小的数据&#xff09;**在排序之后不会改变原始的相对次序。 稳定性对基础类型对象…...

Java数值运算常见陷阱与规避方法

整数除法中的舍入问题 问题现象 当开发者预期进行浮点除法却误用整数除法时,会出现小数部分被截断的情况。典型错误模式如下: void process(int value) {double half = value / 2; // 整数除法导致截断// 使用half变量 }此时...

接口自动化测试:HttpRunner基础

相关文档 HttpRunner V3.x中文文档 HttpRunner 用户指南 使用HttpRunner 3.x实现接口自动化测试 HttpRunner介绍 HttpRunner 是一个开源的 API 测试工具&#xff0c;支持 HTTP(S)/HTTP2/WebSocket/RPC 等网络协议&#xff0c;涵盖接口测试、性能测试、数字体验监测等测试类型…...

MySQL 索引底层结构揭秘:B-Tree 与 B+Tree 的区别与应用

文章目录 一、背景知识&#xff1a;什么是 B-Tree 和 BTree&#xff1f; B-Tree&#xff08;平衡多路查找树&#xff09; BTree&#xff08;B-Tree 的变种&#xff09; 二、结构对比&#xff1a;一张图看懂 三、为什么 MySQL InnoDB 选择 BTree&#xff1f; 1. 范围查询更快 2…...

关于easyexcel动态下拉选问题处理

前些日子突然碰到一个问题&#xff0c;说是客户的导入文件模版想支持部分导入内容的下拉选&#xff0c;于是我就找了easyexcel官网寻找解决方案&#xff0c;并没有找到合适的方案&#xff0c;没办法只能自己动手并分享出来&#xff0c;针对Java生成Excel下拉菜单时因选项过多导…...