Leetcode customs clearance: hash table six, this is really a little simple

Hash table base

Hash table is also called hash table , Hash table is a kind of mapped data structure .

Hash table is a data structure that can be accessed directly according to the value of the key .

It's like old three and old three's station ： Someone came to see the third , The front desk lady pointed , The dog house is the third station .

On the whole , The hash table consists of two elements ： Bucket array and hash function .

Bucket and bucket array

Bucket array used by hash table （Bucket array ）, In fact, it is a capacity of N Normal array of , Just here , We think of each unit as a “ bucket ”（Bucket）, Each bucket unit can hold an entry .

such as , All keys are integers , We can just put key The entry for the key is stored in the bucket unit A[key] Inside ; To save space , Idle units are set to null.

for example , Wu Ling 、 Big bear 、 The king 2 、 Zhang San 、 Li Si , We can put them in the corresponding position of the bucket array .

So when you look up , We number according to the corresponding name , Just look for the subscript of the array , thus , Time complexity is O(1).

But the third said , How can someone's name always be called three 、 What four , At least call " Skywind "、" Xiao Ming " Well .

So here comes the question , Skywind 、 Xiao Ming, where should we put it ？ They can't put it directly in the corresponding subscript position of the bucket array .

therefore , We introduced our second key element hash function .

hash function

In order that the mapping can be extended to all cases , We need a hash function hashFunction Map to the position corresponding to the bucket array .

for example , Some of the commonplace names we mentioned above , Skywind 、 Xiao Ming …… We're going to map them to the corresponding bucket .

In general , The hash function passes the name HashCode Carry out operations , Map the name to the index corresponding to the bucket array .

Hash collision

Our ideal situation , Is calculated by hashing , Each element finds a free pit , But the reality is often not so satisfactory , occasionally , Will find , The city in my heart , Already covered with other people's vines .

A gang and Xiao Ming are mapped to the same location , But this position can only accommodate one person , This is called hash collision .

So in order to avoid hash collision as much as possible , You need to carefully design the hash function , We want the hash function to meet the following requirements ：

• It has to be consistent
• Simple calculation
• The hash address is evenly distributed

Hash function construction method

There are many ways to construct hash functions , Here's the picture , Some methods see the name and know the meaning , And the limit of the length , Not much .

Just to mention here HashMap Hash function of ：

    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
 Copy code 

The whole process is as follows ：

• utilize hashCode() Method to get int Type of hashCode
• hashCode The height of 16 Bit and hashCode It's low 16 Bit does an XOR operation

hashCode Move right 16 position , Is precisely 32bit Half of . Do XOR with yourself （ Same as 0, Different for 1）. Is to mix the high and low positions of hash values , Increase the randomness of the low order . And the mixed value also maintains the characteristics of high position in disguise .

• 32 position int type hashCode Too much scope , Modulo operation with bucket array length is required , Get index value

int index = hash & (arrays.length-1);
 Copy code 

HashMap The hash function is a very good design , It's worth learning .

How to deal with hash conflicts

Even the best design , Hash collisions are inevitable .

that , Hash collision , What should I do ？

Zipper method

A gang and Xiao Ming clashed in the bucket , Let's pick up a small tail in the bucket array —— Just save them with a linked list .

In addition to this , What else can I do ？

alas , If our bucket array still has pits , We can redistribute , This is it.

Linear detection method

The premise of using linear detection method is that there are pits in the bucket array .

Common linear detection methods are ：

• Open address method

Open address method It's when there's a conflict , Go to find the next empty hash address .

Finding the next empty hash address is called probing , Common detection methods are ： Linear detection method 、 Second detection 、 Random detection .

• Then the hash method

This method is also very simple , Use different hash functions to get a hash address , Until there's no conflict .

• Public spill area law

The public spillover area method is to build another public spillover area , Store conflicting elements .

Java Hash structure in

stay Java In the brush question , We have two common hash structures .

One is HashMap,<Key,Value> Type Hash structure .

One is HashSet, There is no set of repeating elements .

aggregate	Underlying implementation	Is it orderly	Whether the value can be repeated	The query efficiency	Efficiency of addition and deletion
HashMap	Array / Linked list / Red and black trees	no	key Do not repeat ,value repeatable	O(1)	O(1)
HashSet	Array / Linked list / Red and black trees	no	Do not repeat	O(1)	O(1)

What kind of topics are usually used Hash Watch ？

Remember the number of times we did before ？

The scene to judge whether an element has appeared , We should think of hash immediately .

Brush questions on the spot

LeetCode1. Sum of two numbers Is a typical example of using a hash table , I won't come again .

LeetCode242. Effective alphabetic words

subject ：242. Effective alphabetic words

difficulty ： Simple

describe ：

