网站建设与管理 ppt,wordpress极验验证注册,鞍山手机网站设计,深圳网站建设 联雅本文属于「征服LeetCode」系列文章之一#xff0c;这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁#xff0c;本系列将至少持续到刷完所有无锁题之日为止#xff1b;由于LeetCode还在不断地创建新题#xff0c;本系列的终止日期可能是永远。在这一系列刷题文章… 本文属于「征服LeetCode」系列文章之一这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁本系列将至少持续到刷完所有无锁题之日为止由于LeetCode还在不断地创建新题本系列的终止日期可能是永远。在这一系列刷题文章中我不仅会讲解多种解题思路及其优化还会用多种编程语言实现题解涉及到通用解法时更将归纳总结出相应的算法模板。 为了方便在PC上运行调试、分享代码文件我还建立了相关的仓库。在这一仓库中你不仅可以看到LeetCode原题链接、题解代码、题解文章链接、同类题目归纳、通用解法总结等还可以看到原题出现频率和相关企业等重要信息。如果有其他优选题解还可以一同分享给他人。 由于本系列文章的内容随时可能发生更新变动欢迎关注和收藏征服LeetCode系列文章目录一文以作备忘。 骑士在一张 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 中的所有整数 互不相同 解法 直接模拟
题目要求骑士的移动的每一步均按照「日」字形跳跃假设从位置 ( x 1 , y 1 ) (x_1, y_1) (x1,y1) 跳跃到 ( x 2 , y 2 ) (x_2, y_2) (x2,y2) 则此时一定满足下面两种情形之一 ∣ x 1 − x 2 ∣ 1 , ∣ y 1 − y 2 ∣ 2 |x_1 - x_2| 1, |y_1 - y_2| 2 ∣x1−x2∣1,∣y1−y2∣2
设矩阵的长度为 n n n 其中 g r i d [ r o w ] [ c o l ] grid[row][col] grid[row][col] 表示单元格 ( r o w , c o l ) (row,col) (row,col)是骑士访问的第 g r i d [ r o w ] [ c o l ] grid[row][col] grid[row][col] 个单元格因此可以知道每个单元格的访问顺序我们用 i n d i c e s indices indices 存储单元格的访问顺序其中 i n d i c e s [ i ] indices[i] indices[i] 表示骑士在经过第 i − 1 i-1 i−1 次跳跃后的位置。
由于骑士的行动是从下标 0 0 0 开始的因此一定需要满足 g r i d [ 0 ] [ 0 ] 0 grid[0][0]0 grid[0][0]0 接下来依次遍历 i n d i c e s indices indices 中的每个元素。由于 i n d i c e s [ i ] indices[i] indices[i] 是一次跳跃的起点 i n d i c e s [ i 1 ] indices[i1] indices[i1] 是该次跳跃的终点则依次检测每一次跳跃的行动路径是否为「日」字形即满足如下条件 ∣ indices [ i ] [ 0 ] − indices [ i 1 ] [ 0 ] ∣ 1 , ∣ indices [ i ] [ 1 ] − indices [ i 1 ] [ 1 ] ∣ 2 ∣ |\textit{indices}[i][0] - \textit{indices}[i1][0]| 1, |\textit{indices}[i][1] - \textit{indices}[i1][1]| 2∣ ∣indices[i][0]−indices[i1][0]∣1,∣indices[i][1]−indices[i1][1]∣2∣ ∣ indices [ i ] [ 0 ] − indices [ i 1 ] [ 0 ] ∣ 2 , ∣ indices [ i ] [ 1 ] − indices [ i 1 ] [ 1 ] ∣ 1 ∣ |\textit{indices}[i][0] - \textit{indices}[i1][0]| 2, |\textit{indices}[i][1] - \textit{indices}[i1][1]| 1∣ ∣indices[i][0]−indices[i1][0]∣2,∣indices[i][1]−indices[i1][1]∣1∣ 。
为了方便计算我们只需检测 ∣ x 1 − x 2 ∣ × ∣ y 1 − y 2 ∣ |x_1 - x_2| \times |y_1 - y_2| ∣x1−x2∣×∣y1−y2∣ 是否等于 2 2 2 即可。如果所有跳跃路径均合法则返回 true \text{true} true 否则返回 false \text{false} false 。
class Solution {
public:bool checkValidGrid(vectorvectorint grid) {if (grid[0][0] ! 0) return false;int n grid.size();vectorarrayint, 2 indices(n * n);for (int i 0; i n; i) for (int j 0; j n; j)indices[grid[i][j]] {i, j};for (int i 1; i indices.size(); i) {int dx abs(indices[i][0] - indices[i - 1][0]);int dy abs(indices[i][1] - indices[i - 1][1]);if (dx * dy ! 2) return false;}return true;}
};复杂度分析
时间复杂度 O ( n 2 ) O(n^2) O(n2) 其中 n n n 表示二维棋盘边的长度。需要检测棋盘中的每个位置一共需要检测 n 2 n^2 n2 个位置因此时间复杂度为 O ( n 2 ) O(n^2) O(n2) 。空间复杂度 O ( n 2 ) O(n^2) O(n2) 其中 n n n 表示二维棋盘边的长度。用来需要存放每个位置的访问顺序一共有 n 2 n^2 n2 个位置需要的空间为 O ( n 2 ) O(n^2) O(n2) 。
