2020-4-15

617076674 · 617076674 · commit 145d30a99452 · 2020-04-15T10:15:45.000+08:00
diff --git a/lcci0305_sort_of_stacks/SortedStack.java b/lcci0305_sort_of_stacks/SortedStack.java
@@ -0,0 +1,24 @@
+package lcci0305_sort_of_stacks;
+
+public class SortedStack {
+
+    public SortedStack() {
+
+    }
+    
+    public void push(int val) {
+
+    }
+    
+    public void pop() {
+
+    }
+    
+    public int peek() {
+        return -1;
+    }
+    
+    public boolean isEmpty() {
+        return false;
+    }
+}
diff --git a/lcci0402_minimum_height_tree/Solution.java b/lcci0402_minimum_height_tree/Solution.java
@@ -0,0 +1,24 @@
+package lcci0402_minimum_height_tree;
+
+/**
+ * 执行用时：0ms，击败100.00%。消耗内存：39.4MB，击败100.00%。
+ */
+public class Solution {
+    public TreeNode sortedArrayToBST(int[] nums) {
+        return sortedArrayToBST(nums, 0, nums.length - 1);
+    }
+
+    private TreeNode sortedArrayToBST(int[] nums, int left, int right) {
+        if (left > right) {
+            return null;
+        }
+        if (left == right) {
+            return new TreeNode(nums[left]);
+        }
+        int mid = left + ((right - left) >> 1);
+        TreeNode treeNode = new TreeNode(nums[mid]);
+        treeNode.left = sortedArrayToBST(nums, left, mid - 1);
+        treeNode.right = sortedArrayToBST(nums, mid + 1, right);
+        return treeNode;
+    }
+}
diff --git a/lcci0402_minimum_height_tree/TreeNode.java b/lcci0402_minimum_height_tree/TreeNode.java
@@ -0,0 +1,13 @@
+package lcci0402_minimum_height_tree;
+
+public class TreeNode {
+    int val;
+
+    TreeNode left;
+
+    TreeNode right;
+
+    TreeNode(int x) {
+        val = x;
+    }
+}
diff --git a/lcci0404_check_balance/Solution.java b/lcci0404_check_balance/Solution.java
@@ -0,0 +1,23 @@
+package lcci0404_check_balance;
+
+/**
+ * 执行用时：1ms，击败100.00%。消耗内存：39.8MB，击败100.00%。
+ */
+public class Solution {
+    public boolean isBalanced(TreeNode root) {
+        if (null == root) {
+            return true;
+        }
+        if (Math.abs(getHeight(root.left) - getHeight(root.right)) > 1) {
+            return false;
+        }
+        return isBalanced(root.left) && isBalanced(root.right);
+    }
+
+    private int getHeight(TreeNode treeNode) {
+        if (null == treeNode) {
+            return 0;
+        }
+        return 1 + Math.max(getHeight(treeNode.left), getHeight(treeNode.right));
+    }
+}
diff --git a/lcci0404_check_balance/TreeNode.java b/lcci0404_check_balance/TreeNode.java
@@ -0,0 +1,13 @@
+package lcci0404_check_balance;
+
+public class TreeNode {
+    int val;
+
+    TreeNode left;
+
+    TreeNode right;
+
+    TreeNode(int x) {
+        val = x;
+    }
+}
diff --git a/question0542_01_matrix/Solution.java b/question0542_01_matrix/Solution.java
@@ -0,0 +1,51 @@
+package question0542_01_matrix;
+
+import java.util.LinkedList;
+import java.util.Queue;
+
+/**
+ * 广搜。
+ *
+ * 时间复杂度和空间复杂度均是O(m * n)。
+ *
+ * 执行用时：18ms，击败58.44%。消耗内存：42.1MB，击败100.00%。
+ */
+public class Solution {
+    public int[][] updateMatrix(int[][] matrix) {
+        int m;
+        if (null == matrix || (m = matrix.length) == 0) {
+            return new int[0][0];
+        }
+        int n;
+        if (null == matrix[0] || (n = matrix[0].length) == 0) {
+            return new int[0][0];
+        }
+        int[][] result = new int[m][n], directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
+        Queue<Integer> queue = new LinkedList<>();
+        for (int i = 0; i < m; i++) {
+            for (int j = 0; j < n; j++) {
+                if (matrix[i][j] == 0) {
+                    matrix[i][j] = -1;
+                    queue.add(i * n + j);
+                }
+            }
+        }
+        int distance = 0;
+        while (!queue.isEmpty()) {
+            int qSize = queue.size();
+            for (int i = 0; i < qSize; i++) {
+                int now = queue.poll(), nowX = now / n, nowY = now % n;
+                result[nowX][nowY] = distance;
+                for (int j = 0; j < 4; j++) {
+                    int newX = nowX + directions[j][0], newY = nowY + directions[j][1];
+                    if (newX >= 0 && newX < m && newY >= 0 && newY < n && matrix[newX][newY] != -1) {
+                        matrix[newX][newY] = -1;
+                        queue.add(newX * n + newY);
+                    }
+                }
+            }
+            distance++;
+        }
+        return result;
+    }
+}
