基础算法

• 基础算法合集

  • 1. 一些排序算法

    • 1. 快排

      • 快排扩展-数组中第k个数

    • 2. 归并排序

      • 归并排序扩展-求数组中逆序对的个数

        • 方法2：树状数组

  • 2. 常见的区间问题

    • 1. 区间合并

    • 2. 区间选点

    • 3. 最大不相交区间数量

    • 4. 区间分组

  • 3. 常见位运算技巧

  • 4. 滑动窗口合集

    • 1. 固定长度的滑动窗口

    • 2. 可变长度的滑动窗口

基础算法合集

常见但是没法归类的一些东西的整理

1. 一些排序算法

会让你手撕的就两个 一个快排 一个归并排序

边界问题好好记一下 撕错了就太丢脸了

1. 快排

void quick_sort(vector<int>& q, int l, int r)
{
    if(l >= r) return;
    int i = l - 1, j = r + 1, x = q[l + r >> 1];
    while(i < j)
    {
        do i ++; while(q[i] < x);
        do j --; while(q[j] > x);
        if(i < j) swap(q[i], q[j]);
    }
    quick_sort(q, l, j);
    quick_sort(q, j + 1, r);
}

快排扩展-数组中第k个数

快排：

• 找到分界点

• 分成两个区间并调整

• 递归排序左边/递归排序右边

这里我们找第K个数，无需排序所有 只要找到一边就可以了

判断依据

• K <= sl : 递归left

• K > sl : 递归right K = K - sl;

int quick_select(vector<int>& q, int l, int r, int k)
{
    if(l == r) return q[l];
    int i = l - 1, j = r + 1, x = q[l + r >> 1];
    while(i < j)
    {
        do i++; while(q[i] < x);
        do j--; while(q[j] > x);
        if(i < j) swap(q[i], q[j]);
    }
    // 这里不再是递归两边了
    int sl = j - l + 1;
    if(k <= sl)
        return quick_select(q, l, j, k);
    else return quick_select(q, j + 1, r, k - sl);
}

2. 归并排序

归排:

• 确定分界点

• 先递归处理左右两边

• 把两个有序数组合二为一

void merge_sort(vector<int>& q, int l, int r)
{
    if(l >= r) return;
    int mid = l + r >> 1;
    merge_sort(q, l, mid);
    merge_sort(q, mid + 1, r);
    vector<int> tmp;
    int k = 0, i = l, j = mid + 1;
    while(i <= mid && j <= r)
        if(q[i] <= q[j]) tmp.push_back(q[i++]);
        else tmp.push_back(q[j++]);
    while(i <= mid) tmp.push_back(q[i++]);
    while(j <= r) tmp.push_back(q[j++]);
    // 贴到原数组中
    for(int i = l, j = 0; i <= r; i++, j++) q[i] = tmp[j];
}

归并排序扩展-求数组中逆序对的个数

左半边的逆序对 + 右半边的逆序对 + 交叉的逆序对

交叉的逆序对 左右两边分别排序 不影响其数量

这样就沿用归并排序的结构 当q[i] > q[j]的时候 q[i] 和 q[i]后面的数肯定都比q[j]大

所以直接加上 mid - i + 1 就可以了

class Solution {
public:
    int reversePairs(vector<int>& nums) {
        return merge_sort(nums, 0, nums.size() - 1);
    }
    int merge_sort(vector<int>& q, int l, int r)
    {
        if(l >= r) return 0;
        int mid = l + r >> 1;
        int res = merge_sort(q, l, mid) + merge_sort(q, mid + 1, r);
        // 归并
        int i = l, j = mid + 1;
        vector<int> tmp;
        while(i <= mid && j <= r)
        {
            if(q[i] <= q[j]) tmp.push_back(q[i++]);
            else
            {
                res += mid - i + 1; // i 后面的都是逆序 因为q[i] 后面的数比q[i]大 同样也比 q[j] 大
                tmp.push_back(q[j++]);
            }
        }
        while(i <= mid) tmp.push_back(q[i++]);
        while(j <= r)   tmp.push_back(q[j++]);
        // 赋值回去
        for(int i = 0, j = l; i < tmp.size(); i++, j++)
            q[j] = tmp[i];
        return res;
    }
};

方法2：树状数组

树状数组可以用来求:左边/右边比当前元素大/小的个数

怎么做呢 就是拿值当下标，每次出现就给其加1，这样区间查询就可以查到比当前元素大 or 小的和：即出现次数之和

