HashMap Problems

Made by Mike_Zhang

数据结构与算法题主题：

Design HashMap

LeetCode Problem #706

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
// import javafx.util.Pair;

class MyHashMap {
    private final int MAX_LEN = 100000;             // the amount of buckets
    private List<Pair<Integer, Integer>>[] map;     // hash map implemented by array
    
    /** Returns the corresponding bucket index. */
    private int getIndex(int key) {
        return key % MAX_LEN;
    }
    
    /** Search the key in a specific bucket. Returns -1 if the key does not existed. */
    private int getPos(int key, int index) {
        // Each bucket contains a list.
        List<Pair<Integer, Integer>> temp = map[index];
        if (temp == null) {
            return -1;
        }
        // Iterate all the elements in the bucket to find the target key.
        for (int i = 0; i < temp.size(); ++i) {
            if (temp.get(i).getKey() == key) {
                return i;
            }
        }
        return -1;
    }

    /** Initialize your data structure here. */
    public MyHashMap() {
        map = (List<Pair<Integer, Integer>>[])new ArrayList[MAX_LEN];
    }
    
    /** value will always be positive. */
    public void put(int key, int value) {
        int index = getIndex(key);
        int pos = getPos(key, index);
        if (pos < 0) {
            // Add new (key, value) pair if key is not existed.
            if (map[index] == null) {
                map[index] = new ArrayList<Pair<Integer, Integer>>();
            }
            map[index].add(new Pair(key, value));
        } else {
            // Update the value if key is existed.
            map[index].set(pos, new Pair(key, value));
        }
    }
    
    /** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */
    public int get(int key) {
        int index = getIndex(key);
        int pos = getPos(key, index);
        if (pos < 0) {
            return -1;
        } else {
            return map[index].get(pos).getValue();
        }
    }
    
    /** Removes the mapping of the specified value key if this map contains a mapping for the key */
    public void remove(int key) {
        int index = getIndex(key);
        int pos = getPos(key, index);
        if (pos >= 0) {
            map[index].remove(pos);
        }
    }
}

/**
 * Your MyHashMap object will be instantiated and called as such:
 * MyHashMap obj = new MyHashMap();
 * obj.put(key,value);
 * int param_2 = obj.get(key);
 * obj.remove(key);
 */

2022-11-22

Next Greater Element I

LeetCode Problem #496

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        // M1 Stack & HashMap
        HashMap<Integer,Integer> hm = new HashMap<>();
        Stack<Integer> stack = new Stack<>();
        for (int n:nums2) {
            while (!stack.isEmpty() && stack.peek()<n) {
                hm.put(stack.pop(),n);
            }
            stack.push(n);
        }
        
        for (int i=0;i<nums1.length;i++) {
            if (hm.containsKey(nums1[i])) {nums1[i] = hm.get(nums1[i]);}
            else {nums1[i] = -1;}
        }
        return nums1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        // M2 HashMap
        HashMap<Integer,Integer> hm = new HashMap<>();
        int s2 = nums2.length;
        hm.put(nums2[s2-1],-1);
        for (int j=s2-2;j>=0;j--) {
            int n1 = nums2[j];
            int n2 = nums2[j+1];
            if (n1<n2) {
                hm.put(n1,n2);
            }
            else {
                int temp = hm.get(n2);
                while (temp < n1 && temp != -1) {
                    temp = hm.get(temp);
                }
                hm.put(n1,temp);
            }
            
        }
        int s1 = nums1.length;
        int[] out = new int[s1];
        for (int k=0;k<s1;k++) {
            out[k] = hm.get(nums1[k]);
        }
        return out;
    }
}

2022-10-08

Longest Harmonious Subsequence

LeetCode Problem #594

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int findLHS(int[] nums) {
        
        // M1 Sorting
        Arrays.sort(nums);
        int maxVal = 0;
        int size = nums.length;
        for (int i=0;i<size-1;i++) {
            int j = i+1;
            while (j<size && nums[j]-nums[i]<=1) {
                j++;
            }
            if (i!=size && nums[j-1]!=nums[i]) {
                maxVal = (j-i)> maxVal? (j-i):maxVal;
            }
        }
        return maxVal;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int findLHS(int[] nums) {
        
        // M2 HashMap
        HashMap<Integer, Integer> hm = new HashMap<>();
        int maxVal = 0;
        for (int num:nums) {
            hm.put(num, hm.getOrDefault(num, 0)+1);
            if (hm.containsKey(num+1)) {
                maxVal = Math.max(maxVal,hm.get(num)+hm.get(num+1));
            }
            if (hm.containsKey(num-1)) {
                maxVal = Math.max(maxVal,hm.get(num)+hm.get(num-1));
            }
        }
        return maxVal;
    }
}

2022-10-09

Jewels and Stones

LeetCode Problem #771

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int numJewelsInStones(String jewels, String stones) {
        
        // M1 HashMap
        HashMap<Character, Integer> hm = new HashMap<>();
        int out = 0;
        for (char c : jewels.toCharArray()) {
            hm.put(c,hm.getOrDefault(c,0)+1);
        }
        for (char s: stones.toCharArray()) {
            if (hm.containsKey(s)) {
                out++;
            }
        }
        return out;
    }
}
1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int numJewelsInStones(String jewels, String stones) {
    
        // M2 indexOf
        int out = 0;
        for (char s: stones.toCharArray()) {
            if (jewels.indexOf(s)!=-1) {out++;}
        }
        return out;
    }
}

