Java教程

766. Toeplitz Matrix

本文主要是介绍766. Toeplitz Matrix,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

The most simple version:

class Solution {
 public boolean isToeplitzMatrix(int[][] matrix) {
    if(matrix==null||matrix[0].length==0)
      return true;
    int m = matrix.length, n = matrix[0].length;
    for(int i=0;i<m-1;i++){
      for(int j=0;j<n-1;j++){
        if(matrix[i][j] != matrix[i+1][j+1])
           return false;
      }
    }
    return true;
  
  }
    
}

If want to avoid re-visite the same cells:

class Solution {
    public boolean isToeplitzMatrix(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        
        for(int k=0;k<n;k++){
            int i=0, j=k;
            while(i<m-1 && j<n-1){
                if(matrix[i][j]!=matrix[i+1][j+1])
                    return false;
                i++;
                j++;

            }
        }
        
        for(int k=1;k<m;k++){
            int i=k, j=0;
            while(i<m-1 && j<n-1){
                if(matrix[i][j]!=matrix[i+1][j+1])
                    return false;
                i++;
                j++;

            }
        }        
        
        return true;
    }
}

Follow up 1: load matrix one line by one line

class Solution {
public boolean isToeplitzMatrix(int[][] matrix) {
        if (matrix.length <= 1 || matrix[0].length <= 1) return true;
        Queue<Integer> q = new LinkedList<>();
        for (int i=matrix[0].length-1; i>=0; i--){ //set criteria
            q.add(matrix[0][i]);
        }
        for (int j=1; j<matrix.length; j++){ 
            q.poll();
            for (int k=matrix[j].length-1; k>0; k--){
                if (matrix[j][k] == q.poll()) // compare
                    q.add(matrix[j][k]);
                else
                    return false; 
            }
            q.add(matrix[j][0]);
        }
        return true;
    }
}

Follow up 2: load matrix one cell by one one cell

class Solution {
    // data used for logic - storage complexity O(R + C)
    HashMap<String, Integer> map = new HashMap<>();
    
    public boolean isToeplitzMatrix(int[][] matrix) {
        // consider this loop as stream of cell value and position from disk.
        for (int r = 0; r < matrix.length; r++) {
            for (int c = 0; c < matrix[0].length; c++) {
                if (!isToeplitzCell(matrix[r][c], r, c)) {
                    return false;
                }
            }
        }
        return true;
    }
    
    // We are accessing only one cell value at a time.
    private boolean isToeplitzCell(int val, int r, int c) {
        int min = Math.min(r, c);
        String cell = String.valueOf(r - min) + "," + String.valueOf(c - min);
        Integer x = map.get(cell);
        if (x == null) {
            map.put(cell, val);
        } else if (x != val) {
            return false;
        }
        return true;
    }
}

 

这篇关于766. Toeplitz Matrix的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!