Laws of practice questions

  1. Read and think for 5-10 minutes
    • Don’t tangle without thinking directly to see the solution;
    • Don’t feel like a failure, how we can’t come out;
    • Basically, these algorithms are impossible for us to figure out on our own;
    • In the case of the ricochet, if we could figure it out from 0-1, we would win the Turing prize;
    • So remember! No train of thought directly see the problem solution, no train of thought directly see the problem solution, no train of thought directly see the problem solution!
    • We just need to know and use it!
  2. There are ideas
    • Start to write code, no, immediately see the solution!
  3. Memorize the topic, skilled
    • So when we’re done with this problem, we need to remember that there are N ways to solve this problem;
    • Repeat and repeat the silent, ** * until they have a profound impact;
  4. Finally start to write (close book)
    • At this point, if we need to look at other people’s code, we have to go back and memorize it;
    • To get to this stage, you’re already familiar with the basic questions, and the next step is practice;

Where to practice?

That must be a force buckle! If you don’t have an account, set up an account and start practicing day after day! ~

Problem 283. – Move zero

283. Move zero | Difficulty: Easy

The title on

Given an array nums, write a function to move all zeros to the end of the array while preserving the relative order of the non-zero elements.

Example:

Input: [0,1,0,3,12] output: [1,3,12,0,0]Copy the code

Description:

  1. Must operate on the original array, cannot copy additional arrays.
  2. Minimize the number of operations.

Key points to note here:

  1. all0Move to the end of the array;
  2. Maintain the relative order of non-zero elements;
  3. Must operate on the original array, cannot copy additional arrays;

Their thinking

When thinking about a problem, use the MECE principle – each thought is relatively independent and then comes to complete exhaustion. First, regardless of the conditions, come up with all possible solutions to the problem, and then evaluate which is the best solution. The same goes for an interview. List all the ideas you can think of, then list your strengths and weaknesses, and come up with your best answer.

  1. Count the zeros
    • Loop through the array to find the position of 0, 0 is the number of 0 plus one;
    • When not 0 is encountered, the value of the non-0 element can be exchanged with the 0 element;
  2. A new array
    • Give a pointeriIncrementing from the head of the array;
    • Give a pointerjDecrement from the end of the array (the total length of the original array);
    • You go to zerojThe position of the pointer is put, and thenj--;
    • If it’s not zero, it goesiThe position of the pointer is put, and theni++;
    • ** Disadvantages: ** High memory usage;
    • ** does not meet the condition: ** must operate on the original array, so it can be implemented but does not meet the condition;
  3. Double pointer switching
    • Give two Pointersiandj, and all start at 0 by default;
    • iPoints to the current position;
    • jThe pointer will keep moving until it finds a non-zero element, and theniValue exchange of position;
    • ifjThe position andiIf not, you can give itjChange the value of 0;
  4. Zero is cleared after the double pointer is replaced
    • This is the same as the third method, which is also a two-pointer;
    • The only difference is noi[Fixed] Replace zero when pointer scanning
    • Instead, after all the non-zero elements are replaced, all the remaining digits are changed to 0;

The problem solving code

“Method 1” – Count the number of zeros:

  • Time complexity:-n elements are traversed N times
  • Space complexity:– Replaces only the original array
/** * @param {number[]} nums * @return {void} Do not return anything, modify nums in-place instead. */
var moveZeroes = function(nums) {
  let zeroCount = 0;
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] == 0) {
      zeroCount += 1;
    } else if (zeroCount > 0) {
      nums[i - zeroCount] = nums[i];
      nums[i] = 0; }}};Copy the code

“Method 2” – Dual pointer switching:

  • Time complexity:-n elements are traversed N times
  • Space complexity:– Replaces only the original array
/** * @param {number[]} nums * @return {void} Do not return anything, modify nums in-place instead. */
var moveZeroes = function(nums) {
  let j = 0;
  for (let i = 0; i < nums.length; i++) {
    if(nums[i] ! = =0) {
      nums[j] = nums[i];
      if(j ! == i) { nums[i] =0; } j++; }}};Copy the code

“Method 3” – Clear after double pointer replacement:

  • Time complexity:Minus N elements, N times, plus the final zero is goneN minus the number of non-zero, that is,O(n+n-i)Generally speakingO(n)
  • Space complexity:– Replaces only the original array
/** * @param {number[]} nums * @return {void} Do not return anything, modify nums in-place instead. */
var moveZeroes = function(nums) {
    var j = 0;
    for (let i = 0; i < nums.length; i++) {
        if(nums[i] ! =0) { nums[j] = nums[i]; j++; }}for (let k = j; k < nums.length; k++) {
        nums[k] = 0; }};Copy the code

Boundary test cases

,1,0,3,12 [0] [1, 2] [0, 0]

Comparison and analysis of problem solving