Given two strings s and t , Write a function to determine t Whether it is s Letter heteronym of .

Be careful ： if s and t Each character in the has the same number of occurrences , said s and t They are mutually alphabetic words .

Example 1:

 Input : s = "anagram", t = "nagaram"
 Output : true
 Copy code 

Example 2:

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

Ideas ：

Since it's all said to use hashifa , I'm too lazy to write violence law again .

We can use HashMap Store the frequency of characters ,s Frequency of occurrence +1,t Frequency of occurrence , At the end of the day hash All positions value Is it all for 0.

The idea is simple , The code implementation is as follows ：

    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            char sChar = s.charAt(i);
            char tChar = t.charAt(i);
            map.put(sChar, map.getOrDefault(sChar, 0) + 1);
            map.put(tChar, map.getOrDefault(tChar, 0) - 1);
        }
        for (Integer v : map.values()) {
            if (v != 0) {
                return false;
            }
        }
        return true;
    }
 Copy code 

There is another way to use arrays as hash tables , It is said that it can accelerate , But personally, I think it's better to use HashMap The way is better to understand and remember .

Time complexity ：O(n)

Spatial complexity ：O(n)

LeetCode1002. Find common characters

subject ：1002. Find common characters

difficulty ： Simple

describe ：

Given an array of strings consisting only of lowercase letters A, Returns all characters displayed in each string in the list （ Include repeating characters ） A list of components . for example , If a character appears in each string 3 Time , But it's not 4 Time , You need to include this character in the final answer 3 Time .

You can return the answers in any order .

Example 1：

 Input ：["bella","label","roller"]
 Output ：["e","l","l"]
 Copy code 

Example 2：

 Input ：["cool","lock","cook"]
 Output ：["c","o"]
 Copy code 

LeetCode349. Intersection of two arrays

subject ：349. Intersection of two arrays

difficulty ： Simple

describe ：

Given two arrays , Write a function to calculate their intersection .

Example 1：

 Input ：nums1 = [1,2,2,1], nums2 = [2,2]
 Output ：[2]
 Copy code 

Example 2：

 Input ：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
 Output ：[9,4]
 Copy code 

Ideas ：

Be careful , Find the intersection , It needs to be removed . When it comes to weight removal , We naturally thought of HashSet.

We can use two HashSet,set1 Storage nums1 Elements , Traverse nums2, Determine whether the element exists in set1, use set2 Storage .

Well understood. .

The code is as follows ：

    public int[] intersection(int[] nums1, int[] nums2) {
        int len1 = nums1.length;
        int len2 = nums2.length;
        if (len1 == 0 || len2 == 0) {
            return new int[0];
        }
        Set<Integer> set1 = new HashSet<>();
        Set<Integer> set2 = new HashSet<>();
        for (int i = 0; i < len1; i++) {
            set1.add(nums1[i]);
        }
        for (int j = 0; j < len2; j++) {
            if (set1.contains(nums2[j])) {
                set2.add(nums2[j]);
            }
        }
        int[] result = new int[set1.size()];
        int k = 0;
        for (int value : set2) {
            result[k++] = value;
        }
        return result;
    }
 Copy code 

Time complexity ：O(n)

Spatial complexity ：O(n)

LeetCode454. Add four numbers II

subject ：454. Add four numbers II 

difficulty ： secondary

describe ：

Given a list of four arrays containing integers A , B , C , D , Calculate how many tuples there are (i, j, k, l) , bring A[i] + B[j] + C[k] + D[l] = 0.

To simplify the problem , be-all A, B, C, D Same length N, And 0 ≤ N ≤ 500 . All integers are in the range of -228 To 228 - 1 Between , The final result will not exceed 231 - 1 .

for example :

 Input :
A = [ 1, 2]
B = [-2,-1]
C = [-1, 2]
D = [ 0, 2]

 Output :
2

 explain :
 Two tuples are as follows :
1. (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0

 Copy code 

Ideas ：

Our idea is to divide four arrays into two groups , A group of deposits HashMap, Another group and HashMap Compare .

• First define One HashMap,key discharge A and B Sum of two numbers ,value discharge A and B The number of times the sum of two numbers appears .
• Ergodic large A And big B Array , Count the sum of two array elements , And the number of times , Put it in map in .
• Definition int Variable count, Used for statistical a+b+c+d = 0 Number of occurrences .
• In ergodic big C And big D Array , Find out if 0-(C+D) stay map If you've seen it in the past , Just use res hold map in key Number of occurrences
• Finally, the statistics are returned count

    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        Map<Integer, Integer> map = new HashMap<>();
        int res = 0;
        for (int i = 0; i < nums1.length; i++) {
            for (int j = 0; j < nums2.length; j++) {
                int sumAB = nums1[i] + nums2[j];
                map.put(sumAB, map.getOrDefault(sumAB, 0) + 1);
            }
        }

        for (int i = 0; i < nums3.length; i++) {
            for (int j = 0; j < nums4.length; j++) {
                int sumCD = -(nums3[i] + nums4[j]);
                if (map.containsKey(sumCD)) {
                    res+=map.get(sumCD);
                }
            }
        }
        return res;
    }
 Copy code 