当然了 由于数据可能很大 这里要保序离散化

// 保序离散化
    vector<int> alls = nums;
    sort(alls.begin(), alls.end());
    alls.erase(unique(alls.begin(), alls.end()), alls.end());
    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; // 记得是加1！
    }

树状数组的几个操作

class Solution {
public:
    int n;
    // 离散化
    vector<int> tree, alls;
    int lowbit(int i)
    {
        return i & (-i);
    }
    void update(int i, int val)
    {
        while(i <= n)
        {
            tree[i] += val;
            i += lowbit(i);
        }
    }
    int query(int i)
    {
        int sum = 0;
        while(i > 0)
        {
            sum += tree[i];
            i -= lowbit(i);
        }
        return sum;
    }
    int find(int x) // 找到第一个大于等于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; // 映射到1, 2, ...n
    }
    int reversePairs(vector<int>& nums) {
        n = nums.size();
        tree = vector<int>(n + 10);
        // 1. 离散化
        alls = nums;
        sort(alls.begin(), alls.end());
        alls.erase(unique(alls.begin(), alls.end()), alls.end());
        int res = 0;
        for(int x : nums)
        {
            int y = find(x);
            res += query(n) - query(y);
            update(y, 1);
        }
        return res;
    }
};

2. 常见的区间问题

区间问题基本都是贪心来搞的 常见的有一下几个

1. 区间合并

按左端点排序 然后遍历区间 如果ed 和新区间的起点分开的话, 就更新合并结果;

看代码就懂了

注意最后可能还剩下一个区间{st, ed} 没有加进去

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;
}

除了用pair存之外，二维vector默认也是按照第一个元素排序的 所以不用担心

2. 区间选点

在数轴上选择尽可能少的点, 使得每个区间内至少包含一个选出的点，输出选择的点的最少数量 「请注意：位于区间端点上的点也算在区间内」

方法：

• 按照区间右端点排序

• 从前往后以此枚举每个区间的右端点：如果当前取件中已经包含这个右端点 直接pass 否则选择当前区间的右端点

struct Interval{
    int l, r;
    bool operator<(const Interval& w) const{
        return r < w.r;
    }
}intervals[N];

int solution()
{
    sort(intervals, intervals + n);
    int res = 0, ed = -2e9;
    for(int i = 0; i < n; i++)
    {
        int l = intervals[i].l, r = intervals[i].r;
        if(ed >= l) continue;
        else
        {
            ed = r;
            res += 1;
        }
    }
    return res;
}

3. 最大不相交区间数量

选择区间之间互不相交（包括端点）

和上面的题是一样的

4. 区间分组

给定区间，请你将这些区间分成若干组，使得每组内部的区间两两之间(包括端点) 没有交集，并使得组数尽可能小

方法：

• 按照做端点从小到大排序

• 从前往后处理每个区间 判断能否放入某个现有的组 （记录组内端点最大值）

• 不能 -> 开新组

找到最小的组：优先队列存右端点

struct Interval{
    int l, r;
    bool operator<(const Interval& w) const
    {
        return l < w.l;
    }
}intervals[N]

int solution()
{
    sort(intervals, intervals + n);
    priority_queue<int, vector<int>, greater<int>> heap;
    for(int i = 0; i < n; i++)
    {
        int l = intervals[i].l, r = intervals[i].r;
        if(heap.empty() || heap.top() >= l)
        {
            heap.push(r)
        }
        else {
            heap.pop();
            heap.push(r);
        }
    }
    return heap.size();
}

3. 常见位运算技巧

常见的一些和 不太常见的一些位运算：

lowbit(x) = i & (-i) 找到最近的1 并扣出来 i & (i - 1) 删除最近的1 i >> k & 1 判断i的第k位是不是1 (注意这里不用写括号 & 的优先级会低一些)

不太常见但是要记的：

• 数组中出现一次 剩下的元素都出现三次

本来觉得没啥但是ms前两天考了

one = (one ^ x) & (~two);
two = (two ^ x) & (~one);

• 取奇数位/ 取偶数位 取奇数位：x & 0xAAAA 取偶数位：x & 0x5555

• 奇偶位对换 ((x & 0xAAAA) >> 1) | ((x & 0x5555) << 1)

4. 滑动窗口合集

滑动窗口分为两种 固定长度的滑动窗口和长度可变的滑动窗口

1. 固定长度的滑动窗口

2. 可变长度的滑动窗口