【 algorithm Interview 】 Leetcode’s most common 150 front end questions — Simple questions (44)

preface

The questions in this article are from LeetCode’s selection of TOP interview questions, which you and your colleagues have personally encountered in over 80% of the time (for front-end positions in Chengdu and Beijing). This paper selects all the simple questions to do classification and reconciliation analysis. All intermediate analysis will be updated later.

In order to help you quickly brush the question, by summarizing the data structure + question type, such as hash table has the function of counting, if the question contains words at most XX times, at least XX times, only and so on words, can be associated with hash table to solve. Brush 3 or 4 similar questions, will develop a conditioned reflex.

Example: there are repeated elements.

The title description is as follows:

Given an array of integers, determine whether there are duplicate elements.

The function returns true if there is a value that appears in the array at least twice. Return false if each element in the array is different.

The sample1: Input: [1.2.3.1] output:trueThe sample2: Input: [1.2.3.4] output:false
Copy the code

If there is a value that occurs at least twice in the array, the problem is solved by counting the number of occurrences of each number.

Solution:

As we iterate through the array, we add to the map after each item in the array, such as [1,2,3,1]

• Item 1: When the first 1 is traversed, the object returns{1, 1}, represents 1 occurs once
• Item 2: when traversal reaches 2, return{1: 1, 2: 1}
• Item 3: when traversal reaches 3, return{1: 1, 2: 1, 3: 1}
• Item 4: When iterating through the second 1, it is found that there is already 1 in the original object, returnfalse

So, naturally, the code comes out as follows:

const containsDuplicate = function(nums) {
    let map = new Map(a);for(let i of nums){
        if(map.has(i)){
            return true;
        }else{
            map.set(i, 1); }}return false;
};
Copy the code

Hash table + count type

In addition to the above question, among the most popular simple questions there are a number of questions that we can solve one by one, this is a type of question

387. The first unique character in a string

A look at the topic, unique, conditioned reflex, count ah, map go! Let’s take a look at the title first:

Given a string, find its first non-repeating character and return its index. If none exists, -1 is returned.

Example: s ="leetcode"return0

s = "loveleetcode"return2
 
// Hint: You can assume that the string contains only lowercase letters
Copy the code

Ideas:

• Traversal string
• With an object{}Let’s count it. It happens once+ 1.
• • So when we’re done, we iterate over the string again to see if their value in the previous recorded object is 1, and if it is, we return the index, not -1.

Reference answer:

var firstUniqChar = function(s) {
  const map = {};
  for(let v of s) map[v] = (map[v] || 0) + 1;
  for(let i = 0; i < s.length; i++) if(map[s[i]] === 1) return i;
  return -1;
};
Copy the code

242. Valid letter heterotopic words

Let’s take a look at the title first:

Given two strings s and t, write a function to determine whether t is an alphabetic allotopic of S.

Note: if each character in S and T occurs the same number of times, s and T are said to be alphabetic allographs.

The sample1: Enter: s ="anagram", t = "nagaram"Output:trueThe sample2: Enter: s ="rat", t = "car"Output:false
Copy the code

Map = map = map = map

• Declare a counter, an objectconst obj = {}
• Traversal s string, if traversal to string of'a'Letters, go and seeobj[a]If there is a
• No presence indicates the first traversal'a'Letter, then initializeobj[a] = 1
• If it existsobj[a] += 1
• T string the same way it does every timeMinus 1
• After iterating through the S string, iterate over the obj object, looking at each pair of itKey: valueWhether or not,valueAre all0

var isAnagram = function(s, t) {

  const sLen = s.length;
  const tLen = t.length;
  if(sLen ! == tLen ) {return false;
  }
  const obj = {};
  for(let i = 0 ; i < sLen ; i++){
      const currentS = s[i];
      const currentT = t[i];
      obj[currentS] ? obj[currentS]++ : obj[currentS] = 1;
      obj[currentT] ? obj[currentT]-- : obj[currentT] = -1;
  }
  return Object.values(obj).every(v= >v===0);
};
Copy the code

169. Majority elements

Let’s look at the question first (the question has the word “times”, it is also a number of questions, map continue to walk) :

Given an array of size N, find most of the elements. Most elements are those that occur more than ⌊ n/2 ⌋ in the array.

