YXC 算法基础笔记（三）

算法基础的内容就到这里结束啦，新的内容也很关键，但是大概率会去重温c++，应该会停更一段时间

双指针算法

双指针算法是一个用的很频繁的算法，算法有的时候其实并不是那么严苛，有的时候算法更多的是一种思想。

for (i = 0, j = 0; i < n; i ++)
{
    while (j < i && check(i, j)) j ++;
    // 每道题目的具体逻辑
}

上面就是双指针算法的常用思想。本质上，利用双指针，节约了时间效率，两个指针都最多从头到尾跑了一次。

下面举一个经典的例子（双指针算法不只是维持两个窗口）

对一串字符串进行截取

#include <iostream>
#include <string.h>

using namespace std;

int main() // 将字符串中的单词按行输出
{
    char str[1000];
    char ch;

    fgets(str, 1000, stdin);

    int n = strlen(str);

    for (int i = 0; str[i]; i ++)
    {
        int j = i;
        while (j < n && str[j] != ' ') j ++;

        // 输出单词
        for (int k = i; k < j; k ++) cout << str[k];
        cout << endl;

        i = j; // i跳跃到空格处，下次循环i就是新的单词的开始
    }

    return 0;
}

这是比较简单的双指针算法、

再一个经典题型是，找到最长的非重复连续子序列。有点像是维护一个滑动窗口。

#include <iostream>

using namespace std;

const int N = 100010;

int q[N], tmp[N];

int main() // 输出一串序列中，最长不连续子串的大小
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &q[i]);
    }

    int res = 0;
    for (int i = 0, j = 0; i < n; i++)
    {
        tmp[q[i]] ++;
        while (tmp[q[i]] > 1)
        {
            tmp[q[j]] --;
            j ++;
        }

        res = max(res, i - j + 1);
    }

    cout << res << endl;

    return 0;
}

这一道题中维持i，j两个指针，利用额外的数组空间来判断序列中是否出现重复元素。每次i指针移动后，要更新j指针的状态，确保在i与j之间的序列没有重复元素，然后更新最长字串的大小。

相比于暴力枚举，因为i，j之间有单调关系，所以能够利用双指针移动来减少时间复杂度。

位运算

比如说：n的二进制表示中第k位是多少

解决思想：

1. 先把第k位移到最后一位 n>>k
2. 看各位是几 x & 1

#include <iostream>

using namespace std;

int main()
{
    int n = 10;

    for (int k = 3, k >= 0; k --)
    {
        cout << (n >> k & 1);
    }

    return 0;
}

方法和思路都很简单，需要注意的是一次要移多少位，以及按位与操作来判断最后一位是多少。

lowbit（）是树状数组的基本操作，作用是返回x的最后一位1，比如说1010000，返回的就是10000；1010返回的就是10。

lowbit（x）从实现上说就是 x&-x。首先从c++来说，一个整数的负数就是其补码，即原数取反加1，所以-x的二进制表现，和x取反加以的二进制表示一样。

x&-x = x&(~x + 1)

举个例子

给定一个长度为n的数列，请你求出数列中每个数

 #include <iostream>

using namespace std;

int lowbit(int x)
{
    return x & -x;
}

int main()
{
    int n;
    cin >> n;
    while (n --)
    {
        int x;
        cin >> x;

        int res = 0;
        while (x) x -= lowbit(x), res ++; // 每次减去x的最后一位1

        cout << res << ' ';
    }

    return 0;
}

需要注意的地方是，如何找到x的最后一位1，每次进行更新操作。

整数离散化

离散化是指：把在某个很大范围内的一些数，映射到一个更短的范围内

需要注意两个问题

1. 原数组中可能有重复元素 所以需要额外去重
2. 如何算出a[i]离散化后的值

假定有一个无限长的数轴，数轴上每个坐标上的数都是 0。

现在，我们首先进行 n次操作，每次操作将某一位置 x 上的数加 c。

接下来，进行 m 次询问，每个询问包含两个整数 l 和 r，你需要求出在区间 [l,r][l,r] 之间的所有数的和。

如果数轴是有限的，并且还比较小的话，可以使用前缀和算法来进行计算。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int N = 300010;

typedef pair<int, int> PII;

int n, m;
int a[N], s[N];

vector<int> alls;
vector<PII> add, query;

// 这是一个二分的板子
int find(int x)
{
    int l = 0, r = alls.size() - 1;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (alls[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return r + 1;
}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i ++)
    {
        int x, c;
        cin >> x >> c;
        add.push_back({x, c});

        alls.push_back(x);
    }

    for (int i = 0; i < m; i ++)
    {
        int l, r;
        cin >> l >> r;
        query.push_back({l, r});

        alls.push_back(l);
        alls.push_back(r);
    }

    // 去重
    sort(alls.begin(), alls.end());
    alls.erase(unique(alls.begin(), alls.end()), alls.end());


    for (auto item : add)
    {
        int x = find(item.first);
        a[x] += item.second;
    }

    // 预处理前缀和
    for (int i = 1; i <= alls.size(); i ++)
    {
        s[i] = s[i - 1] + a[i];
    }

    for (auto item : query)
    {
        int l = find(item.first), r = find(item.second);
        cout << s[r] - s[l - 1] << endl;
    }

    return 0;
}

• unique()函数的实现其实类似于双指针算法

vector<int>::iterator unique(vector<int>& a)
{
    int j = 0;
    for (int i = 0; i < a.size(); i ++)
    {
        if (!i || a[i] != a[i - 1])
            a[j ++ ] = a[i]; // a[0] ~ a[j - 1] 所有a中不重复的数
    }

    return a.begin() + j;
}

区间合并

类似于集合中的合并

给定 n个区间 [l,r]，要求合并所有有交集的区间。

注意如果在端点处相交，也算有交集。

输出合并完成后的区间个数。

例如：[1,3][1,3] 和 [2,6][2,6] 可以合并为一个区间 [1,6][1,6]。

• 按区间左端点排序，然后指针遍历每个区间端点
• 分三种情况考虑区间是否合并，指针该怎么移动

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
const int N = 100010;

typedef pair<int, int> PII; // pair是什么东西，后续补一篇文档

int n;
vector<PII> segs; 

void merge(vector<PII>& segs)
{
    vector<PII> res;

    sort(segs.begin(), segs.end());

    int st = -2e9, ed = -2e9; // 这个区间也有点东西
    for (auto seg : segs)
        if (ed < seg.first)
        {
            if (st != -2e9) res.push_back({st, ed});
            st = seg.first, ed = seg.second;
        }
            else ed = max(ed, seg.second);

    if (st != -2e9) res.push_back({st, ed});

    segs = res;
}

int main()
{
    cin >> n;

    for (int i = 0; i < n; i ++)
    {
        int l, r;
        cin >> l >> r;
        segs.push_back({l, r});
    }

    merge(segs);

    cout << segs.size() << endl;

    return 0;

}