thetheOrange的笔记

发表于 分类于 本文字数： 4k 阅读时长 ≈ 7 分钟

字典树的定义和使用场景

  • 定义

每个样本，从头结点开始，根据字符或者前缀数字构建出来的树，称之为前缀树

字典树

  • 使用场景

当需要根据前缀信息查询时，可以使用字典树

字典树的实现

用类描述

最经典的描述，但是对于字符种类过多的情况，难以处理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <iostream>

using namespace std;

typedef struct TREENODE {
	int pass;
	int end;
	struct TREENODE* next[26] = {};
	TREENODE() : pass(0), end(0) {};
}TreeNode;

class Trie {
public:
	TreeNode* root = nullptr;
	Trie() {
		root = new TreeNode();
	}
	// 插入word
	void insert(string word) {
		TreeNode* node = root;
		node->pass++;
		for (auto c : word) {
			int path = c - 'a';
			// 如果路径为空 则添加路径
			if (!node->next[path]) {
				node->next[path] = new TreeNode();
			}
			node = node->next[path];
			node->pass++;
		}
		node->end++;
	}
	// 查询word个数
	int countWord(string word) {
		TreeNode* node = root;
		for (auto c : word) {
			int path = c - 'a';
			// 如果路径为空 则说明不存在这个word
			if (!node->next[path]) return 0;
			node = node->next[path];
		}
		return node->end;
	}
	// 查询前缀
	int countPrefix(string prefix) {
		TreeNode* node = root;
		for (auto c : prefix) {
			int path = c - 'a';
			// 如果路径为空 则说明不存在这个prefix
			if (!node->next[path]) return 0;
			node = node->next[path];
		}
		return node->pass;
	}
	// 删除word
	void erase(string word) {
		// 先判断是否存在这个word
		if (countWord(word) > 0) {
			TreeNode* node = root;
			node->pass--;
			for (auto c : word) {
				int path = c - 'a';
				if (--node->next[path]->pass == 0) {
					// delete 后面的节点
					node->next[path] = nullptr;
					return;
				}
				node = node->next[path];
			}
			node->end--;
		}
	}
};

哈希表+类 实现

使用哈希表进行了优化，可以处理字符种类多的情况，但是依旧浪费大量的空间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
typedef struct TREENODE {
	int pass;
	int end;
	unordered_map<char, struct TREENODE*> next;
	TREENODE() : pass(0), end(0) {};
}TreeNode;

class Trie {
public:
	TreeNode* root = nullptr;
	Trie() {
		root = new TreeNode();
	}
	// 插入word
	void insert(string word) {
		TreeNode* node = root;
		node->pass++;
		for (auto c : word) {
			// 如果c不存在路径中 则新建一条路径
			if (node->next.count(c) == 0) {
				node->next[c] = new TreeNode();
			}
			node = node->next[c];
			node->pass++;
		}
		node->end++;
	}
	// 查询word个数
	int countWord(string word) {
		TreeNode* node = root;
		for (auto c : word) {
			if (node->next.count(c) == 0) return 0;
			node = node->next[c];
		}
		return node->end;
	}
	// 查询前缀
	int countPrefix(string word) {
		TreeNode* node = root;
		for (auto c : word) {
			if (node->next.count(c) == 0) return 0;
			node = node->next[c];
		}
		return node->pass;
	}
	// 删除word
	void erase(string word) {
		if (countWord(word) > 0) {
			TreeNode* node = root;
			node->pass--;
			for (auto c : word) {
				if (--node->next[c]->pass == 0) {
					// delete 节点
					node->next.erase(c);
					return;
				}
				node = node->next[c];
			}
			node->end--;
		}
	}
};

用静态数组实现

使用静态数组对空间进行了优化，这样无论是多大数据，都可以只申请一次确定空间，进行查询

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <iostream>

using namespace std;

#define MAX 1000

class Trie {
public:
	int nexts[MAX][26] = { {0} };
	int pass[MAX] = { 0 };
	int end[MAX] = { 0 };
	int cnt = 1;
	Trie() {
		cnt = 1;
	}
	// 插入word
	void insert(string word) {
		int cur = 1;
		pass[cur]++;
		for (auto c : word) {
			// 如果c不存在路径中 则新建一条路径
			int path = c - 'a';
			if (nexts[cur][path] == 0) {
				nexts[cur][path] = ++cnt;
			}
			cur = nexts[cur][path];
			pass[cur]++;
		}
		end[cur]++;
	}
	// 查询word个数
	int countWord(string word) {
		int cur = 1;
		for (auto c : word) {
			int path = c - 'a';
			if (nexts[cur][path] == 0) return 0;
			cur = nexts[cur][path];
		}
		return end[cur];
	}
	// 查询前缀
	int countPrefix(string word) {
		int cur = 1;
		for (auto c : word) {
			int path = c - 'a';
			if (nexts[cur][path] == 0) return 0;
			cur = nexts[cur][path];
		}
		return pass[cur];
	}
	// 删除word
	void erase(string word) {
		if (countWord(word) > 0) {
			int cur = 1;
			pass[cur]--;
			for (auto c : word) {
				int path = c - 'a';
				if (--pass[nexts[cur][path]] == 0) {
					nexts[cur][path] = 0;
					return;
				}
				cur = nexts[cur][path];
			}
			end[cur]--;
		}
	}

};

