Write a front end sliding window algorithm topic - speed pass 11 leetcode topics

The sliding window

The essence of a sliding window is a double pointer, using a left pointer and a right pointer to form a window. Windows should have the following features:

The element relationships in the window satisfy one of the constraints given by the problem
A valid window can provide a possible solution to the problem

In general, the index relationship between window types and pointer initials is as follows:

Fixed size window (set size to K) :left = 0, right = k-1
Variable size window:left = 0, right = 0

Left and right pointer movement mode:

rightPointer: Active right move
leftPointer: when[left, right]When the window does not meet the requirements, the passive right move

The basic problem solving template of sliding window is:

// nums is a given interval, usually k is a window qualifier
function slidingWindow(nums, k) {
  let result = 0
  let left = 0
  let right = 0
  // Some relation within the window, here is and
  let sum = 0

  while (right < nums.length) {
    // Maintain some relationship within the window
    sum += nums[right]
    // The left pointer moves to the right passively when the relationship between elements in the window does not meet one of the constraints given in the question
    while (sum < k) {
      // Maintain some relationship within the window
      sum -= nums[left]
      left++
    }
    // A valid window can provide a possible solution to the problem
    result = Math.max(result, right - left + 1)
    right++
  }

  return result
}
Copy the code

In Leetcode, sliding window topics are classified as follows:

Basic template questions, as an appetizer:

1004
1208
1456

On top of the template, there is a bit more deformation:

1423
1658
978

Combination type:

1498: Sliding window + math
3: sliding window + hash table
239: Sliding window + monotone queue
1438: Sliding window + 2 monotonic queues
480: Sliding window + heap

You can directly click the subtitle to enter the corresponding Leetcode page. It is recommended to swipe the questions in the order above

Leetcode 1004 – Medium

参考答案 :

Sliding window standard template problem, template can be understood

Implementation:

function longestOnes(nums, k) {
  let result = 0
  let left = 0
  let right = 0

  while (right < nums.length) {
    if (nums[right] === 0) {
      k--
    }
    while (k < 0) {
      if (nums[left] === 0) {
        k++
      }
      left++
    }
    result = Math.max(result, right - left + 1)
    right++
  }

  return result
}
Copy the code

Leetcode 1208 – Medium

Answer:

Sliding window standard template problem, template can be understood

Implementation:

function equalSubstring(s, t, maxCost) {
  let result = 0
  let left = 0
  let right = 0

  while (right < s.length) {
    maxCost -= Math.abs(s[right].charCodeAt() - t[right].charCodeAt())
    while (maxCost < 0) {
      maxCost += Math.abs(s[left].charCodeAt() - t[left].charCodeAt())
      left++
    }
    result = Math.max(result, right - left + 1)
    right++
  }

  return result
}
Copy the code

Leetcode 1456 – Medium

Answer:

Sliding window standard template problem, template can be understood

Implementation:

function maxVowels(s, k) {
  const vowelsMap = {
    a: 1.e: 1.i: 1.o: 1.u: 1
  }
  // Select the first k values as initial values
  let vowels = 0
  for (let i = 0; i < k; i++) {
    if (s[i] in vowelsMap) {
      vowels++
    }
  }
  let maxVowels = vowels
  / / right movement
  for (let i = k; i < s.length; i++) {
    / / judgment
    if (s[i] in vowelsMap) {
      vowels++
    }
    / / determine
    if (s[i - k] in vowelsMap) {
      vowels--
    }
    maxVowels = Math.max(maxVowels, vowels)
  }
  return maxVowels
}
Copy the code

Leetcode 1423 – Medium

Answer:

Fixed size window

“For each action, you can pick up a card from the beginning or the end of the row, and you must end up with exactly K cards.” It can be converted to maintaining a window with the size of cardPoints. Length -k. Find the minimum value that can be obtained by sliding this window to the right to obtain the maximum value of remaining cards

Implementation:

function maxScore(cardPoints, k) {
  const totalSum = cardPoints.reduce((acc, val) = > acc += val, 0)
  const windowSize = cardPoints.length - k
  // Select the former windowSize as the initial value
  let sum = 0
  for (let i = 0; i < windowSize; i++) {
    sum += cardPoints[i]
  }
  let minSum = sum
  // Start sliding to the right
  for (let i = windowSize; i < cardPoints.length; i++) {
    // Find the difference between one in and one out
    sum += cardPoints[i] - cardPoints[i - windowSize]
    minSum = Math.min(minSum, sum)
  }
  return totalSum - minSum
}
Copy the code

