基础算法-学习笔记

文章目录

• 一、排序
• • 1.快速排序
  • 2.归并排序
• 二、二分
• • 1、整数二分
  • 2、浮点数二分
• 三、高精度
• • 四种应用场景：
  • ①加法：
  • ②减法：
  • ③乘法：
  • ④除法：
• 四、前缀和
• • 1、一维
  • 2、二维
• 五、差分
• • 1.一维差分
  • 2.二维差分
• 六、双指针算法
• • 七、位运算
  • 1、n的二进制表示中第k位是多少？
  • 2、返回n的最后一位1
  • 八、离散化

---

一、排序 1.快速排序

class="superseo">算法思想：

快速排序模板 使用较多为面试官要求，手写快排。
代码：

//快速排序模板 面试官，手写快排
#include
using namespace std;

const int N = 1e6 + 10;
int n;
int q[N];

void quick_sort(int q[], int l, int r) {
	if (l >= r) return;//判断边界

	int x = q[l];//随机取
	int i = l - 1;//初始位置为最右侧的元素的前面
	int j = 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);//这里j对应取q[l]，不能取r，否则会出现递归死循环
	quick_sort(q, j + 1, r);//同理，i对应取q[r]，不能取q[l]
}

int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++)scanf("%d", &q[i]);

	quick_sort(q, 0, n - 1);
	for (int i = 0; i < n; i++)printf("%d ", q[i]);

	return 0;
}

---

2.归并排序

算法思想：

代码如下：

#include
using namespace std;

const int N = 1000010;
int n;
int q[N],temp[N];

//归并
void merge_sort(int q[], int l, int r) {
	if (l >= r) return;//判断边界

	int mid = (l + r)/2;

	merge_sort(q, l, mid);
	merge_sort(q, mid + 1,r);
	
	//归并过程，将两个有序的序列归并到temp中
	int k = 0;//用来表示辅助数组temp中已经合并有元素的个数
	int i = l;//指向左半边起点
	int j = mid + 1;//指向右半边起点
	
	while (i <= mid && j <= r)
	{
		if (q[i] <= q[j]) temp[k++] = q[i++];
		else temp[k++] = q[j++];
	}
	while (i <= mid) temp[k++] = q[i++];
	while (j <= r)temp[k++] = q[j++];

	for (i = l, j = 0; i <= r; i++, j++) q[i] = temp[j];//将temp结果存回q中

}
int main() {
	
	scanf("%d", &n);
	
	for (int i = 0; i < n; i++) scanf("%d", &q[i]);

	merge_sort(q, 0, n - 1);

	for (int i = 0; i < n; i++) printf("%d ", q[i]);

	return 0;
}

二、二分 1、整数二分

思想：

二分找边界：

注意：进行 l=mid 更新时，取mid=（l+r+1）/ 2，补上+1是防止进入死循环。

#include
using namespace std;

const int N = 100010;
int n,m;
int q[N];

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; i++) scanf("%d", &q[i]);
	while (m--) {
		int x;
		scanf("%d", &x);
		
		int l = 0, r = n - 1;
		while (l < r) {
			int mid = (l + r) / 2;

			if (q[mid] >= x) r = mid;
			else l = mid + 1;
		}
		if (q[l] != x) cout << "-1 -1" << endl;
		else {
			cout << l << ' ';

			int l = 0, r = n - 1;
			while (l < r) {
				int mid = (l + r + 1) / 2;
				if (q[mid] <= x) l = mid;
				else r = mid - 1;
			}
			cout << l << endl;
		}
	}
	return 0;
}

2、浮点数二分

求一个浮点数的开方：

#include
using namespace std;

int main() {
	double x;
	cin >> x;

	double l = 0, r = x;
	while (r-l>1e-8)
	{
		double mid = (l + r) / 2;
		if (mid * mid >= x) r = mid;
		else l = mid;
	}
	printf("%lf\n", l);

	return 0;
}

三、高精度

C++需要考虑的问题；在Java 和 Python中不需要考虑

四种应用场景：

大整数在数组中的存储形式：个位存储在前面

