“What you must Ask in an interview” leetcode

Introduction (there are benefits at the end of the article) 🏂

Algorithms have always been a common question in the front-end interview of large factories, and we often prepare for this aspect of the interview are brush questions through Leetcode.

I specifically organized several “interesting” and very “high frequency” algorithm problems in LeetCode, and gave the thought analysis (with diagrams) and code implementation respectively.

Carefully read this article, I believe for you in the algorithm of the interview will be no small help! 🤠

The sum of the two numbers 🦊

❝

The algorithm knowledge involves arrays and hash tables

❞

Topic describes

Given an array of integers nums and a target value target, find the two integers in the array and the target values and return their array subscripts.

You can assume that there is only one answer for each type of input. However, the same element in an array cannot be used twice.

Example:

Given nums = [2.7.11.15], target = 9

Because the nums [0] + nums[1] = 2 + 7 = 9
So return [0.1]
Copy the code

Thought analysis

Most of you might look at this problem and think, “Wow, this is a very simple problem. It’s just a two-level loop through the same array. The value of the first loop loop is denoted as a, and the value of the second loop loop is denoted as B; If a+b = the target value, then the array subscripts of a and B are the answers we want.

There’s nothing wrong with this solution, but is there an optimal solution? 🤔

Remember that two-level loops in many cases mean O(n^2) complexity, which can easily cause your algorithm to time out. Even if you don’t run out of time, the interviewer will discount your impression if you write two traversals when there is one solution. 🤒

In fact, we can add a Map structure to store the iterated numbers and their corresponding index values while iterating through the array. Each time a new number is iterated, go back to the Map to see if the difference between targetNum and that number has already occurred in the previous number. If so, the answer is already there, and we don’t have to go any further.

Let’s use the example in this case and the picture to illustrate the idea mentioned above:

• I’m using objects herediffsTo simulate themapStructure:The first element of the array is iteratedkeyTo 2,valueFor the index 0

• If I walk down, I encounter 7:To calculatetargetNumThe difference between 7 and 7 is 2. GodiffsRetrieves 2 of thiskeyIs found to be a value that appeared before. So here’s the answer to this question!

Code implementation

/ * * * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
* /
const twoSum = function (nums, target) {  const diffs = {};  // Cache array length  const len = nums.length;  // go through the number group  for (let i = 0; i < len; i++) {  // Check whether the target difference exists for the current value  if(diffs[target - nums[i]] ! = =undefined) {  // If there is a corresponding difference, then get the answer  return [diffs[target - nums[i]], i];  }  // If there is no corresponding difference, the current value is recorded  diffs[nums[i]] = i;  } }; Copy the code

Sum of three 🦁

❝

In medium, there are two kinds of algorithms: array and double pointer

❞

Topic describes

Given an array nums containing n integers, determine if nums contains three elements A, B, and c such that a + b + c = 0. Please find all the triples that meet the criteria and are not duplicated.

Note: Repeated triples cannot be included in the answer.

Example:

Given array nums = [- 1.0.1.2.- 1.4 -].
The set of triples that meet the requirements is:[
  [- 1.0.1]. [- 1.- 1.2] ] Copy the code

Thought analysis

Just like the sum of the two numbers above, if you don’t really think about it, the fastest way is probably going to be multi-layer traversal. But with that in mind, we can also turn the summation problem into a difference problem: fix one of the numbers and look for the remaining numbers to see if the sum of two numbers adds up to zero.

Here we use the two-pointer method to solve the problem, which will greatly improve the efficiency compared with the three-layer cycle.

❝

The two-pointer method has a wide range of application, such as summation, ratio of size can be used to solve it. But there is one caveat: the array must be ordered

❞

So our first step is to sort the array:

// Sort nums
nums = nums.sort((a,b) = >{
    return a-b
})
Copy the code

It then iterates through the array, fixing the current number each time it reaches a number. The left pointer points to the next number and the right pointer points to the end of the array. Then the left and right Pointers move toward the center:Each time the pointer moves, it calculates whether the sum of the two Pointers plus the fixed number equals zero. If so, then we have a combination of targets; Otherwise, look at it in two ways:

• If the sum is greater than 0, the number on the right is too large and the right pointer moves to the left
• If the sum is less than 0, the number on the left is smaller and the left pointer moves to the right

Code implementation

/ * * * @param {number[]} nums
 * @return {number[][]}
* /
const threeSum = function(nums) {
 // Store the result array  let res = []  // The target value is 0  let sum = 0  // Sort nums  nums = nums.sort((a,b) = >{  return a-b  })  // Cache array length  const len = nums.length  for(let i=0; i<len2 -; i++) { // left pointer j  let j=i+1  // right pointer k  let k=len- 1  // If duplicate numbers are encountered, skip  if(i>0&&nums[i]===nums[i- 1]) {  continue  }  while(j<k) {  // If the sum of three numbers is less than 0, the left pointer advances  if(nums[i]+nums[j]+nums[k]<0) { j++  // Handle duplicate left pointer elements  while(j<k&&nums[j]===nums[j- 1]) {  j++  }  } else if(nums[i]+nums[j]+nums[k]>0) { // If the sum of three numbers is greater than 0, the right pointer is backward  k--   // Handle duplicate right pointer elements  while(j<k&&nums[k]===nums[k+1]) {  k--  }  } else {  // Get the target number combination and push the result array  res.push([nums[i],nums[j],nums[k]])   // The left and right Pointers move forward together  j++  k--   // If the left pointer element is repeated, skip  while(j<k&&nums[j]===nums[j- 1]) {  j++  }   // If the right pointer element is repeated, skip it  while(j<k&&nums[k]===nums[k+1]) {  k--  }  }  }  }   // Returns an array of results  return res }; Copy the code

The container that holds the most water 🥃

❝

In medium, there are two kinds of algorithms: array and double pointer

❞

Topic describes

Give you n non-negative integers A1, A2… Each number represents a point in the coordinates (I, ai). Draw n vertical lines in the coordinates, and the two endpoints of vertical line I are (I, AI) and (I, 0). Find the two lines that together with the X-axis will hold the most water.

Note: you cannot tilt the container, and the value of n is at least 2.The vertical lines in the figure represent the input array [1,8,6,2,5,4,8,3,7]. In this case, the maximum amount of water the container can hold (shown in blue) is 49.

Example:

Input:1.8.6.2.5.4.8.3.7]
Output:49
Copy the code

Thought analysis

First of all, we can quickly think of a method: to solve in pairs, calculate the amount of water can be carried. Then keep updating the maximum value, and finally return the maximum value.

This solution, which takes two cycles, is O(n^2). This is relatively violent, and the counterpart is the violent method.

Violence law

/ * * * @param {number[]} height
 * @return {number}
* /
var maxArea = function(height) {
 let max = 0;  for(let i = 0; i< height.length- 1; i++) {  for(let j = i + 1; j < height.length; j++) { let area = (j - i) * Math.min(height[i], height[j]);  max = Math.max(max, area)  }  }   return max; } Copy the code

So is there a better way? The answer is yes.

It’s kind of similarDouble pointerThe left pointer points to subscript 0 and the right pointer points tolength-1. Then move from left to right to center, taking the smaller value each time (because the height of the water must be the smaller value).

If the left is less than the right, i++, otherwise j– (this step is just taking the higher of all the heights, we know that area is length times width). The corresponding is the double pointer dynamic slide window

Double pointer dynamic sliding window

/ * * * @param {number[]} height
 * @return {number}
* /
var maxArea = function(height) {
 let max = 0;  let i = 0;  let j = height.length - 1;  while(i < j) {  let minHeight = Math.min(height[i], height[j])  let area = (j - i)*minHeight;  max = Math.max(max, area)  if(height[i] < height[j]) {  i++  } else {  j--  }  }  return max }; Copy the code

Climb the stairs 🎢

❝

The difficulty of the topic is easy, involving the algorithm knowledge of Fibonacci sequence, dynamic programming.

❞

Topic describes

Suppose you’re climbing stairs. It takes n steps to get to the top.

You can climb one or two steps at a time. How many different ways can you climb to the top?

Note: given n is a positive integer.

Example 1:

Input:2
Output:2
Explanation: There are two ways to climb to the top.1.  1Order +1 阶
2.  2 阶
Copy the code

Example 2:

Input:3
Output:3
Explanation: There are three ways to climb to the top.1.  1Order +1Order +1 阶
2.  1Order +2 阶
3. 2Order +1 阶 Copy the code

Thought analysis

This is a very frequent interview question, but also a very classic Fibonacci sequence type question.

We will use the algorithmic idea of dynamic programming to solve this problem – it can be divided into subproblems, the number of ways to climb the NTH stair is equal to the sum of two parts:

• Climb theN - 1Number of ways to step a staircase. Because it takes one more step to get to the NTH
• Climb theN - 2Number of ways to get to the stairs, because it takes 2 more steps to get to the NTH

The formula can be obtained:

climbs[n] = climbs[n- 1] + climbs[n2 -]
Copy the code

The following initialization needs to be done:

climbs[0] = 1;
climbs[1] = 1
Copy the code

Code implementation

/ * * * @param {number} n
 * @return {number}
* /
var climbStairs = function(n) {
 let climbs = [];  climbs[0] = 1;  climbs[1] = 1;  for(let i = 2; i<= n; i++) {  climbs[i] = climbs[i- 1] + climbs[i2 -]  }  return climbs[n]  }; Copy the code

Circular linked lists 🍩

❝

The difficulty of the topic is easy, involving the algorithm knowledge of linked lists, fast and slow Pointers.

❞

Topic describes

Given a linked list, determine whether there are rings in the list.

To represent the rings in a given list, we use the integer pos to represent where in the list the tail joins (the index starts at 0). If pos is -1, there are no rings in the linked list.

Example 1:

Enter: head = [3.2.0.4 -], pos = 1
Output:true
Explanation: A linked list has a ring whose tail is connected to a second node.Copy the code

Example 2:

Enter: head = [1.2], pos = 0
Output:true
Explanation: A linked list has a ring whose tail is connected to the first node.Copy the code

Example 3:

Enter: head = [1], pos = - 1
Output:false
Explanation: There are no rings in the linked list.Copy the code

Thought analysis

List cyclizationThe problem is also a very classic algorithm problem, often encountered in the interview.

There are two common methods to solve this problem: mark method and fast and slow pointer method.

notation

Add a flag bit to each node that has been traversed to traverse the linked list. When the next node is marked, it proves that the single linked list has a ring.

/ * * * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 * this.next = null; *}* /  / * * * @param {ListNode} head  * @return {boolean} * / var hasCycle = function(head) {  while(head) {  if(head.flag) return true  head.flag = true;  head = head.next;  }  return false }; Copy the code

