add 766

fishercoder1534 · fishercoder1534 · commit a1088829c6c5 · 2018-01-20T21:10:38.000-08:00
diff --git a/README.md b/README.md
@@ -22,6 +22,7 @@ Your ideas/fixes/algorithms are more than welcome!
 
 |  #  |      Title     |   Solutions   | Time          | Space         | Video  | Difficulty  | Tag                   
 |-----|----------------|---------------|---------------|---------------|--------|-------------|-------------
+|766|[Toeplitz Matrix](https://leetcode.com/problems/toeplitz-matrix/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_766.java) | O(m*n) | O(1) | |Easy|
 |765|[Couples Holding Hands](https://leetcode.com/problems/couples-holding-hands/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_765.java) | O(n^2) | O(1) | |Hard| 
 |764|[Largest Plus Sign](https://leetcode.com/problems/largest-plus-sign/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_764.java) | O(n^2) | O(n^2) | |Medium| DP
 |763|[Partition Labels](https://leetcode.com/problems/partition-labels/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_763.java) | O(n) | O(1) | |Medium|
diff --git a/src/main/java/com/fishercoder/solutions/_766.java b/src/main/java/com/fishercoder/solutions/_766.java
@@ -0,0 +1,72 @@
+package com.fishercoder.solutions;
+
+/**766. Toeplitz Matrix
+ *
+ * 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:
+
+ matrix will be a 2D array of integers.
+ matrix will have a number of rows and columns in range [1, 20].
+ matrix[i][j] will be integers in range [0, 99].
+
+ */
+public class _766 {
+  public static class Solution1 {
+    public boolean isToeplitzMatrix(int[][] matrix) {
+      int m = matrix.length;
+      int n = matrix[0].length;
+      int i = 0;
+      int j = 0;
+      int sameVal = matrix[i][j];
+      while (++i < m && ++j < n) {
+        if (matrix[i][j] != sameVal) {
+          return false;
+        }
+      }
+
+      for (i = 1, j = 0; i < m; i++) {
+        int tmpI = i;
+        int tmpJ = j;
+        sameVal = matrix[i][j];
+        while (++tmpI < m && ++tmpJ < n) {
+          if (matrix[tmpI][tmpJ] != sameVal) {
+            return false;
+          }
+        }
+      }
+      for (i = 0, j = 1; j < n; j++) {
+        int tmpJ = j;
+        int tmpI = i;
+        sameVal = matrix[tmpI][tmpJ];
+        while (++tmpI < m && ++tmpJ < n) {
+          if (matrix[tmpI][tmpJ] != sameVal) {
+            return false;
+          }
+        }
+      }
+      return true;
+    }
+  }
+}
diff --git a/src/test/java/com/fishercoder/_766Test.java b/src/test/java/com/fishercoder/_766Test.java
@@ -0,0 +1,46 @@
+package com.fishercoder;
+
+import com.fishercoder.solutions._766;
+import org.junit.BeforeClass;
+import org.junit.Test;
+
+import static org.junit.Assert.assertEquals;
+
+public class _766Test {
+  private static _766.Solution1 solution1;
+  private static int[][] matrix;
+
+  @BeforeClass
+  public static void setup() {
+    solution1 = new _766.Solution1();
+  }
+
+  @Test
+  public void test1() {
+    matrix = new int[][] {
+        {1, 2, 3, 4},
+        {5, 1, 2, 3},
+        {9, 5, 1, 2}
+    };
+    assertEquals(true, solution1.isToeplitzMatrix(matrix));
+  }
+
+  @Test
+  public void test2() {
+    matrix = new int[][] {
+        {1, 2},
+        {2, 2},
+    };
+    assertEquals(false, solution1.isToeplitzMatrix(matrix));
+  }
+
+  @Test
+  public void test3() {
+    matrix = new int[][] {
+        {1, 2, 3, 4, 5, 9},
+        {5, 1, 2, 3, 4, 5},
+        {9, 5, 1, 2, 3, 4}
+    };
+    assertEquals(true, solution1.isToeplitzMatrix(matrix));
+  }
+}
