Leetcode skimming (5.29) hash table

1. Happy number

202

subject ：
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 this process The result is 1, So this number is the happy number .
If n yes Happy number Just go back to true ; No , Then return to false .

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

Ideas ：
The judging condition of this question is that the result is 1 Or infinite circulation , Using hash table （unordered_set） To judge infinite loops .
It's divided into two functions , One calculates the sum of squares , A judgement sum of squares is 1 Or infinite loop .

note ：
C++ treat as unordered_set Type of questions to do ,Python Just think of the data type as a set .

C++：

class Solution {
    
public:
    //  Sum of squares function 
    int getSum(int n){
    
        int sum = 0;
        while(n){
    
            //  First find the square of a bit 
            sum += (n % 10) * (n % 10);
            //  Ask for ten more ...
            n /= 10;
        }
        return sum;
    }

    bool isHappy(int n) {
    
        unordered_set<int> set;
        while(1){
    
            int sum = getSum(n);
            if(sum == 1){
    
                return true;
            }
            //  If this sum Once upon a time , It means that we have fallen into an infinite cycle ,return false, Otherwise, continue to insert into the hash table 
            if(set.find(sum) != set.end()){
    
                return false;
            }else{
    
                set.insert(sum);
            }
            n = sum;  //  Did not arrive 1 There is no dead cycle , Then calculate the next round of square sum 
        }
    }
};

Python：

class Solution:
    
    def isHappy(self, n: int) -> bool:
        def calculate_sum(n):
            sum_ = 0
            while n:
                sum_ += (n % 10) ** 2
                n = n // 10
            return sum_

        record = set()

        while True:
            n = calculate_sum(n)
            if n == 1:
                return True
            if n in record:
                return False
            else:
                record.add(n)

2. Sum of two numbers

1

subject ：
Given an array of integers nums And an integer target value target, Please find... In the array And is the target value target the Two Integers , And return their array subscripts .

You can assume that each input corresponds to only one answer . however , The same element in the array cannot be repeated in the answer .

You can return the answers in any order .

 Input ：nums = [2,7,11,15], target = 9
 Output ：[0,1]
 explain ： because  nums[0] + nums[1] == 9 , return  [0, 1] .

 Input ：nums = [3,3], target = 6
 Output ：[0,1]

Ideas ：
C++:
Create a hash table , For each of these x, We first query the hash table for the presence of target - x, If it exists, output target - x and x Corresponding subscript , If it doesn't exist, it will x Insert into hash table , You can guarantee that you won't let x Match yourself .

Python Just do it as an ordinary dictionary

note ：
This topic , Use map, So let's see Use arrays and set To do the limitation of hashing .

The size of the array is limited , And if the elements are small , And the hash value is too big to cause a waste of memory space .

set It's a collection , There can only be one element in it key, And the problem of the sum of two numbers , Not only to judge y Whether it exists and needs to be recorded y The subscript position of , Because to return x and y The subscript . therefore set You can't use .

At this point, you have to choose another data structure ：map ,map It's a kind of key value Storage structure of , It can be used key Save values , use value In the subscript where the value is saved .

Be careful （C++）： At first, the mapping table map It's empty. , So the first time i=0 There must be no corresponding target - nums[i], Even if it does exist, it is not the first i Found , It's the one in the back （ for example ：[2,7,11,15] , target=9, No i=2 Found when , yes i=7 when , Because at this time 2 Has been saved map It's in ） therefore map.insert(pair<int,int>(nums[i], i)) This sentence is not only i Useful only when there is no match , It has to be inserted at the beginning . And this sentence must be put behind , want Search before inserting , Otherwise, you will find yourself （ for example ：[0,0]）

C++：

class Solution {
    
public:
    vector<int> twoSum(vector<int>& nums, int target) {
    
        unordered_map <int,int> map;
        for(int i = 0; i < nums.size(); i++){
    
            auto iter = map.find(target - nums[i]);
            //  The iterator does not iterate to the end , I found it earlier 
            if(iter != map.end()){
    
            	// iter->first Is the value ,iter->second yes index
                return {
    iter->second, i};
            }
            //  This i Can't find , Just put i Information insertion for map in 
            //  Equate to  map[nums[i]]=i
            map.insert(pair<int,int>(nums[i], i));
        }
        return {
    };
    }
};

Python：

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        records = dict()

        for idx, val in enumerate(nums):
            if target - val not in records:
                records[val] = idx
            else: 
                #  If at present idx Of val Can be in records Find the corresponding target - val,
                #  Just go back to target - val Of idx And the current idx
                return [records[target - val], idx]

3. Add four numbers II

454

subject ：
Here are four integer arrays nums1、nums2、nums3 and nums4 , The length of the array is n , Please calculate how many tuples there are (i, j, k, l) To meet the ：

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

 Input ：nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
 Output ：2
 explain ：
 Two tuples are as follows ：
1. (0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0

Ideas ：
Define a unordered_map discharge （a+b, a+b Number of occurrences ）, Traverse A,B Array insertion map in , Re traversal C,D Array , If 0-(c+d) stay map There has been , Count the number of occurrences （value）

note ：
Insert map It can also be direct map[key]++

C++：

class Solution {
    
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
    
        unordered_map<int,int> abmap; // key: a+b Value  value:  The number of times the value appears 
        //  Traverse 1,2 Array 
        for(int a : nums1){
    
            for(int b: nums2){
    
                abmap[a + b]++;  //  Insert this sentence map It's wonderful 
            }
        }

        int count = 0;   //  Statistics  a+b+c+d=0 Number of occurrences 
        //  Traverse 3,4 Array 
        for(int c: nums3){
    
            for(int d: nums4){
    
                if(abmap.find(0 - (c + d)) != abmap.end()){
    
                    count += abmap[0 - (c + d)];
                }
            }
        }
        return count;
    }
};

Python：

class Solution:
    def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:
        hashmap = dict()
        for a in nums1:
            for b in nums2:
                if a + b in hashmap:
                    hashmap[a + b] += 1
                else:
                    hashmap[a + b] = 1

        count = 0
        for c in nums3:
            for d in nums4:
                key = 0 - (c + d)
                if key in hashmap:
                    count += hashmap[key]
        return count

4. Ransom letter

383

subject ：
Here are two strings ：ransomNote and magazine , Judge ransomNote Can it be done by magazine The characters inside make up .

If possible , return true ; Otherwise return to false .

magazine Each character in can only be in ransomNote Used once in .

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

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

Ideas ：（ similar 242. Effective letter ectopic words ）
Use a length of 26 To record magazine The number of times the letters appear in , And then use ransomNote To verify that the array contains ransomNote All the letters needed

note ：
C++ use set,Python use list

C++：

class Solution {
    
public:
    bool canConstruct(string ransomNote, string magazine) {
    
        int record[26] = {
    0};
        for(int i = 0; i < magazine.length(); i++){
    
            record[magazine[i] - 'a']++;
        }
        for(int i = 0; i < ransomNote.length(); i++){
    
            record[ransomNote[i] - 'a']--;
            if(record[ransomNote[i] - 'a'] < 0){
    
                return false;
            }
        }
        return true;
    }
};

Python：

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        record = [0] * 26

        for i in magazine:
            record[ord(i) - ord('a')] += 1

        for i in ransomNote:
            if record[ord(i) - ord('a')] == 0:
                return False
            else:
                record[ord(i) - ord('a')] -= 1
        return True