Fast and slow pointer (double pointer method)

If there is a ring in the single linked list, then the fast and slow Pointers will eventually point to the same node. Otherwise, the fast and slow Pointers cannot meet until the fast pointer points to null.

/ * * * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 * this.next = null; *}* /  / * * * @param {ListNode} head  * @return {boolean} * / var hasCycle = function(head) {  if(! head || ! head.next) { return false  }  let slow = head, fast = head.next;  while(slow ! == fast) { if(! fast || ! fast.next)return false  fast = fast.next.next;  slow = slow.next  }  return true; }; Copy the code

Valid parentheses 🍉

❝

Topic difficulty is easy, involves the algorithm knowledge stack, hash table.

❞

Topic describes

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

A valid string must meet the following requirements:

1. Open parentheses must be closed with close parentheses of the same type. 2. The left parentheses 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

Thought analysis

You can use the stack structure for this problem.

If you encounter an open parenthesis, push it to the stack. If you encounter a close parenthesis, remove the element at the top of the stack. If it doesn’t match, return itfalseIf it matches, the loop continues.The first way to do it is to useswitch case.

switch case

/ * * * @param {string} s
 * @return {boolean}
* /
var isValid = function(s) {
 let arr = [];  let len = s.length;  if(len%2! = =0) return false  for(let i = 0; i<len; i++) { let letter = s[i];  switch(letter) {  case '(': {  arr.push(letter);  break;  }  case '{': {  arr.push(letter);  break;  }  case '[': {  arr.push(letter);  break;  }  case ') ': {  if(arr.pop() ! = ='(') return false  break;  }  case '} ': {  if(arr.pop() ! = ='{') return false  break;  }  case '] ': {  if(arr.pop() ! = ='[') return false  break;  }  }  }  return! arr.length}; Copy the code

The second way is to maintain a map object:

Hash tablemap

/ * * * @param {string} s
 * @return {boolean}
* /
var isValid = function(s) {
 let map = {  '(': ') '. '{': '} '. '[': '] '  }  let stack = [];  let len = s.length;  if(len%2! = =0) return false  for(let i of s) {  if(i in map) {  stack.push(i)  } else {  if(i ! == map[stack.pop()])return false  }  }  return! stack.length}; Copy the code

Maximum sliding window ⛵

❝

The algorithm is a double-endian queue.

❞

