双指针算法

第一类,两个指针分别指向两个序列(归并排序)

第二类,两个指针指向一个序列(快速排序的划分的过程)

基本上双指针算法的通用模板

1
2
3
4
5
for(i = 0, j = 0; i < n; i++){//i整个扫描一遍
    while (j < i && check(i, j))//每次i更新完之后,我们要更新我们的j
        j ++;
    //根据意义do something
}

虽然循环长成这个样子,看上去是两重循环,但是每一个指针在所有循环里面总共的移动次数是不超过n的,两个指针的总共移动次数就不超过2 * n

==双指针算法最核心的性质就是可以将下面的朴素算法优化到O(n).我们运用了某些性质, 本来要枚举O(n * n)种情况,现在只需要枚举O(n)种情况==

核心思想:

1
2
for (int i = 0; i < n;  i ++)
    for (int j = 0; j < n; j ++)

时间复杂度是O(n * n)

但是所有的双指针算法,时间复杂度是O(n)的

举一个例子:输入一个字符串,然后我们要把其中的每一个单词输出出来,单词与单词之间是用一个空格隔开的.

自己的写法

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
#include <iostream>
#include <string>
using namespace std;
const int N = 80;

int main(void)
{
    // char s[N];
    // cin.getline(s, N);
    string s;
    getline(cin, s);

    // cout << s;
    int i = 0;
    while (i < s.size())
    {
        int j = i;
        //找到单词结束的位置,可能是空格,也可能是字符串s的最后一个字母的后面一个位置
        while (j < s.size() && s[j] != ' ')
            j++;
        //输出字符串s的子串从i到j(不包括j)的子串
        for (int k = i; k < j; k++)
            cout << s[k];
        cout << endl;
        //从单词结束的位置j的后面一位开始找,也就是让i  = j + 1
        i = j + 1;
    }
    return 0;
}

个人感觉:因为这都是低级的算法课,真正的高级算法都是不让你写代码,都是给你伪代码,直接让你证明这种算法的正确性,或者让你自己设计一个正确的伪代码步骤并让你证明.高级的都是考察你的数学证明,太难了.

反正我是学习低级的,因此更多的还是靠别人讲了一个遍,我背下来,遇到新题就照猫画虎的模仿然后改写,遇到不会的就背新的.然后就是我刚刚这样子,在学新课的时候,想着自己想写一遍,不求能够数学上完全相信自己是对的,知道大概意思就够了,时间不够,不如多背点稳定做出来的题目.

[!NOTE]

备注:

自己一段时间没学习,写的时候竟然只记得char s[] 的getline的写法,忘记了string s 的getline写法.查阅自己的笔记之后才会想起来,可见记笔记是一件很重要的事情.笔记如下

https://hsuwindow.vip/cshsuwindowDIY/C/grammar/C++PrimerPlusStudyNotesCh4/

char s[N] 的getline的写法记忆

1
cin.getline(s, N);

这里cin是对象,调用对象类的函数用.运算符连接起来,加上第一个参数是数组名字,第二个参数是最多读取的字符数,当然一般是你定义的数组的ArSize.最终构成了上面的写法.

string s 的getline写法记忆

1

因为string s 的写法在char s[]后面出现,因此cin.getline()的第一个参数没有重载成C++String类型的字符串,因此直接调用getline函数.(这一段是我模糊的听课的记忆,有可能是错的,但是能帮助我记忆回想就是好的).getline函数里面第一个参数是从哪里读入,当然是从键盘的标准输入流读入(我这么记得标准输入流是stdin,这里自己也可能记错了,但是能帮助自己记忆就好),所以是cin,第二个参数就是字符串 的名字s了.

y总的写法

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
#include <iostream>
#include <cstring>
using namespace std;

int main(void)
{
    char str[1000];
    gets(str);
    int n = strlen(str);
    for (int i = 0; i < n; i++)
    {
        int j = i;
        // 找到单词结束的位置,可能是空格,也可能是字符串s的最后一个字母的后面一个位置
        while (j < n && str[j] != ' ')
            j++;
        // 这道问题的具体逻辑
        // 输出i到j - 1之间的所有字符
        for (int k = i; k < j; k++)
            cout << str[k];
        cout << endl;
        // 每一次处理完一个单词之后,让i指向 j指向的那一个空格,然后根据最外层for循环的i++那么i就会指向下一个单词的首字母
        i = j;
    }
    return 0;
}

这和我们的模板基本上是对应上的,可以在

