Leetcode - hashtable topic

Preface

          Conduct Hash table exercise ！

One 、 brief introduction

Why?

For arrays a[i] = x, Subscript i It can only be a small integer within a certain range , a number n It is not difficult to access arrays when they are large, real numbers or strings .

What is it?

Hash table is also called hash table , Is it a key that can pass any （key） Data structure for direct access .
The essence is to map a set of complex information into a small range set as an index through a hash function .

form

The hash table consists of two parts , One is the data structure of the implementation , Usually linked list （ Index access is not supported ）、 Array （ Only a very small integer can be supported as a subscript ）. It leads to another part , hash function , By entering a key （key）, Returns the index of the hash table data structure , By placing any one key（ Complex information data , Big integers 、 The set of real Numbers 、 character string ） After the hash function mapping into a simple small information （ Small integers ）.

Externally encapsulated as a data structure that can be accessed directly through key ：hash_table[key] = value;
In fact, it is in the hash function of the data structure hash(key) The location stores value：data_structure[hash(key)] = value,data_structure Array or linked list .

Handling conflicts

1. Mapping a large set to a small set will have conflicts （ Collision ）.

2. Hash collision ： Two different key Calculate the same Hash result .

3. resolvent ： Hash

   • Hash The function is still used to calculate the array subscript
   • Each position of the array stores the header pointer of the linked list
   • Each linked list store has the same Hash The value corresponds to the value to be stored

4. Complete structure drawing
   

aggregate (Set) And Mapping (Map)

1. Set and map are two basic data structures used to maintain information .

2. aggregate (set) It's an abstract concept （ One package ）, How to implement it can be achieved through hash table or balanced binary tree , That is, hash table and balanced binary tree are internal implementations .

   • Collections are used to store non repeating elements
   • Ordered sets are generally realized by balanced binary trees , The time complexity is O(logN)
   • Unordered sets are generally implemented with hash tables , Time complexity bit O(1)

3. mapping （map） It is also an abstract concept （ One package ）, How to implement it can be achieved through hash table or balanced binary tree , That is, hash table and balanced binary tree are internal implementations .

   • Used to store non duplicate key value pairs （key-value Yes ）
   • Ordered set , When traversing, follow key Size arrangement , Generally, balanced binary tree is used to realize , The time complexity is O(logN)
   • Unordered sets are generally implemented with hash tables , Time complexity bit O(1)

Two 、 Brush problem

LeetCode 1. Sum of two numbers

LeetCode 1. Sum of two numbers Original link

Ideas ：

To enumerate two, first think about whether you need to keep the order , If this question returns in any order nums[i]+nums[j] And nums[j]+nums[i] There is no difference between , Add one by yourself j < i Such conditions are convenient for maintenance .

Code analysis ：

class Solution {
    
public:
    vector<int> twoSum(vector<int>& nums, int target) {
    
        /* for every num search if (target-number) in nums( remove num) */

        // j < i
        /*  The whole idea ： for i = 0~n-1 search if (target - nums[i]) exists in nums[0,i-1] nums[0,i-1] Hash table can be used to maintain  */
		//  Time complexity bit  O(n)
        int n = nums.size();
        unordered_map<int, int> val_to_index;
        //  Not equal to the tail , Just found , Indicates presence 
        for (int i = 0; i < n; i ++) {
    
            if (val_to_index.find(target - nums[i]) != val_to_index.end()) {
     
                return {
    val_to_index[target - nums[i]], i};
            }
            // i One cycle at a time ,nums[0, i-1] It also needs an extra number 
            //  Edge cycle i, Variable insertion 
            //  In essence i Before finding , Prevent detection i In itself 
            val_to_index[nums[i]] = i;
        }

        return {
    };
    }
};

LeetCode 1748. The sum of the only elements Original link

class Solution {
    
public:
    int sumOfUnique(vector<int>& nums) {
    
        int sum = 0;
        vector<int> heap(105, 0);

        for (auto num : nums) heap[num] ++;
        for (auto num : nums) {
    
            if (heap[num] == 1) 
                sum += num;
        }
        return sum;
    }
};

LeetCode 387. The first unique character in the string Original link

class Solution {
    
public:
    int firstUniqChar(string s) {
    
        vector<int> heap(26, 0);
        for (auto c : s) heap[c - 'a'] ++;
        for (int i = 0; i < s.size(); i ++) {
    
            if (heap[s[i] - 'a'] == 1)
                return i;
        }
        return -1;
    }
};

LeetCode 1941. Check that all characters appear the same number of times Original link

class Solution {
    
public:
    bool areOccurrencesEqual(string s) {
    
        vector<int> heap(26, 0);

        for (auto c : s) heap[c - 'a'] ++;
        int v = heap[s[0] - 'a'];

        for (int i = 0; i < 26; i ++) {
    
            if (heap[i] > 0 && heap[i] != v) 
                return false;
        }
        return true;
    }
};

LeetCode 448. Find all the missing numbers in the array Original link

• Without space constraints ： Open a length of n Of heap Arrays are used to mark 1-n Whether each number has appeared , Traverse the whole nums Array , Mark all the numbers that have appeared ; And then from 1-n Traverse heap The array will output numbers that have never appeared ;
• O(1) Spatial complexity of ： Modify the original array , If x There have been , take a[x] become -a[x]（ Mark ）, Count the number of unchanged numbers ;

class Solution {
    
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
    
        for (auto x : nums) {
    
            x = abs(x);
            if (nums[x - 1] > 0) nums[x - 1] *= -1; //  Not marked , marked 
        }
        vector<int> ret;
        for (int i = 0; i < nums.size(); i ++) {
    
            if (nums[i] > 0) 
                ret.push_back(i + 1);
        }
        return ret;
    }
};

LeetCode 1512. A good number of pairs Original link

class Solution {
    
public:
    int numIdenticalPairs(vector<int>& nums) {
    
        vector<int> heap(105, 0);
        int ans = 0;

        for (int i = 0; i < nums.size(); i ++) {
    
            ans += heap[nums[i]];
            heap[nums[i]] ++;
        }
        return ans;
    }
};