Topic describes

Given an array numS, there is a sliding window of size K that moves from the leftmost of the array to the rightmost of the array. You can only see k numbers in the sliding window. The sliding window moves only one bit to the right at a time.

Returns the maximum value in the sliding window.

Advanced: Can you solve this problem in linear time complexity?

Example:

Enter: nums = [1.3.- 1.- 3.5.3.6.7], and k =3
Output:3.3.5.5.6.7]
Explanation:
The maximum position of a sliding window--------------- ----- [1 3 - 1] - 3 5 3 6 7 3  1 [3 - 1 - 3] 5 3 6 7 3  1 3 [- 1 - 3 5] 3 6 7 5  1 3 - 1 [- 3 5 3] 6 7 5  1 3 - 1 - 3 [5 3 6] 7 6  1 3 - 1 - 3 5 [3 6 7] 7 Copy the code

Tip:

• 1 <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4
• 1 <= k <= nums.length

Thought analysis

Violence to solve

The first way is easier. And that’s something that most of you can figure out pretty quickly.

• Through the array
• Iterate over the maximum value of each interval and put it in an array

/ * * * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
* /
var maxSlidingWindow = function(nums, k) {  let len = nums.length;  if(len === 0) return []  if(k === 1) return nums  let resArr = []  for(let i = 0; i <= len - k; i++) { let max = Number.MIN_SAFE_INTEGER;  for(let j = i; j < i + k; j++) {  max = Math.max(max, nums[j])  }  resArr.push(max)  }  return resArr; }; Copy the code

deque

This problem can also be solved with a double-ended queue, the core of which is to update the maximum value only according to the element that changes when the window moves.

With the above GIF (image source), let’s sort out the ideas:

• Check that the last element of the queue is greater than or equal to the current element. If so, enqueue the current element directly. Otherwise, the end of the queue elements are removed one by one until the end of the queue elements are greater than or equal to the current element. This step is to maintain decrement of the queue: ensure that the queue header element is the maximum number of sliding Windows currently available. So every time we take the maximum value, we just take the header element.
• Enlists the current element
• Check the header element to see if the header element has been excluded from the sliding window. If so, the head element is removed from the team. (This step is to keep the queue valid: make sure that all the elements in the queue are within the range defined by the sliding window.)
• Rule out special cases where the sliding window has not been initialized and the first maximum has not yet occurred.

/ * * * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
* /
var maxSlidingWindow = function(nums, k) {  // The length of the cache array  const len = nums.length;  const res = [];  const deque = [];  for (let i = 0; i < len; i++) {  // The last element of the queue is smaller than the current element  while (deque.length && nums[deque[deque.length - 1]] < nums[i]) {  deque.pop()  }  deque.push(i)   // When the index of the header element has been excluded from the sliding window  while (deque.length && deque[0] <= i - k) {  // Team head element is correct  deque.shift()  }  if (i >= k - 1) {  res.push(nums[deque[0]])  }  }  return res }; Copy the code

Daily temperature 🌡

❝

On medium, the algorithm knowledge involved in the stack.

❞

Topic describes

According to the daily temperature list, please generate a new list. The output of the corresponding position is how many more days need to wait for the temperature to rise beyond that day. If it does not rise after that, replace it with 0 at that position.

For example, given a list of temperatures = [73, 74, 75, 71, 69, 72, 76, 73], your output would be [1, 1, 4, 2, 1, 1, 0, 0].

Note: The length range of the temperature list is [1, 30000]. Each temperature is an integer in the [30, 100] range of degrees Fahrenheit.

Thought analysis

The first layer locates a temperature, the second layer locates the date of the last temperature rise from this temperature, and then calculates the difference of the corresponding index of the two temperatures.

However, this solution requires two layers of traversal and the time complexity is O(n^2), which is obviously not the optimal solution.

This problem can use stack to do an optimization.

The general idea is: maintain a decrement stack. When the temperature traversed is maintained in a monotonically decreasing state, the index subscripts of these temperatures are pushed into the stack. As soon as there is a number that breaks the monotonic decreasing trend, that is, it is higher than the previous temperature value, then we take the difference of the index subscripts of the two temperatures and get the difference between the previous temperature and the target value of the first temperature rise.

Code implementation

/ * * * @param {number[]} T
 * @return {number[]}
* /
var dailyTemperatures = function(T) {
 const len = T.length;  const stack = [];  const res = (new Array(len)).fill(0);  for (let i=0; i < len; i++) { while(stack.length && T[i] > T[stack[stack.length - 1]]) {  const top = stack.pop();  res[top] = i - top;  }  stack.push(i)  }  return res }; Copy the code

Parenthesis generation 🎯

❝

In medium, it involves the knowledge of recursion and backtracking.

❞

Topic describes

The number n represents the logarithm of parentheses generated. Design a function that generates all possible and valid parentheses combinations.

Example:

Enter n =3
Output:       "((()))".       "() () ()".       "() () ()". "() () ()". "() () ()"  ] Copy the code

