AcWing算法基础课笔记 ------ 第一章 基础算法
这篇博客主要记录了学习AcWing算法基础课第一章节的知识点笔记内容以及自己在学习过程中遇到的一些常见错误案例分析。整体来看，在这一章节的学习中收获颇丰：深入理解了二分查找的标准框架；掌握了大数运算中的加减乘除操作；明确了前缀和数组中第0号位置不作为存储空间的原因及其合理性的背后逻辑；并深刻反思了在应用快速排序算法时出现的一些常见问题及解决方法。
文章目录
-
一. 二分
-
- 1. 数的范围
-
二. 高精度
-
- 1. 加法
- 2. 减法
- 3. 乘法
- 4. 除法
-
三，前缀和与差分
-
- 1. 一维前缀和
- 2. 二维前缀和
- 3. 一维差分
- 4. 二维差分
-
四. 双指针
-
- 1. 数组元素的目标和
-
五. 位运算
-
- 1. 统计出二进制中1的个数
-
六. 区间合并
-
七. qsort 排序二维数组
一. 二分
二分法之前我学习过很多次,但这个课程讲解确实让我对二分有了全新的认识,真的是豁然开朗啊. 在学习过程中,以前我在解决二分题解时经常会遇到各种各样的二分方法:
计算mid值为left与right之和的一半。
计算mid值为left加right加一的一半。
如果check函数返回true，则将左边界设定为当前的mid值；否则将左边界设定为当前的mid加一。
反之亦然，在检查返回false时将右边界设定为此时的mid值；否则将其减一。
……
除此之外还有其他问题和情况
1. 数的范围
这道题的问题陈述如下：从一个数组中输出指定的数值序列3、2、5各自的起始索引（下标），如果找不到该数值，则返回[-1, -1]。在之前的练习中，在LeetCode平台上确实有过类似的问题出现。当时我记得我的解决思路是先找到目标值所在的位置，并通过将目标值与数组中心位置进行比较，并逐步向两侧扩展搜索范围来完成查找。然而，在当时的情况下我没有详细记录具体的实现细节。
第一种：
- 计算得到mid值为（left + right） / 2后呢。
- 确定当前mid值所在的区间范围。
- 比如说我们现在要查找的数是3，在右侧区域中必定不小于3的原因是因为3本身就是我们要找的答案之一。
- 所以情况会是下面这样：这将确保找到起始位置除非这个数不存在于该区域内
//找起点
while(left < right)
{
int mid = (left + right) / 2;
if(nums[mid] >= target)
{
right = mid;
}
else
{
left = mid + 1;
}
}
第二种：
那第二种情况呢就是与之相反的。
- 当当前mid值位于不大于3的区间时, 我们令left = mid,
- 需要注意的是, 这种情况下, 我们需要增加1个单位, 否则就容易陷入死循环.
- 这也就是开头提到的原因, 其实是根据不同的情况进行判断.
while(left < right)
{
int mid = (left + right + 1) / 2;
if(nums[mid] <= target)
{
left = mid;
}
else
{
right = mid - 1;
}这道题目的整体代码如下:
#include <stdio.h>
#define N (100000 + 10)
int main()
{
int n,k,i; // n 为数组大小，k 查找多少次数
int nums[N];
scanf("%d%d",&n,&k);
//录入数组
for (i = 0; i < n; i++)
{
scanf("%d",&nums[i]);
}
//
while(k > 0)
{
k--;
int left = 0, right = n - 1, target;
scanf("%d",&target);
//找起点
while(left < right)
{
int mid = (left + right) / 2;
if(nums[mid] >= target)
{
right = mid;
}
else
{
left = mid + 1;
}
}
if(nums[left] != target)
{
//找不到
printf("-1 -1\n");
continue;
}
printf("%d ",left);
//继续找末尾
right = n - 1;
while(left < right)
{
int mid = (left + right + 1) / 2;
if(nums[mid] <= target)
{
left = mid;
}
else
{
right = mid - 1;
}
}
printf("%d\n",left);
}
return 0;
}二. 高精度
在这一小节中呢？主要是针对那些超出int和long long存储能力范围的数值运算进行了设计与实现。也就是说，在这些情况下无法直接存储或者进行常规操作的数据类型会采用特殊处理方式来进行计算。
1. 加法
题目链接
完成两个数的相加操作吧！之前在LeetCode上练习过这道题吗？哈哈，在听别人讲解后发现原来的思路与现在听别人讲解相比并不如现在的清晰哦~
- 可以采用一个临时变量来保存进位的数值。
- 所有三个条件都需要参与循环；同时要求两个数组均非空且t值非零.
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define N (100000 + 10)
int* Add(int* A, int Asize, int* B, int Bsize, int* size)
{
int* ans = (int*)malloc(sizeof(int) * N);
int i,t = 0;
for (i = 0; i < Asize || i < Bsize || t; i++)
{
if(i < Asize)
{
t += A[i];
}
if(i < Bsize)
{
t += B[i];
}
ans[(*size)++] = t % 10;
t /= 10;
}
return ans;
}
int main()
{
char a[N],b[N];
scanf("%s %s",a,b);
int Alen = strlen(a),Blen = strlen(b);
int A[N],B[N]; //a 和 b的数组形式 高位在前
int Asize = 0, Bsize = 0,i;
//字符串转化为数组 高位在前。
for (i = Alen - 1; i >= 0; i--)
{
A[Asize++] = a[i] - '0';
}
for (i = Blen - 1; i >= 0; i--)
{
B[Bsize++] = b[i] - '0';
}
//相加
int ansSize = 0;
int* ans = Add(A,Asize,B,Bsize,&ansSize);
//打印
for (i = ansSize - 1; i >= 0; i--)
{
printf("%d",ans[i]);
}
printf("\n");
free(ans);
return 0;
}2. 减法
- 这道题也还有一个临时变量 t
- 它的目的就是看是否借位。
- 另外一种情况是说如果要比较两个数的大小的话，则不能直接调用strcmp函数来进行比较了。因为strcmp函数是逐个字符对比其ASCII码值的，并没有考虑到整个字符串的意义所在；因此为了达到预期效果还需要自行编写一个排序算法。
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
#define N (100000 + 10)
bool Compar(int* A, int Asize, int* B, int Bsize)
{
if(Asize != Bsize)
{
return Asize > Bsize;
}
//len same
int i;
for (i = Asize - 1; i >= 0; i--)
{
if(B[i] != A[i])
{
return A[i] > B[i];
}
}
return true;
}
int* Sub(int* A,int Asize, int* B, int Bsize, int* size)
{
int* ans = (int*)malloc(sizeof(int) * N);
int i, t = 0;
for (i = 0; i < Asize; i++)
{
t = A[i] - t;
if(i < Bsize)
t -= B[i];
ans[(*size)++] = (t + 10) % 10;
//是否借位
if(t < 0)
t = 1;
else
t = 0;
}
//前导零。
while((*size) > 1 && ans[(*size) - 1] == 0)
(*size)--;
return ans;
}
int main()
{
char a[N],b[N];
scanf("%s %s",a,b);
int Alen = strlen(a),Blen = strlen(b);
int A[N],B[N]; //a 和 b的数组形式 高位在前
int Asize = 0, Bsize = 0,i;
//数组转化
for (i = Alen - 1; i >= 0; i--)
{
A[Asize++] = a[i] - '0';
}
for (i = Blen - 1; i >= 0; i--)
{
B[Bsize++] = b[i] - '0';
}
int ansSize = 0;
int* ans = NULL;
if(Compar(A,Asize,B,Bsize))
{
// a >= b
ans = Sub(A,Asize,B,Bsize,&ansSize);
for (i = ansSize - 1; i >= 0; i--)
{
printf("%d",ans[i]);
}
printf("\n");
}
else
{
ans = Sub(B,Bsize,A,Asize,&ansSize);
printf("-");
for (i = ansSize - 1; i >= 0; i--)
{
printf("%d",ans[i]);
}
printf("\n");
}
free(ans);
return 0;
}3. 乘法
高精度相乘即为极大数值与极小数值相乘，在代码中我们选择将变量b赋值为int类型。
- 当进行乘法运算时，在逐位使用每个数字的基础上，并将结果加上变量 t。
- 计算变量 t 的模值后得到的结果就是当前的答案。
- 接着将变量 t 执行除以十的操作。
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define N (100000 + 10)
int* Mul(int* A, int Asize, int b, int* size)
{
int* ans = (int*)malloc(sizeof(int) * N);
int i,t = 0;
for (i = 0; i < Asize || t; i++)
{
if(i < Asize)
t += A[i] * b;
ans[(*size)++] = t % 10;
t /= 10;
}
return ans;
}
int main()
{
char a[N];
int A[N],b,i;
scanf("%s %d",a,&b);
if(b == 0)
{
printf("0\n");
return 0;
}
int Asize = 0,Alen = strlen(a);
for (i = Alen - 1; i >= 0; i--)
{
A[Asize++] = a[i] - '0';
}
int ansSize = 0;
int* ans = Mul(A,Asize,b,&ansSize);
for (i = ansSize - 1; i >= 0; i--)
{
printf("%d",ans[i]);
}
printf("\n");
return 0;
}4. 除法
- 除法需要注意的就是在自高位往下计算。
- 在具体模拟除法的过程中其实需要认真细致地理解和掌握其中的运算逻辑。
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define N (100000 + 10)
void Reverse(int* nums, int numsSize)
{
int left = 0,right = numsSize - 1;
while(left < right)
{
int tmp = nums[left];
nums[left++] = nums[right];
nums[right--] = tmp;
}
}
int* Div(int* A, int Asize,int b, int* size, int* rem)
{
int i, t = 0;
int* ans = (int*)malloc(sizeof(int) * N);
for (i = Asize - 1; i >= 0; i--)
{
t = t * 10 + A[i];
ans[(*size)++] = t / b;
t %= b;
}
*rem = t;
Reverse(ans,*size);
while(*size > 1 && ans[(*size) - 1] == 0)
(*size)--;
return ans;
}
int main()
{
char a[N];
int A[N],b,i;
scanf("%s %d",a,&b);
if(b == 0)
{
printf("0\n");
return 0;
}
int Asize = 0,Alen = strlen(a);
for (i = Alen - 1; i >= 0; i--)
{
A[Asize++] = a[i] - '0';
}
int rem = 0;
int ansSize = 0;
int *ans = Div(A,Asize,b,&ansSize,&rem);
for (i = ansSize - 1; i >= 0; i--)
{
printf("%d",ans[i]);
}
printf("\n%d\n",rem);
return 0;
}三，前缀和与差分
过去在应用中的前缀和使用得较多,而对差分的概念了解较少,很少涉及这一知识点。这一小节也学到了一些关于差分的知识点。以前学过的前缀和是基于元数组一一对应的。查看别人题解不明白为什么要跳过一个索引的问题，在进一步思考后发现这样做的目的是为了使所有公式保持一致。
在这一平台上练习时会遇到类似的问题：LeetCode提供一个OJ系统任务（Online Judge），它会提供一个函数让我们去实现其功能。而像蓝桥杯、AcWing等平台则属于编程竞赛类型（OI类），它们通常要求我们编写主程序并直接输出结果。对于这些编程竞赛问题来说，在处理矩阵元素时可以选择性地使用索引0的位置而不存储数据（即使用1号位置存储），这样可以避免一些混淆问题。值得注意的是，在LeetCode这类平台上提供的数组通常都是从索引0开始的。
1. 一维前缀和
求区间[l,r]的和公式： s[l,r] = s[r] - s[l - 1]
#include <stdio.h>
#define N (100000 + 10)
int n;
int prefix[N],nums[N];
int main()
{
int i,k;
scanf("%d%d",&n,&k);
for (i = 0; i < n; i++)
scanf("%d",&nums[i]);
//求前缀和
for (i = 1; i <= n; i++)
prefix[i] = prefix[i - 1] + nums[i - 1];
while(k != 0)
{
int l,r;
scanf("%d%d",&l,&r);
printf("%d\n",prefix[r] - prefix[l - 1]); //前缀和公式
k--;
}
return 0;
}2. 二维前缀和
观察该二维矩阵时会发现其前缀和呈现为这样的结构：即从起始点开始逐步累加各行各列之前的元素值而形成的累积总值分布模式。其中初始边界条件设定为第一行与第一列均为零值。具体而言，在目标位置计算其左上角所有元素之总和即可得到对应的前缀值。
如何具体求解呢？计算图中数值之和：6加3减去1再加上6等于14。其中橙色区域内的数值被重复计算了一次，请注意扣除这一重复部分；接着，在最后一步骤中需将自身数值加入计算以确保结果准确无误。
matrix[x1,x2] = 6.
求前缀和公式:
s[x1,x2] = s[x1,y1 - 1] + s[x1 - 1, y1] - s[x1 - 1, y1 - 1] + matrix[x1,x2].
当我们需要计算某段区间内的总和时，则只需将数值54减去数值6再减去数值15最后加上数值1即可。
对于二维矩阵中计算子矩阵总值的问题来说，在已知整体大矩阵累积和的基础上进行处理是一种有效的方法。
具体而言，
matrix[x_{\text{start}}, y_{\text{end}} \rightarrow x_{\text{end}}, y_{\text{end}}] 的总值可以通过以下公式计算：
s[x_{\text{end}}, y_{\text{end}}] - s[x_{\text{end}}, y_{\text{start}} - 1] - s[x_{\text{start}} - 1, y_{\text{end}}] + s[x_{\text{start}} - 1, y_{\text{start}} - 1]。
#include <stdio.h>
#define N (1000 + 10)
int matrix[N][N],prefix[N][N];
int row, col;
int main()
{
int i, j, k;
scanf("%d%d%d",&row,&col,&k);
for (i = 1; i <= row; i++)
{
for (j = 1; j <= col; j++)
{
scanf("%d",&matrix[i][j]);
}
}
//创建前缀和
for (i = 1; i <= row; i++)
{
for (j = 1; j <= col; j++)
{
prefix[i][j] = prefix[i][j - 1] + prefix[i - 1][j] - prefix[i - 1][j - 1] + matrix[i][j];
}
}
while(k--)
{
int x1,y1,x2,y2;
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
printf("%d\n",prefix[x2][y2] - prefix[x2][y1 - 1] - prefix[x1 - 1][y2] + prefix[x1 - 1][y1 - 1]);
}
return 0;
}3. 一维差分
关于这个概念是什么呢？它指的是当前项与前一项之间的差异吗？因为我在举例说明时使用了一个等比数列，并且公比q是2的情况下（即每个后续项都是前一项的两倍），因此得到的结果是一个公比q'等于2/3的新等比数列。
观察到对差分数组进行前缀和计算后会得到原始nums数组的数据结构。这说明其具体作用是什么？
想要在一个特定区域（例如从索引位置[2,5]）内执行数值增益操作时应该如何设置差分数组？
通过将差分数组中索引位置[2]处增加两个单位，并在索引位置6处减少两个单位（即为5+1），即可实现对选定区域的所有元素进行增益操作的效果。如图所示：只有被选定区域内的元素会受到增益影响而其他未被覆盖的部分则保持不变的状态。
区间d在[l, r]范围内，并取一个常量C。
差分操作式：对于位置l来说会增加C；而针对r+1的位置则会减少C。
在构建数据结构时，我们可调用一个插入函数，在处理当前位置时执行操作。
#include <stdio.h>
#define N (100000 + 10)
int nums[N],diff[N],prefix[N];
//区间[l,r]插入c
void DiffInsert(int l, int r, int c)
{
diff[l] += c;
diff[r + 1] -= c;
}
int main()
{
int i,n,k;
scanf("%d%d",&n,&k);
//原数组
for (i = 1; i <= n; i++)
{
scanf("%d",&nums[i]);
}
//差分数组
for (i = 1; i <= n; i++)
DiffInsert(i,i,nums[i]);
//差分k次
while(k--)
{
int l,r,c;
scanf("%d%d%d",&l,&r,&c);
DiffInsert(l,r,c);
}
//还原
for (i = 1; i <= n; i++)
{
prefix[i] = prefix[i - 1] + diff[i];
printf("%d ",prefix[i]);
}
return 0;
}4. 二维差分
差分的二维矩阵的本质上与2D前缀和是相同的。类似于我们在一维情况中所做的,我们同样采用插入函数的方法，在创建差分数组的过程中对当前的位置进行插入。
diff[x1][y1] += c
diff[x2 + 1][y1] -= c
diff[x1][y2 + 1] -= c
diff[x2 + 1][y2 + 1] += c
#include <stdio.h>
#define N (1000 + 10)
int matrix[N][N],diff[N][N],prefix[N][N];
int row, col;
void DiffInsert(int x1, int y1, int x2, int y2, int c)
{
diff[x1][y1] += c;
diff[x2 + 1][y1] -= c;
diff[x1][y2 + 1] -= c;
diff[x2 + 1][y2 + 1] += c;
}
int main()
{
int i,j,k;
scanf("%d%d%d",&row,&col,&k);
//create matrix
for (i = 1; i <= row; i++)
{
for (j = 1; j <= col; j++)
{
scanf("%d",&matrix[i][j]);
}
}
//diff
for (i = 1; i <= row; i++)
{
for (j = 1; j <= col; j++)
{
DiffInsert(i,j,i,j,matrix[i][j]);
}
}
while(k--)
{
int x1,y1,x2,y2,c;
scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&c);
DiffInsert(x1,y1,x2,y2,c);
}
for (i = 1; i <= row; i++)
{
for (j = 1; j <= col; j++)
{
prefix[i][j] = prefix[i - 1][j] + prefix[i][j - 1] - prefix[i - 1][j - 1] + diff[i][j];
printf("%d ",prefix[i][j]);
}
printf("\n");
}
return 0;
}四. 双指针
双指针在平时的用的还是非常的多感觉，归并排序，快排等等很多。
1. 数组元素的目标和
- 通过设置指针i和j分别指向数组A的开头与数组B的末尾来实现。
- 其中i指向数组A的起始位置，j指向数组B的起始位置。
- 由于这两个数组均为有序结构，在计算过程中若满足A[i] + B[j] < x时。
- 那么应当将j向前移动一位。
- 否则将i向前移动一位。
#include <stdio.h>
#define N (100000 + 10)
int A[N],B[N],map[N];
int n,m,x;
int main()
{
int i,j;
scanf("%d%d%d",&n,&m,&x);
for (i = 0; i < n; i++)
scanf("%d",&A[i]);
for (i = 0; i < m; i++)
scanf("%d",&B[i]);
for (i = 0, j = m - 1; i < n; i++)
{
while(j >= 0 && A[i] + B[j] > x)
{
j--;
}
if(A[i] + B[j] == x)
{
printf("%d %d\n",i,j);
return 0;
}
}
printf("找不到！\n");
return 0;
}五. 位运算
对于位运算方面的知识储备较为有限；实际上，在日常学习或实践过程中，并未见到太多机会应用它；本节主要讲解了位运算的两种常用的操作方式。
通过使用 & 操作符来提取二进制数的第一位。举个例子来说吧：将一个数字与 1 进行 & 操作，则会得到该数字的第一位。这个操作符的作用是：当其数值为 0 时，则结果也为 0。因此，在执行 &1 操作后，除了最高位外的所有位都会被置为 0。
2. 看一下n的第k位数字是几
有了取出第一位后的操作，第k位的话就是n >> k & 1
3. lowbit(x)
可以获取x的最后一个1的位置：
公式是x & -x
111000 得到 1000
101010 得到 10
00111100 的到 10
1. 统计出二进制中1的个数
记忆中有一次，在统计过程中处理它的二进制数时，并没有将其全部计算进去而是直接放入数据中了😓。
- 利用lowbit（x） 求出最后一位1的位置，然后减去，直到变成0位置。
#include <stdio.h>
int n;
int lowbit(int x)
{
return x & -x;
}
int main()
{
scanf("%d",&n);
while(n--)
{
int x,count = 0;
scanf("%d",&x);
while(x != 0)
{
x -= lowbit(x);
count++;
}
printf("%d ",count);
}
return 0;
}六. 区间合并
就比如下图中给定的区间，最后将会返回答案是3，合并成了3个区间
通过一个二维数组存储变量x和y的索引值。
随后对数组进行排序处理，并从左到右依次进行模拟运算。
最终设置begin变量初始值为0；如果end变量初始值设定为1，则进入交集判断阶段。
若判断得出end起点小于等于 begin终点，则表示存在交叠区域；此时并集计算：取pair[begin]第二个元素与pair[end]第二个元素的最大值作为新的 begin位置。
若无交叠区域，则ans增加计数器，并将当前区间的结束点设为主区间结束点。
初始化ans值为1；任何情况下至少有一个区间存在。
#include <stdio.h>
#include <stdlib.h>
#define N (100000 + 10)
int res; //最后的结果
int n,pair[N][2]; //pair 数组存放的是所输入的下标
int cmp(const void* x, const void* y)
{
int* a = (int*)x;
int* b = (int*)y;
if (a[0] != b[0])
{
return a[0] - b[0];
}
else
{
return a[1] - b[1];
}
}
void merge()
{
int begin = 0,end = 1;
while(end < n)
{
if(pair[end][0] <= pair[begin][1])
{
//更新合并后的区间最远处，并集
if(pair[begin][1] < pair[end][1])
{
begin = end;
}
}
else
{
//获取新的起点开始
res += 1;
begin = end;
}
end++;
}
}
int main()
{
int i;
res = 1;
scanf("%d",&n);
//录入数据
for (i = 0; i < n; i++)
{
scanf("%d%d",&pair[i][0],&pair[i][1]);
}
//排序
qsort(pair,n,sizeof(pair[0]),cmp);
//合并
merge();
printf("%d\n",res);
return 0;
}七. qsort 排序二维数组
该qsort排序二维数组是在我进行区间合并时发现的问题，在比赛中再次遇到类似情况则会感到难以处理。
初始化与动态分配内存创建的不同二维数组其比较函数存在差异。
而那些通过调用malloc函数动态申请内存创建的题目则使用了下面提到的第二种比较函数。
int cmp_martix(const void* x, const void* y)
{
int* a = (int*)x;
int* b = (int*)y;
if(a[0] != b[0])
{
return a[0] - b[0];
}
else
{
return a[1] - b[1];
}
}
int cmp_nums(const void* x, const void* y)
{
int** a = (int**)x;
int** b = (int**)y;
if (a[0][0] != b[0][0])
{
return a[0][0] - b[0][0];
}
else
{
return a[0][1] - b[0][1];
}
}
int main()
{
int matrix[N][N];
int i,n;
scanf("%d",&n);
int** nums = (int**)malloc(sizeof(int*) * n);
for (i = 0; i < n; i++)
{
nums[i] = (int*)malloc(sizeof(int) * 2);
scanf("%d%d",&matrix[i][0],&matrix[i][1]);
nums[i][0] = matrix[i][0];
nums[i][1] = matrix[i][1];
}
qsort(matrix,n,sizeof(matrix[0]),cmp_martix);
qsort(nums,n,sizeof(nums[0]),cmp_nums);
//
printf("martix排序后:\n");
for (i = 0; i < n; i++)
{
printf("%d %d\n",matrix[i][0],matrix[i][1]);
}
printf("nums排序后:\n");
for (i = 0; i < n; i++)
{
printf("%d %d\n",nums[i][0],nums[i][1]);
}
return 0;
}完结 ★,° :.☆(￣▽￣)/$:.°★ ❀🎈🎈🎈🎈。