2022-10-18

Isomorphic Strings

LeetCode Problem #205

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public boolean isIsomorphic(String s, String t) {
        HashMap<Character,Character> ht = new HashMap();
        for (int i=0; i<s.length(); i++) {
            char ss = s.charAt(i);
            char tt = t.charAt(i);
            if (!ht.containsKey(ss)) {
                if (ht.containsValue(tt)) {
                    return false;
                }
                ht.put(ss,tt);
            }
            else if (ht.get(ss) != tt){
                return false;
            }
        }
        return true;
    }
}

2022-11-23

Minimum Index Sum of Two Lists

LeetCode Problem #599

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
    public String[] findRestaurant(String[] list1, String[] list2) {
        int s1 = list1.length;
        int s2 = list2.length;
        int minVal = s1+s2;
        List<String> out = new ArrayList<>();
        HashMap<String, Integer> hm = new HashMap<>();
        for (int i=0;i<s1;i++) {
            hm.put(list1[i], i);
        }
        for (int j=0;j<s2;j++) {
            int n;
            if (hm.containsKey(list2[j])) {
                n = hm.get(list2[j]);
                n+=j;
                hm.put(list2[j], n);
                    if (n<minVal) {
                        minVal = n;
                        out.clear();
                        out.add(list2[j]);
                    }
                    else if (n == minVal) {
                        out.add(list2[j]);
                    }
            }

        }
        return out.toArray(new String[out.size()]);
    }
}

2022-11-23

First Unique Character in a String

LeetCode Problem #387

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int firstUniqChar(String s) {
        
        // M3
        int size = s.length();
        if (size == 1) {return 0;}
        
        int[] counter = new int[26];
        
        for (int i=0;i<size;i++) {
            counter[s.charAt(i)-'a']++;
        }
        
        for (int j=0;j<size;j++) {
            if (counter[s.charAt(j)-'a'] == 1) return j;
        }
        return -1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int firstUniqChar(String s) {        
        // M2
        for (char c: s.toCharArray()) {
            int front = s.indexOf(c);
            int end = s.lastIndexOf(c);
            if (front == end) {
                return front;
            }
        }
        return -1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int firstUniqChar(String s) {
        // M1
        int size = s.length();
        if (size == 1) {return 0;}
        HashMap<Character, Integer> hm = new HashMap<>();
        for (int i=0;i<size;i++) {
            char temp = s.charAt(i);
            if (hm.containsKey(temp)) {
                int v = hm.get(temp);
                v+=1;
                hm.put(temp,v);
            }
            else {
                hm.put(temp,1);
            }
        }
        for (int j=0;j<size;j++) {
            if (hm.get(s.charAt(j)) == 1) {return j;}
        }
        return -1;
    }
}

2022-11-23

Contains Duplicate II

LeetCode Problem #219

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        int size = nums.length;
        HashMap<Integer, Integer> hm = new HashMap<>();
        for (int i=0;i<size; i++) {
            int temp = nums[i];
            if (hm.containsKey(temp) && i-hm.get(temp)<=k) {
                return true;
            }
            else {
                hm.put(temp,i);
            }
        }
        return false;
    }
}

2022-11-23

Group Anagrams

LeetCode Problem #49

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        HashMap<String, List<String>> hm = new HashMap();
        for (String str: strs) {
            String temp = sortString(str);
            if (hm.containsKey(temp)) {
                List<String> tempL = hm.get(temp);
                tempL.add(str);
                hm.put(temp,tempL);
            }
            else {
                List<String> slist = new ArrayList<>();
                slist.add(str);
                hm.put(temp,slist);
            }
        }
        List<List<String>> out = new ArrayList<>();
        for (List<String> ls:hm.values()) {
            out.add(ls);
        }
        return out;
        
    }
    private String sortString(String inStr) {
        char[] out = inStr.toCharArray();
        Arrays.sort(out);
        return new String(out);
    }
}

2022-11-23

Group Shifted Strings

LeetCode Problem #249

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
    public List<List<String>> groupStrings(String[] strings) {
        HashMap<String, List<String>> hm = new HashMap();
        for (String str: strings) {
            String temp = hash(str);
            if (hm.containsKey(temp)) {
                List<String> tempL = hm.get(temp);
                tempL.add(str);
                hm.put(temp,tempL);
            }
            else {
                List<String> slist = new ArrayList<>();
                slist.add(str);
                hm.put(temp,slist);
            }
        }
        List<List<String>> out = new ArrayList<>();
        for (List<String> ls:hm.values()) {
            out.add(ls);
        }
        return out;
        
    }
    private String hash(String inStr) {
        char[] chars = inStr.toCharArray();
        char[] out = new char[chars.length];
        out[0] = 'a';
        for (int i=1;i<out.length;i++) {
            int temp = chars[i]-chars[0];
            out[i] = (char)((temp+26)%26+97);
        }
        return new String(out);
    }
}

2022-11-24

Last updated on 2022-11-25

References

Hash Table - LeetCode

写在最后

Hash Table 相关的知识会继续学习，继续更新.
最后，希望大家一起交流，分享，指出问题，谢谢！

原创文章，转载请标明出处
Made by Mike_Zhang




感谢你的支持
Data Structure and Algorithm > Problem Set
#Java #HashMap
HashMap Problems
https://ultrafish.io/post/hashmap-problems/
Author
Mike_Zhang
Posted on
November 25, 2022
Licensed under