You can assume that the array is non-empty and that a given array always has most elements.

Example 1: Input: [3,2,3] Output: 3 Example 2: Input: [2,2,1,1, 2,2] Output: 2Copy the code

Ideas:

• Declare a counter, that is, an objectconst map = {}
• Iterate over the string, start counting, and if the first time I see a letter of the string,Map = 1
• If the map has already recorded the letterMap [recorded letters] += 1
• And in the process of traversing, lookMap [recorded letters]If more thanTotal length of array divided by 2

Answer:

var majorityElement = function(nums) {
  const map = {}
  const n = nums.length >> 1 // >> is the right shift operator, which means divide by 2
  for(let i = 0; i < nums.length; i++){ map[nums[i]] = map[nums[i]] ! = =undefined ? map[nums[i]] + 1 : 1
      if(map[nums[i]] > n) return nums[i]
  }
}
Copy the code

A number that appears only once

If the map appears once, the map will start to move. If the map appears once, the map will start to move.

Given an array of non-empty integers, each element appears twice except for one element. Find the element that appears only once.

Description:

Your algorithm should have linear time complexity. Can you do it without using extra space?

The sample1: Input: [2.2.1] output:1The sample2: Input: [4.1.2.1.2] output:4
Copy the code

So let’s record it with map, something like this,

const countMap = {}; ForEach ((item)=> {countMap[item]? CountMap [item] += 1: countMap[item] = 1}Copy the code

But there’s another way to solve this problem, using the xor operator. First let’s see what xor does:

The xOR operator (^), let’s see what this operator does

• Any number does xor with itself, and the result is zero0, i.e.,A radius of a = 0.
• Any number and 0If I do xOR, I get the same resultA radius 0 = a.
• In xOR operations, it satisfies both the commutative and associative laws, namelyA radius b the radius of a = b radius radius radius a = b = b (a radius a) radius 0 = b.

So the xOR of a letter that occurs twice gets 0, and the xor of a letter that occurs once gets itself

Answer:

var singleNumber = function(nums) {
  let init = nums[0];
  for(let i = 1; i < nums.length; i++){
      init ^=  nums[i];
  }
  return init;
};
Copy the code

The number of ones

Write a function that takes an unsigned integer as an input (in the form of a binary string) and returns the number of digits ‘1’ in its binary expression (also known as hamming weight).

The sample1Input:00000000000000000000000000001011Output:3Explanation: Input binary string00000000000000000000000000001011Among them, three are'1'. The sample2Input:00000000000000000000000010000000Output:1Explanation: Input binary string00000000000000000000000010000000In which there is one'1'.Copy the code

Ideas:

Count the number and convert the whole number to a string as we did before, like this:

digital0001= >String(0001) = >'0001'= > traversal1The number ofCopy the code

And then you just go through it, that’s why I put it in the numeration category, but you can also put it in the math category, and we’ll do it mathematically, and we’ll look at the answer, and then we’ll parse it.

var hammingWeight = function(n) {
    let ret = 0;
    while(n){
        n &= (n - 1);
        ret++;
    }
    return ret;
};
Copy the code

Principle:

Each execution of x = x & (x-1) will change the rightmost 1 in binary representation of x to 0, because x-1 will change that bit (the rightmost 1 in binary representation of x) to 0. So, repeat this operation on x until x becomes 0, and the number of operations is the number of ones in the binary number of x.

Next, we looked at other types of hash tables (not so many of the same types)

Hash table + mapping function

A very common feature of hash tables is to create mappings, such as policy schema in design mode. Mapping tables are often found in enumerations on the back end, as in typescript

// the backend only returns 0,1,2
const TYPE = {
    2: 'orange'.1: 'red'.0: 'blue'
}

// Then the front end is used like thisTYPE[Number returned by the back end0or1or2]
Copy the code

The corresponding questions are:

• 1. Sum of two numbers
• 349. Intersection of two arrays

The sum of two Numbers

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

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

You can return the answers in any order.

The sample1: Input: nums = [2.7.11.15], target = 9Output:0.1Because nums[0] + nums[1] = =9To return to the [0.1]. The sample2: Input: nums = [3.2.4], target = 6Output:1.2] example3: Input: nums = [3.3], target = 6Output:0.1]
Copy the code

