2019-10-12

617076674 · 617076674 · commit fb7f93ec34da · 2019-10-12T21:00:14.000+08:00
diff --git a/question1128_number_of_equivalent_domino_pairs/Solution1.java b/question1128_number_of_equivalent_domino_pairs/Solution1.java
@@ -0,0 +1,39 @@
+package question1128_number_of_equivalent_domino_pairs;
+
+import java.util.Arrays;
+
+/**
+ * 排序后判断。
+ *
+ * 时间复杂度是O(nlogn)，其中n为dominoes数组的长度。空间复杂度是O(1)。
+ *
+ * 执行用时：56ms，击败13.41%。消耗内存：56.1MB，击败100.00%。
+ */
+public class Solution1 {
+    public int numEquivDominoPairs(int[][] dominoes) {
+        int n = dominoes.length;
+        for (int i = 0; i < n; i++) {
+            if (dominoes[i][0] > dominoes[i][1]) {
+                int tmp = dominoes[i][0];
+                dominoes[i][0] = dominoes[i][1];
+                dominoes[i][1] = tmp;
+            }
+        }
+        Arrays.sort(dominoes, (o1, o2) -> {
+            if (o1[0] == o2[0]) {
+                return o1[1] - o2[1];
+            }
+            return o1[0] - o2[0];
+        });
+        int result = 0;
+        for (int i = 0; i < n; ) {
+            int j = i;
+            while (j + 1 < n && dominoes[i][0] == dominoes[j + 1][0] && dominoes[i][1] == dominoes[j + 1][1]) {
+                j++;
+            }
+            result += ((j - i) * (j - i + 1)) >> 1;
+            i = j + 1;
+        }
+        return result;
+    }
+}
diff --git a/question1128_number_of_equivalent_domino_pairs/Solution2.java b/question1128_number_of_equivalent_domino_pairs/Solution2.java
@@ -0,0 +1,28 @@
+package question1128_number_of_equivalent_domino_pairs;
+
+/**
+ * 哈希表。
+ *
+ * 时间复杂度是O(n)，其中n为dominoes数组的长度。空间复杂度是O(1)。
+ *
+ * 执行用时：2ms，击败99.82%。消耗内存：55.1MB，击败100.00%。
+ */
+public class Solution2 {
+    public int numEquivDominoPairs(int[][] dominoes) {
+        int[] map = new int[100];
+        for (int i = 0; i < dominoes.length; i++) {
+            int index;
+            if (dominoes[i][0] <= dominoes[i][1]) {
+                index = dominoes[i][0] * 10 + dominoes[i][1];
+            } else {
+                index = dominoes[i][1] * 10 + dominoes[i][0];
+            }
+            map[index]++;
+        }
+        int result = 0;
+        for (int num : map) {
+            result += (num * (num - 1)) >> 1;
+        }
+        return result;
+    }
+}
diff --git a/question1154_day_of_the_year/Solution.java b/question1154_day_of_the_year/Solution.java
@@ -0,0 +1,33 @@
+package question1154_day_of_the_year;
+
+/**
+ * 对闰年和非闰年进行分别处理。
+ *
+ * 时间复杂度和空间复杂度均是O(1)。
+ *
+ * 执行用时：3ms，击败81.38%。消耗内存：34.5MB，击败100.00%。
+ */
+public class Solution {
+    int[][] dayOfMonth = {{31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31},
+                          {31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}};
+
+    public int dayOfYear(String date) {
+        String[] inputs = date.split("-");
+        int year = Integer.parseInt(inputs[0]), month = Integer.parseInt(inputs[1]), day = Integer.parseInt(inputs[2]);
+        int index = 0, result = 0;
+        if (isLeapYear(year)) {
+            index++;
+        }
+        for (int i = 1; i < month; i++) {
+            result += dayOfMonth[index][i - 1];
+        }
+        return result + day;
+    }
+
+    private boolean isLeapYear(int year) {
+        if (year % 400 == 0 || (year % 4 == 0 && year % 100 != 0)) {
+            return true;
+        }
+        return false;
+    }
+}