发表于 分类于 本文字数： 531 阅读时长 ≈ 1 分钟

适用场景

所有子问题规模相同的递归才能用master公式

公式介绍

T(n) = a * T(n/b) + O(n^c), 其中a, b, c都是常数, a为执行了几次相同规模的子问题，b为子问题的规模，O(n^c)为递归问题外的其他时间复杂度

  1. 如果log(b, a) < c 复杂度为O(n^c)
  2. 如果log(b, a) > c 复杂度为O(n^log(b, a))
  3. 如果log(b, a) == c 复杂度为O(n^c * log n)

补充

T(n) = 2*T(n/2) + O(n*log n)的时间复杂度为O(n* ((log n)的平方))

实例分析

1
2
3
4
5
6
7
int getMax(vector<int>& nums, int l, int r) {
    if (l == r) return nums[l];
    int mid = (l + r) / 2;
    int lmax = getMax(nums, l, mid);
    int rmax = getMax(nums, mid + 1, r);
    return max(lmax, rmax);
}

根据master公式，可得T(n) = 2*(n/2) + O(1)，进而a = 2, b = 2, c = 0，从而log(2, 2) > c，由此时间复杂度为O(n)

感谢

本文整理自左神的 算法讲解020【必备】递归和master公式

发表于 分类于 本文字数： 319 阅读时长 ≈ 1 分钟

暴力解法

对1~n进行枚举

1
2
3
4
5
for (int i = 1; i <= n; ++i) {
    if (n % i == 0) {
        cout << i << endl;
    }
}

这个时候，时间复杂度为O(n)

优化

当n % i == 0且i * i < n，n / i为n的一个因子。由此，我们可以做如下的优化：

1
2
3
4
5
6
7
for (int i = 1; i * i <= n; ++i) {
    if (n % i != 0) continue;
    cout << i << endl;
    if (i * i < n) {
        cout << n / i << endl;
    }
}

时间复杂度就降为了O(sqrt(n))

发表于 更新于 分类于 本文字数： 832 阅读时长 ≈ 2 分钟

正数和负数在二进制中的表达

正数的二进制状态转负数的二进制：

  1. -1
  2. 依次取反

例：
7的二进制为 0111 转为负数则为 0110 -> 1001

负数的二进制状态转正数的二进制，为逆过程：

  1. 依次取反
  2. +1

例：
-7的二进制为 1001 转为正数则为 0110 -> 0111

常见的位运算操作符

  • | 或

    相同位次中只要出现1则返回1

    如 0010 | 0111 = 0111

  • & 与

    相同位次中都出现1则返回1

    如 0010 & 0111 = 0010

  • ~ 取反

    0变成1，1变成0

    如 ~0010 = 1101

  • ^ 异或

    相同位次中都不同才返回1，否则返回0。可以看成无进位的相加

    如 0010 ^ 0111 = 0101

  • >> 右移 和 << 左移

    将二进制整体向左/右移动k位，多出的位置用0补

    如 0010 >> 1 = 0100 0010 >> 1 = 0001

    对于非负整数而言 左移相当于扩大2的k次方倍，左移相当于缩小2的k次方倍

  • >>> 右移

    和>>功能相同，但是多出的位置用符号位补

    如 1010 >>> 1 = 1101

一些技巧

取每个位次的数

对于32位的int类型数据，可以用如下方法依次取出每个位次的数

1
2
3
4
5
// 输入num
for (int i = 31; i >= 0; --i) {
	int tmp = (num >> i) & 1;
	std::cout << tmp << ' ';
}

向二进制状态填入1

对于0而言，可以用如下方法向指定位置填入1

1
ans |= 1 << i; // i为指定位置

异或运算的性质和Brain Kernighan算法

异或运算的性质：

  1. a ^ 0 = 0、a ^ a = 0
  2. 异或运算可以看成是无进位的相加
  3. 异或运算满足交换律 即a ^ b = c -> c ^ b = a
  4. 负数和正数的相互转化可以用a = ~a + 1，相当于a = -a