A hashMap is used to store the iterated elements and their corresponding indexes. Each element is iterated over to see if there is a target number in the hashMap that meets the requirements. Everything is done in one traverse (space for time)

var twoSum = function(nums, target) {
    const map = new Map(a);for(let i = 0, len = nums.length; i < len; i++){
        if(map.get(nums[i]) ! = =undefined) {return [map.get(nums[i]), i];
        } else{ map.set(target - nums[i], i); }}return [];
};
Copy the code

Intersection of two arrays

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

The sample1: Input: nums1 = [1.2.2.1], nums2 = [2.2] output: [2] example2: Input: nums1 = [4.9.5], nums2 = [9.4.9.8.4] output: [9.4] Description: Each element in the output must be unique. We can ignore the order of the output.Copy the code

This problem can be set. It’s very simple, but the space and time complexity is too high to be elegant

var intersection = function (nums1, nums2) {
    return result =[...new Set(nums1)].filter(item= >new Set(nums2).has(item))
};
Copy the code

We can do this with map, which has much lower time and space complexity.

• Use a map to store each item in nums1, similarlymap[nums1[i]] = true
• Then go through NUMs2, if you already have a value in the map, similarmap[nums2[i]], just push it into an array
• And set map[nums2[I]] to false

var intersection = function(nums1, nums2) {
    const map = {};
    const ret = [];
    for(let i = 0; i < nums1.length; i++){
        map[nums1[i]] = true;
    }
    for(let i = 0; i < nums2.length; i++){
        if(map[nums2[i]]){
            ret.push(nums2[i])
            map[nums2[i]] = false}}return ret;
};
Copy the code

Seek regular

This kind of problem can be solved by drawing a picture or a little analysis

13. Convert Roman numerals to whole numbers

The map of Roman numerals to our Arabic numerals is as follows:

        I: 1.V: 5.IV: 4.IX: 9.X: 10.XL: 40.XC: 90.L: 50.C: 100.CD: 400.CM: 900.D: 500.M: 1000.Copy the code

The problem is given a Roman numeral, convert it to an integer. Make sure the input is in the range of 1 to 3999.

The sample1Input:"III"Output:3The sample2Input:"IV"Output:4The sample3Input:"IX"Output:9The sample4Input:"LVIII"Output:58Explanation: L =50, V= 5, III = 3.
Copy the code

And the idea is that the pattern that we found in these cases, is that we just add up the numbers in the map, for example

“LVIII” = ‘L’ (map 50) + ‘V’ (Map 5) + ‘I’ (Map 1) + ‘I’ (MAP 1) + ‘I’ (Map 1)

So the solution is simple, just iterate over the numbers and add up the corresponding values as follows:

var romanToInt = function(s) {
    const map = {
        I: 1.V: 5.IV: 4.IX: 9.X: 10.XL: 40.XC: 90.L: 50.C: 100.CD: 400.CM: 900.D: 500.M: 1000,}let res = 0;
    let index = 0;
    let len = s.length;
    while(index < len){
        if(index + 1 < len && map[s.slice(index, index+2)]){
            res += map[s.slice(index, index+2)];
            index += 2;
        }else{
            res += map[s.slice(index, index+1)];
            index += 1; }}return res;
};
Copy the code

14. Longest public prefix

The title is as follows:

Write a function to find the longest public prefix in an array of strings.

Returns the empty string “” if no public prefix exists.

The sample1: Input: STRS = ["flower"."flow"."flight"] output:"fl"The sample2: Input: STRS = ["dog"."racecar"."car"] output:""Explanation: The input does not have a common prefix. Tip:0 <= strs.length <= 200
0 <= strs[i].length <= 200STRS [I] consists of lowercase letters onlyCopy the code

Suppose you find the longest common prefix for three elements in an array

• You compare the first two and find the longest common prefix for both of them
• And then I’m going to use that to find the longest common prefix for the third element
• N elements just keep doing thatreduceGo down

// This is the method to find the longest common prefix for two elements
var longestCommonPrefix = function (strs) {
  if (strs.length === 0) return ' '
  if (strs.length === 1) return strs[0];
  return strs.reduce(getSameStr, strs[0]);
};

function getSameStr(a, b) {
  let res = ' '
  for (let j = 0; j < a.length; j++) {
    if (a[j] === b[j]) {
      res += a[j];
    } else {
      returnres; }}return res
}
Copy the code

