- 上课理解思路 -> 下课理解背过代码模板 -> 做3-5遍题目（循环AC）
排序
快速排序
快速排序模板题例题
分治：用一个数来分，不需要必须是中心数
先分完再递归两边
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(); // 数组中元素的个数
int[] nums = new int[n]; // 定义数组大小
for(int i=0;i<n;i++){
nums[i] = sc.nextInt(); // 获取数组元素
}
int[] res = quickSort(0,n-1,nums); // 进行快排并把结果保存在res数组中
for(int i=0;i<n;i++){
System.out.print(res[i] + " "); // 输出排序后的结果
}
}
public static int[] quickSort(int l,int r,int[] nums){
// 边界结束条件
// 写成l==r也是可以的
if(l>=r){
return nums;
}
int p = nums[(l+r)/2]; // 1. 确定分界点，不能取到nums[r]因为下面划分区间使用的j
int i = l-1;
int j = r+1;
// 2. 调整范围
while(i<j){
while(nums[++i]<p); // 从左往右找比p大的数
while(nums[--j]>p); // 从右往左找比p小的数
// 此时如果i<j，那么说明找到了满足要求的一组数，交换数组中i,j两个位置的值
if(i<j){
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
// 3. 递归处理左右两段[l,j]与[j+1,r],上述while结束后i>=j
// 分治法
quickSort(l,j,nums);
quickSort(j+1,r,nums);
return nums;
}
}
第k个数
归并排序
归并排序模板题例题
分治：以整个数组的中心点来分
先递归两边再归并
双指针算法，逐个找最小的，存到res数组中
每层都是On，logn分层，总计nlogn
import java.util.*;
public class Main {
public static void main (String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt(); // 数组中元素的个数
int[] nums = new int[n]; // 定义数组大小
for (int i = 0; i < n; i++) {
nums[i] = scanner.nextInt(); // 获取数组中的元素
}
merge_sort(0,n-1,nums); // 进行归并排序
for (int i = 0; i < n; i++) {
System.out.print(nums[i] + " ");
}
}
public static void merge_sort (int l,int r,int[] nums) {
if (l>=r) {
return;
}
int mid = (l+r) >> 1;
int i = l,j = mid + 1; // 两个指针指向两段的首元素
merge_sort(l,mid,nums); // 左区间[l,mid]
merge_sort(mid+1,r,nums); // 右区间[mid+1,r]
int[] temp = new int[r - l + 1]; // 临时数组中存储归并后的数据
int k = 0; // 临时数组的指针，用来存储已经排序好的下标位置
while (i <= mid && j <= r) {
if (nums[i] <= nums[j]) {
// temp[k] = nums[i]; // 把较小的数存储到临时数组中
// k++; // 临时数组指针移动
// i++; // 数组指针移动
temp[k++] = nums[i++];
} else {
temp[k++] = nums[j++];
}
}
// 此时说明i中仍有剩余元素，即j已经走完全路程
while (i <= mid) {
temp[k++] = nums[i++]; // 将剩余元素存储到临时数组中
}
// 此时说明j中仍有剩余元素，即i已经走完全路程
while (j <= r) {
temp[k++] = nums[j++]; // 将剩余元素存储到临时数组中
}
// 临时数组归位
for (int q = l,p = 0; q <= r; q++) {
nums[q] = temp[p++];
}
}
}
逆序对的数量
二分法
有单调性可以进行二分，没有也可以
整数二分法
-
第一个大于等于x的数 || 最后一个大于等于x的数
- l=mid,需要补一个1
假设此时l=r-1，那么mid=(l+r)/2=l，在刚好true的时候，l=mid=l，[l,r]没变，则死循环。
如果补1，那么mid=(l+r+1)/2=r，l=mid=r，则刚好结束。 - r=mid,不需要补一个1
- l=mid,需要补一个1
-
整体逻辑
- 先正常写，每次写一个mid，写一个check函数，想一下答案怎么划分，如果l=mid，则需要+1
- check函数：需要选择答案所在的区间，要保证这个区间内部一定有答案
-
起始位置
-
终结位置
import java.util.*;
public class Main {
public static void main (String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
int[] nums = new int[n];
for (int i = 0; i < n; i++) {
nums[i] = scanner.nextInt();
}
for (int i = 0; i < m; i++) {
int x = scanner.nextInt();
// 首先需要找第一个和它相同的数作为起始位置p
int p = 0,q = 0; // 起始位置p(第一次出现)，结束位置q(最后一次出现)
int l = 0,r = n-1;
while (l < r) {
int mid = (l+r)>>1;
// 找的是x的起始位置即>=x，更新成[l,mid]
// 最前面那个满足>=x的数就是二分的位置
if (nums[mid] >= x) {
r = mid; // 不用补上+1了
} else {
l = mid+1;
}
}
p = r; // 起始位置(nums[l]==nums[r])
l = 0;
r = n-1;
while (l < r) {
int mid = (l+r+1)>>1;
// 找的是x的最终位置即<=x，更新成[mid,r]
// 最后面那个满足<=x的数就是二分的位置
if (nums[mid] <= x) {
l = mid; // 需要补上+1
} else {
r = mid-1;
}
}
q = r; // 最终位置
if (nums[q] != x) {
System.out.println(-1 + " " + -1);
} else {
System.out.println(p + " " + q);
}
}
}
}
浮点数二分法
import java.util.*;
public class Main {
public static void main (String[] args) {
Scanner scanner = new Scanner(System.in);
double n = scanner.nextDouble();
// double l = (double)-1e5;
double l = 0;
// double r = 1e5*1.0;
double r = n;
// 当浮点数区间的长度已经很小的时候就已经可以算作答案了
// 浮点数也没有边界的问题
while (r - l > 1e-8) {
double mid = (l+r)/2;
if (mid * mid * mid >= n) {
r = mid;
} else {
l = mid;
}
}
System.out.printf("%.6f",l); // 6位小数就写1e-8,4位就写1e-6
}
}
高精度
高精度加法
高精度减法
高精度乘法
高精度除法
前缀和与差分
前缀和
差分
双指针算法
位运算
离散化
区间合并
