基础算法

常用技巧

枚举右，维护左（用哈希表查找）
典型例题：1.两数之和

刚做了一个类似题目2342.数位和相等数对的最大和
题解中最巧的是用a[82]来查找我们需要的数。这种妙解估计得这类题目刷多了才有感觉。

排序

  1. 冒泡排序
    通过交换相邻数将每次的最大（或最小）数沉入底下，以此达到排序的作用
  2. 快速排序
    基本原理为分治和递归。其基本思路是先通过一个基准值（以下称为key），将数组中比key大的数放在右边，比key小的数放在左边。key左右两边可以看做是两个新的需要排列的数组，而左边数组要小于右边数组。对这两个数组进行同样的操作，不断递归即可得到一个排序正确的数组，

一开始我打算才用左右指针交换的思路，但细想不对
以下是错误实例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
int partition(int *a,int left,int right){//left指向数组最左端，right指向数组最右端
    //基准值取第一个数
    int key=a[left];
    int set=left; 

    //当左指针在右指针左边且不重合时
    while(left<right){ 
        //找到第一个比基准值小的数
        while(left<right){
            if(a[left]>=key){
                left++;
            }else{
                break;
            }
        }
        //若没找到left会与right值相等

        if(left==right){
            break;
        }

        //找到第一个比基准值大的数
        while(left<right){
            if(a[right]<=key){
                right--;
            }else{
                break;
            }
        }
        //若没找到right会和left值相等
        if(right==left){
            break;
        }

        //交换这两个数的位置
        swap(a[left],a[right]);
    }
    //循环结束后我们可以发现left和right的变化是线性的，意味left左边的数一定key大，right右边的数一定比key小。
    //与基准数位置交换
    swap(a[set],a[left]);//可以得知该位置即是基准数在排序后数组的位置。

    return left //返回基准数所在位置
}

明白这个方法前最主要的是要明白left和right相等时，这个位置数的大小关系在全局中是怎么样的。
二者相等无非就是两种情况：

  1. left没有找到第一个比基准值小的数。意味着left的左边数是要比基准数大的。而right所在数存在两种情况，一是已经经过一次交换的，而是没有经过交换的。经过交换还好，若没有经过交换，该数大于基准数无事发生，若小于基准数，bome，显然有问题。
  2. right没有找到第一个比基准数大的数。此时与上者不同，right所在数一定比基准数小，bome。

问题在于最后的基准数并没有放在它应该在的位置。
交换并没有解决问题。

以下是另一种思路
不妨将最开始的基准数所在位置看做是一个坑位，我们所要做的就是填坑。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
void quickSort(int *a,int left,int right){
    if (left>=right){
        return;
    }
    int set=partition(a,left,right);
    quickSort(a,left,set-1);
    quickSort(a,set+1,right);
}

int partition(int *a,int left,int right){
    if(left==right){
        return 
    }
    int key=a[left];
    int set=left;
    //产生第一个坑位，此时要填入比基准数大的数
    while(left<right){
        //找到第一个比基准数大的数
        while(left<right){
            if(a[right]<=key){
                right--;
            }else{
                break;
            }
        }
        //要是没找到怎么办？
        if(left==right){
            break;
        }
        //找到另说，开始填坑
        a[set]=a[right]
        set=right;
        //产生新的坑，位置为right，此时要填入比基准数小的数
        while(left<right){
            if(a[left]>=key){
                left++;
            }else{
                break;
            }
        }
        //要是没找到怎么办？
        if(left==right){
            break;
        }
        //找到另说
        a[set]=a[left]
        set=left;

        //以此循环
    }
    a[set]=key
    return set
}

这个算是最好懂的思路，其他的方法或多或少有点问题。

倒还是有直接一个函数写完的，刚看到：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
//这里是从小往大排序
void quickSort(int *a,int left,int right){
    int i = left;
    int j = right;
    if(i>=j){
        return;
    }
    //temp作为基准值
    int temp = a[left];
    while(i!=j){
        //从右往左找到一个比基准数小的数
        while(a[j]>=temp && i<j){
            j--;
        }
        //从左往右找到一个比基准数大的数
        while(a[i]<=temp && i<j){
            i++;
        }
        if(i<j){
            swap(a[i],a[j]);
        }
    }
    
    //额，思路与我第一个一致，问题是a[i]有没有可能是比基准数大。
    swap(a[left],a[i]);
    quickSort(a,low,i-1);
    quickSort(a,i+1,high);
}

