2020-4-23

617076674 · 617076674 · commit 38fd1ca954a3 · 2020-04-23T10:50:15.000+08:00
diff --git a/lcci0502_bianry_number_to_string/Solution.java b/lcci0502_bianry_number_to_string/Solution.java
@@ -0,0 +1,32 @@
+package lcci0502_bianry_number_to_string;
+
+/**
+ * 执行用时：0ms，击败100.00%。消耗内存：36.6MB，击败100.00%。
+ */
+public class Solution {
+    public String printBin(double num) {
+        if (num < 0 || num > 1) {
+            return "ERROR";
+        }
+        if (Double.compare(num, 1) == 0) {
+            return "1";
+        }
+        StringBuilder sb = new StringBuilder("0.");
+        double tmp = 0.5;
+        while (true) {
+            if (num >= tmp) {
+                sb.append(1);
+                num -= tmp;
+            } else {
+                sb.append(0);
+            }
+            tmp /= 2;
+            if (Double.compare(num, 0) == 0) {
+                return sb.toString();
+            }
+            if (sb.length() > 32) {
+                return "ERROR";
+            }
+        }
+    }
+}
diff --git a/lcci0504_closed_number/Solution.java b/lcci0504_closed_number/Solution.java
@@ -0,0 +1,56 @@
+package lcci0504_closed_number;
+
+/**
+ * 执行用时：0ms，击败100.00%。消耗内存：36.9MB，击败100.00%。
+ */
+public class Solution {
+    public int[] findClosedNumbers(int num) {
+        return new int[] {getBigger(num), getSmaller(num)};
+    }
+
+    private int getSmaller(int num) {
+        int index = 0, count1 = 0;
+        boolean flag = false;
+        while (index < 32) {
+            if ((num & (1 << index)) != 0) {
+                if (flag) {
+                    break;
+                }
+                count1++;
+            } else {
+                flag = true;
+            }
+            index++;
+        }
+        num ^= (1 << index);
+        num |= ((1 << index) - 1);
+        num &= -(1 << (index - count1 - 1));
+        if (num <= 0) {
+            return -1;
+        }
+        return num;
+    }
+
+    private int getBigger(int num) {
+        int index = 0, count0 = 0;
+        boolean flag = false;
+        while (index < 32) {
+            if ((num & (1 << index)) == 0) {
+                if (flag) {
+                    break;
+                }
+                count0++;
+            } else {
+                flag = true;
+            }
+            index++;
+        }
+        num |= (1 << index);
+        num &= -(1 << index);
+        num |= ((1 << (index - count0 - 1)) - 1);
+        if (num <= 0) {
+            return -1;
+        }
+        return num;
+    }
+}
diff --git a/lcci0508_draw_line/Solution.java b/lcci0508_draw_line/Solution.java
@@ -0,0 +1,49 @@
+package lcci0508_draw_line;
+
+/**
+ * 执行用时：0ms，击败100.00%。消耗内存：39.8MB，击败100.00%。
+ */
+public class Solution {
+    public int[] drawLine(int length, int w, int x1, int x2, int y) {
+        int[] result = new int[length];
+        int index = (w / 32) * y + x1 / 32;
+        if (length <= index) {
+            return result;
+        }
+        int firstLeft = x1 / 32 * 32, firstRight = firstLeft + 31;
+        if (x2 <= firstRight) {
+            int num = 0;
+            for (int i = x1 - firstLeft; i <= x2 - firstLeft; i++) {
+                num |= (1 << (31 - i));
+            }
+            result[index++] = num;
+            if (index == result.length) {
+                return result;
+            }
+        } else {
+            int num = 0;
+            for (int i = x1 - firstLeft; i < 32; i++) {
+                num |= (1 << (31 - i));
+            }
+            result[index++] = num;
+            if (index == result.length) {
+                return result;
+            }
+            for (int i = x1 / 32 + 1; i < x2 / 32; i++) {
+                result[index++] = -1;
+                if (index == result.length) {
+                    return result;
+                }
+            }
+            num = 0;
+            for (int i = 0; i <= x2 % 32; i++) {
+                num |= (1 << (31 - i));
+            }
+            result[index++] = num;
+            if (index == result.length) {
+                return result;
+            }
+        }
+        return result;
+    }
+}
diff --git a/lcci0801_three_steps_problem/Solution.java b/lcci0801_three_steps_problem/Solution.java
@@ -0,0 +1,29 @@
+package lcci0801_three_steps_problem;
+
+/**
+ * 动态规划。
+ *
+ * 时间复杂度是O(n)。空间复杂度是O(1)。
+ *
+ * 执行用时：19ms，击败97.88%。消耗内存：36.1MB，击败100.00%。
+ */
+public class Solution {
+    public int waysToStep(int n) {
+        if (n == 1) {
+            return 1;
+        } else if (n == 2) {
+            return 2;
+        } else if (n == 3) {
+            return 4;
+        }
+        int num1 = 1, num2 = 2, num3 = 4, index = 3, mod = 1000000007;
+        while (index < n) {
+            int tmp = num1;
+            num1 = num2;
+            num2 = num3;
+            num3 = ((tmp + num1) % mod + num2) % mod;
+            index++;
+        }
+        return num3;
+    }
+}
diff --git a/lcci0802_robot_in_a_grid/Solution.java b/lcci0802_robot_in_a_grid/Solution.java
@@ -0,0 +1,43 @@
+package lcci0802_robot_in_a_grid;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.List;
+
+/**
+ * 执行用时：1ms，击败100.00%。消耗内存：41.3MB，击败100.00%。
+ */
+public class Solution {
+    private int[][] directions = {{1, 0}, {0, 1}};
+
+    private int m, n;
+
+    public List<List<Integer>> pathWithObstacles(int[][] obstacleGrid) {
+        m = obstacleGrid.length;
+        n = obstacleGrid[0].length;
+        if (obstacleGrid[m - 1][n - 1] == 1 || obstacleGrid[0][0] == 1) {
+            return new ArrayList<>();
+        }
+        return pathWithObstacles(obstacleGrid, new int[]{0, 0});
+    }
+
+    private List<List<Integer>> pathWithObstacles(int[][] obstacleGrid, int[] now) {
+        obstacleGrid[now[0]][now[1]] = -1;
+        if (now[0] == m - 1 && now[1] == n - 1) {
+            List<List<Integer>> result = new ArrayList<>();
+            result.add(Arrays.asList(now[0], now[1]));
+            return result;
+        }
+        for (int i = 0; i < directions.length; i++) {
+            int newX = now[0] + directions[i][0], newY = now[1] + directions[i][1];
+            if (newX >= 0 && newX < m && newY >= 0 && newY < n && obstacleGrid[newX][newY] == 0) {
+                List<List<Integer>> result = pathWithObstacles(obstacleGrid, new int[] {newX, newY});
+                if (!result.isEmpty()) {
+                    result.add(0, Arrays.asList(now[0], now[1]));
+                    return result;
+                }
+            }
+        }
+        return new ArrayList<>();
+    }
+}
diff --git a/lcci0811_coin/Solution.java b/lcci0811_coin/Solution.java
@@ -0,0 +1,18 @@
+package lcci0811_coin;
+
+/**
+ * 执行用时：44ms，击败39.25%。消耗内存：43.7MB，击败100.00%。
+ */
+public class Solution {
+    public int waysToChange(int n) {
+        int[] coins = {25, 10, 5, 1}, dp = new int[n + 1];
+        dp[0] = 1;
+        for (int i = 0; i < coins.length; i++) {
+            for (int j = coins[i]; j <= n; j++) {
+                dp[j] += dp[j - coins[i]];
+                dp[j] %= 1000000007;
+            }
+        }
+        return dp[n];
+    }
+}
diff --git a/question0199_binary_tree_right_side_view/Solution1.java b/question0199_binary_tree_right_side_view/Solution1.java
@@ -1,4 +1,4 @@
-package question0199;
+package question0199_binary_tree_right_side_view;
 
 import java.util.ArrayList;
 import java.util.LinkedList;