Thought analysis

This problem is done recursively.

Because the left and right parentheses need to match and close. So the number of “(” and”) “is n. When this condition is met, the recursion ends and the corresponding values are put into the result array.

There is one potential limitation: a valid parenthesis combination. The corresponding logic is to place “(” or”) “before each position:

• Check whether the number of (is less than n
• Is the number of “) “less than” (“

Code implementation

/ * * * @param {number} n
 * @return {string[]}
* /
var generateParenthesis = function(n) {
 let res = []  const generate = (cur, left, right) = > {  if (left ===n && right === n) {  res.push(cur)  return  }  if (left < n) {  generate(cur + '(', left + 1, right)  }  if (right < left) {  generate(cur + ') ', left, right + 1)  }  }  generate(' '.0.0)  return res }; Copy the code

The alphabet of the phone number 🎨

❝

In medium, it involves the knowledge of recursion and backtracking.

❞

Topic describes

Given a string containing only the numbers 2-9, return all the letter combinations it can represent.

The mapping of numbers to letters is given as follows (same as a telephone key). Note that 1 does not correspond to any letter.Example:

Input:"23"
Output:"ad"."ae"."af"."bd"."be"."bf"."cd"."ce"."cf"].
Copy the code

Thought analysis

Let’s start with an objectmapStores the mapping between numbers and letters, then iterates through the corresponding string, storing the string in the result array for the first timeresultThe second and subsequent double traversals generate a new array of strings.

Code implementation

The hash map traverses layer by layer

/ * * * @param {string} digits
 * @return {string[]}
* /
var letterCombinations = function(digits) {
 let res = [];  if (digits.length === 0) return []  let map = {  2: 'abc'. 3: 'def'. 4: 'ghi'. 5: 'jkl'. 6: 'mno'. 7: 'pqrs'. 8: 'tuv'. 9: 'wxyz'  }  for (let num of digits) {  let chars = map[num]  if (res.length > 0) {  let temp = []  for (let char of chars) {  for (let oldStr of res) {  temp.push(oldStr + char)  }  }  res = temp  } else { res.push(... chars) }   }  return res }; Copy the code

recursive

/ * * * @param {string} digits
 * @return {string[]}
* /
var letterCombinations = function(digits) {
 let res = [];  if(! digits)return []  let map = {  2: 'abc'. 3: 'def'. 4: 'ghi'. 5: 'jkl'. 6: 'mno'. 7: 'pqrs'. 8: 'tuv'. 9: 'wxyz'  }  function generate(i, str) {  let len = digits.length;  if (i === len) {  res.push(str)  return  }  let chars = map[digits[i]]  for (let j = 0; j < chars.length; j++) {  generate(i+1, str + chars[j])  }  }  generate(0.' ')  return res }; Copy the code

Number of islands 🏝

❝

DFS (Depth-first search)

❞

Topic describes

Given a two-dimensional grid of ‘1’ (land) and ‘0’ (water), count the number of islands in the grid.

Islands are always surrounded by water, and each can only be formed by connecting adjacent lands horizontally or vertically.

Furthermore, you can assume that all four sides of the grid are surrounded by water.

Example 1:

Input:11110
11010
11000
00000
Output:1 Copy the code

Example 2:

Input:11000
11000
00100
00011
Output:3 Explanation: An island can only be formed by connecting adjacent lands horizontally and/or vertically.Copy the code

Thought analysis

As shown in the figure above, we need to count the number of green islands that are connected (horizontally and/or vertically only).

A classic approach to this topic is to sink the island, the general idea is: the use of DFS (depth first search), encountered 1 will be the current 1 into 0, and the current coordinate up and down around the implementation of DFS, and counting.

The terminating condition is: the boundary of the two-dimensional array is exceeded or 0 is encountered.

Code implementation

/ * * * @param {character[][]} grid
 * @return {number}