找到了一个正确的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int Paritition1(int A[], int low, int high) {
    int pivot = A[low];
    while (low < high) {
        while (low < high && A[high] >= pivot) {
            --high;
        }
        A[low] = A[high];
        while (low < high && A[low] <= pivot) {
            ++low;
        }
        A[high] = A[low];
    }
    A[low] = pivot;
    return low;
}

void QuickSort(int A[], int low, int high) //快排母函数
{
    if (low < high) {
        int pivot = Paritition1(A, low, high);
        QuickSort(A, low, pivot - 1);
        QuickSort(A, pivot + 1, high);
    }
}

本质上还是填坑法，只不过代码写得要比我的要精炼。
看了不少快排代码，发现不少有问题的代码都是采用的交换的思路（樂）
归根到底还是一知半解出来瞎晃悠导致的。

优先队列

鉴于leetcode中这种类型出的题十分得多，写一个专题总结一下
以c++为例，priority_queue不具有传统队列中的“先进先出”特性，取而代之的是“优先级高者先出”。换言之传统队列事实上就是一个以“进入队列的先后”作为优先级的priority_queue。如果了解“堆”的话，很容易发现两者很相似。事实上，优先队列就是由堆实现的。
c++中priority_queue的定义是：

1
template <class T, class Container = vector<T>,  class Compare = less<typename Container::value_type> > class priority_queue;

其中第二个参数指的是储存这些数据的容器，可以是vector,deque,不能是list
第三个参数指的是比较函数（就是所谓的优先级）。

我们可以通过重写仿函数的方式来支持自定义数据类型，例子以后再补。

滑动窗口

这个东西基本就是对左右指针进行操作，理论上并不难。
关键就是应用问题。
leetcode-2024 考试的最大烦恼
某种意义上滑动窗口可以看做是双指针的特殊应用形式，我们需要把目光集中到双指针中间的区域。
有一个题解说的好：“双指针的一贯套路就是枚举一个指针，求出符合的另一个指针。不然两个指针都在变化，很容易思路混乱，导致重复情况。”
这大概就是这种思路的固定套路。这个题嘛，我们需要了解为什么滑动窗口可以在O(n)情况下解决这个问题。该问题转化成数学问题就是某一个子串中”T”或”F”的数量不得超过k。滑动窗口其实就是在统计”T””F”数量同时，看看在左指针固定的情况下，右指针最大能到哪。左指针跳过的那些字符在某种程度上算是一种剪枝。基于此理解下完成代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
public:
    int maxConsecutiveAnswers(string answerKey, int k) {
        int n=answerKey.size();
        int left=0;
        int right=0;
        int numT=0;
        int numF=0;
        int ans=1;
        //以左指针为锚点，找出对应的右指针
        while(right<n && left<=right){
            //左指针不动，找出右指针的最大位置
            while(right<n){
                if(answerKey[right]=='T'){
                    numT++;
                }else numF++;
                right++;
                //找出后开始结算
                if(numT>k && numF>k){
                    ans=max(ans,right-left-1);
                    break;
                }
            }
            //如果没找出直接滑倒底；
            if(numT>k && numF>k){}
            else ans=max(ans,right-left);
            //左指针剪枝
            while(right<n && left<=right){
                if(numT>k && numF>k){
                    if(answerKey[left]=='T'){
                        numT--;
                    }else numF--;
                    left++;
                }else{
                    break;
                }
            }
        }
        return ans;
    }
};

代码写得有些乱。
额，学习一下大佬(灵茶山艾府)的代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int maxConsecutiveAnswers(string answerKey, int k) {
        int ans = 0, left = 0, cnt[2]{};
        for (int right = 0; right < answerKey.length(); right++) {
            cnt[answerKey[right] >> 1 & 1]++;
            while (cnt[0] > k && cnt[1] > k) {
                cnt[answerKey[left++] >> 1 & 1]--;
            }
            ans = max(ans, right - left + 1);
        }
        return ans;
    }
};

。。。就不是面向新手的

注意到很多题解都提到了单调性，我自己过去找视频理解了一下，大概就是：
在某一端点固定的情况下，另一端点必然可以由由远及近地逼近这个情况的最优解。这个过程中长度是单调递减的。
这就不难理解大佬的思路，枚举右端点下的最优长度，对结果不断max，这个过程中左端点是可以平滑的移动的。相比较下我的解法不成体系，更像是凑出来的。

定长滑动窗口