21. Merge two ordered lists

In short, this topic is to look at the picture to find the law, is merged into an ascending linked list, the specific topic is as follows:

Let’s take a look at the title first:

Merges two ascending lists into a new ascending list and returns. A new list is formed by concatenating all the nodes of a given two lists.

The sample1: Input: l1 = [1.2.4], l2 = [1.3.4] output: [1.1.2.3.4.4] example2: Input: L1 = [], L2 = [] Output: [] Example3: input: l1 = [], l2 = [0] output: [0The number of nodes in two linked lists ranges from [0.50]
-100 <= Node.val <= 100Both L1 and L2 are arranged in non-decreasing orderCopy the code

Ideas:

Let’s go through them one by one, splicing them together in order, and then go through the next loop to see the code clearer:

// Lists define functions
function ListNode(val, next) {
    this.val = (val===undefined ? 0 : val)
    this.next = (next===undefined ? null : next)
}

var mergeTwoLists = function(l1, l2) {
  const dummpy = node = new ListNode();
  while(l1 && l2){
      if(l1.val >= l2.val){
          node.next = l2;
          node = node.next;
          l2 = l2.next;
      } else {
          node.next = l1;
          node = node.next;
          l1 = l1.next;
      }
  }
  node.next = l1 || l2;
  return dummpy.next;
};
Copy the code

28. Implement STR ()

The title is as follows:

Implement the strStr() function.

Given two strings haystack and needle, find the first place in the haystack string where needle appears (the subscript starts at 0). If none exists, -1 is returned.

The sample1: Enter: haystack ="hello", needle = "ll"Output:2The sample2: Enter: haystack ="aaaaa", needle = "bba"Output: -1The sample3: Enter: haystack ="", needle = ""Output:0Tip:0 <= haystack.length, needle.length <= 5 * 104Haystack and needle are only lowercase charactersCopy the code

Ideas:

Originally, the best algorithm for this problem is KMP, which is difficult for me to understand, so I changed to another way of thinking

• Traverse the string to see if it matches the first letter of the desired string
• If they are the same, cut the string and compare it with the string of the same length
• If they are the same, return the subscript, if they are different, continue to traverse the string

var strStr = function (haystack, needle) {
  if (needle === "") return 0
  for (var i = 0; i < haystack.length; i++) {
      if (haystack[i] === needle[0]) {
          if (haystack.substring(i, i + needle.length) === needle) returni; }}return -1
};
Copy the code

118. Yang Hui Triangle

This is an example of how to find patterns, and how to train your ability to convert two-dimensional arrays into code:

Given a non-negative integer numRows, generate the former numRows of the Yanghui triangle.

In Yang Hui’s triangle, each number is the sum of the numbers on its upper left and upper right.

Example:

Input:5Output: [[1],
    [1.1],
   [1.2.1],
  [1.3.3.1],
 [1.4.6.4.1]]Copy the code

Ideas:

• As you can see in the figure above, the Yang Hui triangle is formednumRowsRow, array hasnumRowsline
• Each row, its first position and its last position in the array are1
• For each row, the values of all positions except the first and lastIs equal to the sum of the two values in the previous row

Translate the idea into code:

var generate = function(numRows) {
  if(numRows === 0) {return[]}const result = Array.from(new Array(numRows), () = >[])
  for(let i = 0; i < numRows; i++){
    result[i][0] = 1; result[i][i] = 1;
      for(let j = 1; j < i; j++){
      result[i][j] = result[i-1][j-1] + result[i-1][j] 
    }
  }
return result
};
Copy the code

121. The best time to buy and sell stocks

The next problem, you simply look at the topic on the line, the solution principle is super simple, look at the picture to talk, find the rule!

Let’s start with the question:

Given an array prices, its ith element prices[I] represents the price of a given stock on day I.

You can only buy the stock on one day and sell it on a different day in the future. Design an algorithm to calculate the maximum profit you can make.

Return the maximum profit you can make from the transaction. If you can’t make any profit, return 0.

The sample1: Input: [7.1.5.3.6.4] output:5Explanation: In no2Day (stock price =1) time to buy, at No5Day (stock price =6), maximum profit =6-1 = 5. Notice the profit can't be7-1 = 6Because the selling price needs to be higher than the buying price; Also, you can't sell stocks before you buy them. The sample2: Input: prices = [7.6.4.3.1] output:0Explanation: In this case, no transaction is completed, so the maximum profit is0. Tip:1 <= prices.length <= 105
0 <= prices[i] <= 104
Copy the code

[7, 1, 5, 3, 6, 4]

• The first day is 7, so let’s record that, because we haven’t gotten to the second day and we don’t know if this price is high or low,The flag minimum is 7
• The second day is one,Smaller than 7, so as long as the current number of days is less than the previous value, it means not to sell, because it is the minimum value,The flag minimum is 7
• Day 3 is 5,5 is bigger than the day before, which means it’s bigger than the minimum, so you can sell it, and the profit is going to be5-1 = 4
• And then on the fourth day, it’s 3, it’s less than 5, it’s the same thing, it’s less than before, it’s going to be the minimum, it’s going to be the minimum, it’s going to do nothing,The flag minimum is 3
• On the fifth day, it was 6… On the sixth day, it was 4, and the rule was the same

It means that as long as today is lower than yesterday, you can take today’s minus the minimum, which is the profit, and compare each time to see if that profit is the largest

If you combine it with the code, it’ll make sense

var maxProfit = function(prices) {
  let res = 0;
  let min = prices[0];
  for(let i = 1; i < prices.length; i++){
      if(prices[i] < min){
          min = prices[i]
      } else {
          res = Math.max(res, prices[i] - min)
      }   
  }
  return res;
};
Copy the code

122. The best time to buy and sell stocks 2

Come again a picture talk topic, simple! Start!

Let’s start with the title:

Given an array prices, prices[I] is the price of a given stock on day I.

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).