①加法：

#include
#include

using namespace std;

//C = A + B  模板
vector<int> add(vector<int>& A, vector<int>& B) {
	vector<int> c;
	int t = 0; //进位
	for (int i = 0; i < A.size() || i < B.size(); i++) {

		if (i < A.size())t += A[i];
		if (i < B.size())t += B[i];//此时，t=t+A[i]+B[i]
		c.push_back(t % 10);
		t /= 10;//大于10产生进位
	}
	if (t)c.push_back(1);//判断一下，最高位是否有进位
	return c;

}
int main() {
	string a, b;
	vector<int>A, B;

	cin >> a >> b;//a="123456"
	for (int i = a.size() - 1; i >= 0; i--)A.push_back(a[i] - '0');
	for (int i = b.size() - 1; i >= 0; i--)B.push_back(b[i] - '0');

	auto c = add(A, B);  //auto代表编译器自己推断类型

	for (int i = c.size() - 1; i >= 0; i--) {
		printf("%d", c[i]);
	}
	return 0;
}

②减法：

A-B分两种情况 :
		A >= B，直接进行计算
		A < B，则计算 -（B-A)

#include
#include

using namespace std;
//函数判断是否有A>=B
bool cmp(vector<int>& A, vector<int>& B) {
	//先判断位数，位数不同直接返回结果
	if (A.size() != B.size()) return A.size() > B.size();
	for (int i = A.size() - 1; i >= 0; i--) {//从高位开始进行比较
		if(A[i]!=B[i]){
			return A[i] > B[i];
		}
		return true;
	}
}
//C = A-B  模板
vector<int> sub(vector<int>& A, vector<int>& B) {
	vector<int> c;
	int t = 0;           //进位
	for (int i = 0, t = 0; i < A.size(); i++) {
		t = A[i] - t;
		if (i < B.size()) t -= B[i];
		c.push_back((t + 10 )% 10);
		if (t < 0) t = 1;
		else t = 0;
	}

	while (c.size() > 1 && c.back() == 0) c.pop_back();//去掉前导0
	return c;
}
int main() {
	string a, b;
	vector<int>A, B;

	cin >> a >> b;//a="123456"
	for (int i = a.size() - 1; i >= 0; i--)A.push_back(a[i] - '0');
	for (int i = b.size() - 1; i >= 0; i--)B.push_back(b[i] - '0');

	//先判断A、B的的大小
	if (cmp(A, B)) {
		auto c = sub(A, B);  //auto代表编译器自己推断类型
		for (int i = c.size() - 1; i >= 0; i--) {
			printf("%d", c[i]);
		}
	}
	else {
		auto c = sub(B, A);  //auto代表编译器自己推断类型
		printf("-");
		for (int i = c.size() - 1; i >= 0; i--) {
			printf("%d", c[i]);
		}
	}

	return 0;
}

③乘法：

#include
#include

using namespace std;

//c=A*b
vector<int> mult(vector<int>& A, int b) {
	vector<int>c;
	int t = 0;    //进位
	for (int i = 0; i < A.size() || t; i++) {
		if(i<A.size()) t += A[i]*b;
		c.push_back(t % 10);
		t /= 10;
	}
	return c;
}

int main() {
	string a;
	int b;
	cin >> a >> b;;
	vector<int> A;
	for (int i = a.size() - 1; i >= 0; i--)A.push_back(a[i] - '0');
	auto c = mult(A, b);
	for (int i = c.size() - 1; i >= 0; i--)printf("%d", c[i]);

	return 0;
}

④除法：

#include
#include
#include
using namespace std;

//  c=A/b ,商是c，余数是r
vector<int> div(vector<int>& A, int b,int &r) {
	vector<int>c;   //商
	r = 0;
	for (int i = A.size()-1; i >=0; i--) {
		r = r * 10 + A[i];
		c.push_back(r / b);
		r %= b;
	}
	reverse(c.begin(), c.end());
	while (c.size() > 1 && c.back() == 0) c.pop_back();//去掉前导0
	return c;
}

