basic_1_算法基础知识

content {:toc}

基础知识

代码风格

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int slowIndex = 0;
        for (int fastIndex = 0; fastIndex < nums.size(); fastIndex++) {
            if (nums[fastIndex] != 0) {
                nums[slowIndex++] = nums[fastIndex];
            }
        }
        for (int i = slowIndex; i < nums.size(); i++) {
            nums[i] = 0;
        }
    }
};

ACM模式

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


#include<iostream>
#include<vector>
using namespace std;
int main() {
    int n;
    while (cin >> n) {
        vector<int> gym(n);
        vector<int> work(n);
        for (int i = 0; i < n; i++) cin >> work[i];
        for (int i = 0; i < n; i++) cin >> gym[i];
        int result = 0;

        // 处理逻辑

        cout << result << endl;
    }
    return 0;
}

leetcode模式/ 核心代码模式

只关注核心逻辑, 培养算法思维

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int slowIndex = 0;
        for (int fastIndex = 0; fastIndex < nums.size(); fastIndex++) {
            if (nums[fastIndex] != 0) {
                nums[slowIndex++] = nums[fastIndex];
            }
        }
        for (int i = slowIndex; i < nums.size(); i++) {
            nums[i] = 0;
        }
    }
};

究竟什么是时间复杂度

时间复杂度是一个函数，它定性描述该算法的运行时间。

我们在软件开发中，时间复杂度就是用来方便开发者估算出程序运行的答题时间。

那么该如何估计程序运行时间呢，通常会估算算法的操作单元数量来代表程序消耗的时间，这里默认 CPU 的每个单元运行消耗的时间都是相同的。

假设算法的问题规模为 n，那么操作单元数量便用函数 f (n) 来表示，随着数据规模 n 的增大，算法执行时间的增长率和 f (n) 的增长率相同，这称作为算法的渐近时间复杂度，简称时间复杂度，记为 O (f (n))。

什么是大o什么是大 O

这里的大 O 是指什么呢，说到时间复杂度，大家都知道 O (n)，O (n^2)，却说不清什么是大 O。

算法导论给出的解释：大 O 用来表示上界的，当用它作为算法的最坏情况运行时间的上界，就是对任意数据输入的运行时间的上界。

同样算法导论给出了例子：拿插入排序来说，插入排序的时间复杂度我们都说是 O (n^2) 。

输入数据的形式对程序运算时间是有很大影响的，在数据本来有序的情况下时间复杂度是 O (n)，但如果数据是逆序的话，插入排序的时间复杂度就是 O (n^2)，也就对于所有输入情况来说，最坏是 O (n^2) 的时间复杂度，所以称插入排序的时间复杂度为 O (n^2)。

同样的同理再看一下快速排序，都知道快速排序是 O (nlogn)，但是当数据已经有序情况下，快速排序的时间复杂度是 O (n^2) 的，所以严格从大 O 的定义来讲，快速排序的时间复杂度应该是 O (n^2)。

但是我们依然说快速排序是 O (nlogn) 的时间复杂度，这个就是业内的一个默认规定，这里说的 O 代表的就是一般情况，而不是严格的上界。

比如下面的常用算法的运行时间

排序算法	平均时间复杂度	最好情况	最坏情况	空间复杂度	排序方式	稳定性
冒泡排序	O(n^2)	O(n)	O(n^2)	OG)	In-place	稳定
快速排序	O(n log n)	O( n logn)		Olon n	In-place	不稳定

抓主要矛盾

1
2
3
4


O(2*n^2 + 10*n + 1000)
= O(2*n^2 + 10*n)
= O(n^2 + n)
= O(n^2)

O (nlogn) 和 O (n)

在算法的时间复杂度分析中，O (nlogn) 和 O (n) 是具有明显差异的复杂度级别。尽管它们都随着输入规模 n 的增加而增加，但增长率不同。

当 n 增加时，O (nlogn) 的增长速度比 O (n) 快得多。具体来说，当 n 增加时，O (nlogn) 的增长率是线性对数级别（即 n 乘以其对数）。而 O (n) 的增长率是线性级别（即 n 的倍数）。

举个例子，假设 n = 10^6，则 O (n) 的时间复杂度为 10^6，而 O (nlogn) 的时间复杂度为 10^6 * log₂(10^6)，约为 10^6 * 20 ≈ 2 * 10^7。可以看到，O (nlogn) 明显大于 O (n)。

当输入规模较大时，如 n = 10^9，O (n) 的时间复杂度为 10^9，而 O (nlogn) 的时间复杂度为 10^9 * log₂(10^9)，约为 10^9 * 30 ≈ 3 * 10^10。同样可以看到，O (nlogn) 明显大于 O (n)。

1
2
3
4


2^10 = 1024 ≈ 1000 
n = 1000 时
O(n) = 1000
O(nlogn) = (1000 * 10) = 10,000

2 一些技巧

1.0 如何判断你的代码能不能在规定时间内通过:

机器处理的数据量为 1e8
因此，一般1e4 范围内的数据可以 O(n2), 1e5范围内的数据O(nlogn)

1.1 概念辨析

命令	解释
fun(x++)	输入到函数里面的是 x
fun(++x)	输入到函数里面的是 x+1
if(! flag)	当 flag == 0的时候执行
if( 1== a)	写出if(1=a)就会报错, 少打了=
int n = 1e5	少写几个零
(a, b)中有	b-a+1 个数字
vector<int>的中位数	a[n/2] 或者 1/2 * (a[n/2] +a[n/2 -1] )
max({a, b, c,,,})	abc,,,,中最大的数

1.2 各种初始化

有三种初始化方式,

小括号初始化, 当你想用默认初始化时, Weight(), 会声明一个函数
大括号统一初始化, 从概念上可以用于一切场合, 表达一切意思的初始化, 有个新特性, 禁止内建型别之间进行隐式窄化型别转化

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


// -----------------------初始化-------------------------
// 列表初始化
vector<vector<int> > map = {
    {1, 0}, {-1, 0}, {0, 1}, {0, -1}
};

// 多维数组的列表初始化, 和上面一样
int map[4][2] = {1, 0, -1, 0, 0, 1, 0, -1};

// 默认值的初始化, 全部是 0
int a[26] ={};
int a[26]{};

// 前三个是 1, 2, 3, 后面的值都是 0 
int a[26] ={1, 2, 3};

// 大括号 初始化
vector<int> v{1,3,4};

1.3 巧用引用`ref`

1
2
3
4
5
6
7
8


// -----------------------巧用引用-------------------------
void mysort(vector<int> &nums){
    // 如果要对数组元素进行改变, 可以使用引用. 
    for(int &x: nums){
        if(x% 2) x=-x;
    }
    sort(nums.begin(), nums.end());
}

1.4 数组的中位数

长度为len, 奇数: 正中间, 偶数中间偏右
使用下标时, a[l, r] $\frac{l+r}{2}$中间靠左

1.6 类型上下界

缩写	类型
INT_MAX INT_MIN	int 类型最大最小
UINT_MAX	unsigned 最大最小
LONG_MIN
LLONG_MAX	long long最大最小
ULONG_MAX

1.5 模板访问类内部成员

模拟题才会用到

1
2
3
4
5
6


// 访问类内部的类型时, 一般而言, 需要实例化以后才可以访问类内部的对象
template<typename T>
class Myclass{
    typename T::subtype *ptr;
}
// 含义是指向类内部类型的指针