Leetcode 1658 – Medium

Answer:

Variable size window

“On each operation, you should remove the leftmost or rightmost element of the array nums” => find a contiguous window where the elements and = sum -x

Implementation:

function minOperations(nums, x) {
  // find the sum of arrays
  let sum = 0
  for (let i = 0; i < nums.length; i++) {
    sum += nums[i]
  }
  const windowSumTarget = sum - x
  // If the sum of the target elements is less than 0, return it directly
  if (windowSumTarget < 0) {
    return -1
  }
  // find a continuous window with elements and = sum -x
  let left = 0
  let right = 0
  let operateCount = Number.MAX_VALUE
  let windowSum = 0
  while (right < nums.length) {
    windowSum += nums[right]
    while (windowSum > windowSumTarget) {
      windowSum -= nums[left]
      left++
    }
    if (windowSum === windowSumTarget) {
      operateCount = Math.min(operateCount, nums.length - (right - left + 1))
    }
    right++
  }
  return operateCount === Number.MAX_VALUE ? -1 : operateCount
}
Copy the code

Leetcode 978 – Medium

Answer:

This question, the title is more difficult to understand, but it is a more typical template question

Implementation:

function maxTurbulenceSize(arr) {
  let result = 1
  let left = 0
  let right = 0
  
  while (right < arr.length - 1) {
    if (left === right) {
      if (arr[left] === arr[left+1]) {
        left++
      }
      right++
    } else {
      if (arr[right-1] < arr[right] && arr[right] > arr[right+1]) {
        right++
      } else if (arr[right-1] > arr[right] && arr[right] < arr[right+1]) {
        right++
      } else {
        left = right
      }
    }
    result = Math.max(result, right - left + 1)}return result
}
Copy the code

Leetcode 1498 – Medium

Answer:

Experience: involving “mod 10^9 + 7” and power, the power table is preprocessed first

Mathematics knowledge: Recursive formula of combinatorial number formula C (n,0) + C (n,1) + C (n,2) +…… Plus c of n,n is equal to 2 to the n

Since subsequences do not require continuity, you can sort the array first. If the interval [l, r] satisfies the condition nums[l] + nums[r] <= target, then all subsequences containing NUMs [l] satisfy the condition

Implementation:

function numSubseq(nums, target) {
  // Can sort
  nums.sort((a, b) = > a < b ? -1 : 1)
  // Preprocessing computes the power table
  const pow = [1]
  for (let i = 1; i < nums.length; i++) {
    pow[i] = (pow[i-1] < <1) % 1000000007
  }
  let count = 0
  let left = 0
  let right = nums.length - 1
  while (left <= right) {
    if (nums[left] + nums[right] > target) {
      right--
    } else {
      // The combination number formula
      count = (count + pow[right - left]) % 1000000007
      left++
    }
  }
  return count
}
Copy the code

Leetcode 3 – Medium

Answer:

Slide window + hash table records the first occurrence of the index position

Implementation:

function lengthOfLongestSubstring(s) {
  if(! s) {return 0
  }
  const counter = {}
  let result = 1
  let left = 0
  let right = 0

  while (right < s.length) {
    if(! (s[right]in counter)) {
      // Record the first occurrence of the index position
      counter[s[right]] = right
    } else {
      // Optimization point: On repetition, the left pointer moves to the next position where the index first appears
      const oldLeft = left
      left = counter[s[right]] + 1
      // Delete counter data between old and new left
      for (let i = oldLeft; i < left; i++) {
        delete counter[s[i]]
      }
      counter[s[right]] = right
    }
    result = Math.max(result, right - left + 1)
    right++
  }
  return result
}
Copy the code

Leetcode 239 – Difficult

Answer:

Fixed size window, the difficulty of this problem is: how to calculate the maximum window in O(1) time, in order to solve this problem, monotonous queue data structure is used

Implementation:

