pat学习笔记

two pointers 双指针

给定一个递增的正整数序列和一个正整数M，求序列中的两个不同位置的数a和b，使得它们的和恰好为M，输出所有满足条件的方案。例如给定序列{1,2,3,4,5,6}和正整数M = 8，就存在2+6=8和3+5=8成立。

容易想到：使用二重循环枚举序列中的整数a和b，判断它们的和是否为M，如果是，输出方案，如果不是，则继续枚举。

代码如下，时间复杂度为O（n^2）。

for(int i=0;i<n;i++){for(int j=i+1;i<n;i++){if(a[i]+a[j]==M){printf("%d %d\n",a[i],a[j]);}}
}

2-SUM-双指针

优化算法如下：该算法的时间复杂度为O（n）。

#include <cstdio>
#include <iostream>
using namespace std;
const int N = 1e5+10;
int a[N];
int main(){int n,k;int cnt = 0;cin>>n>>k;int i = 0,j = n-1;for(int i=0;i<n;i++) cin>>a[i];while(i<j){if(a[i]+a[j]==k){cnt++;i++;j--;}else if(a[i]+a[j]<k){i++;}else {j--;}}cout<<cnt;return 0;
}

序列合并问题：

#include <cstdio>
#include <iostream>
using namespace std;// 定义常量 N，用于确定数组的最大长度
const int N = 1e5 + 10;// 定义三个数组 a、b、c，分别用于存储两个待合并的有序数组和合并后的有序数组
int a[N], b[N], c[N];// 合并函数，将两个有序数组合并为一个有序数组
int merge(int a[], int b[], int c[], int n, int m) {// i 指向数组 a 的起始位置，j 指向数组 b 的起始位置，index 指向数组 c 的起始位置int i = 0, j = 0, index = 0;// 当数组 a 和数组 b 都还有元素未处理时while (i < n && j < m) {// 如果 a[i] 小于等于 b[j]，将 a[i] 放入数组 c 中，并将 i 和 index 指针后移if (a[i] <= b[j]) c[index++] = a[i++];// 否则将 b[j] 放入数组 c 中，并将 j 和 index 指针后移else c[index++] = b[j++];}// 如果数组 a 还有剩余元素，将其依次放入数组 c 中while (i < n) c[index++] = a[i++];// 如果数组 b 还有剩余元素，将其依次放入数组 c 中while (j < m) c[index++] = b[j++];// 返回合并后数组 c 的长度return index;
}int main() {int n, m;// 读取数组 a 的长度 n 和数组 b 的长度 mscanf("%d%d",&n,&m);// 读取数组 a 的 n 个元素for (int i = 0; i < n; i++) scanf("%d",&a[i]);// 读取数组 b 的 m 个元素for (int i = 0; i < m; i++) scanf("%d",&b[i]);// 调用 merge 函数合并数组 a 和数组 b 到数组 c 中，并获取合并后数组 c 的长度int res = merge(a, b, c, n, m);// 输出合并后数组 c 的元素for (int i = 0; i < res; i++) {printf("%d", c[i]);// 除了最后一个元素，每个元素后面输出一个空格if (i < res - 1) cout << " ";}return 0;
}

归并排序

递归写法

