This series has no flower head, is pure LeetCode problem breakdown analysis, not with a line or a small group of clever solution, but with clear code and simple enough ideas to help you clarify the meaning of the problem. Let you in the interview no longer afraid of algorithms written tests.

1. The sum of two numbers

The label

  • Array
  • Map
  • simple

The title

Leetcode portal

Let’s just open leetcode. Let’s just open leetcode.

Finds the sum of two numbers in a given array equal to the given value, and returns the index of the two numbers in the array.

Basic knowledge of

MDN: The Map object holds key-value pairs and can remember the original insertion order of the keys. Any value (object or raw value) can be used as a key or a value.

  • Map.prototype.get(key)

    • Returns the value corresponding to the key, or undefined if none exists.

  • Map.prototype.has(key)

    • Returns a Boolean value indicating whether the Map instance contains the value corresponding to the key.

  • Map.prototype.set(key, value)

    • Sets the value of the key in the Map object. Return the Map object.

The JavaScript standard has built-in object maps

The basic idea

  1. First establish a map structure, using the map can be very convenient to establish the value and coordinate mapping.
  2. Scan the array sequentially. For each element, if you look for the other half of the number in the map that can combine the given value, you can simply return the index of both. If you can’t find it, you store the number in the map, wait until you reach the other half, then pull it out and return the result.

Writing implement

/ * * *@param {number[]} nums
 * @param {number} target
 * @return {number[]}* /
var twoSum = function(nums, target) {
  // Create the map data structure
  const myMap = new Map(a)for (i = 0; i < nums.length; i++) {
    // (the other half of the number) = (and - the number)
    let reverse = target - nums[i]
    if (myMap.has(reverse)) {
      // Find the direct output of two indices
      return [myMap.get(reverse), i]
    }
    // If you don't find it, save it to the map
    myMap.set(nums[i], i)
  }
  return null
};
Copy the code

2. Add -two-numbers

The label

  • Array
  • Linklist
  • medium

The title

Leetcode portal

Let’s just open leetcode. Let’s just open leetcode.

2 reverse order of the list, required from the low start add, the result is also output in reverse order, return value is the head node of the reverse result of the list.

Basic knowledge of

  • Linked list data structure
  • Math knowledge carry, %10 take digit

The basic idea

  1. In order to avoid the two lists being empty directly, we also need to create a preHead node of the head node to point to the real head node.
  2. Since the preHead node itself cannot change, we use a pointer to point to the last node in the new list.
  3. Add the sequential bits of the list, just pay attention to the carry, and then take (and %10) for each of the bits, and add the highest bit if there is still carry1
  4. Finally return the front node preHead->next and ok

Writing implement

/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */
/ * * *@param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}* /
var addTwoNumbers = function(l1, l2) {
  // In order to avoid the 2 linked list, directly create a front node of the head node for empty
  let preHead = new ListNode(-1),
  // As the current pointer to the new list, it now points to the front node and then moves backwards
  cur = preHead,
  sum = 0./ / and
  carry = 0  / / carry
  // Add the two lists as long as one of them is not empty. If the two lists are empty, carry is 1, and the highest bit is 1
  while (l1 || l2 || carry) {
    // The sum is going to be the sum of the two places and add the bits
    sum = (l1 ? l1.val : 0) + (l2 ? l2.val : 0) + carry
    // Carry is greater than or equal to 10
    carry = sum >= 10 ? 1 : 0
    // The value of the next digit in the new list is this (and % 10). For example, this digit is (7 + 5) % 10
    cur.next = new ListNode(sum % 10)
    // The new list pointer is moved back, and the original 2 list pointer is also moved back, not empty of course
    cur = cur.next
    l1 && (l1 = l1.next)
    l2 && (l2 = l2.next)
  }
  // Finally return the header node. Note that it is not the front node
  return preHead.next
};
Copy the code

3. The longest-substring-without-repeating-characters longest-substring-without-repeating-characters

The label

  • Array
  • Map
  • Sliding window idea

The title

Leetcode portal

Let’s just open leetcode. Let’s just open leetcode.

Find the oldest string in a string with no duplicate letters.

Basic knowledge of

  • Map operation, look at the first problem above
  • Sliding window idea

Sliding window algorithm ideas

  1. We use the left and right pointer technique of double Pointers in the string S, initializing left = right = 0, and calling the index closed interval [left, right] a “window.”
  2. We expand the window [left, right] by increasing the right pointer until the string in the window meets the requirement (all characters in T).
  3. At this point, we stop incrementing the right and shrink the window [left, right] by incrementing the left pointer until the string in the window no longer fits (excluding all the characters in T). Also, each time we add left, we update the results for one round.
  4. Repeat steps 2 and 3 until right reaches the end of the string S.

In short, the second step is to find a viable solution, and the third step is to optimize the viable solution, and finally find the optimal solution. The left and right Pointers move in turn, the window size increases or decreases, and the window continues to slide to the right.

Take this example: the right edge of a sliding window continues to move right, as long as there are no repeated characters, continue to expand the window boundary to the right. Once a duplicate character is present, you need to narrow the left margin until the duplicate character moves out of the left margin, and then continue to move the right margin of the sliding window. In the same way, each move needs to calculate the current length and determine whether the maximum length needs to be updated. The final maximum value is what the problem asks.

The basic idea

  1. Maintain a sliding window with double Pointers for clipping substrings.
  2. Keep moving the right pointer until a repeat character is encountered and move the left pointer to the next bit of the repeat character.
  3. When the pointer is moved, the maximum length of the record window is the answer.

Writing implement

/ * * *@param {string} s
 * @return {number}* /
var lengthOfLongestSubstring = function(s) {
  let len = s.length,
  maxNow = 0.// Temporary maximum
  left = 0.// Define the left pointer coordinates
  map = new Map(a);// Use map as a sliding window to store characters and corresponding subscripts
  // The right pointer moves backwards
  for (let right = 0; right < len; right++) {
    // If a duplicate character occurs, move the left pointer to the next bit of the duplicate character.
    // Note that the index that satisfies both repeated characters is greater than the left pointer, indicating a repeat in the window
    if (map.has(s[right]) && map.get(s[right]) >= left) {
      // Slide the left window to the right until there is no repetition
      left = map.get(s[right]) + 1
    }
    // In this case, the length is the difference between the left and right coordinates + 1
    maxNow = Math.max(maxNow, right - left + 1);
    // Store the subscript of each character
    map.set(s[right], right)
  }
  return maxNow
};
Copy the code

That’s all for today. If you want to brush the questions with me, you can add my wechat to search my wechat id, infinity_9368. You can chat and add my password “Tianwang Gai Tigeri” in English. Please send me the verification message presious Tower shock the Reiver Monster. I will pass it if I see it