Note: The following data are returned after submission in the buckles. Each submission may be inconsistent. Therefore, it is normal for the output results of similar schemes to be different, and the final optimal scheme should be determined by code analysis, rather than relying only on the output data of likou, which can only be used as our reference.

methods The execution time Memory consumption
“Method one” – Count the number of zeros 96 ms (win 17.82%) 37.1 MB
“Method two” – dual pointer swap 72 ms (beat 87.23%) 37.2 MB
“Method 3” – Clear zero after double pointer replacement 76 ms (beat 73.98%) 37.2 MB

Analyze:

  • The first method is to locate the position where 0 needs to be replaced by counting the number of occurrences of 0, which involves onei - zeroCountSo it takes longer to run than other methods;
  • The second method is to run two Pointers together, one is fixed at the 0 element, the other is to go all the way to find the non-0 element, and finally do a swap. This method does not involve operation, but also a cycle can be completed, relatively speaking, is the optimal solution.
  • The third method also uses double Pointers. The only difference with the second method is that all zeros are replaced first, and then all remaining elements are replaced with zeros at once. In terms of readability, individuals find it easier to understand, but time and space complexity is consistent with the second method.

Question 11 – The container that holds the most water

283. Container with the most water | Difficulty: Medium

The title on

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

Key words:

  1. First of all, our goal is to select two pillars so that the maximum area can be obtained before the two pillars (the larger the area, the more water nature can hold);
  2. Choosing the longest two columns is not the same as having the largest area, because the distance between them is also a dimension that determines space;
  3. So the focus is to find a pair of columns with the largest ratio of height to width, so as to get the largest area;
  4. Note that in calculating the area, we can only use the shortest of a pair of columns as the height, because water can only fill up to the height of the shortest column;
  5. Area calculation formula:Height x width is equal to area

Their thinking

  1. Enumeration — violent solution

    • I go to the left and the right to find all the areas;
    • List all column combinations;
    • Figure out the area of each of the combinations;
    • Finally output the maximum area of the set;
    • ** Disadvantages: ** traversals are too many, so the time complexity is relatively high
    • The complexity of the: Time complexity, spatial complexity

  2. Double pointer

    • Left and right are moving to the middle;

    • Double Pointers can be considered if you need to move left and right;

    • In the same case, the farther the distance is, the better;

    • The area is limited by the height of the shorter edge;

    • So let’s move the shorter pointer inward;

    • A regular move above until the two Pointers overlap;

The problem solving code

“Method one” – Enumeration (violent solution) :

  • Time complexity:– double cycle, so the total cycle is N^2.
  • Space complexity:
/** * @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

“Method 2” – Dual pointer:

  • Time complexity:– The double pointer traverses the entire array at most once.
  • Space complexity:– Only extra constant level space is required.
/** * @param {number[]} height * @return {number} */
var maxArea = function(height) {
    let max = 0

    for (let i = 0, j = height.length - 1; i < j; ) {
        let minHeight = height[i] < height[j] ? height[i ++] : height[j --]
        let area = (j - i + 1) * minHeight
        max = Math.max(max, area)
    }

    return max
};
Copy the code

Comparison and analysis of problem solving

methods Execution time (ms) Memory consumption
Enumeration (violent solution) 984 MS (win 9.99%) 35.9 MB
Double pointer 56 ms (beat 99.88%) 36 MB

Look at the

  • By using the second method, we go fromThe time complexity of the, the total execution time is approximatelyFast 17 times.

Problem 70. – Climb the stairs

283. Move zero | Difficulty: Easy

The title on

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 of the building.

  1. 1 order plus 1 order
  2. 2 order

Example 2:

Input: 3 Output: 3 Explanation: There are three ways to climb to the top of the building.

  1. 1 order plus 1 order plus 1 order
  2. 1 order plus 2 order
  3. 2 order plus 1 order

Answer key point

In fact, the topic itself is not difficult. In LeetCode, the topic belongs to the “simple” level. However, if you have no idea or do not know the topic at all, it is normal to have no clue. If we don’t know, we don’t know what to do. If we knew, it would be quite easy.

Here’s the idea:

First of all, what’s the biggest mistake we make when we solve the problem?

  • I only did it once
  • Do it at least five times

And then what is the idea of optimization?

  • Space for time
  • Ascending dimensional thinking (upgrade to two dimensions)

What do I do when I’m confused?

  • Can we do it by force first?
  • What should we do about the basic case? Can you simplify things?

The rule for solving all problems:

  • Look for recently repeated subproblems
  • Why is that? Because writing programs we can only writeif.else.for.while.recursion(recursive)
  • The computer is invented by human beings, the computer is certainly not so strong as the human brain, it is actually a simple repeating machine
  • The same is true of computer programs, which solve problems with repetition
  • If we encounter algorithm problems, is that we need to use procedures to solve the problem, the problem itself is repeatable
  • No matter in the algorithm of recalculation, divide and conquer, dynamic programming, recursion, all are looking for repeatability principle
  • So it’s all about finding patterns.