* /
var numIslands = function(grid) {
 const rows = grid.length;  if (rows === 0) return 0  const cols = grid[0].length;  let res = 0;  for (let i = 0; i < rows; i++) {  for (let j = 0; j < cols; j++) {  if (grid[i][j] === '1') {  helper(grid, i, j, rows, cols)  res++  }  }  }  return res }  function helper(grid, i, j, rows, cols) {  if (i < 0 || j < 0 || i > rows - 1 || j > cols - 1 || grid[i][j] === "0")  return;   grid[i][j] = "0"   helper(grid, i + 1, j, rows, cols);  helper(grid, i, j + 1, rows, cols);  helper(grid, i - 1, j, rows, cols);  helper(grid, i, j - 1, rows, cols);  } Copy the code

Distributing cookies 🍪

❝

Greedy algorithms.

❞

Topic describes

Let’s say you’re a great parent and you want to give your kids some cookies. However, no more than one cookie can be given to each child. For each child, there is an appetite gi, which is the minimum size of a cookie to satisfy a child’s appetite; And every cookie j has a size Sj. If sj >= gi, we can assign 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 kids and two cookies,3The appetite values of each child are:1.2.3.Although you have two little cookies, because of their size1You can only let your appetite be1Are satisfied with their children.So you should output1.Copy the code

Example 2:

Input:1.2], [1.2.3]

Output:2

Explanation:You have two kids and three cookies,2The appetites of each child are1.2.The number and size of cookies you have is enough to satisfy all children.So you should output2. Copy the code

Thought analysis

This problem is a typical greedy algorithm class. The solution is as follows:

• Meet the needs of children with small appetites first
• Set the maximum number of children that can be satisfied asmaxNum = 0
• Those with small appetites take small, those with big appetites take big
• I’m going up on both sides, and I’m going to compare them
  • whenCookies j> =I appetiteWhen,i++,j++,maxNum++
  • whenCookies j < I appetite“, indicating that there are not enough cookies to eat, change to bigger ones,j++
• Stop at the border

Code implementation

/ * * * @param {number[]} g
 * @param {number[]} s
 * @return {number}
* /
var findContentChildren = function(g, s) {  g = g.sort((a, b) = > a - b)  s = s.sort((a, b) = > a - b)  let gLen = g.length,  sLen = s.length,  i = 0. j = 0. maxNum = 0;  while (i < gLen && j < sLen) {  if (s[j] >= g[i]) {  i++;  maxNum++  }  j++  }  return maxNum }; Copy the code

The best time to buy and sell stocks II 🚁

❝

The topic is easy, involving the algorithm knowledge of dynamic programming, greedy algorithm.

❞

Topic describes

Given an array, its ith element is the price of a given stock on the ith day.

Design an algorithm to calculate the maximum profit you can make. You can make as many trades (buying and selling a stock multiple times) as possible.

Note: You can’t participate in more than one transaction at a time (you must sell your previous shares before buying again).

Example 1:

Input:7.1.5.3.6.4]
Output:7
Explanation: In no2Day (stock price =1) time to buy, at No3Day (stock price =5), the trade can make a profit5- 1 = 4 。
Then, at No4Day (stock price =3) time to buy, at No5Day (stock price =6), the trade can make a profit6- 3 = 3 。
Copy the code

Example 2:

Input:1.2.3.4.5]
Output:4
Explanation: In no1Day (stock price =1) time to buy, at No5Day (stock price =5), the trade can make a profit5- 1 = 4 。
Mind you can't be in the first1Heaven and the first2Buy stocks day after day and sell them later.Because you're doing multiple trades at once, you have to sell your shares before you can buy them again.Copy the code

Example 3:

Input:7.6.4.3.1]
Output:0
Explanation: In this case, no transaction is completed, so the maximum profit is0.Copy the code

Tip:

• 1 <= prices.length <= 3 * 10 ^ 4
• 0 <= prices[i] <= 10 ^ 4

Thought analysis

In fact, the topic is also relatively simple:

• Maintaining a variableprofitTo store profits
• Because you can buy and sell many times, you want the price of the back to be higher than the price of the front, so you can buy and sell
• Therefore, as long asprices[i+1] > prices[i], then go to overlayprofit
• I’m done iteratingprofitThat’s the maximum profit you can make

Code implementation

/ * * * @param {number[]} prices
 * @return {number}
