Derivation of ring linked list -- the starting point of locating ring

Method 1: record the existing nodes of the flag encountered for the first time

function detectCycle(head) {

    while (head) {
        if (head.flag) return head;
        else {
            head.flag = true;
            head = head.next;
        }
    }

    return null;
}

Method 2: double pointer

Define slow pointer and fast pointer. The two go hand in hand, slow one step at a time and fast two steps at a time. In this way, if they move in a linked list, there must be a time to meet. The proof of this principle is also relatively simple: we assume that the number of moves is t, the distance of slow movement is t, and the distance of fast movement is 2t. If the length of the ring is s, then when the following condition:

2t - t = s

That is:

t = s

When satisfied, slow and fast will meet. On the contrary, if the two do not meet, and fast traverses to the end of the linked list and finds that the next pointer points to null, there is no ring in the linked list.

Valid parentheses

const leftToRight = {
    "(": ")",
    "[": "]",
    "{": "}"
}; //map

function isValid(s) {

    if (!s) return true; //Empty string is unconditionally true

    const stack = [];

    for (let i = 0; i < s.length; i++) {

        const ch = s[i];

        if (ch === "(" || ch === "{" || ch === "[") stack.push(leftToRight[ch]);
        else { //If it is not an open bracket, it must be a right bracket paired with the open bracket at the top of the stack
            if (!stack.length || stack.pop() !== ch) {
                return false; //If the stack is not empty and the left bracket at the top of the stack does not match the current character, it is judged to be invalid
            }
        }

    }
    return !stack.length; //If all parentheses can be paired successfully, then the final stack should be empty
}

Leetcode 739 daily temperature

Brute force traversal method: direct two-layer traversal. The first layer locates a temperature, and the second layer locates the date of the nearest temperature rise from this temperature, and then calculate the difference between the corresponding indexes of the two temperatures.

The secret to avoid repeated operations is to timely get unnecessary data out of the stack to avoid interference with our subsequent traversal. Take this question for example, our idea is to try to maintain a decreasing stack.
When the traversed temperature maintains a monotonous decreasing trend, we will perform the stack operation on the index subscripts of these temperatures; As long as a number appears, it breaks this monotonous decreasing trend, that is, it is higher than the previous temperature value. At this time, we calculate the difference between the index subscripts of the two temperatures to obtain the target difference between the previous temperature and the first temperature rise.

