Leetcode 解题套路

[MatNoble]

[MatNoble]

数组 Array 双指针 Two Pointers

[0, i), [i, j), [j, len(array))

同向

• [0, i) 的数据代表处理好的数据
• [i, j) 中的数据是那些处理过但不需要的数据
• [j, len(array)) 区间的数据为接下来待处理的数据

1. Initialize two pointers i and j, usually both equal to 0
2. while j < array.length:
   • if we need array[j], then we keep it by assigning array[i] = array[j], and move i forward, make it ready at the next position
   • otherwise skip it. We do not need to move i since its spot is not fulfilled

---

反向

• [0, i) 和 (j, array.length) 内的数据均为处理好的数据
• [i, j] 中的数据待处理

1. Initialize two pointers i = 0, j = array.length – 1
2. while i <= j:
   • Decide what you should do based on the value of array[i] and array[j]
   • Move at least one pointer forward in its direction

参考自：图灵星球

[MatNoble]

Binary Search 二分搜索

[MatNoble]

Linked List 链表

[MatNoble]

HashMap 哈希表

在平均 O(1) 时间内快速增删查, 用于加速查找

[MatNoble]

Stack 栈

单调栈

每次新元素入栈后，栈内的元素都保持有序（单调递增或单调递减）。

Next Greater Element

循环数组

[MatNoble]

DP Search

搜索空间可以用 Tree 的形式展现出来，便于理解。时间复杂度取决于这棵树的深度和每个 node 的 children 个数。

Search 最重要的是：定义好状态，保证每个子问题都能用一个状态来描述

Top Down DFS 模板

1. Define ATATE of subproblems
2. Initialize initial state
3. Call dfs(init_state)

dfs(state):

• Base case check
• For each subproblem x
  • Update state = next_state_x
  • Branch down --> call dfs(next_state_x)
  • Restore state