This series is nothing fancy, just pure Leetcode problem breakdown analysis, not to use a sexy line or a niche solution, but with clear code and simple enough thinking to help you clarify the problem. Let you in the interview no longer afraid of algorithm written test.

46. Square root of x (SQRTX)

The label

  • mathematics
  • simple

The title

Leetcode portal

Let’s just open leetCode.

Implement the int SQRT (int x) function.

Calculates and returns the square root of x, where x is a non-negative integer.

Since the return type is an integer, only the integer part of the result is retained, and the fractional part is omitted.

Input: 8 Output: 2 Description: The square root of 8 is 2.82842... Because the return type is an integer, the decimal part will be omitted.Copy the code

The relevant knowledge

Binary processing, binary search is the core idea, can see this binary search

First of all, let’s make sure that the problem is finding roots, and it’s monotonic, and dichotomy works.

Basic steps

  1. Special sentence
  2. Declare the left and right boundary Pointers, and create a midpoint
  3. Look at the situation
    1. Return mid if the square of mid is exactly equal to x
    2. If the square root of mid is less than x, it means that the square root falls between mid and right, left = mid + 1
    3. If the square root of mid is greater than x, it means that the square root falls between left and mid, and right = mid-1

Writing implement

/ * * *@param {number} x
 * @return {number}* /
var mySqrt = function(x) {
  / / sentence
  if (x === 0) {
    return 0
  }
  // dichotomy, first declare the left and right boundaries
  let [left, right, res] = [1, x, 0]
  while (left <= right) {
    let mid = left + Math.floor((right - left) / 2)
    if ( x === mid * mid) {
      return mid
    } else if (mid * mid < x) {
      left = mid + 1
      res = mid
    } else {
      right = mid - 1}}return res
};

console.log(mySqrt(10))
Copy the code

In addition, this problem can also be solved by some mathematical methods, interested in understanding: Newton iteration

Here is no need to repeat the direct code:

var mySqrt = function(x) {
  let res = x
  while(res * res > x) {
    res = Math.floor((res + Math.floor((x / res))) / 2)}return res
};
Copy the code

47. Climbing stairs

The label

  • Dynamic programming
  • mathematics
  • simple

The title

Leetcode portal

Let’s just open leetCode.

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.

The relevant knowledge

Classic stair climbing problem (simple DP)

A staircase can be made byn-1 和 n-2Up the stairs.

If you don’t know anything about dynamic programming, move to dynamic programming

Basic steps

We repeat the steps again to deepen the impression

  1. Search for optimal substructure (state representation)
  2. Induction of state transition Equation (State calculation)
  3. Boundary initialization

  • State representation: DP [I] represents the number of options to climb to step I

  • Dp [I] = dp[I – 1] + DP [I – 2]

  • Boundary conditions: We started at level 0, so from level 0 to level 0 we can consider that there is only one solution, namely f(0) = 1; There is only one way to go from level 0 to level 1, which is to climb one level, f(1) = 1. We can just go down and see, to our surprise, if this isn’t the Fibonacci sequence.

Writing implement

var climbStairs = function(n) {
  let 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]
};
console.log(climbStairs(3))
Copy the code

In addition, I would like to recommend the article of the eldest brother to you. It is very simple and profound. It is very effective for the students who advance in the front end. Core concepts and algorithm disassembly series

That’s all for today. If you want to work with me, you can add me to my wechat account infinity_9368, and you can chat with me and add my secret code “Tianwang Gedi Hu”. Verify the message please send me presious tower shock the rever monster, I see it through, the code is not on the ha, add after I will do my best to help you, but pay attention to the way of asking questions, suggest reading this article first: the wisdom of asking questions

reference