int main() {
	string a;
	int b;
	cin >> a >> b;;
	vector<int> A;
	for (int i = a.size() - 1; i >= 0; i--)A.push_back(a[i] - '0');
	
	int r;
	auto c = div(A, b,r);
	for (int i = c.size() - 1; i >= 0; i--)printf("%d", c[i]);

	cout << endl;
	cout << r << endl;

	return 0;
}

四、前缀和

1、一维

#include
using namespace std;

const int N = 100010;

int k, m;
int a[N], s[N];

int main() {
	scanf("%d%d", &k, &m);
	for (int i = 1; i <= k; i++)scanf("%d", &a[i]);

	for (int i = 1; i <= k; i++)s[i] = s[i - 1] + a[i];//前缀和的初始化

	while (m--) {
		int l, r;
		scanf("%d%d", &l, &r);
		printf("%d\n", s[r] - s[l - 1]);//区间和的计算
	}

	return 0;
}

2、二维

#include

const int N = 1010;

int m1, n1, q;
int a[N][N], s[N][N];

int main() {
	scanf("%d%d%d", &n1, &m1, &q);
	for (int i = 1; i <= n1; i++) {
		for (int j = 1; j <= m1; j++) {
			scanf("%d", &a[i][j]);
		}
	}

	for (int i = 1; i <= n1; i++)
		for (int j = 1; j <= m1; j++)
			s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i][j - 1] + a[i][j];//求前缀和

	while (q--) {
		int x1, y1, x2, y2;
		scanf("%d%d%d%d", &x1, &x2, &y1, &y2);
		printf("%d\n", s[x2][y2] - s[x1 - 1][2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]);//算子矩阵的和
	}
	return 0;
}

五、差分

前缀和的逆运算；构造B数组，使得A数组是其前缀和，A称为前缀和；B称为差分。

1.一维差分

#include

using namespace std;

const int N = 100010;

int m, n;
int a[N], b[N];


void insert(int l, int r, int c) {
	b[l] += c;
	b[r + 1] -= c;
}
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]);

	//从前往后，插入构造
	for (int i = 1; i <= n; i++) insert(i, i, a[i]);

	while (m--)
	{
		int l, r, c;
		scanf("%d%d%d", &l, &r, &c);
		insert(l, r, c);

	}
	for (int i = 1; i <= n; i++) b[i] += b[i - 1];

	for (int i = 1; i <= n; i++) printf("%d ", b[i]);

	return 0;
}

2.二维差分

#include
using namespace std;

const int N = 1010;
int n2, m2, q1;
int a[N][N];//原矩阵
int b[N][N];//差分矩阵

void insert(int x1, int y1, int x2, int y2, int c) {
	b[x1][y1] += c;
	b[x2 + 1][y1] -= c;
	b[x1][y2 + 1] -= c;
	b[x2 + 1][y2 + 1] += c;
}
int main() {

	scanf("%d%d%d", &n2, &m2, &q1);

	for (int i = 1; i <= n2; i++)
		for (int j = 1; j <= m2; j++)
			scanf("%d", &a[i][j]);

	for (int i = 1; i <= n2; i++)
		for (int j = 1; j <= m2; j++)
			insert(i, j, i, j, a[i][j]);

	while (q1--)
	{
		int x1, x2, y1, y2, c;
		cin >> x1 >> y1 >> x2 >> y2 >> c;
		insert(x1, y1, x2, y2, c);

	}

	for (int i = 1; i <= n2; i++)
		for (int j = 1; j <= m2; j++)
			b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];

	for (int i = 1; i <= n2; i++) {
		for (int j = 1; j <= m2; j++) printf("%d ", b[i][j]);
		puts("");
	}

	return 0;
}

六、双指针算法

凡是具有以下形式的算法都可以被称作双指针算法

for(i=0,j=0;j<n;i++){
	while(j<i && check(i,j)) j++;

	//每道题目的具体逻辑
}

核心思想：将下面的朴素算法优化到O（n）

for(int i=0;i<n;i++)
	for(int j=0;j>n;j++)
	O(N^2)