Brain Kernighan算法

目的：提取出二进制状态最右边的1

1
int pos = a & (-a);

发表于 更新于 分类于 本文字数： 5.6k 阅读时长 ≈ 10 分钟

辅助函数

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

// 交换函数
void swap(vector<int>& nums, int x, int y) {
	int tmp = nums[x];
	nums[x] = nums[y];
	nums[y] = tmp;
}

// 测试函数
void test(vector<int>& nums) {
	for (auto i : nums) cout << i << ' ';
}

选择排序

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

/* 
选择排序
在每一轮找到最小的值插入到数组前面
时间复杂度 O(n^2)
空间复杂度 O(1)
稳定性 无
*/
void selectionSort(vector<int>& nums) {
	int n = nums.size();
	for (int i = 0; i < n - 1; ++i) {
		int min_el = INT_MAX, min_index = -1;
		for (int j = i; j < n; ++j) {
			if (nums[j] < min_el) {
				min_el = nums[j];
				min_index = j;
			}
		}
		swap(nums, i, min_index);
	}
}

冒泡排序

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

/*
冒泡排序
两两比较大小 大的数字往后移
时间复杂度 O(n^2)
空间复杂度 O(1)
*/
void bubbleSort(vector<int>& nums) {
	int n = nums.size();
	for (int i = 0; i < n - 1; ++i)
		for (int j = 0; j < n - i; ++j) {
			if (j + 1 < n && nums[j] > nums[j + 1]) swap(nums, j, j + 1);
		}
}

直接插入排序

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

/*
直接插入排序
依次选择最小的值插入到数组前面
时间复杂度 O(n^2)
空间复杂度 O(1)
稳定性 有
*/
void insertSort(vector<int>& nums) {
	int n = nums.size();
	for (int i = 1; i < n; ++i)
		for (int j = i - 1; j >= 0 && nums[j + 1] < nums[j]; --j)
			swap(nums, j + 1, j);
}

二分插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

/*
二分插入排序
根据前面数组的有序性 二分查找最小的值插入到数组前面
时间复杂度 O(n^2)
空间复杂度 O(1)
稳定性 有
*/
int lower_bound(vector<int>& nums, int start, int end, int x) {
	int l = start, r = end;
	while (l <= r) {
		int mid = (l + r) / 2;
		if (x > nums[mid]) l = mid + 1;
		else r = mid - 1;
	}
	return l;
}

void insertSort_2(vector<int>& nums) {
	int n = nums.size();
	if (n <= 1) return;
	// 前2个元素按从小到大排序
	if (nums[1] < nums[0]) swap(nums, 0, 1);
	for (int i = 2; i < n; ++i) {
		int pos = lower_bound(nums, 0, i - 1, nums[i] + 1);
		pos = pos == n ? n - 1 : pos;
		int x = nums[i];
		// 插入元素
		for (int j = i - 1; j >= pos; --j) {
			swap(nums, j, j + 1);
		}
	}
}

希尔排序

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

