Half a year of work experience preparation for job-hopping in the first half of 2022 – algorithm learning diary

18 years of software engineering graduate.

Muddle-headed civil graduate students, muddle-headed retest was kicked.

20 years in the epidemic family squatted for most of half a year, through the guidance of college roommate self-study half a year ago in March 21, started to work in Shenzhen, working experience from zero to the present 5 months and 26 days, I plan to jump to a bigger factory after 22 years.

In the new week, the PM in the group ran away last week, and has no business to write for the time being due to unclear demand.

Start with a recent collection of algorithms to learn a good article, record, the main content of today’s learning also comes from this article, the rest of the content will be carefully read.

# Write front-end algorithm advanced guide, how am I two months zero base brush 200 questions

Intersection of two arrays

Describe the problem: Given two arrays, write a function to calculate their intersection.

The sample1: Input: nums1 = [1.2.2.1], nums2 = [2.2] output: [2.2] example2: Input: nums1 = [4.9.5], nums2 = [9.4.9.8.4] output: [4.9]

Copy the code

Source: LeetCode link: leetcode-cn.com/problems/in… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

1. This paper presents a solution using hash table, double function-time complexity: O(n+m)


let intersect = function(nums1, nums2) {
   let map1 = makeCountMap(nums1)
   let map2 = makeCountMap(nums2)
   let res = []
   for(let num of map1.keys()) {
       const count1 = map1.get(num)
       const count2 = map2.get(num)
       if(count2) {
           // If num in 1 does occur in 2, then the element with the least number of occurrences is counted and pushed by the count
           const pushCount = Math.min(count1, count2)
           for(let i = 0; i < pushCount; i++) {
               res.push(num)
           }
       }
   }
   return res
} 

function makeCountMap(nums) {
    let map = new Map(a)for(let i = 0; i < nums.length; i++) {
        let num = nums[i]
        let count = map.get(num)
        if(count) {
            map.set(num, count + 1)}else {
            map.set(num, 1)}}return map
}
Copy the code
Here is another solution to the single-function hash table – time complexity: O(n+m)
// Create a hash table by iterating over the short array and then iterating over the long array

let intersect = function (nums1, nums2) {
    // Keep the short array first
    if (nums1.length > nums2.length) {
        return intersect(nums2, nums1)
    }
    let map = new Map(a)// Iterate over the short array to establish the number of occurrences of each value
    for(let i = 0; i < nums1.length; i++) {
        let count = (map.get(nums1[i]) || 0) + 1
        map.set(nums1[i], count)
    }
    // set the stack record intersection
    let res = []
     // Traverse the long array against the short array
    for (let i = 0; i < nums2.length; i++) {
        let count = map.get(nums2[i]) || 0
        // Update the number of times recorded in the short array in the map structure (subtracting)
        if(count) {
            res.push(nums2[i])
            map.set(nums2[i], count - 1)}}return res 
}
console.log(intersect([1.2.3], [1.2])); / / [1, 2]
Copy the code

2. Double pointer + sort

To be honest, I did not know what the specific method of double pointer is before (tai Chai Tai chai TT). I saw it on leetCode today, and here I will describe it in my own words: The first step is to sort the array in ascending order using arr.prototype.sort (). This method passes in a comparison function of the form (a, b) => a-b; If a-b=0, return 0 3. If a-b>0, B will be in front of A. And arr2 = [b1, B2, b3...] Res = [] Sets two Pointers I and j to record the element 1 that points to arr1 and arR2, respectively. If the two elements currently being compared are equal, then the element is pushed onto the stack. I and j will refer back to 2 at the same time. The pointer to the smaller value will point back one bit until one of the arrays is iterated, and the extra element in the long array will be unique. Ignore that, and the res will be the desired intersectionCopy the code

OK, now list the solutions

let intersect = function (nums1, nums2) {
    / / sorting
    nums1.sort((a, b) = > a - b)
    nums2.sort((a, b) = > a - b)
    // Build Pointers and record stacks
    let i = 0, j = 0, res = []
    / / traverse
    while(i < nums1.length && j < nums2.length) {
        if(nums1[i] === nums2[j]) {
            res.push(nums1[i])
            i++
            j++
        } else nums1[i] < nums2[j] ? i++ : j++
    }
    return res 
}

console.log(intersect([1.2.3], [2.3]));  / / [2, 3]
Copy the code
And then you see the advanced double pointer plus merge sort
let intersect = function(nums1, nums2) {
    nums1 = nums1.sort((a,b) = > a - b);
    nums2 = nums2.sort((a,b) = > a - b);
    let i = 0;
    let j = 0;
    let k = 0;
    while(i < nums1.length && j < nums2.length){
        if(nums1[i] < nums2[j]){
            i++;
        }else if(nums1[i] > nums2[j]){
            j++;
        }
        else{ nums1[k++] = nums1[i]; i++; j++; }}return nums1.slice(0,k);
};
Copy the code

Nums1 [k++] = nums1[I]; If I =0 and j=0 point to the same two values, set to x, x will be stored directly to nums1[0](because k is 0), then k will increment, nums1 and nums2 will jump back at the same time

Slice (0, k) returns the desired result

The advantage is that there is no need to open a new record stack, reducing space complexity

Post a ruan es6-map and Set data structure es6.ruanyifeng.com/#docs/set-m…

3. Cycle of Violence – Time complexity O(n^2)

let intersect = function (nums1, nums2) {
    let result = []
    let minArr = nums1.length > nums2.length ? nums2 : nums1
    let maxArr = nums1.length > nums2.length ? nums1 : nums2
    for( let i = 0; i < minArr.length; i++ ) {
        let maxIndex = maxArr.indexOf(minArr[i])
        if(maxIndex ! = -1) {
            result.push(maxArr.splice(maxIndex, 1) [0])}}return result
}
Copy the code

4. Post a time complexity and space complexity interpretation

Time and space complexity of algorithms

This article was originally published in the wechat public account “More than thinking”, welcome to follow, exchange more Internet cognition, work management, big data, Web, blockchain technology.

summary

What we learned today is not difficult, but it’s really beneficial to me.

  1. I learned the idea of the algorithm,

  2. Review and consolidate various array methods and Set, Map data structures,

  3. There are such as

 if(nums1[i] === nums2[j]) {
            res.push(nums1[i])
            i++
            j++
        } else nums1[i] < nums2[j] ? i++ : j++
Copy the code
            nums1[k++] = nums1[i];
            i++;
            j++;
Copy the code

More elegant details

The end of the

Recently, I have been playing a little crazy. I have to go back home to attend my college classmate's wedding banquet on October 1. I hope I can keep to my original aspiration and make progress in September.Copy the code