* /
var maxProfit = function(prices) {
 let profit = 0;  for (let i=0; i < prices.length - 1; i++) {  if (prices[i+1] > prices[i]) profit += prices[i+1] - prices[i]  }  return profit }; Copy the code

Different paths 🛣

❝

Dynamic programming is one of the most important algorithms in the world.

❞

Topic describes

A robot is located in the upper left corner of an M x N grid (the starting point is marked “Start” in the figure below).

The robot can only move one step to the right or down at a time. The robot attempts to reach the lower right corner of the grid (marked “Finish” in the image below).

How many different paths are there?For example, the image above shows a 7 x 3 grid. How many possible paths are there?

Example 1:

Enter: m =3, n = 2
Output:3
Explanation:Starting at the top left, there are total3Path to the bottom right corner.1.Right -> right -> down2.Right -> down -> right3.Down -> right -> rightCopy the code

Example 2:

Enter: m =7, n = 3
Output:28
Copy the code

Thought analysis

The robot can only move one step to the right or down, so the path from the top left to the bottom right is equal to the total number of paths from the right + the total number of paths from the bottom.

Therefore, the dynamic equation can be deduced as: DP [I][j] = DP [i-1][j]+ DP [I][J-1].

Code implementation

❝

This is initialized with Array(m).fill(Array(n).fill(1)), because each cell has at least one move.

❞

/ * * * @param {number} m
 * @param {number} n
 * @return {number}
* /
var uniquePaths = function(m, n) {  let dp = Array(m).fill(Array(n).fill(1))  for (let i = 1; i < m; i++) { for (let j = 1; j< n; j++) {  dp[i][j] = dp[i- 1][j] + dp[i][j- 1]  }  }  return dp[m- 1][n- 1]  }; Copy the code

Change for 💰

❝

Dynamic programming is one of the most important algorithms in the world.

❞

Topic describes

Give coins of different denominations and an amount. Write a function to calculate the minimum number of coins needed to make up the total. If no one coin combination makes up the total, return -1.

Example 1:

Enter: Coins = [1.2.5], amount = 11
Output:3
Explanation:11 = 5 + 5 + 1
Copy the code

Example 2:

Enter: Coins = [2], amount = 3
Output:- 1
Copy the code

Explanation: You can think of an infinite number of each coin.

Thought analysis

Let’s do the same thingDynamic programmingTo solve it.

Given coins of different denominations [1, 2, 5] and a target of 60, what is the minimum number of coins required?

We need to decompose the subproblem first, layer by layer to find the optimal substructure.

❝

Dp [I]: indicates the number of coins in the optimal solution when the total amount is I

❞

Let’s think about it: how many ways can we find the total amount of 60? There are 3 ways, because we have 3 different denominations of coins.

• Take a coin with a face value of 1 + the number of coins with the best solution of 59. Namely, dp[59] + 1
• Take a coin with a face value of 2 + the number of coins with the best solution of 58. Namely, dp[58] + 1
• Take a coin with a value of 5 + the number of coins with the best solution of 55. Namely, dp[55] + 1

Therefore, the optimal solution with a total amount of 60 is the optimal one among the above three solutions, that is, the one with the least number of coins. Let’s use the following code to express it:

dp[60] = Math.min(dp[59] + 1, dp[58] + 1, dp[55] + 1);
Copy the code

State transition equation is derived as follows:

dp[i] = Math.min(dp[i - coin] + 1, dp[i - coin] + 1,...).Copy the code

❝

We need to compare the number of possible coins, traverse the Coins array, and compare them separately

❞

Code implementation

/ * * * @param {number[]} coins
 * @param {number} amount
 * @return {number}
* /
var coinChange = function(coins, amount) {  let dp = new Array(amount+1).fill(Infinity)  dp[0] = 0;  for (let i=0; i<= amount; i++) { for (let coin of coins) {  if (i - coin >= 0) {  dp[i] = Math.min(dp[i], dp[i-coin]+1)  }  }  }  return dp[amount] === Infinity ? - 1 : dp[amount] }; Copy the code

welfare

In fact, most front-end students are quite at a loss in the systematic learning of algorithms. Here I have organized a mind map, which can be regarded as a comprehensive summary of the front-end algorithm system.

I also maintain onegithubWarehouse:https://github.com/Jack-cool/js_algorithmWhich contains a large number ofleetcodeProblem solving, and is constantly updated, feel good to give astarHa! Ha! 🤗

This article is formatted using MDNICE