ToeplitzMatrix [source code]

public class ToeplitzMatrix {
static
/******************************************************************************/
class Solution {
    public boolean isToeplitzMatrix(int[][] matrix) {
        int R = matrix.length, C = matrix[0].length;
        if (R <= 1 || C <= 1)
            return true;
        int x = R - 1, y = 0, val = matrix[x][y], delta_x = -1, delta_y = -1;
        while (!(x == 0 && y == C - 1)) {
            if (matrix[x][y] != val)
                return false;
            if (!inBound (x + delta_x, y + delta_y, matrix)) {
                // order of the following branches are critical!
                if (x == 0)
                    y++;
                else if (y == 0)
                    x--;
                else if (y == C - 1)
                    x--;
                else if (x == R - 1)
                    y++;
                val = matrix[x][y];
                delta_x = -delta_x;
                delta_y = -delta_y;
            } else {
                x += delta_x;
                y += delta_y;
            }
        }
        return true;
    }

    boolean inBound (int x, int y, int[][] matrix) {
        int R = matrix.length, C = matrix[0].length;
        return x >= 0 && y >= 0 && x < R && y < C;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        ToeplitzMatrix.Solution tester = new ToeplitzMatrix.Solution();
        int[][][] inputs = {
            {{1,2,3,4},{5,1,2,3},{9,5,1,2}}, {{1}},
            {{1,2},{2,2}}, {{0}},
        };
        for (int i = 0; i < inputs.length / 2; i++) {
            int[][] matrix = inputs[2 * i];
            boolean ans = inputs[2 * i + 1][0][0] > 0;
            System.out.println (Printer.separator ());
            boolean output = tester.isToeplitzMatrix (matrix);
            System.out.printf ("%s -> %s, expected: %b\n", 
                Matrix.printMatrix (matrix), Printer.wrapColor (output + "", output == ans ? "green" : "red"), ans
            );
        }
    }
}

题目思路应该还是很明显的, 就是画好坐标轴, 然后实际坐标计算的时候仔细一点; 另外注意Corner Case, 毕竟Google;

另外, 感觉他题目里面是不是写错了, 写的是左上到右下, 但是例子里计算的都是左下到右上;

这题好像可以画数轴来计算, 但是之前好像有一题, 做过一个类似的, 对角线循环的思路; 这里可以尝试写一下;

本身应该是一个很简单的题目, 但是最后还是超时了, 速度是30ms (NA).

pre-leaf for diagonal traversal

这个diagonal traversal, 我一段时间没有写过, 所以现在就手生了; 在自己写的过程中, 发现一个技巧, 就是这里用pre leaf判断要比leaf判断要好用的很多;

首先, 这个题目一个自然的你要知道的处理, 就是碰壁之后, 要沿着bound滑动一个距离, 然后invert increments; 但是这个操作的触发时机并不是那么trivial: 并不是一旦碰壁就触发的; 假如你一旦在bound就触发反转, 那么你怎么处理一个diagonal的起点? 我一开始就是这样处理: 

class Solution {  
    public boolean isToeplitzMatrix(int[][] matrix) {  
        int R = matrix.length, C = matrix[0].length;  
        if (R <= 1 || C <= 1)  
            return true;  
        int x = R - 1, y = 0, val = matrix[x][y], delta_x = -1, delta_y = -1;  
        while (!(x == 0 && y == C - 1)) {  
            if (x == 0 || y == 0 || x == R - 1 || y == C - 1) {  
                if (x == 0)  
                    y++;  
                else if (y == 0)  
                    x--;  
                else if (x == R - 1)  
                    y++;  
                else if (y == C - 1)  
                    x--;  

                val = matrix[x][y];  
                delta_x = -delta_x;  
                delta_y = -delta_y;  
                x += delta_x;  
                y += delta_y;  
            }  
            if (matrix[x][y] != val)  
                return false;  
            x += delta_x;  
            y += delta_y;  
        }  
        return true;  
    }  
}

但是最后发现这个代码错的很离谱, 而且完全不知道怎么修改, 就是因为这里依赖的是一个leaf判断, 很麻烦; 但是改成pre leaf的思路之后, 就豁然开朗了;

另外, 这题还有一个关键的地方, 就是: 

if (x == 0)  
    y++;  
else if (y == 0)  
    x--;  
else if (x == R - 1)  
    y++;  
else if (y == C - 1)  
    x--;

这四个branch的顺序关系至关重要; 用这个优先级操作, 来保证当我们在两个bound的交点(顶点)的位置的时候, 能够有正确的处理; 首先, 你还是要笔算来总结规律; 就按照题目中给的这个3x4的矩阵, 我们要把所有的bound位置划分成四个区域: 

A: [0][0..C-1]  
B: [1..R-1][0]  
C: [0..R-1][C-1]  
D: [R-1][0..C-2]

这四个区域, 分别对应上面四个有优先级从上到下的branch; 注意, 左上角我们放到了A而不是B, 右下角我们放在了C而不是D, 这个是因为笔算了一个trace之后得到的决定; 通过这样一个归类, 就不要单独判断顶点(当然这样也可以, 是最直接最保险的办法: 先把两个顶点作为最开始的两个branch处理掉), 而每一个branch可以只判断一个bound就行了;

下面就剩下起点的处理了; 当然你可能说左下角本身其实是不用处理的; 但是为了代码的一致性, 我这里还是从这里开始; 一个需要注意的地方就是, 你给左下角的方向应该是(-1, -1)而不是(1, 1): 因为我们希望在左下角这个位置按照上面四个branch的正常流程进行一个反转操作; 所以在(2, 0)的地方, 我们希望下一步滑到(1, 0)的位置, 并且方向反转到(1, 1), 就行了;

editorial

Approach #1: Group by Category [Accepted]

Intuition and Algorithm

We ask what feature makes two coordinates (r1, c1) and (r2, c2) belong to the same diagonal?

It turns out two coordinates are on the same diagonal if and only if r1 - c1 == r2 - c2.

This leads to the following idea: remember the value of that diagonal as groups[r-c]. If we see a mismatch, the matrix is not Toeplitz; otherwise it is. 

class Solution {  
    public boolean isToeplitzMatrix(int[][] matrix) {  
        Map<Integer, Integer> groups = new HashMap();  
        for (int r = 0; r < matrix.length; ++r) {  
            for (int c = 0; c < matrix[0].length; ++c) {  
                if (!groups.containsKey(r-c))  
                    groups.put(r-c, matrix[r][c]);  
                else if (groups.get(r-c) != matrix[r][c])  
                    return False;  
            }  
        }  
        return True;  
    }  
}

这个思路是类似我一开始的对角线扫描的思路, 但是他最后实现的方法比我的方法简单很多; 我的方法还是不停的increment这个扫描线的offset, 然后看跟matrix的交点; 这样一个思路就太姜了, 太局限于数学计算上的思维. 他这里的方法, 直接就是正常的走这个matrix, 关键是注意到, diagonal最后实际上对应的不过是坐标之间的数学关系.

依赖于这个intuition, 他最后的思路就是建立一个keyed by relation (x, y)的Map; 每一个坐标(x, y)都在一个diagonal上面, 所以relation函数对于每一个坐标(x, y)都有效; 这个函数的返回值就直接对赢了这个坐标所在的diagonal;

这里给出了diagonal问题的另外一个思路: 不要总是想着diagonal线条本身, 而是单纯的把diagonal看成是其上的坐标点本身的一个普通的性质而已;

Approach #2: Compare With Top-Left Neighbor [Accepted]

Intuition and Algorithm

For each diagonal with elements in order a1,a2,a3,…,ak
, we can check a1=a2,a2=a3,…,ak−1=ak
. The matrix is Toeplitz if and only if all of these conditions are true for all (top-left to bottom-right) diagonals.

Every element belongs to some diagonal, and it's previous element (if it exists) is it's top-left neighbor. Thus, for the square (r, c), we only need to check r == 0 OR c == 0 OR matrix[r-1][c-1] == matrix[r][c]. 

class Solution {  
    public boolean isToeplitzMatrix(int[][] matrix) {  
        for (int r = 0; r < matrix.length; ++r)  
            for (int c = 0; c < matrix[0].length; ++c)  
                if (r > 0 && c > 0 && matrix[r-1][c-1] != matrix[r][c])  
                    return false;  
        return true;  
    }  
}

这个方法是对题目要求的进一步转化; 这个做法并没有盯着diagonal这个关键词下功夫, 而是去理解, equal diagonal这个条件到底可以怎么利用. again, 他还是转换到了直接每一个坐标点自己的一个性质;

总体来说, 虽然我自己做这一题的时候学到了东西, 但是还是稍微犯了一点over general的毛病: 希望用宰牛刀来解决每一个问题; 有时候适当的分析题目本身的个性也不失一个好的办法; 当然, 最后这个结果应该还是可以满意的, 毕竟复习了diagonal traversal;

discussion基本都是跟editorial2类似的解法; submission暂时没有;

Problem Description

A matrix is Toeplitz if every diagonal from top-left to bottom-right has the same element.

Now given an M x N matrix, return True if and only if the matrix is Toeplitz.

Example 1: 

Input: matrix = [[1,2,3,4],[5,1,2,3],[9,5,1,2]]  
Output: True  
Explanation:  
1234  
5123  
9512  

In the above grid, the diagonals are "[9]", "[5, 5]", "[1, 1, 1]", "[2, 2, 2]", "[3, 3]", "[4]", and in each diagonal all elements are the same, so the answer is True.

Example 2: 

Input: matrix = [[1,2],[2,2]]  
Output: False  
Explanation:  
The diagonal "[1, 2]" has different elements.

Note:

  1. matrix will be a 2D array of integers.
  2. matrix will have a number of rows and columns in range [1, 20].
  3. matrix[i][j] will be integers in range [0, 99].

Difficulty:Easy
Total Accepted:4.3K
Total Submissions:6.6K
Contributor:zafarella
Companies
google
Related Topics
array
Similar Questions
Valid Word Square

Hint 1
Check whether each value is equal to the value of it's top-left neighbor.

results matching ""

    No results matching ""