algorithm

发表于2025-07-30更新于2025-12-27

算法学习笔记

线性枚举

一种暴力算法，对元素进行依次处理

求最大值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int findMax(vector<int> v) {
    int max = v[0];
    for (int i = 1; i < v.size(); i++) {
        if (v[i] > max) {
            max = v[i];
        }
    }
    return max;
}

int main() {
vector<int> v = {23,12,55,34,87,13,76};
cout <<"Max:"<< findMax(v) << endl;
    return 0;
}
1
2
输出：
Max:87

真题

1550. 存在连续三个奇数的数组

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    bool threeConsecutiveOdds(vector<int>& arr) {
        for(int i=1;i<arr.size()-1;i++){
            if(arr[i-1]%2==1&&arr[i]%2==1&&arr[i+1]%2==1)
                return true;
            
        }
        return false;
    }
};

485. 最大连续 1 的个数

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int findMaxConsecutiveOnes(vector<int>& nums) {
        int sum=0,max=-100;
        for(int i=0;i<nums.size();){
            while(i<nums.size()&&nums[i++]==1) sum++;
            if(max<sum) max=sum;
            sum=0;
        }
        return max;
    }
};

540. 有序数组中的单一元素

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        int i=0;
        for(i=0;i<nums.size()-1;i+=2){
            if(nums[i]!=nums[i+1]){
                return nums[i];
            }
        }
        return nums[i--];
    }
};

模拟

没有特定的算法，按照题目要求一步一步做 废话-_-(

真题

面试题 16.01. 交换数字

1
2
3
4
5
6
7
8
9
class Solution {
public:
    vector<int> swapNumbers(vector<int>& numbers) {
        numbers[0] = numbers[0] ^ numbers[1];
        numbers[1] = numbers[0] ^ numbers[1];
        numbers[0] = numbers[0] ^ numbers[1];
        return numbers;
    }
};

LCR 133. 位 1 的个数

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int hammingWeight(uint32_t n) {
        int count = 0;
        while (n > 0) {
            if (n & 1) {
                count++;
            }
            n >>= 1;
        }
        return count;
    }
};

递推

递推是一个循环或者迭代的过程

斐波那契数列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void fbV() {
    vector<int> v({0,1});
    for(int i=1;i<=30;i++) {
        v.push_back(v[i]+v[i-1]);

    }
    for(int i=0;i<v.size();i++) {
        cout<<v[i]<<" ";
    }
}

int main() {
fbV();
    return 0;
}
1
2
输出：
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040 1346269

真题

70.爬楼梯

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    int climbStairs(int n) {
        vector<int> v({1,1});
        for(int i = 1;i < n;i++){
            v.push_back(v[i-1]+v[i]);
        }
        return v[n];
    }
};

119. 杨辉三角 II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<int> getRow(int rowIndex) {
        int v[35][35];
        for(int i = 0;i<=rowIndex;i++){
            for(int j = 0;j <= i;j++){
                if(j == 0 || j == i) v[i][j] = 1;
                else{
                    v[i][j] = v[i-1][j] + v[i-1][j-1];
                }
            }
        }
        vector<int> n;
        for(int i = 0;i <= rowIndex;i++){
            n.push_back(v[rowIndex][i]);
        }
        return n;
    }
};

排序

选择排序

最暴力的一集，时间复杂度o(n^2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<iostream>
using namespace std;
void select_sort(int* a,int n)
{
	for (int i = 0; i < n; i++)
	{
		int index = i;
		for (int j = i + 1; j < n; j++)
		{
			if (a[index] > a[j])index = j;
		}
		swap(a[i], a[index]);
	}
}
void main()
{
	int a[10]{ 5,7,9,6,3,1,4,8 };
	select_sort(a, 8);
	for (int i = 0; i < 8; i++)
	{
		cout << a[i]<<" ";
	}
}

冒泡排序

最暴力的二集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void MP(vector<int>& v) {
    for (int i = 0; i < v.size()-1; i++) {
        for (int j = 0; j < v.size()-i-1; j++) {
            if (v[j] > v[j+1]) {
                swap(v[j], v[j+1]);
            }
        }
    }
}

void print_vector(vector<int>& v) {
    for (int i = 0; i < v.size(); i++) {
        cout << v[i] << " ";
    }
    cout << endl;
}

int main() {
    vector<int> v({93,21,43,6,1,3,5,3,23,32});
    MP(v);
    print_vector(v);

    return 0;
}

插入排序

最暴力的三集

1
2
3
4
5
6
7
8
9
10
11
12
13
void InsertSort(vector<int>& v) {
    for (int i = 1; i < v.size(); i++) {
        int temp = v[i];  // 保存当前要插入的元素
        int j = i - 1;

        // 移动元素，找到插入位置
        while (j >= 0 && v[j] > temp) {
            v[j + 1] = v[j];  // 元素后移
            j--;
        }
        v[j + 1] = temp;  // 将待插入元素放到正确位置
    }
}

计数排序

用好了效率爆炸，用不好程序爆炸，最局限的一集

1
2
3
4
5
6
7
8
9
10
11
12
13
void countingSort(vector<int>& v) {
    vector<int> temp(10000);
    for (int i = 0; i < v.size(); i++) {
        temp[v[i]] += 1;
    }
    v.clear();
    for (int i = 0; i < temp.size(); i++) {
        while (temp[i] > 0) {
            v.push_back(i);
            temp[i] -= 1;
        }
    }
}

归并排序

回归到了人类可以使用的排序，归并思想拆开来说就是递归和合并，先通过递归逻辑拆到最简处理，然后再合并

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
vector <int> tem;
void merge_sort(vector<int>& v, int l, int r) {
    if (l >= r) return;
    int mid = (l+r)/ 2;
    merge_sort(v, l, mid);
    merge_sort(v, mid + 1, r);

    int i  = l ,j = mid + 1 ;
    while (i <= mid && j <= r) {
        if (v[i] <= v[j]) {
            tem.push_back(v[i++]);
        }
        else {
            tem.push_back(v[j++]);
        }
    }
    while (i <= mid) tem.push_back(v[i++]);
    while (j <= r) tem.push_back(v[j++]);
    for (int k = l,p = 0; k <= r; k++,p++) v[k] = tem[p];
    tem.clear();
}

快速排序

桶排序

基数排序

堆排序

哈希

贪心

前缀和

双指针

滑动窗口

二分查找

最短路Dijkstra

最小生成树Prim

深度&&广度优先搜索

深度优先搜索

广度优先搜索

数据结构

树

二叉树

二叉搜索树

图

邻接矩阵

邻接表

哈希表

数论

质数

约数

费马定理

欧拉函数

快速幂

扩展欧几里得算法

中国剩余定理

高斯消元

组合计数

容斥原理

简单博弈论

最短路

最短路Bellman-Ford

最短路Floyd

最短路Dijkstra+Heap

最短路SPFA

DP

线性DP

拓扑排序

记忆化搜索

0/1背包

0/1背包空间优化

完全背包

完全背包时间优化

区间DP

计数类DP

数位统计DP

状态压缩DP

树形DP