/*
希尔排序
对子表进行插入排序
时间复杂度(n^2)
空间复杂度O(1)
稳定性 无
*/
void shellSort(vector<int>& nums, int d) {
	int n = nums.size();
	while (d >= 1) {
		// 以下为插入排序的流程 不过步长改为了d
		for (int i = d; i < n; ++i) {
			for (int j = i - d; j >= 0 && nums[j + d] < nums[j]; j -= d) {
				swap(nums, j + d, j);
			}
		}
		d /= 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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

/*
快速排序
时间复杂度 O(n*log n)
空间复杂度 O(log n)
稳定性 无
*/
// 快速排序 第一种写法
void quickSort(vector<int>& nums, int start, int end) {
	if (start >= end) return;
	int left = start, right = end, pivot = nums[start];
	while (left < right) {
		// 移动右指针 直到遇到小于pivot的元素
		for (; left < right && nums[right] >= pivot; )  --right;
		// 处理比pivot小的元素
		nums[left] = nums[right];
		// 移动左指针 直到遇到大于pivot的元素
		for (; left < right && nums[left] <= pivot; ) ++left;
		// 处理比pivot大的元素
		nums[right] = nums[left];
	}
	// 归位pivot
	nums[left] = pivot;
	quickSort(nums, start, left - 1);
	quickSort(nums, left + 1, end);
}
// 快速排序 第二种写法
void quickSort2(vector<int>& nums, int l, int r) {
	if (l >= r) return;
	int pivot = nums[l], slow = l;
	for (int i = l; i <= r; ++i) {
		if (nums[i] <= pivot) {
			swap(nums, i, slow);
			++slow;
		}
	}
	swap(nums, slow - 1, l);
	quickSort2(nums, l, slow - 2);
	quickSort2(nums, slow, r);
}

堆排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

/*
堆排序
时间复杂度 O(n*log n)
空间复杂度 O(1)
稳定性 无
*/
// 向上调整
void heapInsert(vector<int>& heap, int i) {
	while (i >= 1 && heap[i] > heap[(i - 1) / 2]) {
		swap(heap, i, (i - 1) / 2);
		i = (i - 1) / 2;
	}
}

// 向下调整
void heapify(vector<int>& heap, int i, int size) {
	int l = 2 * i + 1;
	while (l < size) {
		// 从左右孩子中选出最大的孩子
		int mx = l + 1 < size && heap[l] < heap[l + 1] ? l + 1 : l;
		// 比较最大的孩子与当前元素
		if (heap[i] >= heap[mx]) break;
		// 如果当前元素比最大的孩子小 则向最大的孩子移动
		swap(heap, i, mx);
		// 更新 i, l
		i = mx;
		l = 2 * i + 1;
	}

}

// 建堆 自下而上
void build_bottom(vector<int>& ns) {
	int n = ns.size();
	for (int i = n - 1; i >= 0; --i) {
		heapify(ns, i, n);
	}
}

// 建堆 自上而下
void build_top(vector<int>& ns) {
	int n = ns.size();
	for (int i = 0; i < n; ++i) {
		heapInsert(ns, i);
	}
}

void heapSort(vector<int>& nums, void(*build)(vector<int>& ns)) {
	int n = nums.size(), last = n;
	// 建堆 
	build_bottom(nums);
	// 大数归位
	while (last > 1) {
		swap(nums, 0, last - 1);
		--last;
		heapify(nums, 0, last);
	}
}

归并排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

/*
归并排序
递归将数组分成两部分 分别将这两部分排序好 再合并 最后将辅助数组里面的值刷回原数组
时间复杂度 O(n*log n)
空间复杂度 O(n)
稳定性 有
*/

void merge(vector<int>& nums, int l, int mid, int r) {
	vector<int> help((int)nums.size(), 0); // 辅助数组
	int i = l, a = l, b = mid + 1;
	while (a <= mid && b <= r) {
		help[i++] = nums[a] <= nums[b] ? nums[a++] : nums[b++];
	}
	// 必有一个指针越界 要么是a 要么是b
	while (a <= mid) {
		help[i++] = nums[a++];
	}
	while (b <= r) {
		help[i++] = nums[b++];
	}
	// 将辅助数组中的数据刷回原数组
	for (int j = l; j <= r; ++j) {
		nums[j] = help[j];
	}
}

void mergeSort(vector<int>& nums, int l, int r) {
	if (l == r) return;
	int mid = (l + r) / 2;
	mergeSort(nums, l, mid);
	mergeSort(nums, mid + 1, r);
	merge(nums, l, mid, r);
}

桶排序（基数排序）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

/*
桶排序 (基数排序)
时间复杂度 O(n)
空间复杂度 O(n + k) k为桶的数量
稳定性 有
*/
// 十进制
int BASE = 10;
// 计数位数
int countDigit(int x) {
	int cnt = 0;
	while (x > 0) {
		x /= BASE;
		++cnt;
	}
	return cnt;
}

void radixSort(vector<int>& nums) {
	int min_el = INT_MAX, max_el = INT_MIN, n = nums.size();
	// 获取最小值和最大值
	for (auto i : nums) {
		min_el = min(min_el, i);
		max_el = max(max_el, i);
	}
	// bits：nums中最大值的位数
	int bits = countDigit(max_el);
	// 将nums中的所有值减去最小值
	for (int i = 0; i < n; ++i) nums[i] -= min_el;
	vector<int> help(n, 0);
	// 桶排序
	for (int offset = 1, i = 0; i < bits; ++i, offset *= BASE) {
		vector<int> cnts(BASE, 0);
		// 统计各个位数的次数
		for (auto num : nums) cnts[(num / offset) % BASE]++;
		// 计算前缀位数次序和
		for (int j = 1; j < BASE; ++j) cnts[j] += cnts[j - 1];
		// 倒序遍历nums 插入对应位置的元素到help中
		for (int j = n - 1; j >= 0; --j) {
			help[--cnts[(nums[j] / offset) % BASE]] = nums[j];
		}
		// 将help数组中的值刷入nums中
		for (int j = 0; j < n; ++j) nums[j] = help[j];
	}
	// 还原数组
	for (int i = 0; i < n; ++i) nums[i] += min_el;
}

0%