Time complexity ：O(n²)

Spatial complexity ：O(n)

LeetCode383. Ransom letter

subject ：454. Add four numbers II

difficulty ： Simple

describe ：

Give a ransom (ransom) String and a magazine (magazine) character string , Judge the first string ransom Can I have a second string magazines The characters inside make up . If it can be constructed , return true ; Otherwise return to false.

( Title Description ： In order not to reveal the handwriting of the ransom letter , To search magazines for the letters you need , Make up words to express meaning . Each character in the magazine string can only be used once in the ransom letter string .)

Example 1：

 Input ：ransomNote = "a", magazine = "b"
 Output ：false
 Copy code 

Example 2：

 Input ：ransomNote = "aa", magazine = "ab"
 Output ：false
 Copy code 

Example 3：

 Input ：ransomNote = "aa", magazine = "aab"
 Output ：true
 Copy code 

Ideas

The solution of this problem is also very similar .

use HashMap Store the characters of the newspaper array and the number of occurrences of the characters , Traverse the ransom letter array , Take the corresponding character .

Be careful , Each character can only be used once , So you need to subtract... When taking characters 1.

The code is as follows ：

    public boolean canConstruct(String ransomNote, String magazine) {
        Map<Character, Integer> hash = new HashMap<>();
        for (int i = 0; i < magazine.length(); i++) {
            char m = magazine.charAt(i);
            hash.put(m, hash.getOrDefault(m, 0) + 1);
        }
        for (int i = 0; i < ransomNote.length(); i++) {
            char r = ransomNote.charAt(i);
            if (!hash.containsKey(r)) {
                return false;
            }
            if (hash.get(r) == 0) {
                return false;
            }
            hash.put(r, hash.get(r) - 1);
        }
        return true;
    }
 Copy code 

Time complexity ：O(n)

Spatial complexity ：O(n)

LeetCode202. Happy number

subject ：202. Happy number  

difficulty ： Simple

describe ：

Write an algorithm to judge a number n Is it a happy number .

「 Happy number 」 Defined as ：

• For a positive integer , Replace the number with the sum of the squares of the numbers in each of its positions .
• Then repeat the process until the number becomes 1, It could be Infinite loop But it doesn't change 1.
• If It can be 1, So this number is the happy number .

If n If it's happy, count it back true ; No , Then return to false .

Example 1：

 Input ：19
 Output ：true
 explain ：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1
 Copy code 

Example 2：

 Input ：n = 2
 Output ：false
 Copy code 

Ideas ：

The key to solving this problem is It could be Infinite loop But it doesn't change 1..

We certainly can't let it take happiness, and the process goes on indefinitely , But now that it's circulating , Then the sum of squares of the digits must repeat , This becomes the problem of judging whether the element appears .

We can use HashSet Store the sum of squares , If the current sum of squares has occurred , Indicates that an infinite loop has started .

    public boolean isHappy(int n) {
    Set<Integer> set = new HashSet<>();
    while (true) {
        int sum = getSum(n);
        // Happy count 
        if (sum == 1) {
            return true;
        }
        //sum There have been 
        if (set.contains(sum)) {
            return false;
        } else {
            set.add(sum);
        }
        n = sum;
    }
}

    /**
     * @return int
     * @Description:  Get the sum of squares 
     * @date 2021/8/11 22:41
     */
    int getSum(int n) {
        int sum = 0;
        while (n > 0) {
            int temp = n % 10;
            sum += temp * temp;
            n = n / 10;
        }
        return sum;
    }
 Copy code 

Time complexity ：O(logn)

Spatial complexity ：O(logn)

This problem can also be solved by means of double pointers , Use two numbers , A quick pointer , A slow pointer , If you enter the cycle , Eventually the two pointers will meet .

summary

Or a doggerel ：

Do simple things over and over again , Do the same thing over and over again , Do serious things creatively ！

In order to help you improve your algorithm ability , We collected and sorted out several very nice The algorithm notes of , Limited to platform reasons , Only partial screenshots can be shown , Small partners in need   Gongzhong 【 No hair loss, aspiring youth 】 Free access

The first

All the contents of this note are pure hand , Sorting algorithm / The code for the data structure may not be the optimal solution , The implementation of the code is written in a relatively easy to understand way . Almost every line of code has a corresponding comment , It should be understandable .

Catalog Overview