Leetcode刷题指南

Leetcode刷题指南

1. 数据结构

1.1 数组

• 循环数组问题：把数组扩大为两倍即可，但不是真的扩大两倍，而是通过索引取模的方式

1.2 链表

链表可以通过引入虚拟头节点 ListNode *dummy = new ListNode{-1, nullptr} 来极大简化

0. **递归：**要区分基础情况和跳出情况，即可以有两种return，比如：如果链表为空，那么返回。这时候的return并非是用来跳出递归的，而是一个base情况的判断，只有最基本的（最后一层递归）会用到。一系列操作，比如反转链表之后，再return，则时候是退出递归的return，即后面每一层递归想出栈都是走的这一条return。

1. 反转链表【递归】：反转从 head->next 开始的链表，然后拼接上第一个节点。base：单节点链表

2. 反转前 n 个元素：反转从 head->next 开始的 n-1 个元素，然后拼接。base：n = 1

3. 反转 [m, n] 的元素：反转从 head->next 开始的 [m-1, n - 1] 的元素，然后拼接。base：m = 1，同上

4. 倒序输出链表：对链表进行后序遍历，（递归的base是，head==nil）

1.3 栈与队列

单调队列

有这样一类问题：如何得到一个队列中的最值？遍历，然后维护一个最值就好了。但这会有一个问题：当最值出队之后，次最值无从得知，需要再次遍历。可以参考例题：

【剑指Offer：队列最大值】，【leetcode-1438. 绝对差不超过限制的最长连续子数组（解法二）】

如何快速得到一个队列中，当前所有元素的最值呢？维护一个单调队列 queueMax，对入队元素 Value，如果 queueMax.back() > value，则直接入队，否则一直 queueMax.pop_back()，直至满足该条件。这样便可以保证：对原队列中所有元素，单调队列的队首，总是其最大值。如果原队列出队，使得最值出队，则单调队列中的下一个，仍是原队列中剩余元素的最值。

单调栈

类似的还有单调栈的问题 503. 下一个更大元素 II - 力扣（LeetCode）：给你一个数组，有什么办法返回一个数组res，使得res中存放原数组元素，其后面第一个比自己大的元素。也即利用单调栈寻找第一个大于自己的元素：

（1）数组从后往前入栈（出栈时即是顺序），如果栈顶元素小于自己，则一直出栈，直至栈顶大于自己，此时即有 $res[i]=stack.top()$ ，再把当前元素入栈。

（2）从前入栈也可以（看题解写法）。从栈里的元素的角度看：元素先入栈，如果后面碰到比它大的元素，那它就会出栈；从要入栈的元素角度看，如果我比栈顶大，那就出栈，直到栈顶比我大我再入栈。这样一来，出栈就意味着，碰到了后面第一个比自己大的元素，而留在栈里的说明目前还没有比它大的。

下面是示意图：

而我们仍需一个数组来记忆元素的下一个大哥，所以如果直接是元素入栈的话，你只是知道了2的下一个大哥是5，但是找不到2的索引，就没办法设置结果stack2.pop();数组。因此可以采取：索引入栈、pair入栈、哈希数组

索引入栈的话，即 $if(nums[i]>nums[s.top()])\to ret[s.top()]=nums[i],s.pop()$，如果大于栈顶，那就一直出栈（出的是索引），并且把出栈元素的邻近大哥（即ret）标记为待入栈元素

2. 双指针

双指针一般用于数组字串和链表，尤其是二者还有序的情况。有三种双指针：

1. 两指针：字面意义上的双指针，就是说有两个表需要遍历，你整俩指针出来
2. 左右指针：左右分为，从两端往中间同时跑，和从中间往两边（最长回文子串）
3. 快慢指针：又分为，同时出发一快一满，和速度相同，但其中一个先走（维持 k 间距）
4. 滑动窗口：[left, right) 这么个区间，不断扩大right，直至这是一个满足要求的窗口，然后缩小 left，使得此窗口为一个紧确的窗口，然后再扩大 right 搜索新的窗口，满足了再紧确，直至抵达边界。
   注意滑动窗口，要分清何为"valid window"，有时候这是一个大小不固定的，有时候又是固定大小的。

下面是一些应用：

（1）链表

• **求链表中点：**二倍速指针走到末尾，一倍速走到中点
• 求链表倒数第 k 个节点：先走 k 步的离开末尾时，后面那个距离它为 k，即倒数第 k 个
• 判断链表有无环：地球是圆的的话，快慢指针终有相遇的一天
• 求出环的入口：快慢指针相遇之时，让一个重回起点再走，再次相遇即是在入口（列一下式子就出来了）
• 求两链表的交点：
  ① 两个指针各自遍历链表。在走到链表结尾的时候（p==nullptr），进入另一个链表。这样它们会走过相同的路程，即$a+b+c$，该处即为交点。如果不相交，则走过 $m+n$ 后会有： p==q==nullptr，也是相等
  ② 把其中一个链表的尾巴和另一个的头相连，就成了判断有无环，有就找到环入口的问题
  ③ 先求出两表的长度，让长的指针先走（long - short）步，这样链表就对齐了，对齐了就好办了

（2）数组

• 数组原地删除相同元素：（有序数组）快指针在前面探路，遇到不同的赋值给slow++，这样前面的都不同
• 数组原地删除某一值：快指针在前面探路，只要不碰到 target，就赋值给 slow++
• 数组二分查找：（有序）最常见的双指针 low 和 high，或者叫 left 和 right
• 两数之和：（有序）两端开始，和大了就把大的缩点，和小了就把小的加点
• 原地反转数组：从两头开始互相交换【原地反转链表呢？>> 递归】
• 回文串判断：两头开始比较是否相等
• 求最大回文子串：从某一点或两点开始，往两边扩散求最长回文串；如此对全部元素都扩一遍，求最大值