@@ -37,4 +37,4 @@ public List<Integer> rightSideView(TreeNode root) {
         }
         return result;
     }
-}
+}
diff --git a/question0199_binary_tree_right_side_view/Solution2.java b/question0199_binary_tree_right_side_view/Solution2.java
@@ -1,4 +1,4 @@
-package question0199;
+package question0199_binary_tree_right_side_view;
 
 import java.util.ArrayList;
 import java.util.LinkedList;
@@ -37,4 +37,4 @@ public List<Integer> rightSideView(TreeNode root) {
         }
         return result;
     }
-}
+}
diff --git a/question0199_binary_tree_right_side_view/TreeNode.java b/question0199_binary_tree_right_side_view/TreeNode.java
@@ -1,11 +1,13 @@
-package question0199;
+package question0199_binary_tree_right_side_view;
 
 public class TreeNode {
     int val;
+
     TreeNode left;
+
     TreeNode right;
 
     TreeNode(int x) {
         val = x;
     }
-}
+}
diff --git a/question0518_coin_change_2/Solution2.java b/question0518_coin_change_2/Solution2.java
@@ -1,8 +1,5 @@
 package question0518_coin_change_2;
 
-import java.util.ArrayList;
-import java.util.List;
-
 /**
  * 对Solution进行降维处理。
  *
@@ -15,10 +12,8 @@ public int change(int amount, int[] coins) {
         int[] dp = new int[amount + 1];
         dp[0] = 1;
         for (int i = 0; i < coins.length; i++) {
-            for (int j = 1; j < amount + 1; j++) {
-                if (j >= coins[i]) {
-                    dp[j] += dp[j - coins[i]];
-                }
+            for (int j = coins[i]; j < amount + 1; j++) {
+                dp[j] += dp[j - coins[i]];
             }
         }
         return dp[amount];

Original file line number	Diff line number	Diff line change
`@@ -1,4 +1,4 @@`
`1`		`-package question0199;`
	`1`	`+package question0199_binary_tree_right_side_view;`
`2`	`2`
`3`	`3`	`import java.util.ArrayList;`
`4`	`4`	`import java.util.LinkedList;`
`@@ -37,4 +37,4 @@ public List<Integer> rightSideView(TreeNode root) {`
`37`	`37`	`}`
`38`	`38`	`return result;`
`39`	`39`	`}`
`40`		`-}`
	`40`	`+}`