数据结构与算法刷题笔记

首先推荐两个网址：
一: 代码随想录.
二：labuladong 的算法小抄

数据结构与算法 1栈 1.1单调栈 1.2括号匹配 2队列 1双指针法

这里的指针通俗的理解为索引，不强制为C、C++的指针；
双指针主要分为两种：
+ 同向
+ 反向

1.1快慢指针模板 （同向）

int i = 0;
int j = 0;
while (j < length) {
    if (...) {
        // 调整i
    }
    j++;
}

典型例题：

27. 移除元素 206. 反转链表 1.2左右指针模板 （反向）

int i = 0;
int j = len - 1;
while (i < j) {
    // 动作
    // 至少移动i和j中一个
}

典型例题：

977. 有序数组的平方 344. 反转字符串

void reverseString(char* s, int sSize) {
    int left = 0;
    int right = sSize - 1;
    while (left < right) {
        int temp = s[left];
        s[left] = s[right];
        s[right] = temp;
        left++;
        right--;
    }
}

2、滑动窗口法（双指针的高级应用）

本质上，滑动窗口也属于双指针，由于可以解决某一类题目（连续子数组、子字符串）等，单独诉述。

2.1窗口固定 2.2窗口可变 209. 长度最小的子数组 3、二分法 恰好搜索型模板 704. 二分查找 查找左边界模板 查找右边界模板 哈希表和前缀和 回溯算法