The sample1: Input: prices = [7.1.5.3.6.4] output:7Explanation: 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. The sample2: Input: prices = [1.2.3.4.5] output:4Explanation: 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. The sample3: Input: prices = [7.6.4.3.1] output:0Explanation: In this case, no transaction is completed, so the maximum profit is0.Copy the code

Look at the picture and the idea comes out immediately:

Our profit is the same as the green part of the graph, which means as long as today minus yesterday, a positive number is profit, simple, ha ha!

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

206. Reverse linked lists

This problem must master solid, is the basis of solving many linked list problems. Let’s start with the title:

Given the head node of a single linked list, reverse the list and return the reversed list.

Example 1:

Enter: head = [1.2.3.4.5] output: [5.4.3.2.1]
Copy the code

Example 2:

Enter: head = [1.2] output: [2.1]
Copy the code

Let’s add a null to the front of the list so that it’s the same before and after the flip.Answer:

var reverseList = function(head) {
  let [pre, node] = [null, head];
  while(node){
      const temp = node.next;
      node.next = pre;
      pre = node;
      node = temp;
  }
  return pre;
};
Copy the code

Double pointer

Double pointer is the most common method to solve number group type problems

• For example, a double pointer that has a pointer at the beginning and end and then moves toward the middle,
• The other is that the speed is a pointer, and both Pointers start from the left, so one goes fast and one goes slow

Specific details or need to understand from the topic, we start now!

26. Delete duplicates from array

Let’s take a look at the title:

Give you an ordered array nums, ask you to delete the repeated elements in place, so that each element appears only once, return the deleted array after the new length.

Instead of using extra array space, you must modify the input array in place and do so with O(1) extra space.