/**
 * @param {number[]} temperatures
 * @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]]) { 
            //If the stack is not 0 and there is a temperature value that breaks the decreasing trend
            const top = stack.pop() //Index the corresponding stack top temperature value out of the stack  
            res[top] = i - top //Calculate the index difference between the current stack top temperature value and the first temperature value higher than it 
        }
        stack.push(i) //Note that instead of the temperature value, the index value is stored in the stack, which is convenient for later calculation

    }
    
    return res;
}

Leetcode 155 minimum stack

Method 1: O(n)

const MinStack = function() {
    this.stack = []
};

MinStack.prototype.push = function(x) {
    this.stack.push(x)
};

MinStack.prototype.pop = function() {
    this.stack.pop()
};

MinStack.prototype.top = function() {
    if (!this.stack || !this.stack.length) {
        return
    }
    return this.stack[this.stack.length - 1]
};

//Take the minimum value according to the idea of one-time traversal
MinStack.prototype.getMin = function() {
    let minValue = Infinity
    const { stack } = this
    for (let i = 0; i < stack.length; i++) {
        if (stack[i] < minValue) {
            minValue = stack[i]
        }
    }
    return minValue
};

Method 2: o

const MinStack2 = function() {
    this.stack = [];
    // Define auxiliary stack
    this.stack2 = [];
};

MinStack2.prototype.push = function(x) {
    this.stack.push(x);
    // If the value entered into the stack is less than the current minimum value, it will be pushed into the top of the auxiliary stack
    if (this.stack2.length == 0 || this.stack2[this.stack2.length - 1] >= x) {
        this.stack2.push(x);
    }
};

MinStack2.prototype.pop = function() {
    // If the out of stack value is equal to the current minimum value, the auxiliary stack should also out stack the elements at the top of the stack to ensure the effectiveness of the minimum value
    if (this.stack.pop() == this.stack2[this.stack2.length - 1]) {
        this.stack2.pop();
    }
};

MinStack2.prototype.top = function() {
    return this.stack[this.stack.length - 1];
};

MinStack2.prototype.getMin = function() {
    // The top of the auxiliary stack stores the minimum value in the target
    return this.stack2[this.stack2.length - 1];
};

Implement queue with stack

const MyQueue = function() {
    this.stack1 = [];
    this.stack2 = [];
}

MyQueue.prototype.push = function(x) {
    this.stack1.push(x);
};

MyQueue.prototype.pop = function() {
    if (this.stack2.length <= 0) { //If stack2 is empty, the element of stack1 needs to be transferred in
        while (this.stack1.length !== 0) { //When stack1 is not empty, exit the stack
            this.stack2.push(this.stack1.pop()); //Push stack1 out of stack elements into stack2
        }
    }
    return this.stack2.pop(); //In order to achieve the purpose of reverse order, we only list the stack elements from stack2
};

//The only difference between this method and pop is that it doesn't take the located value out of the stack
MyQueue.prototype.peek = function() {
    if (this.stack2.length <= 0) {
        while (this.stack1.length != 0) {
            this.stack2.push(this.stack1.pop());
        }
    }
    const stack2Len = this.stack2.length;
    return stack2Len && this.stack2[stack2Len - 1];
};


MyQueue.prototype.empty = function() {
    return !this.stack1.length && !this.stack2.length;
};

Leetcode 239 sliding window Max

Method 1: double pointer traversal O(kn)

function maxSlidingWindow(nums, k) {
    const res = [];
    const len = nums.length;
    let left = 0,
        right = k - 1;

    while (right < len) {
        const max = calMax(nums, left, right);
        res.push(max);
        left++, right++;
    }

    return res;
}

function calMax(arr, left, right) {
    if (!arr || !arr.length) return;
    let maxNum = arr[left];
    for (let i = left; i <= right; i++)
        if (arr[i] > maxNum) maxNum = arr[i];
    return maxNum;
}

Method 2: double ended queue O(n)

• Check the tail elements to see if they all meet the conditions greater than or equal to the current element. If so, directly join the current element into the team. Otherwise, the tail elements are dequeued one by one until the tail element is greater than or equal to the current element.
• Queue current element
• Check the queue header element to see if it has been excluded from the sliding window. If yes, the team head element is removed from the team.
• Judge the status of the sliding window: see whether the number of elements traversed is less than k. If the number of elements is less than k, it means that the elements in the first sliding window have not been traversed and the first maximum value has not appeared. At this time, we can not move the result array and can only continue to update the queue; If the number of elements is greater than or equal to K, it means that the maximum value of the sliding window has appeared. At this time, every time you traverse a new element (that is, every step forward of the sliding window), you should timely add the maximum value corresponding to the current sliding window to the result array (the maximum value is the queue head element of the double ended queue at this moment).

These four steps have the following purposes:

• Maintain the decrement of the queue: ensure that the queue head element is the maximum value of the current sliding window. In this way, each time we take the maximum value, we can directly take the team head element.
• There is nothing to say about this step, which is to update the contents of the queue on the basis of maintaining the decrement of the queue.
• Maintain the validity of the queue: ensure that all elements in the queue are within the range delineated by the sliding window.
• Exclude the special cases where the sliding window has not been initialized and the first maximum value has not appeared.

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
const maxSlidingWindow = function (nums, k) {
  // Length of cache array
  const len = nums.length;
  // Initialize result array
  const res = [];
  // Initialize Dual Ended queue
  const deque = [];
  // Start traversing array
  for (let i = 0; i < len; i++) {
    // When the tail element is smaller than the current element
    while (deque.length && nums[deque[deque.length - 1]] < nums[i]) {
      // Keep the tail element (index) out of the queue until the tail element is greater than or equal to the current element
      deque.pop();
    }
    // Index of the current element in the queue (note the index)
    deque.push(i);
    // When the index of the queue header element has been excluded from the sliding window
    while (deque.length && deque[0] <= i - k) {
      // Index the queue header element out of the queue
      deque.shift();
    }
    // Judge the state of the sliding window, and update the result array only when the number of elements traversed is greater than k
    if (i >= k - 1) {
      res.push(nums[deque[0]]);
    }
  }
  // Return result array
  return res;
};

Leetcode 345 inverts vowels in a string

Double finger needling

/**
 * @param {string} s
 * @return {string}
 */
var reverseVowels = function(s) {
    const n = s.length;
    const arr = Array.from(s);
    let i = 0, j = n - 1;
    while (i < j) {
        while (i < n && !isVowel(arr[i])) {
            ++i;
        }
        while (j > 0 && !isVowel(s[j])) {
            --j;
        }
        if (i < j) {
            swap(arr, i, j);
            ++i;
            --j;
        }
    }
    return arr.join('');
}

const isVowel = (ch) => {
    return "aeiouAEIOU".indexOf(ch) >= 0;
}

const swap = (arr, i, j) => {
    const temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

Leetcode 11 container with the most water

/**
 * @param {number[]} height
 * @return {number}
 */
var maxArea = function(arr) {
    let left=0,right=arr.length-1;
    let ans=0;
    while(left<right){
        let area=Math.min(arr[left],arr[right])*(right-left);
        ans=Math.max(ans,area);
        if(arr[left]<=arr[right]) left++;
        else right--;
    }

    return ans;
};