一般而言基础的定长滑动窗口算是极为简单了，有些能采用定长滑动窗口的题需要采用一定的技巧。
leetcode-1888
这个题因为存在一个：类型 1 ：删除 字符串 s 的第一个字符并将它 添加 到字符串结尾。
不免会考虑到环这种。另外这个题若能注意到“01”和“10”情况下的互补关系则事半功倍。

求最大最长问题

例题可以参考一开始说的那个，算是这类题目的典型题

求最小最短问题

与上同理，主思路一样，求解过程中都具备由大到小的单调性。

二分算法

对于我而言，二分算法最为重要的是理解左右指针的意义。指针左边代表什么，指针右边代表什么，以及指针相遇又代表什么，弄清楚这个基本就能弄清二分算法。
一般而言，这种算法思路无非划定解的范围，然后根据解的某一单调性暴力求解。

二分答案

最小化最大值

最大化最小值

第k小

这种标题一般都认为这要用堆要解决（优先队列也行），属于是孰能生巧了。

单调栈

单调栈顾名思义是指栈中的元素是单调递减或递增。
需要注意的是：每个元素都一定入栈。
其核心思想是：及时去掉无用数据，保证栈中数据有序。
以leetcode-739 每日温度为例
题目要求找到一个数最右边第一个比它大的数，我们不妨先心算其中第一个案例，体会其数据的变化过程：

1
temperatures = [73,74,75,71,69,72,76,73]

对于73而言，74比它大，于后面数组元素而言，73已经没啥作用，此时可以在答案数组中写下
1
ans.pushback(1);

对于75，与上同理；
对于71，虽然暂时比75小，但考虑到对后来元素有作用，应该保留
69同理；
72,76同第一个73的情况。
细细观察，我们不妨想象一个从栈顶到栈底单调递增的单调栈。
73入栈，74替掉它，75再替，71入栈，69入栈，72入栈（替掉69,71），76亦然…
数据的有用程度的变化过程刚好与单调栈类似。因此我们可以写代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        stack<int> a;
        int n=temperatures.size();
        vector<int> ans(n);
        int cur=temperatures[0];
        for(int i=0;i<n;i++){
            while(!a.empty()&& temperatures[i]>temperatures[a.top()]){
                int previousIndex = a.top();
                ans[previousIndex]=i-previousIndex;
                a.pop();
            }
            a.push(i);
        }
        return ans;
    }
};

对于该栈中停留的每一个元素而言，它们只是暂时没有找到右边第一个比它们大的数，它们从栈底到栈顶成单调递减的趋势。它们出栈意味着那个让它们出栈的元素就是右边第一个比它们大的数。明白这一点就能明白为啥这题能用单调栈。
说实话，人脑在模拟的时候可能采取的更多的是暴力n*n的方式，这导致很多人一开始不能理解单调栈的做法。如果要在实际中作出的话O(n)的方法，少不了一番思索。可能对于我，思考遍历过程中元素的是否有用可能对做出这种方法更有用处一些。

矩形系列

字典序最小

贡献法

DP

动态规划（Dynamic Programming,简称DP）

背包

选与不选问题。
0-1背包问题

状态机

划分

区间

状压

数位

数据结构优化

树形

博弈

概率期望

图论

DFS

单纯的dfs不能解决一些对时间有着高要求的问题，在python中我们可以使用@cache装饰器来进行记忆化搜索，这里主要记录在C++中如何解决记忆化问题。一般而言dfs函数某些状态下的结果被反复使用时我们通常考虑记忆化搜索来进行剪枝。c++没有@cache这个东西（目前我也没见到类似的东西），我们一般采用递推的方式来记忆化。
例如leetcode-2915

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    int solve(vector<int>& nums,int set,int sum,int &target,int length){

        int n=nums.size();
        
        //上一个位置选完后
        if(sum>target){
            return -1;
        }
        if(sum==target){
            return length;
        }
        if(set==nums.size()){
            return -1;
        }
        //只留下了比target小的，以及长度未到标的。      
        //当前位置选了
        int a=solve(nums,set+1,sum+nums[set],target,length+1);
        //不选
        int b=solve(nums,set+1,sum,target,length);

        return max(a,b);

    }
    int lengthOfLongestSubsequence(vector<int>& nums, int target) {
        return solve(nums,0,0,target,0);
    }
};

这是我时间上死活过不去的代码。

这是我采用递推方式的代码

BFS

拓扑排序

最短路

最小生成树

二分图

基环树

欧拉路径