The sample1: Input: nums = [1.1.2] output:2, nums = [1.2The function should return the new length2, and the first two elements of the original array NUMs are modified to1.2. You don't need to worry about the element after the new length in the array. The sample2: Input: nums = [0.0.1.1.1.2.2.3.3.4] output:5, nums = [0.1.2.3.4The function should return the new length5, and the first five elements of the original array NUMs are changed to0.1.2.3.4. You don't need to worry about the element after the new length in the array. Tip:0 <= nums.length <= 3 * 104
-104 <= nums[i] <= 104Nums are sorted in ascending orderCopy the code

The initial state is:

• A pointer is slowiThe fast pointer isj
• ifnums[i]Is equal to thenums[j]That means it’s the same element,jKeep going,iStill in situ
• ifnums[i]Is not equal tonums[j]The statement is not the same element, sonums[i++] = nums[j].jKeep going

Similarly, the I pointer guarantees that it and the number before it are not repeated, and j is a traverser

var removeDuplicates = function(nums) { let i = 0; for(let j = 1; j < nums.length; j++){ if(nums[j] ! == nums[i]){ nums[i+1] = nums[j]; i++ } } return i + 1 };Copy the code

88. Merge two ordered arrays

Let’s start with the title:

Merge nums2 into nums1 to make nums1 an ordered array.

Initialize nums1 and nums2 to m and n, respectively. You can assume that nums1 has a space size equal to m + n so that it has enough space to hold elements from Nums2.

Example 1: Input nums1 = [1,2,3,0,0], m = 3, nums2 = [2,5,6], n = 3 Output: [1,2,2,3,5,6] Nums1 = [1], m = 1, nums2 = [], n = 0  nums1.length == m + n nums2.length == n 0 <= m, n <= 200 1 <= m + n <= 200 -109 <= nums1[i], nums2[i] <= 109Copy the code

So this is a pretty easy problem to think about, just create an array, compare each of these two arrays, and push them

However, since it is an ordered array, the first array has just enough space for the second array, so we can use a double pointer to solve the problem, traversing from back to front

For reference:

var merge = function (nums1, m, nums2, n) {
  let len = m + n - 1;
  m--, n--;
  while (m >= 0 && n >= 0) {
    if (nums1[m] > nums2[n]) {
      nums1[len] = nums1[m--]
    } else {
      nums1[len] = nums2[n--]
    }
    len--;
  }
  if(m === -1) {return nums1.splice(0, len+1. nums2.slice(0, n + 1));
  }
  if(n === -1) {returnnums1; }};Copy the code

125. Verify palindrome strings

Please look at the title:

Given a string, verify that it is a palindrome string, considering only alphanumeric characters, regardless of letter case.

Note: In this case, we define an empty string as a valid palindrome string.

The sample1Input:"A man, a plan, a canal: Panama"Output:trueExplanation:"amanaplanacanalpanama"Is a palindrome string example2Input:"race a car"Output:falseExplanation:"raceacar"Not a palindrome stringCopy the code

This problem is so simple that I don’t have to write an idea, but if YOU look at the code, you can just do it with a double pointer,

var isPalindrome = function(s) {
  s = s.replace(/[^\w]/g.' ').toLowerCase();
  let leftPointer = 0;
  let rightPointer = s.length - 1;
  while(rightPointer > leftPointer){
      if(s[leftPointer++] === s[rightPointer--]){
          continue;
      }else{
          return false; }}return true;
};
Copy the code

234. Palindrome linked list

It’s the same idea as above, it’s a double pointer comparison, but the main thing is that it’s a bit of a hassle to write, to use the flip list that we talked about earlier,

Answer:

• Let’s use a fast or slow pointer to tell us where the middle point of the list is, and then cut it off
• And then cut it into two lists, and flip the list behind it
• Finally, judge whether each item of the two lists is the same

Key point: How to cut the list off from the middle point by having one pointer take one step at a time and the other pointer take two steps at a time, so that the multiples of each step differ by 2. The code is as follows:

  let fast = head;
  let slow = head;
  let prev;
  while (fast && fast.next) {
    prev = slow;
    slow = slow.next;
    fast = fast.next.next;
  }
prev.next = null;  // Break two linked lists
Copy the code

• And then we need to flip the list

 // reverse the bottom half
  let head2 = null;
  while (slow) {
    const tmp = slow.next;
    slow.next = head2;
    head2 = slow;
    slow = tmp;
  }
Copy the code

• Finally, the comparison will see the specific code below

const isPalindrome = (head) = > {
  if (head == null || head.next == null) {
    return true;
  }
  let fast = head;
  let slow = head;
  let prev;
  while (fast && fast.next) {
    prev = slow;
    slow = slow.next;
    fast = fast.next.next;
  }
  prev.next = null;  // Break two linked lists
  // reverse the bottom half
  let head2 = null;
  while (slow) {
    const tmp = slow.next;
    slow.next = head2;
    head2 = slow;
    slow = tmp;
  }
  / / than
  while (head && head2) {
    if(head.val ! = head2.val) {return false;
    }
    head = head.next;
    head2 = head2.next;
  }
  return true;
};
Copy the code

237. Delete a node from a linked list

The title is as follows:

Write a function that removes a given (non-trailing) node from a linked list. The only argument passed to the function is the node to be deleted.

There is a linked list — head = [4,5,1,9], which can be expressed as:

 

The sample1: Enter: head = [4.5.1.9], node = 5Output:4.1.9Given that the value in your linked list is5After calling your function, the strain of the list is4 -> 1 -> 9.The sample2: Enter: head = [4.5.1.9], node = 1Output:4.5.9Given that the value in your linked list is1After calling your function, the strain of the list is4 -> 5 -> 9.Tip: The linked list contains at least two nodes. All nodes in a linked list have unique values. The given node is a non-trailing node and must be a valid node in the linked list. Do not return any results from your function.Copy the code

Next: val = node.next-next: val = node.Next-next: val = node.Next-next: val = node.next-next You can try to draw it on the draft and you will understand it soon with the code!

var deleteNode = function(node) {
  node.val = node.next.val
  node.next = node.next.next
};
Copy the code

283. Move the zero

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: Enter: [0.1.0.3.12] output: [1.3.12.0.0] Note: must operate on the original array, cannot copy additional arrays. Minimize the number of operations.Copy the code

As shown in the animation, we can use the fast and slow pointer to solve the problem, which is not easy to describe in language, see the GIF

var moveZeroes = function(nums) {
  let i = j = 0;
  while(i < nums.length) {
      if(nums[i] ! = =0){
          [nums[i], nums[j]] = [nums[j], nums[i]]
          j++
      }
      i++
  }

  return nums
};
Copy the code

344. Reverse the string

The title is as follows:

Write a function that reverses the input string. The input string is given in the form of the character array char[].

Instead of allocating extra space to another array, you must modify the input array in place, using O(1) extra space to solve the problem.

You can assume that all the characters in the array are printable characters in the ASCII code table.

Example 1: input: [" h ", "e", "l", "l", "o"] output: [" o ", "l", "l", "e", "h"] example 2: input: [" h ", "a", "n", "n", "a", "h"] output: [" h ", "a", "n", "n", "a", "h"]Copy the code

This topic is really too simple, know to use the first double pointer can, see reference:

var reverseString = function(s) {
  let l = 0 ;
  let r = s.length - 1;
  while(l < r){
    [s[l], s[r]] = [s[r], s[l]];
    l++; r--;
  }
  return s;
};
Copy the code

350. Intersection of two arrays II

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

 

The sample1: Input: nums1 = [1.2.2.1], nums2 = [2.2] output: [2.2] example2: Input: nums1 = [4.9.5], nums2 = [9.4.9.8.4] output: [4.9] Note: The number of occurrences of each element in the output should be the same as the minimum number of occurrences of the element in both arrays. We can ignore the order of the output.Copy the code

This intersection needs to retain repeated elements, can be used to solve the double pointer, the specific idea and code is as follows

• If two arrays are ordered, the intersection of the two arrays can be obtained using the two-pointer method.

• The two arrays are sorted first, then iterated through with two Pointers.

• Initially, two Pointers point to the heads of two arrays. Each time you compare the numbers in the two arrays to which the two Pointers point, if the two numbers are not equal, move the pointer to the smaller number one to the right, if the two numbers are equal, add that number to the answer, and move both Pointers one to the right. The traversal ends when at least one pointer is out of range

var intersect = function(nums1, nums2) {
  nums1 = nums1.sort((a, b) = > a - b);
  nums2 = nums2.sort((a, b) = > a - b);
  let l1 = 0;
  let l2 = 0;
  const nums1Len = nums1.length;
  const nums2Len = nums2.length;
  const ret = [];
  while(l1 < nums1Len && l2 < nums2Len){
    if(nums1[l1] === nums2[l2]){
      ret.push(nums1[l1]);
      l1++;
      l2++;
    }
    if(nums1[l1] > nums2[l2]) l2++;
    if(nums1[l1] < nums2[l2]) l1++;
  }
  return ret;
};
Copy the code

The classification and solutions for the remaining 20 questions should be written tomorrow or the day after tomorrow, and the rest will include

• The stack
• Dynamic programming
• Mathematical problems
• Ring problem