In-depth analysis topics:

First of all, we use the simplification of thinking to analyze:

To get to the first step, we can only climb one step, so there’s only one possible way, so when n = 1, there’s only one possible way.

So if we want to get to the second step, we either have to climb two steps in a row, or we have to climb two steps at once to get to the second step. So there are 2 possibilities.

What if you need to get to the third step?

Here’s a trick, to get to the third step we can think in a different way, if we still list all the possibilities to get to the third step in the same way as the first step and the second step, then if n is large, we just rely on the brain, it’s really hard. But there’s a neat way of thinking about it.


In retrospect, we thought of only two possibilities for reaching the third step:

  1. Or climb one step from the second step
  2. Or climb two steps from the first step


Would it be the same if it was the fourth step?

  1. Or climb one step from the third step
  2. Or climb two steps from the second step


There is a ‘rule’ here. To get to step N we need to know:

  1. To reach the firstn-1How many possible steps
  2. To reach the firstn-2How many possible steps
  3. And then you add these two together and you get to number onenHow many possible steps

So here’s the old Fibola sequence:

Their thinking

  1. Fibonacci– “Silly recursion”
    • Just use the Fibola formula in a recursive loop
    • But the time complexity is very high
  2. Dynamic programming
    • Using the principle described above, we reach nonOne step only: climb itStep way number + climb upNumber of steps = climb to number 1The number of steps
    • So the formula is going to be
    • Also need to initialize: 和
    • In this way the time complexity is reduced
  3. Dynamic programming 2 – only the last 3 methods are recorded
    • The method is the same as the dynamic programming method above, but here we only record the number of climbing methods for the last three steps
    • usef1.f2.f3As a stored variable
    • The default 和 Can be
  4. General term formula (Binet’s Formular)
    • Those of you who are mathematically observant, or those of you who are mathematically adept, will see that this is the Fibo sequence, and we can also use the Fibo formula.
    • The formula is:
    • Time complexity:

The problem solving code

“Method one” Fibo time

  • Time complexity:
  • Space complexity:
/** * @param {number} n * @return {number} */
var climbStairs = function(n) {
    if (n <= 2) return n
    return climbStairs(n- 1) + climbStairs(n2 -)};Copy the code

“Method two” dynamic programming

  • Time complexity:
  • Space complexity:
/** * @param {number} n * @return {number} */
var climbStairs = function(n) {
    const dp = [];
    dp[0] = 1;
    dp[1] = 1;
    for(let i = 2;  i <= n;  i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
};
Copy the code

“Method 3” dynamic programming 2

  • Time complexity:
  • Space complexity:
/** * @param {number} n * @return {number} */
var climbStairs = function (n) {
    if (n <= 2) {
        return n
    }
    let f1 = 1, f2 = 2, f3
    for (let i = 3; i <= n; i++) {
        f3 = f1 + f2
        f1 = f2
        f2 = f3
    }
    return f3
};
Copy the code

“Method four” general term formula

  • Time complexity:
  • Space complexity:
/** * @param {number} n * @return {number} */
var climbStairs = function(n) {
    const sqrt_5 = Math.sqrt(5);
    const fib_n = Math.pow((1 + sqrt_5) / 2, n + 1) - Math.pow((1 - sqrt_5) / 2,n + 1);
    return Math.round(fib_n / sqrt_5);
};
Copy the code

Comparison and analysis of problem solving

methods Execution time (ms) Memory consumption
“Method one” Fibo time Out of time limit N/A
“Method two” dynamic programming 68 ms 32.4 MB
“Method 3” dynamic programming 2 53 ms 32.3 MB
“Method three” general term formula 67 ms 32.4 MB

Look at the

  • In terms of time complexity, the “general term formula” should be the best performance, but the execution time of the force link is not very reliable, as I mentioned above, without further explanation.
  • So the optimal solution is still the third method, the general term formula.
  • This is followed by “dynamic programming 2”, which uses arrays because only three variables are stored. It has an advantage in space complexity.
  • And the last time I lost the fibo recursion, this method was eliminated before I could complete it. The time complexity is too high. Procedure

A series of reading

  1. “How to learn Data Structures and Algorithms efficiently” — Nowadays, if you want to become a senior development engineer or enter a big factory, whether it is front end, back end or AI, algorithms are the most important. It doesn’t matter whether the position we need to enter the company ends up as an algorithm engineer. So when you don’t learn algorithms, grow up hair.
  2. Analyzing Temporal and Spatial Complexity – the core of algorithms, data Structures and Algorithms is all about this core. Its existence is also to solve our performance problems in the process of programming, but also let us have more advanced thinking and ideas, write better programs.
  3. The most common types of data structures are array, linked list and hop list. In this installment, we’ll take a look at how they work and implement them.