LeetCode Day5 HashTable

LeetCode 242. Valid Anagram

Given two strings s and t, return true if t is an anagram of s, and false otherwise.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Example 1:

Input: s = "anagram", t = "nagaram"
Output: true
Example 2:

Input: s = "rat", t = "car"
Output: false

Original Page

It is not a hard question we can use the HashMap to figure it out.

        Map<Character,Integer> sMap = new HashMap<Character,Integer>();
        Map<Character,Integer> tMap = new HashMap<Character,Integer>();
        for(int i=0;i<s.length(); i++){
            Character c = s.charAt(i);
            if(sMap.containsKey(c)){
                sMap.replace(c,sMap.get(c)+1);
            }else{
                sMap.put(c,1);
            }
        }

        for(int i=0;i<t.length(); i++){
            Character c = t.charAt(i);
            if(tMap.containsKey(c)){
                tMap.replace(c,tMap.get(c)+1);
            }else{
                tMap.put(c,1);
            }
        }

        Set<Character> keySet = sMap.keySet();

        for (Character c: keySet){
            if ( !sMap.get(c).equals(tMap.get(c))) {
                return false;
            }
        }



        return s.length() == t.length();
    }

But the above method has some defects, even though it is an O(n)method but contains too many redundant codes e.g. we even do not need 2 HashMap we can solve it by using only one hashmap.

LeetCode 349. Intersection of Two Arrays

Given two integer arrays nums1 and nums2, return an array of their
intersection
. Each element in the result must be unique and you may return the result in any order.
Original Page

Example 1:

Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2]
Example 2:

Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [9,4]
Explanation: [4,9] is also accepted.

Constraints:

1 <= nums1.length, nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 1000

    public int[] intersection(int[] nums1, int[] nums2) {
        int[] selfHash = new int[1001];
        for(int i: nums1){
            selfHash[i] ++;
        }

        for(int i: nums2){
            if(selfHash[i]>0){
                selfHash[i] = -1;
            }
        }
        int size = 0;

        for(int i=0; i<1001; i++){
            if(selfHash[i]<0){
                size++;
            }
        } 
        if(size == 0){
            return new int[0];
        }
        int[] output = new int[size];
        int index = 0;
        for(int i=0; i<1001; i++){
            if(selfHash[i]<0){
                output[index++] = i;
            }
        }

        return output;       
    }

Similarly, I also wrote some useless codes, and I think it is not a good idea to use a self-build hashmap (based on the normal array)

It may waste resources because of an un-extensible array, which pushes me to build 1001 sized array(the question said the element will be from 0 to 1000) even though the test case only contains 3 numbers in each input array, we need to build 1001 sized one

Fortunately, 1000 is not large enough, if the size is 10000000, we can use Set it will be more efficient.

public int[] intersection(int[] nums1, int[] nums2) {
        Set<Integer> set = new HashSet<Integer>();
        for(int i : nums1){
            set.add(i);
        }
        Set<Integer> output = new HashSet<Integer>();
        for(int i: nums2){
            if(!set.isEmpty() && set.contains(i)){
                output.add(i);
            }
        }

        return output.stream().mapToInt(Integer::intValue).toArray();
    }

Both of these code are some, we can use x->x because Java can Autoboxing

---

LeetCode No.1 Two Sum

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]
Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]
Original Page

This is not a difficult question

    public int[] twoSum(int[] nums, int target) {
        int[] result = {-1,-1};
        for(int i=0;i<nums.length;i++){
            for(int j=i+1; j<nums.length; j++){
                if(nums[j]+ nums[i] == target){
                    result[0] = j;
                    result[1] = i;
                    return result;
                }
            }
        }
        return result;
    }

    public int[] twoSum(int[] nums, int target) {
        Map<Integer,Integer> map = new HashMap<Integer,Integer>();
        int[] result = new int[2];
        for(int i=0; i<nums.length; i++){
            int num = nums[i];
            if(map.containsKey(num)){
                    result[0] = map.get(num);
                    result[1] = i;
            }else{
                    map.put(target-num,i);
                }
        }
        return result; 
    }