csharp 解法, 执行用时: 100 ms, 内存消耗: 43.9 MB, 提交时间: 2023-09-13 07:51:05

public class Solution
{
    public bool CheckValidGrid(int[][] grid)
    {
        var n = grid.Length;
        var d = new (int, int)[n * n];
        for (var i = 0; i < n; i++)
        {
            for (var j = 0; j < n; j++)
            {
                if (grid[i][j] == 0)
                {
                    if (i != 0 || j != 0) return false;
                }
                d[grid[i][j]] = (i, j);
            }
        }

        for (var i = 1; i < n * n; i++)
        {
            var a = d[i].Item1 - d[i - 1].Item1;
            var b = d[i].Item2 - d[i - 1].Item2;
            if(a*a+b*b!=5)return false;
        }
        return true;
    }
}

cpp 解法, 执行用时: 20 ms, 内存消耗: 27.3 MB, 提交时间: 2023-09-13 07:50:50

class Solution {
public:
    bool checkValidGrid(vector<vector<int>>& grid) {
        auto n=grid.size();
        pair<int,int> d[n*n];
        for(int i=0;i<n;i++)for(int j=0;j<n;j++){
            d[grid[i][j]]=pair(i,j);
            if(grid[i][j]==0)if(i!=0||j!=0)return false;
        }
        for (int i=1;i<n*n;i++) {
            auto a= abs(d[i].first-d[i-1].first);
            auto b= abs(d[i].second-d[i-1].second);
            if((a!=1||b!=2)&&(a!=2||b!=1))return false;
        }
        return true;
    }
};

ruby 解法, 执行用时: 68 ms, 内存消耗: 206.2 MB, 提交时间: 2023-09-13 07:50:09

# @param {Integer[][]} grid
# @return {Boolean}
def check_valid_grid(grid)
  n = grid.length
  d = [0] * (n * n)
  (0...n).each do |i|
    (0...n).each do |j|
      if grid[i][j] == 0
        if i != 0 || j != 0
          return false
        end
      end
      d[grid[i][j]] = [i, j]
    end
  end
  (1...n * n).each do |i|
    a = d[i][0] - d[i - 1][0]
    b = d[i][1] - d[i - 1][1]
    if (a * a + b * b) != 5
      return false
    end
  end
  true
end

dart 解法, 执行用时: 308 ms, 内存消耗: 161.3 MB, 提交时间: 2023-09-13 07:49:45

class Solution {
  bool checkValidGrid(List<List<int>> grid) {
    var n=grid.length;
    var d=List.generate(n*n, (index) =>[0,0]);
    for(var i=0;i<n;i++)for(var j=0;j<n;j++){
      if(grid[i][j]==0){
        if(i!=0||j!=0)return false;
      }
      d[grid[i][j]]=[i,j];
    }
    for(var i=1;i<n*n;i++){
      var a=d[i][0]-d[i-1][0];
      var b=d[i][1]-d[i-1][1];
      if(a*a+b*b!=5)return false;
    }
    return true;
  }
}

typescript 解法, 执行用时: 72 ms, 内存消耗: 44.1 MB, 提交时间: 2023-09-13 07:49:29

function checkValidGrid(grid: number[][]): boolean {
    let n = grid.length
    let d = new Array(n * n)
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            d[grid[i][j]]=[i,j]
            if(grid[i][j]==0){
                if(i!=0||j!=0)return false
            }
        }
    }
    for(let i=1;i<n*n;i++){
        let a=d[i][0]-d[i-1][0]
        let b=d[i][1]-d[i-1][1]
        if (a*a+b*b!=5)return false
    }
    return true
};

kotlin 解法, 执行用时: 196 ms, 内存消耗: 43.1 MB, 提交时间: 2023-09-13 07:49:02

import kotlin.math.abs

class Solution {
    fun checkValidGrid(grid: Array<IntArray>): Boolean {
        val n=grid.size
        val d=Array(n*n){Pair(0,0)}
        for(i in 0 until n){
            for (j in 0 until n){
                d[grid[i][j]]= Pair(i,j)
            }
        }
        if(d[0]!=Pair(0,0))return false
        for (i in 1 until n*n){
            val a= abs(d[i].first-d[i-1].first)
            val b= abs(d[i].second-d[i-1].second)
            if((a!=2||b!=1)&&(a!=1||b!=2))return false
        }
        return true
    }
}

rust 解法, 执行用时: 0 ms, 内存消耗: 2 MB, 提交时间: 2023-09-13 07:48:39

impl Solution {
    pub fn check_valid_grid(grid: Vec<Vec<i32>>) -> bool {
        let n=grid.len();
        let mut d=vec![(0_usize,0_usize);n*n];
        for i in 0..n{
            for j in 0..n{
                if grid[i][j]==0{
                    if i!=0||j!=0{
                        return false;
                    }
                }
                d[grid[i][j] as usize]=(i,j);
            }
        }
        for i in 1..n*n{
            let a=(d[i].0 as i32)-(d[i-1].0 as i32);
            let b=(d[i].1 as i32)-(d[i-1].1 as i32);
            if a*a+b*b!=5{
                return false;
            }
        }
        true
    }
}

rust 解法, 执行用时: 0 ms, 内存消耗: 2.2 MB, 提交时间: 2023-09-13 07:47:55