#include <iostream>
#include <cstdio>
using namespace std;
const int maxn = 1010;
int a[maxn];
//将数组A的[L1,R1]与[L2,r2]区间合并为有序区间(此处L2即为r1+1)
void merge(int a[], int l1, int r1, int l2, int r2) {int i = l1, j = l2; //i指向a[l1],j指向a[l2] int temp[maxn], index = 0; //temp临时存放合并后的数组，index为其下标while (i <= r1 && j <= r2) {if (a[i] <= a[j]) { //如果a[i]<=a[j]temp[index++] = a[i++]; //将a[i]加入序列temp } else {temp[index++] = a[j++];}}while (i <= r1) temp[index++] = a[i++];while (j <= r2) temp[index++] = a[j++];for (i = 0; i < index; i++) {a[l1 + i] = temp[i]; //将合并后的序列赋值给数组a }
}
//将array数组当前区间[left,right]进行归并排序
void mergeSort(int a[], int left, int right) {if (left < right) { //只要left小于right int mid = (left + right) / 2; //取[left,right]的中点 mergeSort(a, left, mid); //递归，将左子区间[left,mid]归并排序 mergeSort(a, mid + 1, right); //递归，将右子区间[mid+1,right]归并排序 merge(a, left, mid, mid + 1, right); //将左子区间和右子区间合并 }
}int main() {int n;cin >> n;for (int i = 0; i < n; i++) cin >> a[i];// 调用归并排序函数对数组进行排序mergeSort(a, 0, n - 1);// 输出排序后的数组for (int i = 0; i < n; i++) {cout << a[i];if (i < n - 1) cout << " ";}return 0;
}    

非递归写法

/*1. 外层循环 for(int step = 2; step/2 <= n; step *= 2)
step 的含义：step 表示当前每组元素的个数。在归并排序的非递归实现中，我们从最小的有序子数组开始合并，初始时每组有 2 个元素（即 step = 2），然后每次将 step 乘以 2，逐渐扩大每组的元素个数。
循环条件 step/2 <= n：当 step/2 大于数组的长度 n 时，说明已经完成了所有的合并操作，因为此时分组已经包含了整个数组，所以循环结束。
step *= 2：每次循环结束后，将 step 乘以 2，这样就可以将相邻的两个有序子数组合并成一个更大的有序数组。
2. 内层循环 for(int i = 1; i <= n; i += step)
i 的含义：i 表示当前组的起始位置。每次循环将 i 增加 step，这样就可以依次处理数组中的每一组元素。
循环条件 i <= n：确保 i 不会超出数组的范围。
3. int mid = i + step/2 - 1
mid 的含义：mid 表示当前组中左子区间的最后一个元素的下标。因为左子区间的元素个数为 step/2，所以 mid 的值为 i + step/2 - 1。
4. if(mid + 1 <= n)
判断右子区间是否存在元素：如果 mid + 1 大于数组的长度 n，说明右子区间不存在元素，不需要进行合并操作；否则，需要将左子区间 [i, mid] 和右子区间 [mid + 1, min(i + step - 1, n)] 进行合并。
5. merge(a, i, mid, mid + 1, min(i + step - 1, n))
调用 merge 函数进行合并：merge 函数的作用是将两个有序子数组合并成一个更大的有序数组。这里的左子区间为 [i, mid]，右子区间为 [mid + 1, min(i + step - 1, n)]。使用 min(i + step - 1, n) 是为了防止右子区间的下标超出数组的范围。
注意事项
代码中数组的下标是从 1 开始的，而在 C++ 中数组的下标通常是从 0 开始的。如果要在实际代码中使用，需要根据具体情况进行调整。
代码中使用了变量 n，但在提供的代码片段中并没有对 n 进行定义，在实际使用时需要确保 n 是数组的长度*/
void mergeSort(int a[]){// step为组内元素个数，step/2为左子区间元素个数，注意等号可以不取for(int step = 2; step/2 <= n; step *= 2){// 每step个元素一组，组内前step/2和后step/2个元素进行合并for(int i = 1; i <= n; i += step){ // 对每一组 int mid = i + step/2 - 1; // 左子区间元素个数为step/2 if(mid + 1 <= n){ // 右子区间存在元素则合并 // 左子区间为[i, mid], 右子区间为[mid + 1, min(i + step - 1, n)]merge(a, i, mid, mid + 1, min(i + step - 1, n)); }} } 
}

 快速排序的交换方式：

//对区间[left,right]进行划分
int partition(int a[],int left,int right){int temp = a[left];//将a[left]存放至临时变量tempwhile(left<right){//只要left与rightwhile(left<right&&a[right]>temp) right--;//反复左移right a[left] = a[right];//将a[right]挪到a[left]while(left<right&&a[left]<=temp) left++;//反复右移left a[right] = a[left];//将a[left]挪到a[right] } a[left] = temp;//把temp放到left与right相遇的地方 return left;//返回相遇的下标 
} 

快速排序的递归实现如下：

//快速排序，left 与right初值为序列首尾下标（如1,与n） 
void quicksort(int a[],int left,int right){if(left<right){//当前区间的长度不超过1 //将[left,right]按a[left]一分为二int pos = partition(a,left,right);quicksort(a,left,pos-1);//对左子区间递归进行快速排序 quicksort(a,pos+1,right); //对右子区间递归进行快速排序 }
}

快速排序

#include <cstdio>
#include <iostream>
using namespace std;
const int maxn = 1010;
int a[maxn];
//对区间[left,right]进行划分
int partition(int a[],int left,int right){int temp = a[left];//将a[left]存放至临时变量tempwhile(left<right){//只要left与rightwhile(left<right&&a[right]>temp) right--;//反复左移right a[left] = a[right];//将a[right]挪到a[left]while(left<right&&a[left]<=temp) left++;//反复右移left a[right] = a[left];//将a[left]挪到a[right] } a[left] = temp;//把temp放到left与right相遇的地方 return left;//返回相遇的下标 
} 
//快速排序，left 与right初值为序列首尾下标（如1,与n） 
void quicksort(int a[],int left,int right){if(left<right){//当前区间的长度不超过1 //将[left,right]按a[left]一分为二int pos = partition(a,left,right);quicksort(a,left,pos-1);//对左子区间递归进行快速排序 quicksort(a,pos+1,right); //对右子区间递归进行快速排序 }
}
int main(){int n;cin>>n;for(int i=0;i<n;i++) cin>>a[i];quicksort(a,0,n-1);for(int i=0;i<n;i++){cout<<a[i];if(i<n-1) cout<<" ";}return 0;
}