update leetcode (examplehub#145)

realDuYuanChao · github-actions · web-flow · commit 2005cf7f7df3 · 2021-08-05T20:53:28.000+08:00
* valid-anagram

* missing number

* Formatted with Google Java Formatter

Co-authored-by: github-actions &lt;${GITHUB_ACTOR}@users.noreply.github.com&gt;
diff --git a/src/main/java/com/examplehub/leetcode/easy/MissingNumber.java b/src/main/java/com/examplehub/leetcode/easy/MissingNumber.java
@@ -0,0 +1,49 @@
+package com.examplehub.leetcode.easy;
+
+import com.examplehub.maths.SumToNFormula;
+import java.util.Arrays;
+import java.util.HashSet;
+import java.util.Set;
+
+/** https://leetcode.com/problems/missing-number/ */
+public class MissingNumber {
+  public static int solution1(int... nums) {
+    Arrays.sort(nums);
+    for (int i = 0; i < nums.length; ++i) {
+      if (nums[i] != i) {
+        return i;
+      }
+    }
+    return nums.length;
+  }
+
+  public static int solution2(int... nums) {
+    Set<Integer> set = new HashSet<>();
+    for (int num : nums) {
+      set.add(num);
+    }
+    for (int i = 0; i < nums.length; ++i) {
+      if (!set.contains(i)) {
+        return i;
+      }
+    }
+    return nums.length;
+  }
+
+  public static int solution3(int... nums) {
+    int missingNumber = nums.length;
+    for (int i = 0; i < nums.length; ++i) {
+      missingNumber ^= nums[i] ^ i;
+    }
+    return missingNumber;
+  }
+
+  public static int solution4(int... nums) {
+    int bigSum = SumToNFormula.sum(nums.length);
+    int smallSum = 0;
+    for (int num : nums) {
+      smallSum += num;
+    }
+    return bigSum - smallSum;
+  }
+}
diff --git a/src/main/java/com/examplehub/leetcode/easy/ValidAnagram.java b/src/main/java/com/examplehub/leetcode/easy/ValidAnagram.java
@@ -0,0 +1,49 @@
+package com.examplehub.leetcode.easy;
+
+import java.util.Arrays;
+
+/** https://leetcode.com/problems/valid-anagram/ */
+public class ValidAnagram {
+  public static boolean solution1(String s, String t) {
+    if (s.length() != t.length()) {
+      return false;
+    }
+    char[] firstChars = s.toCharArray();
+    char[] secondChars = t.toCharArray();
+    Arrays.sort(firstChars);
+    Arrays.sort(secondChars);
+    return Arrays.equals(firstChars, secondChars);
+  }
+
+  public static boolean solution2(String s, String t) {
+    if (s.length() != t.length()) {
+      return false;
+    }
+    StringBuilder builder = new StringBuilder(s);
+    for (char ch : t.toCharArray()) {
+      int index = builder.indexOf(ch + "");
+      if (index != -1) {
+        builder.deleteCharAt(index);
+      }
+    }
+    return builder.length() == 0;
+  }
+
+  public static boolean solution3(String s, String t) {
+    if (s.length() != t.length()) {
+      return false;
+    }
+    int[] hashTable = new int[26];
+    for (char ch : s.toCharArray()) {
+      hashTable[ch - 'a']++;
+    }
+    for (char ch : t.toCharArray()) {
+      int index = ch - 'a';
+      hashTable[index]--;
+      if (hashTable[index] < 0) {
+        return false;
+      }
+    }
+    return true;
+  }
+}
diff --git a/src/test/java/com/examplehub/leetcode/easy/MissingNumberTest.java b/src/test/java/com/examplehub/leetcode/easy/MissingNumberTest.java
@@ -0,0 +1,35 @@
+package com.examplehub.leetcode.easy;
+
+import static org.junit.jupiter.api.Assertions.*;
+
+import org.junit.jupiter.api.Test;
+
+class MissingNumberTest {
+  @Test
+  void testSolution1() {
+    assertEquals(2, MissingNumber.solution1(3, 0, 1));
+    assertEquals(2, MissingNumber.solution1(0, 1));
+    assertEquals(8, MissingNumber.solution1(9, 6, 4, 2, 3, 5, 7, 0, 1));
+  }
+
+  @Test
+  void testSolution2() {
+    assertEquals(2, MissingNumber.solution2(3, 0, 1));
+    assertEquals(2, MissingNumber.solution2(0, 1));
+    assertEquals(8, MissingNumber.solution2(9, 6, 4, 2, 3, 5, 7, 0, 1));
+  }
+
+  @Test
+  void testSolution3() {
+    assertEquals(2, MissingNumber.solution3(3, 0, 1));
+    assertEquals(2, MissingNumber.solution3(0, 1));
+    assertEquals(8, MissingNumber.solution3(9, 6, 4, 2, 3, 5, 7, 0, 1));
+  }
+
+  @Test
+  void testSolution4() {
+    assertEquals(2, MissingNumber.solution4(3, 0, 1));
+    assertEquals(2, MissingNumber.solution4(0, 1));
+    assertEquals(8, MissingNumber.solution4(9, 6, 4, 2, 3, 5, 7, 0, 1));
+  }
+}
diff --git a/src/test/java/com/examplehub/leetcode/easy/ValidAnagramTest.java b/src/test/java/com/examplehub/leetcode/easy/ValidAnagramTest.java
@@ -0,0 +1,27 @@
+package com.examplehub.leetcode.easy;
+
+import static org.junit.jupiter.api.Assertions.*;
+
+import org.junit.jupiter.api.Test;
+
+class ValidAnagramTest {
+  @Test
+  void testSolution1() {
+    assertTrue(ValidAnagram.solution1("anagram", "nagaram"));
+    assertFalse(ValidAnagram.solution1("rat", "car"));
+  }
+
+  @Test
+  void testSolution2() {
+    assertTrue(ValidAnagram.solution2("anagram", "nagaram"));
+    assertFalse(ValidAnagram.solution2("rat", "car"));
+    assertFalse(ValidAnagram.solution2("a", "ab"));
+  }
+
+  @Test
+  void testSolution3() {
+    assertTrue(ValidAnagram.solution3("anagram", "nagaram"));
+    assertFalse(ValidAnagram.solution3("rat", "car"));
+    assertFalse(ValidAnagram.solution3("a", "ab"));
+  }
+}