impl Solution {
    pub fn check_valid_grid(grid: Vec<Vec<i32>>) -> bool {
        let n: usize = grid.len();
        let mut places: Vec<(i32, i32)> = vec![(0, 0); n * n];
        for row in 0..n {
            for col in 0..n {
                places[grid[row][col] as usize].0 = row as i32;
                places[grid[row][col] as usize].1 = col as i32;
            }
        }
        let offset: Vec<(i32, i32)> = vec![
            (-1, -2), (-2, -1), (-2, 1), (1, -2),
            (1, 2), (2, 1), (2, -1), (-1, 2)
        ];
        if places[0].0 != 0 || places[0].1 != 0 {
            return false
        }
        for index in 1..places.len() {
            let mut is_right: bool = false;
            for offset_index in 0..8 {
                if places[index - 1].0 + offset[offset_index].0 == places[index].0 && places[index - 1].1 + offset[offset_index].1 == places[index].1 {
                    is_right = true;
                    break;
                }
            }
            if ! is_right {
                return false
            }
        }
        true
    }
}

javascript 解法, 执行用时: 64 ms, 内存消耗: 43.1 MB, 提交时间: 2023-09-13 07:47:23

/**
 * @param {number[][]} grid
 * @return {boolean}
 */
var checkValidGrid = function(grid) {
    if (grid[0][0] != 0) {
        return false;
    }
    const n = grid.length;
    let indices = Array(n * n).fill().map(() => Array(2));
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            indices[grid[i][j]][0] = i;
            indices[grid[i][j]][1] = j;
        }
    }
    for (let i = 1; i < n * n; i++) {
        let dx = Math.abs(indices[i][0] - indices[i - 1][0]);
        let dy = Math.abs(indices[i][1] - indices[i - 1][1]);
        if (dx * dy != 2) {
            return false;
        }
    }
    return true;
};

java 解法, 执行用时: 1 ms, 内存消耗: 42 MB, 提交时间: 2023-09-13 07:47:09

class Solution {
    public boolean checkValidGrid(int[][] grid) {
        if (grid[0][0] != 0) {
            return false;
        }
        int n = grid.length;
        int[][] indices = new int[n * n][2];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                indices[grid[i][j]][0] = i;
                indices[grid[i][j]][1] = j;
            }
        }
        for (int i = 1; i < n * n; i++) {
            int dx = Math.abs(indices[i][0] - indices[i - 1][0]);
            int dy = Math.abs(indices[i][1] - indices[i - 1][1]);
            if (dx * dy != 2) {
                return false;
            }
        }
        return true;
    }
}

php 解法, 执行用时: 24 ms, 内存消耗: 18.9 MB, 提交时间: 2023-09-13 07:46:32

class Solution {

    /**
     * @param Integer[][] $grid
     * @return Boolean
     */
    function checkValidGrid($grid) {
        $pos = array_fill(0, count($grid) ** 2, 0);
        foreach ($grid as $i => $row) {
            foreach ( $row as $j => $x) {
                $pos[$x] = [$i, $j];  # 记录坐标
            }
        }
        if ( $pos[0] != [0, 0] )  # 必须从左上角出发
            return false;
        for ( $i = 1; $i < count($pos); $i++ ) {
            $dx = abs($pos[$i][0] - $pos[$i-1][0]);
            $dy = abs($pos[$i][1] - $pos[$i-1][1]);
            if ( ($dx != 2 or $dy != 1) and ($dx != 1 or $dy != 2) )  # 不合法
                return false;
        }
        return true;
    }
}

golang 解法, 执行用时: 8 ms, 内存消耗: 3.7 MB, 提交时间: 2023-03-19 21:56:47

func checkValidGrid(grid [][]int) bool {
	type pair struct{ i, j int }
	pos := make([]pair, len(grid)*len(grid))
	for i, row := range grid {
		for j, x := range row {
			pos[x] = pair{i, j} // 记录坐标
		}
	}
	if pos[0] != (pair{}) { // 必须从左上角出发
		return false
	}
	for i := 1; i < len(pos); i++ {
		dx := abs(pos[i].i - pos[i-1].i)
		dy := abs(pos[i].j - pos[i-1].j) // 移动距离
		if (dx != 2 || dy != 1) && (dx != 1 || dy != 2) { // 不合法
			return false
		}
	}
	return true
}

func abs(x int) int { if x < 0 { return -x }; return x }

python3 解法, 执行用时: 48 ms, 内存消耗: 14.9 MB, 提交时间: 2023-03-19 21:56:30

# 模拟，代码实现时，可以把每个值的坐标记录到一个数组中，方便判断。
class Solution:
    def checkValidGrid(self, grid: List[List[int]]) -> bool:
        pos = [0] * (len(grid) ** 2)
        for i, row in enumerate(grid):
            for j, x in enumerate(row):
                pos[x] = (i, j)  # 记录坐标
        if pos[0] != (0, 0):  # 必须从左上角出发
            return False
        for (i, j), (x, y) in pairwise(pos):
            dx, dy = abs(x - i), abs(y - j)  # 移动距离
            if (dx != 2 or dy != 1) and (dx != 1 or dy != 2):  # 不合法
                return False
        return True