盛水最多容器 11

题目：

​ 如下图，给你一个数组height，找出能“盛水”的最大值

分析：

​ 从两端扫一遍数组，则盛水量为：
m a x _ c o n t a i n = ( r i g h t − l e f t ) × min ⁡ { h e i g h t [ l e f t ] ,   h e i g h t [ r i g h t ] } max\_contain = (right - left)\times \min\{height[left],\ height[right]\} max_contain=(right−left)×min{height[left], height[right]}
​ 现在考虑怎么个扫描法。反正只要移动，容器的“底”必然会变小，如果移动长板，那么容器的边最多不会超过原来的短板，因为边去的是最小值，移动后小于原来的短板，则变小，移动后大于，边也不会变大，因此移动长板，必然会使容量减小。那么就移动短边。

题解：

int maxArea(vector<int>& height) {
    int l = 0, r = height.size() - 1;
    int max_contain = 0;
    while (l < r) {
        int area = min(height[l], height[r]) * (r - l);
        ans = max(max_contain, area);
        if (height[l] <= height[r])
            ++l;
        else
            --r;
    }
    return max_contain;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

3 二分法

对有序数组进行二分查找，有三种情况：只查找目标、查找目标元素序列左边界、右边界。

二分查找思想很简单，关键在一些细节：比如 right 是等于 size 还是 size-1， while 循环 $\le$ 还是 $<$，找着目标之后 right 是等于 mid 还是 mid-1。其实很好理解，只需要分清你的搜索区间是什么：

如果 $left=0,right=len-1$，那搜索区间就是闭区间 $[left,right]$，while 循环如果写$l<r$，则退出条件就是$left==right$，此时闭区间 $[left,left]$ 里面还有一个元素，有元素还退出，那肯定是要漏了，所以应该选$left\le right$，如果搜索区间为左闭右开则同理。

搜索目标的左右边界，与直接搜索目标区别在于：找到目标后不是直接返回，而是继续缩小区间。搜元素是命中时退出，搜边界一定是 left > right 退出。那么：

1. 如果存在目标元素，则到最后一定是 $left\to target,right\to target-1$，只需 return nums[left];
2. 如果目标不存在，则 KaTeX parse error: Undefined control sequence: \or at position 25: … nums.size()\ \̲o̲r̲\ right\rarr -1

模板如下

int left_bound(int nums[], int target) {
    int left = 0, right = nums.length - 1;	 //（0）
    while (left <= right) { 				//（1）
        // 防止加法溢出
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] == target) {
            // 别返回，锁定左侧边界
            right = mid - 1;				//（2）
        }
    }
    // 判断 target 是否存在于 nums 中
    // 此时 target ⽐所有数都大/小，返回 -1
    if (left == nums.length || right == -1)	 //（3）
        return -1;
    return left;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

下面是一些应用：

• 查找峰值：【无序】也可以二分，即先比较mid和两边的元素大小，如果mid在上坡，则说明峰值在前方，left = mid + 1，如果在下坡，说明在后方，right = mid - 1，如果直接命中，则返回

4 贪心 & 动态规划

4.1 线性 DP

1 斐波那契数列

$$dp[i]=dp[i-1]+dp[i-2]\stackrel{\text{优化}}{\Rightarrow }r=p+q$$

矩阵快速幂

其实斐波那契数列还有一个O(log n) 复杂度的做法：用矩阵快速幂，转换成求这么个矩阵的 n 次幂
$$
\begin{pmatrix}
F_{n+1} & F_n
\end{pmatrix}

$$\begin{pmatrix} F_{n} & F_{n-1} \end{pmatrix}$$
$$\begin{pmatrix} 1 & 1 \ 1 & 0 \end{pmatrix}$$

$$\begin{pmatrix} F_{1} & F_{0} \end{pmatrix}$$
{ $$\begin{pmatrix} 1 & 1 \ 1 & 0 \end{pmatrix}$$ }^n
$$
而矩阵快速幂，跟一般的快速幂都是类似的，都是将幂分解为二进制表示，$a^n=a^{2^i}{a}^{2^{i-1}}\cdots a^0$，然后运用累乘的思想。

typedef vector<vector<double>> Matrix;
Matrix MatrixMultiply(const Matrix& A, const Matrix& B); // 自行实现矩阵相乘
Matrix MatrixPower(const Matrix& A, const int n){
    // A^13 = A^8 * A^4 * A^1
    int size = A.size();
    // 创建一个结果矩阵，先初始化为 单位矩阵
    Matrix result(size, vector<int>(size, 0));
    for (int i = 0; i < size; i++) {
        result[i][i] = 1;
    }
    Matrix base = A;
    while (n > 0) {
        // 如果该位上为 1，说明有 2^i 这一项，则乘上
        if (n & 1) {
            result = multiply(result, base);
        }
        // 将base自乘，用于下一位的计算
        base = MatrixMultiply(base, base);
        // 右移一位
        n >>= 1;
    }
    return result;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

O(log n) 的时间复杂度就是在base = MatrixMultiply(base, base); 这一步来的。因为将矩阵的幂换成了如干个 $2^i$ 个幂相乘，最高不会超过 $2^{log(n)}$ 次，而且每个更高级的幂都是用低级的平方上去的，不会有额外复杂度

2 BST 种类

求由 n 个节点构成的 二叉搜索树 有多少种？

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/繁依Fanyi0/article/detail/632915