2020-6-20

zhuchen · zhuchen · commit 468da7d63fd6 · 2021-06-20T23:07:11.000+08:00
diff --git a/question0458_poor_pigs/Solution.java b/question0458_poor_pigs/Solution.java
@@ -0,0 +1,10 @@
+package question0458_poor_pigs;
+
+public class Solution {
+
+  public int poorPigs(int buckets, int minutesToDie, int minutesToTest) {
+    int states = minutesToTest / minutesToDie + 1;
+    return (int) Math.ceil(Math.log(buckets) / Math.log(states));
+  }
+
+}
diff --git a/question0479_largest_palindrome_product/Solution.java b/question0479_largest_palindrome_product/Solution.java
@@ -0,0 +1,31 @@
+package question0479_largest_palindrome_product;
+
+public class Solution {
+
+    public int largestPalindrome(int n) {
+        if (n == 1) {
+            return 9;
+        }
+        int upper = (int) (Math.pow(10, n) - 1), lower = (int) Math.pow(10, n - 1);
+        for (int i = upper; i >= lower; i--) {
+            String s = String.valueOf(i);
+            String reverseS = reverse(s);
+            long num = Long.parseLong(s + reverseS);
+            for (long j = upper; j * j >= num; j--) {
+                if (num % j == 0) {
+                    return (int) (num % 1337);
+                }
+            }
+        }
+        return -1;
+    }
+
+    private static String reverse(String s) {
+        StringBuilder sb = new StringBuilder();
+        for (int i = s.length() - 1; i >= 0; i--) {
+            sb.append(s.charAt(i));
+        }
+        return sb.toString();
+    }
+
+}
diff --git a/question0493_reverse_pairs/Solution.java b/question0493_reverse_pairs/Solution.java
@@ -0,0 +1,50 @@
+package question0493_reverse_pairs;
+
+public class Solution {
+
+  public int reversePairs(int[] nums) {
+    if (nums.length == 0) {
+      return 0;
+    }
+    return reversePairsRecursive(nums, 0, nums.length - 1);
+  }
+
+  public int reversePairsRecursive(int[] nums, int left, int right) {
+    if (left == right) {
+      return 0;
+    }
+    int mid = left + ((right - left) >> 1), resultLeft = reversePairsRecursive(nums, left, mid),
+        resultRight = reversePairsRecursive(nums, mid + 1, right),
+        result = resultLeft + resultRight;
+    // 首先统计下标对的数量
+    int i = left, j = mid + 1;
+    while (i <= mid) {
+      while (j <= right && (long) nums[i] > 2 * (long) nums[j]) {
+        j++;
+      }
+      result += j - mid - 1;
+      i++;
+    }
+    // 随后合并两个排序数组
+    int[] copy = new int[right - left + 1];
+    int index1 = left, index2 = mid + 1, index = 0;
+    while (index1 <= mid || index2 <= right) {
+      if (index1 > mid) {
+        copy[index++] = nums[index2++];
+      } else if (index2 > right) {
+        copy[index++] = nums[index1++];
+      } else {
+        if (nums[index1] < nums[index2]) {
+          copy[index++] = nums[index1++];
+        } else {
+          copy[index++] = nums[index2++];
+        }
+      }
+    }
+    for (int k = 0; k < copy.length; k++) {
+      nums[left + k] = copy[k];
+    }
+    return result;
+  }
+
+}
