Hash Table Mock

242. Valid Anagram

Solved

Easy

Topics

Companies

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.

class Solution {
    public boolean isAnagram(String s, String t) {
        if(s.length() != t.length()){
            return false;
        }
        Map map = new HashMap<>();
        for(int i = 0; i < s.length(); i++){
            map.put(s.charAt(i),map.getOrDefault(s.charAt(i),0)+1);
        }
        for(int i = 0; i < s.length(); i++){
            map.put(t.charAt(i),map.getOrDefault(t.charAt(i),0)-1);
            if(map.get(t.charAt(i))<0){
                return false;
            }
        }
        return true;
    }
}

class Solution {
    public boolean isAnagram(String s, String t) {
        if(s.length() != t.length()){
            return false;
        }
        int[] counts = new int[26];
        char[] chrs = s.toCharArray();
        char[] chrt = t.toCharArray();
        for(int i = 0; i < s.length(); i++){
            counts[chrs[i]-'a']++;
            counts[chrt[i]-'a']--;
        }
        for(int i = 0; i<26; i++){
            if(counts[i] != 0){
                return false;
            }
        }
        return true;
    }
}

349. Intersection of Two Arrays

Solved

Easy

Topics

Companies

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.

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        Set set1 = new HashSet<>();
        Set resSet = new HashSet<>();
        //遍历数组1
        for (int i : nums1) {
            set1.add(i);
        }
        //遍历数组2的过程中判断哈希表中是否存在该元素
        for (int i : nums2) {
            if (set1.contains(i)) {
                resSet.add(i);
            }
        }
        int[] arr = new int[resSet.size()];
        int j = 0;
        for(int i : resSet){
            arr[j++] = i;
        }
        
        return arr;
    }
}

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        List list = new ArrayList();
        int[] counts = new int[1001];
        for(int i = 0; i < nums1.length; i++){
            counts[nums1[i]] = 1;
        }
        for(int i = 0; i < nums2.length; i++){
            if(counts[nums2[i]] == 1){
                list.add(nums2[i]);
                counts[nums2[i]] = 2;
            }
        }
        int[] ans = new int[list.size()];
        for(int i = 0; i < list.size();i++){
            ans[i] = list.get(i);
        }
        return ans;
    }
}

202. Happy Number

Solved

Easy

Topics

Companies

Write an algorithm to determine if a number n is happy.

A happy number is a number defined by the following process:

• Starting with any positive integer, replace the number by the sum of the squares of its digits.
• Repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1.
• Those numbers for which this process ends in 1 are happy.

Return true if n is a happy number, and false if not.

Example 1:

Input: n = 19
Output: true
Explanation:
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

class Solution {
    public boolean isHappy(int n) {
        Set set = new HashSet();
        while(n != 1 && !set.contains(n)){
            set.add(n);
            n = getNextNumber(n);
        }
        return n == 1;
    }
    private int getNextNumber(int n){
        int res = 0;
        while(n > 0){
            int temp = n % 10;
            res += temp * temp;
            n = n/10;
        }
        return res;
    }
}

1. Two Sum

Solved

Easy

Topics

Companies

Hint

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.

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map map = new HashMap();
        for(int i = 0; i < nums.length; i++){
            if(map.containsKey(target-nums[i])){
                return new int[]{i,map.get(target-nums[i])};
            }
            map.put(nums[i],i);
        }
        return null;
    }
}

383. Ransom Note

Solved

Easy

Topics

Companies

Given two strings ransomNote and magazine, return true if ransomNote can be constructed by using the letters from magazine and false otherwise.

Each letter in magazine can only be used once in ransomNote.

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        int[] counts = new int[26];
        for(int i = 0; i < magazine.length(); i++){
            counts[magazine.charAt(i)-'a']++;
        }
        for(int i = 0; i < ransomNote.length(); i++){
            counts[ransomNote.charAt(i)-'a']--;
            if(counts[ransomNote.charAt(i)-'a'] < 0){
                return false;
            }
        }
        return true;
    }
}

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        if (ransomNote.length() > magazine.length()) {
            return false;
        }
        Map map = new HashMap<>();
        for (char ch : magazine.toCharArray()) {
            map.put(ch, map.getOrDefault(ch, 0) + 1);
        }
        for (char ch : ransomNote.toCharArray()) {
            map.put(ch, map.getOrDefault(ch, 0) - 1);
            if (map.get(ch) < 0) {
                return false;
            }
        }
        return true;
    }
}

454. 4Sum II

Solved

Medium

Topics

Companies

Given four integer arrays nums1, nums2, nums3, and nums4 all of length n, return the number of tuples (i, j, k, l) such that:

• 0 <= i, j, k, l < n
• nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        HashMap map = new HashMap<>();
        
        for(int num1: nums1){
            for(int num2: nums2){
                map.put(num1+num2, map.getOrDefault(num1+num2, 0) + 1);
            }
        }
        
        int res = 0;
        
        for(int num3: nums3){
            for(int num4: nums4){
                res += map.getOrDefault(-(num3+num4), 0);//只写get可能会返回null
            }
        }
        
        return res;
    }
}

49. Group Anagrams

Solved

Medium

Topics

Companies

Given an array of strings strs, group the anagrams together. You can return the answer in any order.

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: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]

class Solution {
    public List> groupAnagrams(String[] strs) {
        Map> map = new HashMap>();
        for (String str : strs) {
            char[] array = str.toCharArray();
            Arrays.sort(array);
            String key = new String(array);
            List list = map.getOrDefault(key, new ArrayList());
            list.add(str);
            map.put(key, list);
        }
        return new ArrayList>(map.values());
    }
}

class Solution {
    public List> groupAnagrams(String[] strs) {
        Map> map = new HashMap>();
        for (String str : strs) {
            int[] counts = new int[26];
            int length = str.length();
            for (int i = 0; i < length; i++) {
                counts[str.charAt(i) - 'a']++;
            }
            // 将每个出现次数大于 0 的字母和出现次数按顺序拼接成字符串，作为哈希表的键
            StringBuffer sb = new StringBuffer();
            for (int i = 0; i < 26; i++) {
                if (counts[i] != 0) {
                    sb.append((char) ('a' + i));
                    sb.append(counts[i]);
                }
            }
            String key = sb.toString();
            List list = map.getOrDefault(key, new ArrayList());
            list.add(str);
            map.put(key, list);
        }
        return new ArrayList>(map.values());
    }
}

128. Longest Consecutive Sequence

Solved

Medium

Topics

Companies

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.

You must write an algorithm that runs in O(n) time.

Example 1:

Input: nums = [100,4,200,1,3,2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

Example 2:

Input: nums = [0,3,7,2,5,8,4,6,0,1]
Output: 9

class Solution {
    public int longestConsecutive(int[] nums) {
        Set numSet = new HashSet();
        for (int num : nums) {
            numSet.add(num);
        }
 
        int longestLength = 0;
 
        for (int num : numSet) {
            if (!numSet.contains(num - 1)) {
                int currentNum = num;
                int currentLength = 1;
 
                while (numSet.contains(currentNum + 1)) {
                    currentNum += 1;
                    currentLength += 1;
                }
                longestLength = Math.max(longestLength, currentLength);
            }
        }
 
        return longestLength;
    }
}