大型网站的空间,深圳网站建设公司业务招聘,创意100图片欣赏,贵州城乡和住房建设厅网站【LetMeFly】2596.检查骑士巡视方案
力扣题目链接#xff1a;https://leetcode.cn/problems/check-knight-tour-configuration/
骑士在一张 n x n 的棋盘上巡视。在有效的巡视方案中#xff0c;骑士会从棋盘的 左上角 出发#xff0c;并且访问棋盘上的每个格子 恰好一次 。…【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].length3 n 70 grid[row][col] n * ngrid 中的所有整数 互不相同
方法一排序 模拟
创建一个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 pairint, int pii;
class Solution {
public:bool checkValidGrid(vectorvectorint grid) {int n grid.size();vectorpii 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原创不易转载经作者同意后请附上原文链接哦~ Tisfyhttps://letmefly.blog.csdn.net/article/details/132847346