function maxSlidingWindow(nums, k) {
  const queue = []
  // Monotonic stack/queue template
  // Maintain the first k number of monotonous queue: from the end of the queue to the head of the queue increment
  for (let i = 0; i < k; i++) {
    while (queue.length && nums[i] >= nums[queue[queue.length - 1]]) {
      queue.pop()
    }
    // Set index to index
    queue.push(i)
  }

  const result = [nums[queue[0]]]
  let right = k

  while (right < nums.length) {
    // Here we continue to maintain monotonic queues
    // Use > also can AC, but the time is obviously increased, why? => queue.shilt() is called many times
    while (queue.length && nums[right] >= nums[queue[queue.length - 1]]) {
      queue.pop()
    }
    queue.push(right)
    // The monotonic queue head (maximum index) is out of range
    while (queue[0] <= right - k) {
      queue.shift()
    }
    result.push(nums[queue[0]])
    right++
  }

  return result
}
Copy the code

Leetcode 1438 – Medium

Answer:

The difficulty of this question is: how to calculate the maximum and minimum values of the window in O(1) time, similar to question 239

Implementation:

function longestSubarray(nums, limit) {
  const queMin = []
  const queMax = []
  let left = 0
  let right = 0
  let result = 0

  while (right < nums.length) {
    while (queMax.length && nums[right] > queMax[queMax.length - 1]) {
      queMax.pop()
    }
    queMax.push(nums[right])
    while (queMin.length && nums[right] < queMin[queMin.length - 1]) {
      queMin.pop()
    }
    queMin.push(nums[right])
    // Based on question 239, we can get to this point
    QueMax [0] can be used to obtain the maximum value of the interval, and queMin[0] can obtain the minimum value of the interval. If their absolute difference is illegal, the left interval needs to be shrunk
    Nums [left] = queMax/queMin; nums[left] = queMax/queMin
    while (queMax.length && queMin.length && queMax[0] - queMin[0] > limit) {
      if (nums[left] === queMin[0]) {
        queMin.shift()
      }
      if (nums[left] === queMax[0]) {
        queMax.shift()
      }
      left++
    }
    result = Math.max(result, right - left + 1)
    right++
  }

  return result
}
Copy the code

Leetcode 480 – Difficult

Answer:

This is a fairly classic sliding window problem, can be said to be very difficult. Enumerate the time complexity of the following solutions:

The median of sorting calculation for every slide: the number of slides isn-k, the time complexity of each sort isO(klogk), the total time complexity isO(nklogk)
Mean linear selection for each slide: the number of slides isn-k, the time complexity of each median selection isO(k), the total time complexity isO(nk)
Double heap with “delete specified element” operation: the number of slides isn-k, the heap size isO(k), the time complexity of deleting elements in the heap isO(k), the insertion time complexity isO(logk), the total time complexity isO(nk)
Double heap with lazy deleted elements: official solution, time complexity isO(nlogn)
Bibalanced tree:O(nlogk)The knowledge blind area is involved

The solution to this problem is: double heap with “delete specified element” operation. The idea of using double heap can refer to the median in leetcode-295 data stream

Implementation:

A heap with “delete specified element”, if Java, is the TAT with this data structure

// Heap data structure implementation with "delete specified element"
class Heap {
  constructor(data = [], less) {
    this.data = data
    this.less = less || ((a, b) = > a < b)

    if (this.length) {
      for (let p = (this.length - 2) > >1; p >= 0; p--) {
        this._down(p)
      }
    }
  }
  get length() {
    return this.data.length
  }
  peak() {
    return this.data[0]}remove(val) {
    let index = -1
    for (let i = 0; i < this.length; i++) {
        if (this.data[i] === val) {
            index = i
            break}}if (index === -1) return false
    this._swap(index, this.length - 1)
    this.data.pop()
    this._up(index)
    this._down(index)
    return true
  }
  push(val) {
    this.data.push(val)
    this._up(this.length - 1)}pop() {
    if (!this.length) {
      return
    }
    this._swap(0.this.length - 1)
    const popItem = this.data.pop()
    this._down(0)
    return popItem
  }
  _swap(i, j){[this.data[i], this.data[j]] = [this.data[j], this.data[i]]
  }
  _up(i) {
    if (i <= 0) return
    const pIndex = (i - 1) > >1
    if (this.less(this.data[i], this.data[pIndex])) {
      this._swap(i, pIndex)
      this._up(pIndex)
    }
  }
  _down(i) {
    let leftIndex = i * 2 + 1
    if (leftIndex >= this.length) {
      return
    }
    if (leftIndex + 1 < this.length && this.less(this.data[leftIndex+1].this.data[leftIndex])) {
      leftIndex++
    }
    if (this.less(this.data[leftIndex], this.data[i])) {
      this._swap(leftIndex, i)
      this._down(leftIndex)
    }
  }
}
Copy the code

