Leetcode - hash table

---

Preface

The examples of this article will pass python To achieve , But the hash table is in python The expression in is in dictionary form . So there is still a big conflict with other languages . stay python in , In fact, there is a very useful class ——defaultdict. Please refer to ：
https://blog.csdn.net/yangsong95/article/details/82319675

---

One 、242. Effective alphabetic words

Answer key

Array is also a special hash table , And the string in this topic has only lowercase characters , Then you can define an array , To record strings s The number of times a character appears in a character . The length of the array can be set to 26, Initialize to 0, because a To z Of ASCII It's also 26 Consecutive values . Define an array called record Used to record strings on s The number of times a character appears in a character .

You need to map the characters to the array, that is, the index subscript of the hash table , Because the characters a To character z Of ASCII yes 26 It's a continuous number , So the characters a Map to subscript 0, Corresponding characters z Map to subscript 25.

Re traversal character string s When , Only need to s[i] - ‘a’ The element in which you are doing +1 Just operate , There's no need to remember characters a Of ASCII, Just find a relative value . So the string s The number of times characters appear in , The statistics come out .

Let's see how to check strings t Whether these characters appear in , Also traversing the string t When , Yes t The characters in the hash table are mapped to the values on the index -1 The operation of .

So finally check ,record Array if some elements are not zero 0, Description string s and t It must be who has more characters or who has less characters ,return false.

Finally, if record All elements of the array are zero 0, Description string s and t It's a letter variant word ,return true.

Code

'''  Create a new one 0-25 Array , In a traverse s When , Add one to the corresponding position , Traverse t When , Subtract one from the corresponding position ,  If the last array is all 0, Then return to True, Otherwise return to false '''

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        res = [0]*26
        for i in range(len(s)):
            res[ord(s[i])-ord('a')] += 1 #ord() Function is python Built in functions , We can work out ASCII code , This problem only needs to find and a The relative distance is good 
        print(res)
        for j in range(len(t)):
            res[ord(t[j])-ord('a')] -= 1
        print(res)
        for k in range(len(res)):
            if res[k] != 0:
                return False
                break
            
        return True

The following method does not use an array as a hash table , Using the above mentioned defaultdict

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        from collections import defaultdict
        
        s_dict = defaultdict(int)
        t_dict = defaultdict(int)

        for x in s:
            s_dict[x] += 1
        
        for x in t:
            t_dict[x] += 1

        return s_dict == t_dict

Two 、349. Intersection of two arrays

Answer key

In fact, this problem can be solved by direct traversal , But the time complexity is too high , Use here set To solve this problem .
set and list In fact, there are essential differences ,set It's going to be weightless ,list Can't

Code

The code is simple , Because after set After processing , There is no repetition of the elements in the list

'''  In fact, this topic can be achieved through traversal , But the time complexity is too high , It can be used set To solve this problem  set It's going to be weightless  '''
class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        return list(set(nums1) & set(nums2))

3、 ... and 、202. Happy number

Answer key

This question needs to understand what is happy number , In fact, as long as you understand , When a number repeats a certain result in the calculation process , This number must not be a happy number , Because it has fallen into an infinite cycle , If the final calculation result is one , Then it is happy number . There is another requirement , Understand the logic of decomposing a number .

Code

'''  If a number repeats , Then it indicates that it has entered a dead cycle , It must not be a happy number  '''
class Solution:
    def isHappy(self, n: int) -> bool:
        # The calculation process 
        def cal_happy(num):
            sum = 0
            # Start with a bit 
            while num:
                sum += (num%10)**2
                num = num//10
            return sum
        # Create a new collection to store the number that has appeared 
        record = set()

        while True:
            n = cal_happy(n)
            # If n=1,, It means happy number 
            if n == 1:
                return True
            # If it is already in the set , Then return directly False
            if n in record:
                return False
            else:
                record.add(n)

Four 、1. Sum of two numbers

Answer key

This topic gives an array , But the subscript is required to be returned when returning . We can think about it , stay Python What storage structure can store two kinds of data corresponding to each other at the same time ？ you 're right , That's the dictionary . We can get key Save values ,value Save the subscript of the value .

Code

'''  Using dictionaries , Because we need to store values and subscripts  '''
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        record = dict()
        # Enumeration is more convenient , There is no need to get the value of the current position through the index 
        for idx,val in enumerate(nums):
            if target-val not in record:
                record[val]=idx
            else:
                # If it exists, it returns the dictionary record index and the current index 
                return [record[target-val],idx]

5、 ... and 、454. Add four numbers II

Answer key

First of all, define a dict1, take num1 and num2 And put into the dictionary ,key For harmony ,value Is the number of occurrences
Then define another dict2, Judge num3 and num4 Is the opposite of and in dict2 in , If it exists, use count Statistics value