核心思想是利用单调性，省去多余的遍历，
将原本On²的问题化简为On，具体形式可分为：
1.双序列双指针：如归并排序
2.单序列双指针：如字符串匹配

例题：


双指针问题：解决思路可以从暴力做法进行切入

#include
using namespace std;

const int N = 100010;

int n;
int a[N];//原来的数
int s[N];//当前j到i区间每个数出现的次数

int main() {
	cin >> n;
	for (int i = 0; i < n; i++)cin >> a[i];

	int res = 0;
	for (int i = 0, j = 0; i < n; i++) {
		s[a[i]]++;
		while (s[a[i]]>1)
		{
			s[a[j]]--;
			j++;
		}
		res = max(res, i - j + 1);
	}

	cout << res << endl;

	return 0;
}

七、位运算 1、n的二进制表示中第k位是多少？

①先把第k位移动到最后一位 n>>k
②看一下个位是多少  x&1
结合①② 得到公式：n>>k&1

#include
using namespace std;

int main() {

	int n = 10;
		for (int k = 3; k >= 0; k--) 
			cout << (n >> k & 1);
	return 0;
}
//输出结果 1010

2、返回n的最后一位1

lowbit(x):返回x的最后一位1
若x=1010  则 lowbit(x)=10;
若x=10100 则lowbit(x)=100;

实现原理：x&-x = x&(~x+1)
负数-x,存储是补码形式，在x 的基础上取反加1

lowbit应用：统计x中1的个数

//统计二进制中1的个数
#include
using namespace std;

int lowbit(int x) {
	return x & -x;
}
int main() {
	int n;
	cin >> n;
	while (n--) {
		int x;
		cin >> x;
		int res = 0;
		while (x) {
			x -= lowbit(x);//每次减去x的最后一位1
			res++;
		}
		cout << res << ' ';
	}

	return 0;
}

八、离散化

核心思想是将很大范围的稀疏点按次序映射到一个数组中，类似哈希，方便查询一个范围的和等 *** 作。

//区间和
#include
#include
#include
using namespace std;

typedef pair<int, int> PII;

const int N = 300010;//数据规模是n+2m,其中n，m都小于1000000

int n, m;
int a[N], s[N];
vector<int> alls;//存储需要离散化的数据
vector<PII> add;
vector<PII> query;

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;
}
//unique函数实现原理：双指针思想
vector<int>::iterator unique(vector<int>& a) {
	int j = 0;
	for (int i = 0; i < a.size(); i++)
		if (!i || a[i] != a[i - 1])// 将所有满足性质的数拿出来
			a[j++] = a[i];
	//此时，a[0]-a[j-1]所有a中不重复的数

	return a.begin() + j;
}
int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		int x, c;
		cin >> x >> c;
		add.push_back({ x,c });

		alls.push_back(x);
	}
	for (int i = 0; i < m; i++) {
		int l, r;
		cin >> l >> r;
		query.push_back({ l, r });

		alls.push_back(l);
		alls.push_back(r);
	}
	//去重
	sort(alls.begin(), alls.end());
	//alls.erase(unique(alls.begin(), alls.end()), alls.end());
	alls.erase(unique(alls), alls.end());

	for (auto item : add) {
		int x = find(item.first);
		a[x] += item.second;
	}

	//预处理前缀和
	for (int i = 0; i <= alls.size(); i++) {
		s[i] = s[i - 1] + a[i];
	}
	//处理询问
	for (auto item : query) {
		int l = find(item.first), r = find(item.second);
		cout << s[r] - s[l - 1] << endl;
	}
	return 0;
}

//区间合并：
#include
#include
#include
using namespace std;

typedef pair<int, int> PII;

const int N = 100010;
int n;
vector<PII> segs;

void merge(vector<PII>& segs) {
	vector<PII> res;

	sort(segs.begin(), segs.end());//在c++中优先以左端点排序

	int st = -2e9;
	int 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;
}
int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		int l, r;
		cin >> l >> r;
		segs.push_back({ l,r });
	}
	merge(segs);

	cout << segs.size() << endl;

	return 0;
}