1
2
while (j < i && check(i, j))//每次i更新完之后,我们要更新我们的j
        j ++;

上面做一些小改动,然后是写这道问题的具体逻辑.(写具体逻辑的时候还是要笔和草稿纸,自己刚刚没有笔和草稿纸脑袋有非常的混乱,什么都记不清楚)

1
2
3
4
5
6
for(i = 0, j = 0; i < n; i++){//i整个扫描一遍
    while (j < i && check(i, j))//每次i更新完之后,我们要更新我们的j
        j ++;
    //根据意义do something
    // 这道问题的具体逻辑
}

模板就是为了帮助大家来节省时间.

凡是有这样==形式==的,都可以被称作双指针算法.核心思想就是可以吧本来要枚举O(n * n)种情况,枚举i , j两种循环.我们从中挖掘了某种性质,让我们利用这种性质只需要枚举O(n)种情况.凡是有这样性质的题目都可以被称作双指针算法.包括我们之前讲 的快排,或者归并排序的归并那一步,还有明天要将的kmp算法都是一个这样的问题.

看一个新的问题,就是打卡题

AcWing 799. 最长连续不重复子序列

一个自己的小技巧,就是对公差为1 的等差整数数列.求区间[a, b]或者区间[a, b)之间有多少个数字.例如0,1 ,2 就有三个数字.自己总结的公式如下

1
2
3
4
5
//记忆口诀:
//左闭右闭的时候,要不要加一取特值判断,令b = a,则b - a 等于 0,而闭区间[a, a]之间有且仅有一个数字就是a.因此左闭右闭的时候,要加一
//左闭右开的时候,令b = a,则b - a 等于 0,而左闭右开区间[a, a)之间不可能有数字,也就是数字个数是零.因此左闭右开的时候,不用加一
count([a, b]) = b - a + 1;
count([a, b)) = b - a;

自己的写法

说实话,我红温了,自己用动脑袋就头疼,以后再也不动闹了.他们的东西我果然看不懂,我是个笨蛋

check函数写不对,我开摆了,以后我动脑我就给自己一巴掌,还不赶紧去背诵自己可能会的.

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
#include <iostream>
#include <cstring>
using namespace std;
const int N = 100010;
int n;
int q[N];
bool check(int i, int j);
int main(void)
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d", &q[i]);
    // 因为一个数字组成的序列一定是不重复的,因此初始设置为1
    int maxcount = 1;
    for (int i = 0; i < n; i++)
    {
        // 左闭右闭区间[i, j]的区间里面元素数量count  = j  - i + 1,因此j = i + count - 1
        int j = i + maxcount - 1; // j 一定 >= i,这里j 指向不重复连续子序列的最后一个数字位置
        while (j < n && check(i, j))
            j++;
        // 结束的时候,在区间[i , j]里面的数字有重复的,
        // 而区间[i , j - 1]里面的数字没有重复的,也就是j指向的数字导致了重复
        // 或者是j == n

        // 有一种情况,就是假设maxcount此时等于7,然后j = i + maxcount - 1直接check等于false,那么????

        // 计算此时的curcount,没有重复的连续序列的数字个数
        int curcount = (j - 1) - i + 1;
        if (curcount > maxcount)
            maxcount = curcount;
    }
    // for (int i = 0; i < n; i++)
    //     printf("%d", q[i]);
    // cout << "maxcount = ";
    cout << maxcount << endl;
    return 0;
}
// 这里j 指向不重复连续子序列的最后一个数字位置
// 先假设这里j 一定 >= i

// 自己发现这个check函数写错了
// 然后自己发现好像可以写到里面main,更加的简化
// check检查数组里面是否有重复的数字,有则返回false,没重复则返回true
bool check(int i, int j)
{
}

涉及到找重复数字,有一篇博客

算法 - 找重复数字 （抽屉，链表环）

AcWing 800. 数组元素的目标和

AcWing 2816. 判断子序列

位运算

AcWing 801. 二进制中1的个数29601人打卡

离散化

AcWing 802. 区间和24287人打卡

区间合并

AcWing 803. 区间合并25423人打卡

DONE

==最终的记忆还是要看文字描述的思路,然后自己慢慢回忆起来代码是怎么写的.要有从精简的文字概括到复现代码的过程才能记得牢靠.==

这一节的笔记就到这里了.学完之后立马自己重新写一遍还是很有效果的.以后要一直坚持,然后复习的时间规律我之后再说.