Abstract

【 Interview must brush 101】 series blog The purpose is to summarize the interview must brush 101 Interesting in 、 Exercises that may be tested in the interview . Summarize the general problem-solving methods , Summarize ideas for special exercises . It is written for your review , I also hope to communicate with you .

【 Interview must brush 101】 recursive / Backtracking algorithm summary I
【 Interview must brush 101】 recursive / Backtracking algorithm summary II
【 Interview must brush 101】 Linked list
【 Interview must brush 101】 Binary tree
【 Interview must brush 101】 Two points search
【 Interview must brush 101】 Stacks and queues

1 Basic knowledge of

Hash, General translation “ hash ”, There are also direct transliteration for " Hash " Of , I'm just taking the input of any length （ It's also called pre mapping , pre-p_w_picpath）, By the hash algorithm , To a fixed length output , The output is the hash value . This transformation is a compression mapping , That is to say , The space for hash values is usually much smaller than the space for input , Different inputs may be hashed into phases Same output , It is not possible to uniquely determine the input value from the hash value . In short, it is a function of compressing messages of any length into message summaries of a fixed length . All in all ,hash It refers to using a small piece of data To identify a large amount of data , To verify its integrity .

Just remember , according to hash Value retrieval , Its time complexity is O(1), But the spatial complexity is O(n).

2 The interview must brush exercises

2.1 Two numbers that appear only once in the array

There is no need to paint the snake and add the foot , Look at this brother's solution ：
Answer key | # Two numbers that appear only once in the array #_ Niuke blog (nowcoder.net)

import java.util.*;

public class Solution {
    
    public int[] FindNumsAppearOnce (int[] array) {
    
        //  First, all differences or operations 
        int t = 0;
        for (int i = 0; i < array.length; i++) {
    
            t ^= array[i];
        }
        //  Find different digits 
        int idx = 1;
        while ((t & idx) == 0) {
    
            idx <<= 1;
        }
        //  according to cnt To group 
        int t1 = 0, t2 = 0;
        for (int i = 0; i < array.length; i++) {
    
            if ((array[i] & idx) == 0) {
    
                t1 ^= array[i];
            } else {
    
                t2 ^= array[i];
            }
        }
        if (t1 > t2) {
    
            int tmp = t1;
            t1 = t2;
            t2 = tmp;
        }
        return new int[]{
    t1, t2};
    }
}

2.2 A number that appears more than half the times in an array

Voting algorithm ： Well understood , More than half of them . It's hard for anyone to come , I want to hit all of you alone , Anyway, my number is still super , The last thing left must be me .

import java.util.*;
public class Solution {
    
    public int MoreThanHalfNum_Solution(int [] array) {
    
        //  The space complexity is O(1) Indicates not available hashmap ah ？
        //  What are the characteristics of arrays longer than half ？  use “ Voting algorithm Boyer-Moore”
        int condinate = array[0];
        int cnt = 0;
        for (int i = 0; i < array.length; i++) {
    
            if (array[i] == condinate) {
    
                cnt ++;
            } else {
    
                cnt --;
            }
            if (cnt == 0) {
    
                condinate = array[i + 1];
            }
        }
        return condinate;
    }
}

2.3 Missing first positive integer

In situ hash, Use positive and negative values to distinguish whether there has been

step 1： We can traverse the array first and change all negative numbers to n+1.
step 2： And then iterate through the array , Whenever an element is encountered, its absolute value does not exceed n when , Means that this element is 1～n The elements that appear in , We can change the elements in the subscript corresponding to this value to negative numbers , Equivalent to every positive integer that has appeared , We point all subscripts equal to its value to a negative number , This is an operation similar to the implementation principle of hash table .
step 3： Finally, the first non negative number encountered when traversing the array , Its subscript is the first positive integer that does not appear , Because it has not been modified in the previous process , It means that the positive integer corresponding to this subscript has not appeared .

import java.util.*;

public class Solution {
    
    public int minNumberDisappeared (int[] nums) {
    
        int n = nums.length;
        for (int i = 0; i < n; i++) {
    
            if (nums[i] <= 0) nums[i] = n + 1;
        }
        for (int i = 0; i < n; i++) {
    
            if (Math.abs(nums[i]) <= n) {
    
                nums[Math.abs(nums[i]) - 1] = -Math.abs(nums[Math.abs(nums[i]) - 1]);
            }
        }
        for (int i = 0; i < n; i++) {
    
            if (nums[i] > 0) {
    
                return i + 1;
            }
        }
        return n + 1;
    }
}

2.4 Sum of three numbers

The most important thing is to distinguish whether it is repeated or not , Do it through three , Distinguish before and after i、l and r Whether the upper and lower numbers are the same , If yes, skip . Note that there i You can only judge with the previous one , Because of existence -10、-10、20 This option .

import java.util.*;

public class Solution {
    
    public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
    
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        if (num.length < 3) {
    
            return res;
        }
        Arrays.sort(num);
        
        int n = num.length;
        for (int i = 0; i < n - 2; i++) {
    
            if (i > 0 && num[i - 1] == num[i]) {
    
                continue;
            }
            int l = i + 1, r = num.length - 1;
            while (l < r) {
    
                if (num[l] + num[r] + num[i] > 0) r--;
                else if (num[l] + num[r] + num[i] < 0) l++;
                else {
    
                    ArrayList<Integer> tmp = new ArrayList<>();
                    tmp.add(num[l]);
                    tmp.add(num[r]);
                    tmp.add(num[i]);
                    res.add(tmp);
                    while (num[l] == num[l + 1] && l + 1 < r) l++;
                    while (num[r] == num[r - 1] && r - 1 > l) r--;
                    l++;
                    r--;
                }
            }
        }
        return res;
    }
}

3 Summary of knowledge points

• Two numbers that appear only once in the array ： An operation
• The number of occurrences in the array exceeds the normal number ： Voting algorithm
• Missing first positive integer ： In situ hash Algorithm
• Sum of three numbers ： Double pointer

In fact, I feel hash Nothing special , however hash It is also very commonly used in other algorithms , You need to always remember this data structure .

4 summary

Hold the line , Will be stronger .