2019-10-10 刷题总结 -- Hash Table

今天主要刷hash table的题目，主要按照frequency从高到低的顺序。

1. two sum: 使用HashMap
2. 3 sum： 一开始以为是简单的for loop➕two sum的解法，但实际上把代码写出来后发现自己完全忽视了duplicates的情况。对于有duplicate的情况，一般需要先把arrray排序。

加入重复性考虑后，pseudocode变成这样：

// sort the array
Arrays.sort(nums)
for i = 0 to nums.length-2:
    low = i+1, high = nums.length-1;
    // skip duplicates
    if (i == 0 || (i > 0 && nums[i] == nums[i-1]:
            while (low < high) :
                    sum = nums[i] + nums[low] + nums[high]
                    if (sum == 0):
                            add to the result
                            // doing skipping duplicates here
                            low++; high--;
                    else  if (sum < 0):
                              // doing skipping duplicates here
                             low++
                    else:
                              // doing skipping duplicates here
                              high--;

最后放上完整的代码：

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0; i < nums.length - 2; i++) {
            // skip duplicates
            if (i == 0 || (i > 0 && nums[i] != nums[i-1])) {
                int low = i+1, high = nums.length-1, sum = 0 - nums[i];
                while (low < high) {
                    if (nums[low] + nums[high] == sum) {
                        res.add(Arrays.asList(new Integer[]{nums[i], nums[low], nums[high]}));
                        // skip duplicates
                        while (low < high && nums[low] == nums[low+1]) {
                            low++;
                        }
                        while (low < high && nums[high] == nums[high-1]) {
                            high--;
                        }
                        low++;
                        high--;
                    } else if (nums[low] + nums[high] < sum) {
                        // skip duplicates
                        while (low < high && nums[low] == nums[low+1]) {
                            low++;
                        }
                            low++;
                    } else {
                        // skip duplicates
                        while (low < high && nums[high] == nums[high-1]) {
                            high--;
                        }
                            high--;
                    }
                }
            }
        }
        return res;
    }
}

3. 4 Sum: 思路基本和3 Sum相同，就是比3 Sum多了一个for loop

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0; i < nums.length - 3; i++) {
            if (i == 0 || (i > 0 && nums[i] != nums[i-1])) {
                for (int j = i+1; j < nums.length - 2; j++) {
                    if (j == i+1 || (j > i+1 && nums[j] != nums[j-1])) {
                        int lo = j+1, hi = nums.length-1, sum = target-nums[i]-nums[j];
                        while (lo < hi) {
                            if (nums[lo] + nums[hi] == sum) {
                                res.add(Arrays.asList(new Integer[]{nums[i], nums[j], nums[lo], nums[hi]}));
                                while (lo < hi && nums[lo] == nums[lo+1]) {
                                    lo++;
                                }
                                while (lo < hi && nums[hi] == nums[hi-1]) {
                                    hi--;
                                }
                                lo++;
                                hi--;
                            } else if (nums[lo] + nums[hi] < sum) {
                                while (lo < hi && nums[lo] == nums[lo+1]) {
                                    lo++;
                                }
                                lo++;
                            } else {
                                while (lo < hi && nums[hi] == nums[hi-1]) {
                                    hi--;
                                }
                                hi--;
                            }
                        }
                    }
                    
                }
            }
            
        }
        return res;
    }
}

4. Jewels and Stones
   把只包含字母的string转化为固定长度的array来表示可以节省一些时间。
5. Single Number
   所有数都出现两次，除了一个数只出现一次。
   第一反应是a ^ a = 0

class Solution {
    public int singleNumber(int[] nums) {
        int res = 0;
        for (int n: nums) {
            res ^= n;
        }
        return res;
    }
}

但鉴于这是一个hash table的问题，再用繁琐一点的hash table解法来做一次。但是慢多了。

class Solution {
    public int singleNumber(int[] nums) {
        Map<Integer, Integer> map =  new HashMap<>();
        for (int n: nums) {
            if (map.containsKey(n)) {
                map.remove(n);
            } else {
                map.put(n,1);
            }
        }
        for (Map.Entry<Integer, Integer> entry: map.entrySet()) {
            return entry.getKey();
        }
        return 0;
    }
}