1.基础算法

第一章 排序

1.1 冒泡排序

1.2 归并排序

1.3 快速排序

思路:

Basic Case: 当前区间没有值或只有一个值,就直接返回

• 确定分界值: 选中间,不要问,问就是这样快,没理由,解释太烦
• 调整范围:
  • ①两个指针在越界位置
  • ②左侧只要满足小于x, 就i++;右侧只要满足大于x,就j–
  • ③i会在大于x的地方停下,j会在小于x的地方停下,此时只要i<j满足大循环的条件就交换
• 递归处理左右两端: j最终会在中点位置停下?对的,会在当前区间的中点位置停下,so接下来,继续递归 quick_sort(l, j); quick_sort(j + 1, r);这两段

代码:

• 解释版本
• 模板版本

void quick_sort(int l, int r) {
    if (l >= r) return;						//Basic Case: 当前区间没有值或只有一个值,就直接返回
	int x = arr[l+r>>1];					//确定分界值: 选中间,不要问,问就是这样快,没理由,解释太烦
    int i = l - 1, j = r + 1; 				//①两个指针在越界位置
    while (i < j) {
        do i++; while (arr[i] < x);			//②左侧只要满足小于x, 就i++;
        do j--; while (arr[j] > x);			//②右侧只要满足大于x,就j--
        if (i < j) swap(arr[i], arr[j]);	//③i会在大于x的地方停下,j会在小于x的地方停下,此时只要i<j满足大循环的条件就交换
    }
    quick_sort(l, j); quick_sort(j + 1, r);	//递归处理左右两端: j最终会在中点位置停下?对的,会在当前区间的中点位置停下,
											//so接下来,继续递归 quick_sort(l, j); quick_sort(j + 1, r);这两段
}

void quick_sort(int l, int r) {
    if (l >= r) return;

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

注意:

1. +和>>谁会先算: 加法!
2. 这里中间的x是值,是用于 比较的值,不是位置,归并中的分界是点,是个pos
3. 天坑 2023年9月12日15:46:32: 以下两种快排函数哪个正确,另一个为什么不正确

• 代码一
• 代码二
• 揭晓答案

void quick_sort(int l, int r) {
    if (r <= l) return;

    int i = l - 1, j = r + 1;
    int mid = arr[l + r >> 1];
    while (i < j) {
        do
            i++;
        while (arr[i] < mid);
        do
            j--;
        while (arr[j] > mid);
        if (i < j) swap(arr[i], arr[j]);
    }
    quick_sort(l, j);
    quick_sort(j + 1, r);
}

void quick_sort(int l, int r) {
    if (r <= l) return;

    int i = l - 1, j = r + 1;
    int mid =l + r >> 1;
    while (i < j) {
        do
            i++;
        while (arr[i] < arr[mid]);
        do
            j--;
        while (arr[j] > arr[mid]);
        if (i < j) swap(arr[i], arr[j]);
    }
    quick_sort(l, j);
    quick_sort(j + 1, r);
}

第一个正确,第二个错误:
Q: 啊,不对吗?我第二个也在比较值呀,你看我里面用的都是arr[mid]呀,我没有在比较索引呀
A: 第二个函数可能会出现问题。问题在于 mid 的计算方式。在第二个函数中，mid 被计算为 (l + r) >> 1，这是中间索引。然后在 while 循环中，你使用 arr[mid] 作为比较的基准值。但是，在循环过程中，如果 arr[i] 和 arr[j] 发生了交换，那么 arr[mid] 的值可能会改变。这就可能导致排序过程出现错误。所以，为了避免这种情况，你可以像第一个函数那样，在进入循环之前就确定好 mid 的值。这样即使 arr[i] 和 arr[j] 发生了交换，mid 的值也不会改变，可以保证排序过程的正确性。

心得:

• 2023年9月1日17:34:26

2023年9月1日17:34:26:
嗯,基础的不弄好,dp是真的弄不好!

每日一题:

• 2023年9月12日15:33:32

2023年9月12日15:33:32:
WA  要引起重视,昨天让你写个快排,你都写不出来,
错误: `int mid = i + j >> 1;  // l+r>>1;` 你觉得应该不
正确: `int x = arr[l+r>>1];`  要引起重视,下次再WA,或让你手写有误的话,(罚跑一圈哈) 
~~不过有要表扬的 ,至少记住了是比较值比是比较下标,还是可以的~~不对,不能表扬,有误!!!! 看注意的第4点

第二章 二分

2.1 二分查找

第三章 高精度

3.1 高精度加法

3.2 高精度减法

3.3 高精度乘法

3.4 高精度除法

第四章 前缀和与差分

4.1 一维前缀和

4.2 二维前缀和

4.3 一维差分

4.4 二维差分

第五章 双指针

5.1 最长连续不重复子序列

5.2 数组元素的目标和

第六章 位运算

6.1 二进制中1的个数

第七章 离散化

7.1 区间和

第八章 区间合并

8.1 区间合并