295 questions, Median expansion in data streams:


// MedianFinder finds the median in the data stream
class MedianFinder {
  constructor() {
    // The maximum heap stores the smaller half of the input number
    this.maxHeap = new Heap([], (a, b) = > a > b)
    // The smallest heap stores the larger half of the input number
    this.minHeap = new Heap([], (a, b) = > a < b)
  }
  push(num) {
    if (!this.maxHeap.length || num <= this.maxHeap.peak()) {
      this.maxHeap.push(num)
    } else {
      this.minHeap.push(num)
    }
    this.makeBalance()
  }
  remove(value) {
    if (value <= this.maxHeap.peak()) {
      this.maxHeap.remove(value)
    } else {
      this.minHeap.remove(value)
    }
    this.makeBalance()
  }
  findMedian() {
    if (this.maxHeap.length === this.minHeap.length) {
      return (this.maxHeap.peak() + this.minHeap.peak()) / 2
    }
    return this.maxHeap.peak()
  }
  // Adjust the balance of the two heaps
  makeBalance() {
    if (this.maxHeap.length > this.minHeap.length + 1) {
      // The maximum heap is two more than the minimum heap, pop the maximum heap top, push into the minimum heap
      this.minHeap.push(this.maxHeap.pop())
    } else if  (this.minHeap.length > this.maxHeap.length) {
      // The minimum heap is larger than the maximum heap, pop the minimum heap top, push into the maximum heap
      this.maxHeap.push(this.minHeap.pop())
    }
  }
}
Copy the code

Finally answer

// How to calculate the median of the interval, see 295
function medianSlidingWindow(nums, k) {
  // Based on question 295, suppose we have a MedianFinder class that can help us find the median
  const medianFinder = new MedianFinder()
  for (let i = 0; i < k; i++) {
    medianFinder.push(nums[i])
  }
  // Find the median of the first k digits
  const result = [medianFinder.findMedian()]
  // continue to iterate through the following
  for (let i = k; i < nums.length; i++) {
    // Remove the first one and add another one
    medianFinder.remove(nums[i - k])
    medianFinder.push(nums[i])
    result.push(medianFinder.findMedian())
  }

  return result
}
Copy the code

reference

Refer to some leetcode problem solutions

480 – Explain the time complexity of common solutions in this problem

mo4tech.com (Moment For Technology) is a global community with thousands techies from across the global hang out!Passionate technologists, be it gadget freaks, tech enthusiasts, coders, technopreneurs, or CIOs, you would find them all here.

Write a front end sliding window algorithm topic – speed pass 11 leetcode topics

The sliding window

Leetcode 1004 – Medium

Leetcode 1208 – Medium

Leetcode 1456 – Medium

Leetcode 1423 – Medium

Leetcode 1658 – Medium

Leetcode 978 – Medium

Leetcode 1498 – Medium

Leetcode 3 – Medium

Leetcode 239 – Difficult

Leetcode 1438 – Medium

Leetcode 480 – Difficult

reference

Write a front end sliding window algorithm topic – speed pass 11 leetcode topics

The sliding window

Leetcode 1004 – Medium

Leetcode 1208 – Medium

Leetcode 1456 – Medium

Leetcode 1423 – Medium

Leetcode 1658 – Medium

Leetcode 978 – Medium

Leetcode 1498 – Medium

Leetcode 3 – Medium

Leetcode 239 – Difficult

Leetcode 1438 – Medium

Leetcode 480 – Difficult

reference

Related Posts

There are two ways for the front end to get the file address to download

Web front-end advanced Webpack – Manual configuration of Webpack and multi – entrance and multi – exit packaging

Some knowledge points of CORS are shared across domain resources