preface

Recently, the frequency of LeetCode examination is increasing in the interview of domestic big factories. I’ve also seen more and more front end students focus on the topic of algorithms.

But the algorithm is a very high bar, in the eyes of a novice algorithm, it has a very high IQ bar. Is that what it actually looks like? If you doubt that you’re smart enough to learn algorithms, you should first finish this article: Born Not Smart, which inspired me to get started on algorithms.

In this article, I will first summarize the classification of several required questions, give detailed solutions of the required examples under this classification, and at the end of the article, give the way to obtain the required questions under each category.

Be patient to see the end, there will be heavy dry goods.

heart

I started to learn algorithms in May when I was ready to leave my job. Before that, I had no basis for algorithms. At the beginning, I had the same feelings about algorithms as everyone else. However, after looking at the relationship between algorithm and IQ, I found that algorithm is a discipline that can be gradually developed through practice, rather than the admission ticket only after THE IQ reaches a certain point, so I started my algorithm road. By means of video course, classification, problem solving, and review, THE number of problems I solved reached 200 in two months. For a new algorithm, this should be a still can score, this article, I summed up some of my learning experience, and some classic examples to share with you.

Learning style

  1. Classification brush questions: many first contact force buckle students do not understand the method of brush questions, some people follow the question number brush, some people follow a daily brush, but this aimless brush way will generally give up one day in the middle, or brush for a long time but found no precipitation. Here is not worded, directly point out a brush method recommended by all the big guy: their learning stage is divided into several time periods to brush different categories of questions, such as the first week dedicated to solving linked list related questions, the second week dedicated to solving binary tree related questions. In this way, your knowledge will form a system, through a period of deliberate practice to strengthen the relevant knowledge points in your mind, not easy to forget.

  2. Proper give up: a lot of students encounter a difficult problem, must immerse oneself in study, do him 2 hours. Finally frustrated, over time may give up the algorithm road. To know that algorithm is a precipitation of decades in the field, the solution of a certain algorithm may be some professors for many years of research efforts, you want to rely on their own a novice to come up with an equally excellent solution, it is not too much. Therefore, we should learn to give up properly. Generally speaking, students who have a purpose (interview) to brush the questions will give up to look at the solution directly within 10 minutes if they have no clue about a new question, and then record it and review it repeatedly until the solution becomes their own knowledge. This is the most efficient way to learn.

  3. Accept that you are a novice: yes, to put it bluntly, accept that you are not a genius. You will encounter a lot of trouble in the process of brushing you, such as the same type of questions have seen examples, slightly changed the conditions can not be solved. Or have no clue about an easy problem. Believe me, this is normal. It doesn’t mean that you are not good at learning algorithms. It just means that algorithms are really a broad and profound field.

Classification of the outline

  1. Complexity analysis of the algorithm.
  2. Sorting algorithms and their differences and optimizations.
  3. Array of double pointer, sliding window idea.
  4. Use Map and Set to handle lookup table problems.
  5. Various problems with linked lists.
  6. Using recursive and iterative methods to solve binary tree problems.
  7. Stack, queue, DFS, BFS.
  8. Backtracking, greedy algorithms, dynamic programming.

Answer key

As an appetizer, I’ll post a few classic questions from each category, along with my explanations, and at the end of the article I’ll give you a collection of recommended questions to brush for each category, so be sure to check it out.

Lookup table problem

Intersection of two arrays II-350

Given two arrays, write a function to calculate their intersection.

Example 1: input: nums1 =,2,2,1 [1], nums2 = (2, 2] output: [2] example 2: input: nums1 =,9,5 [4], nums2 =,4,9,8,4 [9] output: [4, 9]Copy the code

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

Create a map for each array to store the num -> count key-value pairs and count the number of each number.

Then iterate over one of the maps, check the number of occurrences of this number in the two arrays, take the smallest number (for example, array 1 appears once, array 2 appears twice, then the intersection should take 1 time), and push it to the result array.