Code

'''  First of all, define a dict1, take num1 and num2 And put into the dictionary ,key For harmony ,value Is the number of occurrences   Then define another dict2, Judge num3 and num4 Is the opposite of and in dict2 in , If it exists, use count Statistics value '''
class Solution:
    def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:
        dict1 = dict()
        for i in nums1:
            for j in nums2:
                if i+j in dict1:
                    dict1[i+j] += 1
                else:
                    dict1[i+j] = 1
    
        count = 0
        for i in nums3:
            for j in nums4:
                key = -(i+j)
                if key in dict1:
                    count += dict1[key]
        return count

6、 ... and 、383. Ransom letter

Answer key

This topic and 242. Effective alphabetic ectopic words are much like , Effective alphabetic words (opens new window) Equivalent to finding the string a and character string b Whether they can be made up of each other , And the problem is to find strings a Can a string be formed b, No strings b Can it be a string a.

Code

''' This topic is actually similar to that heterotopic word '''

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        record = [0]*26
        # First traverse magazine, Put the letters that appear in and a Add one to the relative position of 
        for i in magazine:
            record[ord(i)-ord('a')] += 1
        # Traverse ransomNote
        for i in ransomNote:
            # If it doesn't appear , You must return to false
            if record[ord(i)-ord('a')] == 0:
                return False
            else:
                record[ord(i)-ord('a')] -= 1
        
        return True

Use defaultdict

'''  This topic is actually similar to that heterotopic word , Use defaultdict() '''

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        from collections import defaultdict
        # Record the number of times each letter appears ,key For the letters ,value Is the number of occurrences 
        hashmap = defaultdict(int)
        # Add one to every occurrence 
        for x in magazine:
            hashmap[x] += 1
        
        for x in ransomNote:
            # obtain x Number of occurrences 
            val = hashmap.get(x)
            # If ran The letter in is mag There's no such thing as , Or it has been used up ,false
            if val is None or val ==0:
                return False
            # Times minus one 
            else:
                hashmap[x] -= 1

        return True

7、 ... and 、15. Sum of three numbers

Answer key

We adopt the double pointer method for this problem , First, sort the array （ In doing array related topics , If there is no thought , Just sort the array first ）, And then there's a layer for loop ,i Start traversing where the subscript is zero ,left=i+1,right At the end of the array .

If nums[i] + nums[left] + nums[right] > 0 Just explain At this time, the sum of three numbers is large , Because arrays are sorted , therefore right The subscript should move to the left , Only in this way can the sum of three numbers be smaller .

If nums[i] + nums[left] + nums[right] < 0 explain here The sum of three numbers is small ,left Just move to the right , To make the sum of three numbers bigger , until left And right Until we meet .

Code

In the code , There are two places that reflect the operation of weight removal , Be sure to take an example and implement it manually , In this way, we can better understand . In the beginning , I didn't expect to go to the first place , So the result has been repeated .

'''  About array related topics , First consider whether sorting can be handled better  '''

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        res = [] # Returns an array of 
        nums = sorted(nums) # Prioritize 

        for i in range(len(nums)):
            if nums[i]>0:
                return res
            left = i+1
            right = len(nums)-1
            # duplicate removal 
            if i>0 and nums[i] == nums[i-1]:
                continue

            total = 0
            while left < right:
                total = nums[i]+nums[left]+nums[right]
                if total<0:
                    left += 1
                elif total>0:
                    right -= 1
                else:
                    res.append([nums[i],nums[left],nums[right]])
                    # duplicate removal 
                    while left<right and nums[left]==nums[left+1]: 
                        left+=1
                    while left<right and nums[right]==nums[right-1]: 
                        right-=1
                    left += 1
                    right -= 1

        return res

8、 ... and 、18. Sum of four numbers

Answer key

This topic is no different from the sum of three numbers , Just add another layer of circulation on the basis of the sum of three numbers , In fact, it is similar to three pointers .

Code

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        nums.sort()
        n = len(nums)
        res = []
        for i in range(n):
            if i > 0 and nums[i] == nums[i - 1]: continue
            for k in range(i+1, n):
                if k > i + 1 and nums[k] == nums[k-1]: continue
                p = k + 1
                q = n - 1

                while p < q:
                    if nums[i] + nums[k] + nums[p] + nums[q] > target: q -= 1
                    elif nums[i] + nums[k] + nums[p] + nums[q] < target: p += 1
                    else:
                        res.append([nums[i], nums[k], nums[p], nums[q]])
                        while p < q and nums[p] == nums[p + 1]: p += 1
                        while p < q and nums[q] == nums[q - 1]: q -= 1
                        p += 1
                        q -= 1
        return res