Array

Key Points

An Example

Problems

Common problems/skills related to array

  • Double Pointers
    • Slow and Faster
    • Left and Right
    • Binary Search
    • Sliding Window
  • Prefix Sum
  • N-Sum
  • Merge Sort related
  • BitMask related
  • Math related

Problems - Double Pointers

Key Principle

在处理数组和链表相关问题时，双指针技巧是经常用到的，双指针技巧主要分为两类：左右指针和快慢指针。

所谓左右指针，就是两个指针相向而行或者相背而行；

而所谓快慢指针，就是两个指针同向而行，一快一慢。(滑动窗口是快慢指针的一个类型)

对于单链表来说，大部分技巧都属于快慢指针，单链表的六大解题套路 都涵盖了，比如链表环判断，倒数第 K 个链表节点等问题，它们都是通过一个 fast 快指针和一个 slow 慢指针配合完成任务。

在数组中并没有真正意义上的指针，但我们可以把索引当做数组中的指针，这样也可以在数组中施展双指针技巧，本文主要讲数组相关的双指针算法。

Problems

Problems Possible Solutions Key Points Code Comments
26. Remove Duplicates from Sorted Array Double Pointers, slow + fast code
83. Remove Duplicates from Sorted List Double Pointers, slow + fast Edged case of head == nil code
27. Remove Element Double Pointers, slow + fast code
283. Move Zeroes Double Pointers, slow + fast * Similar as Problem 27. Just remove the 0, and pad the index from k with 0 code Similar to the logic of pivot logic in quick sort
167. Two Sum II - Input Array Is Sorted Double Pointers, left + right, from both sides to central code
344. Reverse String Double Pointers, left + right, from both sides to central code
5. Longest Palindromic Substring Double Pointers, left + right, from central to both sides * 找回文串的难点在于，回文串的的长度可能是奇数也可能是偶数，解决该问题的核心是从中心向两端扩散的双指针技巧 code
88. Merge Sorted Array Double Pointers * Pointers move from high to low index code
-

Reference

  1. https://labuladong.online/algo/essential-technique/array-two-pointers-summary-2/

Problems - Double Pointers - Binary Search Problems

Key Points

  1. The border of [left, right], or [left, right)?
Problems Possible Solutions Key Points Code Comments
704. Binary Search BS * The border of [left, right] code
34. Find First and Last Position of Element in Sorted Array BS The border of [left, right]
 Control the left most or right most index
* The edged case		 code
875. Koko Eating Bananas BS * How to abstract the problem to Binary Search code
1011. Capacity To Ship Packages Within D Days BS * How to abstract the problem to Binary Search code

Reference

  1. https://labuladong.online/algo/essential-technique/binary-search-framework-2/
  2. https://labuladong.online/algo/frequency-interview/binary-search-in-action/

Problems - Double Pointers - Sliding Window Problems

Key Principle

1.我们在字符串 S 中使用双指针中的左右指针技巧，初始化 left = right = 0，把索引左闭右开区间 [left, right) 称为一个「窗口」。 2.我们先不断地增加 right 指针扩大窗口 [left, right)，直到窗口中的字符串符合要求（包含了 T 中的所有字符）。 3.此时，我们停止增加 right，转而不断增加 left 指针缩小窗口 [left, right)，直到窗口中的字符串不再符合要求（不包含 T 中的所有字符了）。同时，每次增加 left，我们都要更新一轮结果。 4.重复第 2 和第 3 步，直到 right 到达字符串 S 的尽头。 第 2 步相当于在寻找一个「可行解」，然后第 3 步在优化这个「可行解」，最终找到最优解.

Notes

  1. The logic of extend window and shrunk window maybe different from problem to problem. For example, it's different for problem 76 and 159.
  2. The workflow maybe different from problem to problem also. For example, problem 395.
Problems Possible Solutions Key Points Code Comments
76. Minimum Window Substring Sliding Window operate the supporting vars at the same time code
159. Longest Substring with At Most Two Distinct Characters Sliding Window The extend and shrunk window logic is different from problem 76 code
3. Longest Substring Without Repeating Characters Sliding Window Version v2 and PV1. PV1 shows the standard workflow of Sliding Window clearly code
395. Longest Substring with At Least K Repeating Characters Sliding Window the workflow is different from the framework. Extend, shrunk, and the check if we have a valid result code
1423. Maximum Points You Can Obtain from Cards Sliding Window * Hard point is to convert the problem to sliding window scenarios. code
424. Longest Repeating Character Replacement Sliding Window *Utilize the index of character in the string code

Reference

  1. https://labuladong.online/algo/essential-technique/sliding-window-framework-2/

Problems - N-Sum Problems

Types Problems Key Points Possible Solutions Comments
nSum Problems 259 Double pointer
Remove the duplication		 code

Problems - LIS Problems

Problems Possible Solutions Key Points Code Comments
674. Longest Continuous Increasing Subsequence Edged case: the array ALL is increasing code

Problems - MergeSort Related Problems

Key Principles

Break down the problems into sub problems and the merge. Divide and Conquer

Problems Possible Solutions Key Points Code Comments
315. Count of Smaller Numbers After Self Merge Sort
 Binary Indexed Tree
* Segment Tree		 Principle why merge sort can work (R1) code
493. Reverse Pairs Merge Sort
 Binary Indexed Tree
* Segment Tree		 How to insert the logic into MergeSort code
327. Count of Range Sum Merge Sort
 Binary Indexed Tree
* Segment Tree		 Convert the problem to presum problem
merge sort
* Refer to the code		 code

Reference: R1. https://labuladong.online/algo/practice-in-action/merge-sort/

Problems - PreSum Problems

Key Principles

Problems Possible Solutions Key Points Code Comments
303. Range Sum Query - Immutable Presum * If the left num is included code
304. Range Sum Query 2D - Immutable Presum if left is included
 the set calculation		 code

Reference: R1. https://labuladong.online/algo/practice-in-action/merge-sort://labuladong.online/algo/data-structure/prefix-sum/

Problems - BitMask Problems

Problems Possible Solutions Key Points Code Comments
2506. Count Pairs Of Similar Strings bitmask should contain SAME characters code

Problems - Math Related Problems

Problems Possible Solutions Key Points Code Comments
1010. Pairs of Songs With Total Durations Divisible by 60 get the idea of % 60.
 Edged case of length = 0 or 30		 code

Problems - Others

Problems Possible Solutions Key Points Code Comments
1062. Longest Repeating Substring 1.1 The idea of loop logic.
 1.2 Stop loop in advance and edged case
* 2 The idea of binary search with possible length		 code

results matching ""

    No results matching ""