Valid soduku (examplehub#195)

realDuYuanChao · web-flow · commit d2d100b03134 · 2021-11-05T10:57:26.000+08:00
* ValidSudoku

* valid sudoku
diff --git a/src/main/java/com/examplehub/leetcode/middle/ValidSudoku.java b/src/main/java/com/examplehub/leetcode/middle/ValidSudoku.java
@@ -0,0 +1,68 @@
+package com.examplehub.leetcode.middle;
+
+/**
+ * https://leetcode.com/problems/valid-sudoku/
+ */
+public class ValidSudoku {
+  public static boolean solution1(char[][] board) {
+
+    //travel all rows to check
+    for (int i = 0; i < 9; i++) {
+      int[] digitTable = new int[10];
+      for (int j = 0; j < 9; j++) {
+        if (board[i][j] != '.') {
+          digitTable[board[i][j] - '0']++;
+        }
+      }
+      if (containsRepeat(digitTable)) {
+        return false;
+      }
+    }
+
+    //travel all columns to check
+    for (int i = 0; i < 9; i++) {
+      int[] digitTable = new int[10];
+      for (int j = 0; j < 9; j++) {
+        if (board[j][i] != '.') {
+          digitTable[board[j][i] - '0']++;
+        }
+      }
+      if (containsRepeat(digitTable)) {
+        return false;
+      }
+    }
+
+    //travel all sub-box
+    //TODO
+    return true;
+  }
+
+  public static boolean containsRepeat(int[] table) {
+    for (int num : table) {
+      if (num > 1) {
+        return true;
+      }
+    }
+    return false;
+  }
+
+  public static boolean solution2(char[][] board) {
+    int[][] rows = new int[9][9];
+    int[][] cols = new int[9][9];
+    int[][][] subBoxes = new int[3][3][9];
+    for (int i = 0; i < 9; ++i) {
+      for (int j = 0; j < 9; ++j) {
+        if (board[i][j] != '.') {
+          int index = board[i][j] - '1';
+          rows[i][index]++;
+          cols[j][index]++;
+          subBoxes[i / 3][j / 3][index]++;
+          if (rows[i][index] > 1 || cols[j][index] > 1 || subBoxes[i / 3][j / 3][index] > 1) {
+            return false;
+          }
+        }
+      }
+    }
+    return true;
+  }
+}
diff --git a/src/test/java/com/examplehub/leetcode/middle/ValidSudokuTest.java b/src/test/java/com/examplehub/leetcode/middle/ValidSudokuTest.java
@@ -0,0 +1,68 @@
+
+
+package com.examplehub.leetcode.middle;
+
+import org.junit.jupiter.api.Test;
+
+import static org.junit.jupiter.api.Assertions.*;
+
+class ValidSudokuTest {
+
+  @Test
+  void testSolution1() {
+    char[][] board = {
+            {'5', '3', '.', '.', '7', '.', '.', '.', '.'},
+            {'6', '.', '.', '1', '9', '5', '.', '.', '.'},
+            {'.', '9', '8', '.', '.', '.', '.', '6', '.'},
+            {'8', '.', '.', '.', '6', '.', '.', '.', '3'},
+            {'4', '.', '.', '8', '.', '3', '.', '.', '1'},
+            {'7', '.', '.', '.', '2', '.', '.', '.', '6'},
+            {'.', '6', '.', '.', '.', '.', '2', '8', '.'},
+            {'.', '.', '.', '4', '1', '9', '.', '.', '5'},
+            {'.', '.', '.', '.', '8', '.', '.', '7', '9'},
+    };
+    assertTrue(ValidSudoku.solution1(board));
+
+    board = new char[][]{
+            {'8', '3', '.', '.', '7', '.', '.', '.', '.'},
+            {'6', '.', '.', '1', '9', '5', '.', '.', '.'},
+            {'.', '9', '8', '.', '.', '.', '.', '6', '.'},
+            {'8', '.', '.', '.', '6', '.', '.', '.', '3'},
+            {'4', '.', '.', '8', '.', '3', '.', '.', '1'},
+            {'7', '.', '.', '.', '2', '.', '.', '.', '6'},
+            {'.', '6', '.', '.', '.', '.', '2', '8', '.'},
+            {'.', '.', '.', '4', '1', '9', '.', '.', '5'},
+            {'.', '.', '.', '.', '8', '.', '.', '7', '9'},
+    };
+    assertFalse(ValidSudoku.solution1(board));
+  }
+
+  @Test
+  void testSolution2() {
+    char[][] board = {
+            {'5', '3', '.', '.', '7', '.', '.', '.', '.'},
+            {'6', '.', '.', '1', '9', '5', '.', '.', '.'},
+            {'.', '9', '8', '.', '.', '.', '.', '6', '.'},
+            {'8', '.', '.', '.', '6', '.', '.', '.', '3'},
+            {'4', '.', '.', '8', '.', '3', '.', '.', '1'},
+            {'7', '.', '.', '.', '2', '.', '.', '.', '6'},
+            {'.', '6', '.', '.', '.', '.', '2', '8', '.'},
+            {'.', '.', '.', '4', '1', '9', '.', '.', '5'},
+            {'.', '.', '.', '.', '8', '.', '.', '7', '9'},
+    };
+    assertTrue(ValidSudoku.solution2(board));
+
+    board = new char[][]{
+            {'8', '3', '.', '.', '7', '.', '.', '.', '.'},
+            {'6', '.', '.', '1', '9', '5', '.', '.', '.'},
+            {'.', '9', '8', '.', '.', '.', '.', '6', '.'},
+            {'8', '.', '.', '.', '6', '.', '.', '.', '3'},
+            {'4', '.', '.', '8', '.', '3', '.', '.', '1'},
+            {'7', '.', '.', '.', '2', '.', '.', '.', '6'},
+            {'.', '6', '.', '.', '.', '.', '2', '8', '.'},
+            {'.', '.', '.', '4', '1', '9', '.', '.', '5'},
+            {'.', '.', '.', '.', '8', '.', '.', '7', '9'},
+    };
+    assertFalse(ValidSudoku.solution2(board));
+  }
+}