/** * @param {number[]} nums1 * @param {number[]} nums2 * @return {number[]} */
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) {
      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

Double pointer problem

The sum of the three closest numbers is minus 16

Given an array nums of n integers and a target value. Find the three integers in NUMS so that their sum is closest to target. Returns the sum of these three numbers. Suppose there is only one answer for each set of inputs.

Example: Input: nums = [-1,2,1,-4], target = 1 Output: 2 Description: The closest sum to target is 2 (-1 + 2 + 1 = 2).Copy the code

Tip:

3 <= nums.length <= 10^3 -10^3 <= nums[i] <= 10^3 -10^4 <= target <= 10^4

Source: LeetCode

Link: leetcode-cn.com/problems/3s…

Copyright belongs to collar network. Commercial reprint please contact the official authorization, non-commercial reprint please indicate the source.

First sort in ascending order, then select a base point I (0 <= I <= nums.length-3) from left to right, and use double pointer to continuously find the smallest difference on the right side of the base point.

Assuming the base point is I, when initializing, the double Pointers are:

  • left:i + 1To the right of the base point.
  • right: nums.length - 1Last bit of the array.

If the sum is larger than the target, you can move the right pointer to the left one bit to try a smaller value, and if not, you can move the left pointer to the right.

In this process, the global minimum difference, min, and res recorded at this time are constantly updated.

Finally, return res.

/** * @param {number[]} nums * @param {number} target * @return {number} */
let threeSumClosest = function (nums, target) {
  let n = nums.length
  if (n === 3) {
    return getSum(nums)
  }
  // Sort in ascending order first
  nums.sort((a, b) = > a - b)

  let min = Infinity // The minimum difference between target and target
  let res

  // Try to set a base pointer from left to right. Keep at least two digits on the right side, or you won't get three
  for (let i = 0; i <= nums.length - 3; i++) {
    let basic = nums[i]
    let left = i + 1 // The left pointer tries from the first to the right of I
    let right = n - 1 // The right pointer starts with the last item of the array

    while (left < right) {
      let sum = basic + nums[left] + nums[right] // Sum the three numbers
      // Update the minimum difference
      let diff = Math.abs(sum - target)
      if (diff < min) {
        min = diff
        res = sum
      }
      if (sum < target) {
        // If the sum is less than the target value, try moving the left pointer to the right to enlarge the value
        left++
      } else if (sum > target) {
        // Otherwise, the right pointer moves to the left
        right--
      } else {
        // If they are equal, the difference is 0
        return sum
      }
    }
  }

  return res
}

function getSum(nums) {
  return nums.reduce((total, cur) = > total + cur, 0)}Copy the code

Sliding window problem

The oldest string without duplicate characters is -3

Given a string, find the longest string that does not contain repeating characters.

Example 1:

Input:"abcabcbb"Output: 3 Explanation: because the most important string with no duplicate characters is"abc"So its length is 3.Copy the code

Example 2:

Input:"bbbbb"Output: 1 Explanation: because the most important string with no duplicate characters is"b"So its length is 1.Copy the code

Example 3:

Input:"pwwkew"Output: 3 Explanation: because the most important string with no duplicate characters is"wke"So its length is 3. Note that your answer must be the length of the substring,"pwke"It's a subsequence, not a substring.Copy the code

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

This is a typical sliding window problem, define a left boundary left and a right boundary right, form a window, and in this window to ensure that there is no repeated string.

This requires a new variable, freqMap, to record the frequency of the letters in the window. STR [right + 1] = STR [right + 1] = freqMap

  1. This value doesn’t show up, so let’s justright ++To expand the right edge of the window.
  2. If this value ever appears, then takeleft ++, indent it to the left, and remember tostr[left]The value of the position isfreqMapSubtracting.

The loop condition is left < str.length, allowing the left edge to slide all the way to the right edge of the string.

/** * @param {string} s * @return {number} */
let lengthOfLongestSubstring = function (str) {
  let n = str.length
  // Slide window to s[left...right]
  let left = 0
  let right = - 1
  let freqMap = {} // Record the frequency of subscripts in the current substring
  let max = 0 // The maximum length of the substring found that satisfies the condition

  while (left < n) {
    let nextLetter = str[right + 1]
    if(! freqMap[nextLetter] && nextLetter ! = =undefined) {
      freqMap[nextLetter] = 1
      right++
    } else {
      freqMap[str[left]] = 0
      left++
    }
    max = Math.max(max, right - left + 1)}return max
}
Copy the code

List problem

Switch nodes -24 in the linked list in pairs

Given a linked list, swap the adjacent nodes in pairs and return the swapped list.

You can’t just change the values inside a node, but actually switch nodes.

Example:

Given 1->2->3->4, you should return 2->1->4->3.Copy the code

Source: LeetCode

Link: leetcode-cn.com/problems/sw…

Copyright belongs to collar network. Commercial reprint please contact the official authorization, non-commercial reprint please indicate the source.

In the case of 1 -> 2 -> 3 -> 4, you can define a recursive helper function for each node to exchange with its next node. For example, helper(1) handles 1 -> 2. And the next of the tail node 1 that turns the swap into 2 -> 1 continues to point to helper(3), which is 4 -> 3 after the swap.

In the boundary case, if we do a pairwise swap, then our function returns the head node that we switched, but if we do an odd number of remaining terms, we can’t switch, so we need to return the original head node. This is reflected in both the helper function and the main function.

let swapPairs = function (head) {
  if(! head)return null
  let helper = function (node) {
    let tempNext = node.next
    if (tempNext) {
      let tempNextNext = node.next.next
      node.next.next = node
      if (tempNextNext) {
        node.next = helper(tempNextNext)
      } else {
        node.next = null}}return tempNext || node
  }

  let res = helper(head)

  return res || head
}
Copy the code

Depth first traversal problem

All paths of the binary tree -257

Given a binary tree, return all paths from the root node to the leaf node.

Note: A leaf node is a node with no child nodes.

Example:

Input: 1 / \ 2 3\5 Output: ["1 - > 2 - > 5"."1 - > 3"[Explanation: The paths from all root nodes to leaf nodes are: 1->2->5, 1->3Copy the code

Source: LeetCode

Link: leetcode-cn.com/problems/bi…

Copyright belongs to collar network. Commercial reprint please contact the official authorization, non-commercial reprint please indicate the source.

Use the value of the current node to concatenate all paths obtained by recursively calling the current function to the left and right subtrees.

It’s going to be the path from the root node to the left subtree, plus all the paths from the root node to the right subtree.

Up to the leaf node, just return an array of values for the current node.

let binaryTreePaths = function (root) {
  let res = []
  if(! root) {return res
  }

  if(! root.left && ! root.right) {return [`${root.val}`]}let leftPaths = binaryTreePaths(root.left)
  let rightPaths = binaryTreePaths(root.right)

  leftPaths.forEach((leftPath) = > {
    res.push(`${root.val}->${leftPath}`)
  })
  rightPaths.forEach((rightPath) = > {
    res.push(`${root.val}->${rightPath}`)})return res
}
Copy the code

Breadth first Traversal (BFS) problem

Look for the maximum value -515 in each tree row

Leetcode-cn.com/problems/fi…

You need to find the maximum value in each row of the binary tree.

Input: 1 / \ 3 2 / \ 5 3 9 Output: [1, 3, 9]Copy the code

This is a typical BFS problem. BFS maintains a queue and pushes the grandchildren to the queue while reading the children. After the children in the queue are processed, the grandchildren will be processed again. And this allows you to do sequential traversal, which is to do it layer by layer.

However, there is a problem that stuck me for a while, that is, how to know which level the node is currently dealing with. At the beginning, I tried to write a binary tree to find the level of an index, but found that this formula can only deal with “balanced binary tree”.

They are not dedicated to maintaining the hierarchy. Take a closer look at the hierarchy.

So, for each round of the while loop, we open another for loop, and the end of that for loop is “the length of the pre-cached snapshot,” which is the length of the queue at the time of the while loop. In fact, this length is exactly the “length of a hierarchy.”

After caching, the for loop can safely push children into the array without affecting the current level of the cache.

Another tip is that after the for loop is processed, you should intercept the queue length to the cache length described above. I started with queue.splice(0, len) and only beat 33% of people. Instead of doing it shift by shift in a for loop, you beat 77% of the participants.

/** * @param {TreeNode} root * @return {number[]} */
let largestValues = function (root) {
  if(! root)return []
  let queue = [root]
  let maximums = []

  while (queue.length) {
    let max = Number.MIN_SAFE_INTEGER
    // We need to cache length, which represents all nodes at the current level
    // After the start of the loop will push the new node length is not stable
    let len = queue.length
    for (let i = 0; i < len; i++) {
      let node = queue[i]
      max = Math.max(node.val, max)

      if (node.left) {
        queue.push(node.left)
      }
      if (node.right) {
        queue.push(node.right)
      }
    }

    // This "level" is processed, intercept.
    for (let i = 0; i < len; i++) {
      queue.shift()
    }

    // When the for loop ends, all nodes at the current level are processed
    // Push the maximum value into the array.
    maximums.push(max)
  }

  return maximums
}
Copy the code

Stack issues

Valid parentheses -20

Given a string containing only ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘, ‘]’, determine whether the string is valid.

A valid string must meet the following requirements:

  • The opening parenthesis must be closed with a closing parenthesis of the same type.
  • The opening brackets must be closed in the correct order.
  • Note that an empty string can be considered a valid string.

Example 1:

Input:"()"Output:true
Copy the code

Example 2:

Input:"[the] {} ()"Output:true
Copy the code

Example 3:

Input:"(]"Output:false
Copy the code

Example 4:

Input:"([]"Output:false
Copy the code

Example 5:

Input:"{[]}"Output:true
Copy the code

Leetcode-cn.com/problems/va…

Note in advance the mapping table of open parenthesis types (, {, [and close parenthesis types),},]. When the open parenthesis is encountered in the traversal, it is put into the stack (which is actually an array). When the close parenthesis is encountered, the top element of the stack is popped out. See if the closing parenthesis matches the opening parenthesis (for example, (and) are a matching pair of parentheses).

When the traversal is complete, there should be no remaining elements on the stack, returning success or failure.

/** * @param {string} s * @return {boolean} */
let isValid = function (s) {
  let sl = s.length
  if (sl % 2! = =0) return false
  let leftToRight = {
    "{": "}"."[": "]"."(": ")",}// Create an inverse value -> key mapping table
  let rightToLeft = createReversedMap(leftToRight)
  // The stack used to match the open and close brackets
  let stack = []

  for (let i = 0; i < s.length; i++) {
    let bracket = s[i]
    // Put the open bracket on the stack
    if (leftToRight[bracket]) {
      stack.push(bracket)
    } else {
      let needLeftBracket = rightToLeft[bracket]
      // Open parentheses are not direct failures
      if(! needLeftBracket) {return false
      }

      // Removing the last parenthesis from the stack will fail if it is not the desired open parenthesis
      let lastBracket = stack.pop()
      if(needLeftBracket ! == lastBracket) {return false}}}if (stack.length) {
    return false
  }
  return true
}

function createReversedMap(map) {
  return Object.keys(map).reduce((prev, key) = > {
    const value = map[key]
    prev[value] = key
    return prev
  }, {})
}
Copy the code

Recursion and backtracking

Just look at the two articles I wrote. Recursion and backtracking are even one of the most common algorithmic scenarios in ordinary business development, so I’ve highlighted the two articles.

Is it difficult to complete the permutation algorithm of the front-end E-commerce SKU? Learn this routine and thoroughly master the permutation and combination.

Front – end “N queen” recursive backtracking classic problem diagram

Dynamic programming

Robbery. – 198

You are a professional thief, planning to steal houses along the street. Each house has a certain amount of cash hidden in it, and the only restriction that affects your theft is that the adjacent houses are connected to the anti-theft system. If two adjacent houses are broken into on the same night, the system will automatically alarm.

Given an array of non-negative integers representing the amount of money stored in each house, calculate the maximum amount you can steal without activating the alarm.

Example 1: Input: [1,2,3,1] Output: 4 Explanation: Steal house 1 (amount = 1), then steal house 3 (amount = 3). Maximum amount stolen = 1 + 3 = 4. Example 2: Input: [2,7,9,3,1] Output: 12 Explanation: Steal house # 1 (amount = 2), steal house # 3 (amount = 9), then steal house # 5 (amount = 1). Maximum amount stolen = 2 + 9 + 1 = 12.Copy the code

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

A very important process of dynamic programming is to find the “state” and the “state transition equation”. In this problem, let I be the subscript of the current room, and the state is the maximum value to steal from I

In front of a house, a burglar has only two choices: to steal or not to steal.

  1. In the case of theft, the value is “the current value of the house” + “the maximum value of the next two houses to start stealing.”
  2. Without stealing, the value is “the maximum value of the next house to start stealing.”

Of these two values, select the maximum value recorded in DP [I] to get the maximum value that can be stolen starting from I.

The starting point of dynamic programming is to find the base state. In this case, the maximum value starting from the end point must be best to find, because the end point cannot steal any further, so let n be the total number of houses, dp[n-1] is nums[n-1], the thief can only choose to steal this house. You can’t just jump over and choose the next house that doesn’t exist.

Then the state transition equation of dynamic programming is found:

// Rob the current house
robNow = nums[i] + dp[i + 2] // "current house value" + "I + 2 subscript the house as the maximum value from the starting point"

// Take the next house instead of the current one
robNext = dp[i + 1] // "I + 1 subscript the house as the maximum value from the starting point"

// Select the maximum value for both
dp[i] = Math.max(robNow, robNext)
Copy the code

And solve from the back.

function (nums) {
  if(! nums.length) {return 0;
  }
  let dp = [];

  for (let i = nums.length - 1; i >= 0; i--) {
    let robNow = nums[i] + (dp[i + 2] | |0)
    let robNext = dp[i + 1] | |0

    dp[i] = Math.max(robNow, robNext)
  }

  return dp[0];
};
Copy the code

Finally, return the maximum value of the loot starting from 0.

Greedy algorithm problem

Pass out the cookies. -455

Let’s say you’re a great parent and you want to give your kids some cookies. However, each child can only be given one cookie at most. For every child I, there is an appetite value GI, which is the minimum size of cookie that can satisfy a child’s appetite; And each cookie j has a size, SJ. If sj >= gi, we can distribute this cookie J to child I, and the child will be satisfied. Your goal is to satisfy as many children as possible and output this maximum number.

Note:

You can assume that appetite is positive. A child can have no more than one cookie.

Example 1: Input: [1,2,3], [1,1] Output: 1 Explanation: You have three children and two cookies. The appetites of the three children are: 1,2,3. Although you have two small cookies, since they are both size 1, you can only satisfy the child whose appetite value is 1. So you should print 1. Example 2: input: [1,2], [1,2,3] output: 2 explanation: you have two children and three cookies. Each child has an appetite value of 1,2. The number and size of cookies you have is enough to satisfy any child. So you should print 2.Copy the code

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

Prioritize the cookies and the needs of the children, and then start from the smallest cookies to the children with the smallest needs, constantly try new cookies and new children, so as to ensure that every cookie given to the children is just right not to waste, and meet the needs.

Double pointer is used to continuously update the subscript of child I’s demand and the value of cookie J until one of the two reaches the end position:

  1. If the current biscuit does not satisfy the child’s appetite, then putj++Look for the next cookie and don’t worry about it going to waste because it’s less likely to satisfy the next kid.
  2. If so, theni++; j++; count++Keep track of the current number of successes and move on to the next kid and the next cookie.
/** * @param {number[]} g * @param {number[]} s * @return {number} */
let findContentChildren = function (g, s) {
  g.sort((a, b) = > a - b)
  s.sort((a, b) = > a - b)

  let i = 0
  let j = 0

  let count = 0
  while (j < s.length && i < g.length) {
    let need = g[i]
    let cookie = s[j]

    if (cookie >= need) {
      count++
      i++
      j++
    } else {
      j++
    }
  }

  return count
}
Copy the code

Will do topics

In fact, I have written so much. The topics mentioned in the above categories are just the topics that are more suitable to be explained as examples under the current classification. They are just the tip of the iceberg in the whole learning process of LeetCode. These questions can serve as an introduction to the category, but inevitably, you’ll have to work hard on the other classic questions in each category.

If you trust me, you can also click here to get the detailed solutions of the required problems in each category (remember to collect them). I followed the outline given by an ACM Asia regional medalist to sort out the 100+ detailed solutions of the required problems.

So what is called must do the topic?

  1. It’s about algorithms, not kit-kat, at its core.
  2. It examines knowledge points that can be applied to many similar problems.
  3. Interview hot topic, big factory likes to test this topic, explain this knowledge point is very important.

Of course, you can also go to zhihu and other platforms to search related issues, there will be a lot of people summed up, but more than I summed up the whole of rare. More than 100 questions say more or less, say less or less. It takes about a month to study, solve and absorb these problems carefully. But trust me, after a month, you will be a completely different person in the algorithm field, and you will be able to handle the algorithm interview of the big domestic factories with ease.

conclusion

The debate over the usefulness of algorithms in engineering has been a perennial one. I’m not going to talk about that here, but my own ideas are absolutely useful, as long as you’re not a simple requirement person, you’ll benefit more or less from learning your algorithms as you develop your architecture and encounter difficulties.

Utilitarian point again, even in order to interview, brush algorithm can enter dafang is also a starting point of your career, dafang to bring you the environment, strict Code Review, perfect mentor mechanism and collaboration process is your dream as an engineer.

Hopefully, this article will stop you from being afraid of algorithmic interviews and join me in taking down the castle. Come on, everyone!

❤️ Thank you all

1. If this article is helpful to you, give it a like. Your likes are my motivation.

2. Follow the public number “front-end from advanced to hospital” can add my friends, I pull you into the “front-end advanced exchange group”, we communicate and progress together.