Leetcode 217 - Contains Duplicate

Given an array of integers, find if the array contains any duplicates. Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.

需要能够快速查询，然后有一个数和对应出现次数的对应，所以想到用Hashtable
Solution1:

import java.util.*;
public class Solution {
    public boolean containsDuplicate(int[] nums) {
        Hashtable nummap = new Hashtable();
        for (int n : nums) {
            if (nummap.get(n) != null) return true;
            else nummap.put(n,1);
        }
        return false;
    }
}

其实只关心每个num出现没出现，0或者1，所以用不到map，只需要知道有没有就可以，所以hashset就可以。
Solution2:

public class Solution {
    public boolean containsDuplicate(int[] nums) {
        HashSet numset = new HashSet();
        for (int n : nums) {
            if (!numset.add(n)) return true;
        }
        return false;
    }
}

Leetcode 242 - Valid Anagram

Given two strings s and t, write a function to determine if t is an anagram of s.

For example,
s = "anagram", t = "nagaram", return true.
s = "rat", t = "car", return false.

Note:
You may assume the string contains only lowercase alphabets.

Follow up:
What if the inputs contain unicode characters? How would you adapt your solution to such case?

做法1：

把两个string都sort好，然后比较之。
Time: O(nlogn)
Space: O(1)

这样的话答案78.41%

public class Solution {
    public boolean isAnagram(String s, String t) {
        char[] ss = s.toCharArray();
        Arrays.sort(ss);
        String sss = new String(ss);
        char[] tt = t.toCharArray();
        Arrays.sort(tt);
        String ttt = new String(tt);
        return sss.equals(ttt);
    }
}

做法2： 用一个数组存起来
似乎比sort还要慢一些, 46.32%, 8ms。

public class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) return false;
        else if (s.length() == 0) return true;
        int[] numbychar = new int[256];
        int num_unique = 0;
        int num_complete = 0;
        char[] s_char = s.toCharArray();
        for (char c : s_char) {
            if (numbychar[c] == 0) num_unique++;
            ++numbychar[c];
        }
        for (int i = 0; i < t.length(); i++) {
            int c = (int) t.charAt(i);
            if (numbychar[c] == 0) return false;
            --numbychar[c];
            if (numbychar[c] == 0) {
                ++num_complete;
                if (num_complete == num_unique) {
                    return i==t.length()-1;
                }
            }
        }
        return false;
    }
}

Improve the 2nd solution: use a hashtable

import java.util.*;
public class Solution {
    public boolean isAnagram(String s, String t) {
        if(s.length()!=t.length()) return false;
        
        Hashtable 
            theTableS = new Hashtable(),
            theTableT = new Hashtable();
        for (char i:s.toCharArray()) {
            if (theTableS.containsKey(i))
                theTableS.put(i,theTableS.get(i)+1);
            else theTableS.put(i,1);
        }
        for (char i:t.toCharArray()) {
            if (theTableT.containsKey(i)) 
                theTableT.put(i,theTableT.get(i)+1);
            else theTableT.put(i,1);
        }
        return theTableT.equals(theTableS);
    }
}

HashTable

Use HC as index to quickly query some key in the hash table.

Pro:
Quick lookup, insert and remove O(1) (on average)
Challenge:
1. Collisions: values with same hashcode
    1) Solution 1: linear probing: insert. Just put it in the next open spot.
        Has to search for subsequent space for values. May be a problem when the hash table gets full.
        Random probing is an alternative.
    2) Solution 2: separate chaining. Just keep a list at each spot.
        This solution is usually preferred. But drawbacks.
2. Resizing: resize if gets too full (70%)
    requires create a new table, new hash function, and reinsert everything.
3. Ordering data.
    Hash Table don't have order within structure.

Hash Set vs. Hash Map
1. Hash Set: java.util
    class hashset<E>
    boolean add(E e)
    boolean contains(Object o)
    Just tells you if an item is in the set. Perfect for a dictionary.

2. Hash Map: java.util
    class hashmap<K,V>
    V get(Object key)
    V put(K key, V value)
    Stores both a key and some data associated with the key.