Guff_9hys

这个屌丝很懒，什么也没留下！

热门标签

核心算法模板

作者：Guff_9hys | 2024-07-03 20:18:27

踩

核心算法模板

面试手撕算法通关 -- 持续更新

单链表

#include <iostream>
#include <vector>
using namespace std;
// 节点结构
struct ListNode {
	int val;
	ListNode* next;
	ListNode(int x) :val(x), next(NULL) {}
};
// 创建链表
ListNode* Creat(vector<int>& arr) {
	ListNode* p, * dummy, * pre;	// 注意这种连续初始化的方式！
	dummy = new ListNode(0);	// 给一个初始值0（虚拟头节点）
	pre = dummy;
	for (int i = 0; i < arr.size(); ++i) {
		p = new ListNode(arr[i]);
		pre->next = p;
		pre = p;
	}
	return dummy->next;
}
int main() {
	vector<int> arr = { 5,4,3,2,1,0 };
	ListNode* L = Creat(arr);
    // 打印链表
	while (L != NULL) {
		cout << L->val;
		L = L->next;
	}
	return 0;
}
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

双向链表

struct ListNode {
	int val;
	ListNode* prev;
	ListNode* next;
	ListNode(int v) :val(v), prev(nullptr), next(nullptr) {}
};

class DoubleList {
public:
	DoubleList() {
		head = new ListNode(0);
		tail = new ListNode(0);
		head->next = tail;
		tail->prev = head;
	}
	// 在链表尾部添加节点x，时间 O(1)
	void AddList(ListNode* x) {
		x->prev = tail->prev;
		x->next = tail;
		tail->prev->next = x;
		tail->prev = x;
	}
	// 删除链表中的 x 节点
	void Remove(ListNode* x) {
		x->next->prev = x->prev;
		x->prev->next = x->next;
	}

private:
	ListNode* head;
	ListNode* tail;
};
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

LRU

// 创建节点
struct Node {
	int key, val;
	Node* prev;	// 前驱节点
	Node* next;	// 后驱节点
	Node(int k, int v) :key(k), val(v), prev(nullptr), next(nullptr) {}
};
// 创建双向链表类
class DoubleList {
public:
    DoubleList() {
        head = new Node(0, 0);
        tail = new Node(0, 0);
        head->next = tail;
        tail->prev = head;
        size = 0;
    }
   
    void addList(Node* x) {  // 在链表尾部添加节点x，时间 O(1)
        x->prev = tail->prev;
        x->next = tail;
        tail->prev->next = x;
        tail->prev = x;
        size++;
    }
    
    void remove(Node* x) {	// 由于是双链表且给的是目标 Node 节点，时间 O(1)
        x->next->prev = x->prev;
        x->prev->next = x->next;
        size--;
    }
    
    Node* removeFirst() {	// 自定义函数：删除链表中第一个节点，并返回该节点，时间 O(1)
        if (head->next == tail)	// 若无插入，则默认不移除，返回空指针
            return nullptr;
        Node* first = head->next;
        remove(first);
        return first;
    }
    
    int sizeOfList() {	// 返回链表长度，时间 O(1)
        return size;
    }
private:
    Node* head; // 双向链表头节点
    Node* tail; // 双向链表尾节点
    int size;
};

class LRUCache {
public:
	LRUCache(int capacity) :cap(capacity) {}

	int get(int key) {
		if (!hashMap.count(key)) {
			return -1;
		}
		makeRecently(key);	// 将该数据提升为最近使用的
		return hashMap[key]->val;
	}

	void put(int key, int value) {
		if (hashMap.count(key)) {
			//makeRecently(key);  //不能这样写！提升key操作不会更改hashmap中键key对应的值val，而此处put需要更新val（即使遇到已经存在的索引key）
			deleteKey(key);	// 删除旧的数据	
			addRecently(key, value); // 新插入的数据为最近使用的数据
			return;
		}
		if (cache.sizeOfList() == cap) {	// 若容量已满，需要删除最久未使用的key
			removeLeastRecently();
		}
		addRecently(key, value);
	}

private:
	/*--------私有方法：哈希链表的抽象API--------*/
	void makeRecently(int key) { // 将某个 key 提升为最近使用 ——> 在 get 方法中，使用（获取）需要将 key 键值对提升为最近使用
		Node* x = hashMap[key];
		cache.remove(x);	// 先从链表中删除这个节点
		cache.addList(x);	// 重新插到队尾
	}
	void addRecently(int key, int val) { // 添加最近使用的元素 ——> 在 put 方法中，修改 or 插入时都需要该添加操作 
		Node* x = new Node(key, val);
		cache.addList(x);	 // 链表尾部就是最近使用的元素
		hashMap.insert(make_pair(key, x));	// 注意：记得在哈希表中添加映射！！！
	}
	void deleteKey(int key) { // 删除某个key ——> 在 put 方法中，修改时需要先删除
		Node* x = hashMap[key];
		cache.remove(x);	// 从链表中删除
		hashMap.erase(key);	// 从 map 中删除
	}
	// 删除最久未使用的元素 ——> 在 put 方法中，插入时需要先验证容量是否满，若满，则需要移除最久没使用的
	void removeLeastRecently() {
		Node* x = cache.removeFirst();	// 链表头部的第一个元素就是最久未使用的
		int deleteKey = x->key;
		hashMap.erase(deleteKey);	// 注意：别忘了从 map 中删除它的 key！！！
	}

private:
	unordered_map<int, Node*> hashMap;
	DoubleList cache;
	int cap;
};
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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103

------------------------

二叉树：构建

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
// 节点结构
struct TreeNode {
	int val;
	TreeNode* left;
	TreeNode* right;
	TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
// 根据数组构造二叉树
TreeNode* ConstructBinaryTree(const vector<int>& vec) {
	vector<TreeNode*> vecTree(vec.size(), NULL);	// 注意：初始化指针置空
	TreeNode* root = NULL;
	for (int i = 0; i < vec.size(); i++) {
		TreeNode* node = NULL;	// 初始化为空节点
		if (vec[i] != -1) {
			node = new TreeNode(vec[i]);	// 非空节点
		}
		vecTree[i] = node;	// 赋值节点
		if (i == 0) {	// 找到根节点
			root = node;
		}
	}
	for (int i = 0; i * 2 + 2 < vec.size(); i++) {
		if (vecTree[i] != NULL) {
			vecTree[i]->left = vecTree[i * 2 + 1];
			vecTree[i]->right = vecTree[i * 2 + 2];
		}
	}
	return root;
}
int main() {
	// 用 -1 来表示null，注意：本代码没有考虑输入异常数据的情况
	vector<int> vec = { 4,1,6,0,2,5,7,-1,-1,-1,3,-1,-1,-1,8 };	// 代表的其实是：二叉树的层序遍历
	TreeNode* root = ConstructBinaryTree(vec);
}
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

二叉树：迭代遍历

/*	----【深度优先遍历-DFS】的统一迭代法（标志位法）框架----	*/
vector<int> postorderTraversal(TreeNode* root) {
    vector<int> result;
    stack<TreeNode*> st;	//利用：栈---先进后出
    if (root != NULL) st.push(root);
    while (!st.empty()) {
        TreeNode* node = st.top();
        if (node != NULL) {          
            st.pop(); 	//将该访问的中间节点弹出，避免重复操作，下面会重新再将该中间节点添加到栈中     
            //前序遍历（中左右）（遵循：入栈顺序和遍历顺序相反！）
            if (node->right) st.push(node->right);  // 右
            if (node->left) st.push(node->left);    // 左
            st.push(node);                          // 中
            st.push(NULL);
            //中序遍历（左中右）
            if (node->right) st.push(node->right);  // 右
            st.push(node);                          // 中
            st.push(NULL);
            if (node->left) st.push(node->left);    // 左			   
            //后续遍历（左右中）
            st.push(node);                          // 中
            st.push(NULL);
            if (node->right) st.push(node->right);  // 右
            if (node->left) st.push(node->left);    // 左
        } 
        else {
            st.pop();	// 将空节点弹出
            node = st.top();	// 取出访问的中间元素
            st.pop();
            // 节点处理逻辑语句{.....}！！！根据题意修改！
            result.push_back(node->val);
        }
    }
    return result;
}

/*	----【广度优先遍历-BFS（层级遍历）】的迭代法框架（关键！！！）----	*/
vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> result;
    queue<TreeNode*> que;	//利用：队列---先进先出
    if (root != NULL) que.push(root);  
    // while 循环控制一层一层往下走，for 循环利用 size 变量控制从[左到右]遍历每一层二叉树节点。
    while (!que.empty()) {
        int size = que.size();	//注意！
        vector<int> vec;
        // 这里一定要使用先固定大小size，不要使用que.size()，因为que.size在for中是不断变化的！
        for (int i = 0; i < size; i++) {
            TreeNode* node = que.front();
            que.pop();
            vec.push_back(node->val);	// 划重点：根据题意修改！eg：这里是遍历，存储当前节点值
            if (node->left) que.push(node->left);
            if (node->right) que.push(node->right);
        }
        result.push_back(vec);	 // 划重点：更新整棵树的遍历结果在这里
    }
    return result;
}
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

快速排序

class Quick {
public:
    void sort(vector<int>& nums) {
        shuffle(nums);	// 洗牌算法，将输入的数组随机打乱，避免出现耗时的极端情况
        sort(nums, 0, nums.size() - 1);	// 排序整个数组（原地修改）
    }
private:
    void sort(vector<int>& nums, int low, int high) {
        if (low >= high)   return;	// 注意：根据partition函数，p的范围：[low,high]，故递归sort的判断应该是>=而非==
        int p = partition(nums, low, high);	// 对 nums[lo..hi] 进行切分，使得 nums[lo..p-1] <= nums[p] < nums[p+1..hi]
        sort(nums, low, p - 1);
        sort(nums, p + 1, high);
    }
    // 对 nums[lo..hi] 进行切分（关键函数！！！必背！）
    int partition(vector<int>& nums, int low, int high) {
        int pivot = nums[low];
        int i = low + 1, j = high;	// 尤其注意：把 i, j 定义为开区间，同时定义：[lo, i) <= pivot；(j, hi] > pivot
        // 当 i > j 时结束循环，以保证区间 [lo, hi] 都被覆盖
        while (i <= j) {
            while (i < high && nums[i] <= pivot) {	// 此 while 结束时恰好 nums[i] > pivot
                i++;
            }	
            while (j > low && nums[j] > pivot) {	// 此 while 结束时恰好 nums[j] <= pivot
                j--;
            }	
            if (i >= j)    break;
            // 如果走到这里，一定有：nums[i] > pivot && nums[j] < pivot
            // 所以需要交换 nums[i] 和 nums[j]，保证 nums[low..i] < pivot < nums[j..high]
            swap(nums[i], nums[j]);
        }
        swap(nums[low], nums[j]);	 // 将 pivot（即：nums[low]） 放到合适的位置，即 pivot 左边元素较小，右边元素较大
        return j;
    }
    void shuffle(vector<int>& nums) {	// 洗牌算法实现
        int n = nums.size();
        for (int i = 0; i < n; i++) {
            int randIndex = rand() % (n - i) + i;   // 生成 [i, n - 1] 的随机数
            swap(nums[i], nums[randIndex]);
        }
    }
};
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

归并排序

class Merge {
public:
	// 留出调用接口
	void sort(vector<int>& nums) {
		temp.resize(nums.size());	// 先给辅助数组开辟内存空间
		sort(nums, 0, nums.size() - 1);	// 排序整个数组（原地修改）
	}
private:
	vector<int> temp;	// 用于辅助合并有序数组
	// 定义：将子数组 nums[lo..hi] 进行排序
	void sort(vector<int>& nums, int low, int high) {
		if (low == high)   return;		// 单个元素不用排序
		int mid = low + (high - low) / 2;	// 这样写是为了防止溢出，效果等同于 (hi + lo) / 2
		sort(nums, low, mid);			// 先对【左半部分】数组 nums[lo..mid] 排序
		sort(nums, mid + 1, high);	 	// 再对【右半部分】数组 nums[mid+1..hi] 排序
		merge(nums, low, mid, high);	// 将两部分有序数组【合并】成一个【有序】数组
	}
	// 将 nums[lo..mid] 和 nums[mid+1..hi] 这两个有序数组【合并】成一个【有序】数组（关键函数！！！必背！）
	void merge(vector<int>& nums, int low, int mid, int high) {
		for (int i = low; i <= high; i++) {
			temp[i] = nums[i];	// 先把 nums[lo..hi] 复制到辅助数组中，以便合并后结果能直接存入 nums
		}
		// 数组双指针技巧，合并两个有序数组
		int i = low, j = mid + 1;
		for (int p = low; p <= high; p++) {
			// 注意：次序不能搞错！先判断左or右半边数组是否已经被合并，然后再判断元素大小
			if (i == mid + 1) {
				nums[p] = temp[j++];	// 左半边数组已全部被合并
			}
			else if (j == high + 1) {
				nums[p] = temp[i++];	// 右半边数组已全部被合并
			}
			else if (temp[i] > temp[j]) {
				nums[p] = temp[j++];
			}
			else {	// temp[i] <= temp[j]
				nums[p] = temp[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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

冒泡排序

// 原始版本（如果 n == a.size()，则是对整个数组a排序）
void bubbleSort(vector<int>& a, int n) {
	for (int i = 0; i < n - 1 ; ++i) {	// 对于数组a的前n个元素，排序n - 1轮
		for (int j = 0; j < n - 1 - i; ++j) {	// 每一轮分别进行n - 1、n - 2...1（= n - 1 - i）次循环
			if (a[j] < a[j + 1])	// 降序！若改为升序，则：a[j] > a[j + 1]
				swap(a[j], a[j + 1]);
		}
	}
}
// 优化版本
void bubbleSort(vector<int>& a) {
	int n = a.size();
	bool flag = false;
	for (int i = 0; i < n - 1; ++i) {	// 对于数组a的共n个元素，排序n - 1轮
		flag = false;
		for (int j = 0; j < n - 1 - i; ++j) {
			if (a[j] < a[j + 1]) {	// 降序！若改为升序，则：a[j] > a[j + 1]
				// 某一趟排序中，只要发生一次元素交换，flag就从false变为了true
				// 也即表示这一趟排序还不能确定所剩待排序列是否已经有序，应继续下一趟循环
				flag = true;
				swap(a[j], a[j + 1]);
			}
		}
		// 但若某一趟中一次元素交换都没有，即依然为flag = false，那么表明所剩待排序列已经有序
		// 之后就不必再进行趟数比较，外层循环应该结束，即此时if (!flag) break; 跳出循环
		if (!flag) { break; }
	}
}
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

计数排序 *

vector<int> vecRaw = { 0,5,7,9,6,3,4,5,2, };
vector<int> vecObj(vecRaw.size(), 0);
void CountSort(vector<int>& vecRaw, vector<int>& vecObj) {
	if (vecRaw.size() == 0)	// 确保待排序容器非空
		return;
	int vecCountLength = (*max_element(begin(vecRaw), end(vecRaw))) + 1;	// 使用 vecRaw 的最大值 + 1 作为计数容器 countVec 的大小
	vector<int> vecCount(vecCountLength, 0);
	
	for (int i = 0; i < vecRaw.size(); i++)	// 统计每个键值出现的次数
		vecCount[vecRaw[i]]++;
	
	for (int i = 1; i < vecCountLength; i++)	// 后面的键值出现的位置为前面所有键值出现的次数之和
		vecCount[i] += vecCount[i - 1];

	for (int i = vecRaw.size(); i > 0; i--)	// 将键值放到目标位置，此处逆序是为了保持相同键值的稳定性
		vecObj[--vecCount[vecRaw[i - 1]]] = vecRaw[i - 1];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

大顶堆

class MaxHeap {
public:
	MaxHeap() {
		max_heap.resize(1);	// 新建一个初始空位，使得：父节点索引i对应子节点索引为2*i、2*i+1
	}
	// 构建最大堆则从 size/2 开始进行下沉
    void Sink(int sink_node, int size) {  // 下沉操作
        int parent = sink_node;
        while (parent * 2 <= size) {  // 二叉树性质：左孩子为 son=2*parent
            int son = 2 * parent;
            if (son + 1 <= size && max_heap[son] < max_heap[son + 1]) {  // son+1<=size 表：有右孩子 且 右孩子更大，索引=son+1=2*parent+1
                son++;   // 指向最大孩子
            }
            if (max_heap[parent] >= max_heap[son]) {	 // 下沉结点比左右孩子节点最大值还大，表：下沉结束，直接退出
                return;
            }
            else {  // 下沉结点不是最大，交换
                swap(max_heap[parent], max_heap[son]);
            }
            parent = son;   // 继续下沉
        }
    }
	void Rise(int size) {  // 一直上浮直到满足最大堆或者到达根
		while (size > 1 && max_heap[size] > max_heap[size / 2]) {
			swap(max_heap[size], max_heap[size / 2]);
			size /= 2;
		}
	}
	void Pop() {   // 首尾交换 -> 弹出尾元素 -> 调整最大堆（下沉）
		max_heap[1] = max_heap[max_heap.size() - 1];
		max_heap.pop_back();
		Sink(1, max_heap.size() - 1);  // 转发，下沉结点， 大小
	}
	void Push(int val) {
		max_heap.push_back(val);
		Rise(max_heap.size() - 1);  // 最后一个结点进行上浮
	}
	bool Empty() {
		return max_heap.size() == 1;
	}
	int Top() {
		return max_heap[1];
	}

private:
	vector<int> max_heap;
};
// 测试代码如下：
int main() {
	// 操作次数和存放指令
	int count;
	string op;
	cin >> count;
	cin.get();    // 读取缓冲的换行符
	MaxHeap maxheap;	// 大根堆的数据结构
	while (--count >= 0) {
		getline(cin, op);   // 读取空格！
		if (op.substr(0, 4) == "push") {
			int val = stoi(op.substr(5));
			maxheap.Push(val);
		}
		if (maxheap.Empty()) {  // 空直接跳过本次循环（一位多余）
			cout << "empty" << endl;
			continue;
		}
		if (op.substr(0, 3) == "top") {
			cout << maxheap.Top() << endl;
		}
		if (op.substr(0, 3) == "pop") {
			maxheap.Pop();
		}
	}
	return 0;
}
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
74

堆排序

void HeapSortSolution() {
	// 1: 先将待排序的数视作完全二叉树(按层次遍历顺序进行编号, 从0开始)
    vector<int> arr = { 3,4,2,1,5,8,7,6 };  
    HeapSort(arr, arr.size());
}
void HeapSort(vector<int>& arr, int len) {
    // 将得到的无序序列转化为一个【无序大顶堆】，i从最后一个父节点开始调整。无序大顶堆：满足大顶堆性质，但堆数组不是有序的！
    for (int i = len / 2 - 1; i >= 0; i--) {	
        Adjust(arr, i, len - 1);	
    }
    // 在输出堆顶元素之后（完全二叉树的树根结点），如何调整剩余元素构建一个新的堆？结论：构建大顶堆--排序结果升序，构建小顶堆--排序结果降序
    for (int i = len - 1; i > 0; i--) {	
        swap(arr[0], arr[i]);   // 新无序区arr[0...i-1]和新有序区arr[i...len-1] ——> 该有序区【升序】！因为每次取一个【无序大顶堆】的堆顶元素！
        Adjust(arr, 0, i - 1);  // 将无序区arr[0...i-1]构建成一个新的【无序大顶堆】
    }
}
void Adjust(vector<int>& arr, int start, int end) {	// 依据之前构建【大顶堆】的方法，进行相应的下沉操作 --- 修改为：(1)、(2)就是【小顶堆】
	int parent = start;
	while (parent * 2 + 1 <= end) {
		int son = parent * 2 + 1;
		if (son + 1 <= end && arr[son] < arr[son + 1]) {	// 改为：arr[son] > arr[son + 1] --- (1)
			son++;
		}
		if (arr[parent] >= arr[son]) {	// 改为：arr[parent] < arr[son] --- (2)
			return;
		}
		else {
			swap(arr[parent], arr[son]);
		}
		parent = son;
	}
}
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

前缀树（字典树）

class Trie {
private:
    vector<Trie*> children;
    bool isEnd;
public:
    Trie() : children(26), isEnd(false) {}
    
    void insert(string word) {	// 插入：向 Trie 中插入一个单词 word
        Trie* node = this;
        for (char ch : word) {
            if (node->children[ch - 'a'] == nullptr) {
                node->children[ch - 'a'] = new Trie(); // 一直匹配到前缀链上没有对应的字符，这时开始不断开辟新的结点
            }
            node = node->children[ch - 'a'];
        }
        node->isEnd = true;	// 直到插入完 word 的最后一个字符，并将最后一个结点isEnd = true;
    }
    
    Trie* searchPrefix(string prefix) {	// 查找前缀的方法
        Trie* node = this;
        for (char ch : prefix) {
            if (node->children[ch - 'a'] == nullptr) {
                return nullptr;
            }
            node = node->children[ch - 'a'];
        }
        return node;	// 若是前缀就返回最后一个字母所在的node，否则返回nullptr
    }
    
    bool search(string word) {	// 查找 Trie 中是否存在单词 word
        Trie* node = this->searchPrefix(word);
        return node != nullptr && node->isEnd;	// 如果匹配到了最后一个字符，只需判断 node->isEnd 即可。
    }
    
    bool startsWith(string prefix) {	// 判断 Trie 中是或有以 prefix 为前缀的单词
        Trie* node = this->searchPrefix(word);
        return node != nullptr;	// 不需要判断最后一个字符结点的isEnd
    }
};
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

------------------------

图：DFS

// 以 T-130. 被围绕的区域 为例：
vector<vector<int>> dirs = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
vector<vector<int>> visited;
void DFS(vector<vector<char>>& board, int i, int j) {
	int m = board.size(), n = board[0].size();
	if (i < 0 || j < 0 || i >= m || j >= n || visited[i][j]) {
		return;
	}
	visited[i][j] = true;	// ！！！   
	for (vector<int> d : dirs) {
		int next_i = i + d[0];
		int next_j = j + d[1];
		dfs(board, next_i, next_j);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

图：BFS

// 以 T-130. 被围绕的区域 为例：
vector<vector<int>> dirs = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
vector<vector<int>> visited;
void BFS(vector<vector<char>>& board, int i, int j) {
    int m = board.size(), n = board[0].size();
    queue<pair<int, int>> que;
    que.push(make_pair(i, j)); // 加入起点！
    visited[i][j] = true; 	// 注意！不要遗漏！
    while (!que.empty()) {
        int size = que.size();
        for (int j = 0; j < size; ++j) {
            pair<int, int> cur = que.front();
            que.pop();
            for (vector<int> d : dirs) { 
                int x = i + d[0];
                int y = j + d[1];
                if (x < 0 || x >= m || y < 0 || y >= n || visited[x][y]) {
                    continue;
                }
                visited[x][y] = true;	// ！！！
                que.push(make_pair(x, y));
            }
        }
    }
    // 对于步数的题目，这里可以更新！
}
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

建图函数

vector<vector<int>> graph;	// graph[s] 是一个列表，存储着节点 s 所指向的节点。
vector<vector<int>> buildGraph(int numCourses, vector<vector<int>>& prerequisites){		//【有向图】建图函数
    vector<vector<int>> graph(numCourses, vector<int>(0,0));	// 图中共有 numCourses 个节点
    for(vector<int> edge : prerequisites){
        // 添加一条从 from 指向 to 的有向边，边的方向是「被依赖」关系，即：先完成from才能完成to
        int from = edge[1];
        int to = edge[0];
        graph[from].push_back(to);	// 对于【无向图】！需要后面再添加一句：graph[to].push_back(from); 即可！
    }
    return graph;
}
1
2
3
4
5
6
7
8
9
10
11

拓扑排序

/* ------- DFS ------- */
vector<int> postorder;
vector<int> path;
vector<int> visited;
bool hasCycle = false;
vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
    vector<vector<int>> graph = buildGraph(numCourses, prerequisites);	// 建图函数
    path.resize(numCourses, 0);
    visited.resize(numCourses, 0);
    for (int i = 0; i < numCourses; ++i) {
        dfs(graph, i);
    }
    if (hasCycle) {	// 存在环则无法进行拓扑排序！
        return vector<int>{};
    }
    reverse(postorder.begin(), postorder.end());	// 将后序位置结果进行反转！！！就是拓扑排序的结果。
    return vector<int>(postorder.begin(), postorder.end());
}
void dfs(vector<vector<int>>& graph, int from) {
    if (path[from]) {
        hasCycle = true;
    }
    if (visited[from] || hasCycle) {
        return;
    }
    visited[from] = true;
    path[from] = true;
    for (auto& to : graph[from]) {
        dfs(graph, to);
    }
    path[from] = false;
    postorder.emplace_back(from);	// 后序位置处理！！！
}

/* ------- BFS ------- */
vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
    vector<vector<int>> graph = buildGraph(numCourses, prerequisites);	// 建图函数
    vector<int> indegree(numCourses, 0);	// 入度数组
    for (auto& edge : prerequisites) {
        int to = edge[0];
        indegree[to]++;	// 节点to的入度+1
    }
    queue<int> q;
    for (int i = 0; i < numCourses; i++) {
        if (indegree[i] == 0) {
            q.push(i);
        }
    }
    vector<int> ans;
    int count = 0;
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        count++;
        ans.emplace_back(cur);
        for (auto& adj : graph[cur]) {
            indegree[adj]--;
            if (indegree[adj] == 0) {
                q.push(adj);
            }
        }
    }
    return count == numCourses ? ans : vector<int>{};	// 存在环则无法进行拓扑排序！
}
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

二分图判定

/* ------- DFS ------- */
bool isOk = true;
vector<int> color, visited;
bool isBipartite(vector<vector<int>>& graph) {
	int size = graph.size();
	color.resize(size);
	visited.resize(size);
	for (int i = 0; i < size; ++i) {
		if (!isOk) {
			return false;
		}
		if (!visited[i]) {
			dfs(graph, i);
		}
	}
	return true;
}
void dfs(vector<vector<int>>& graph, int i) {
	visited[i] = true;	 // !!!
	for (int j : graph[i]) {
		if (!visited[j]) {
			color[j] = !color[i];	// 进行染色（只有两种颜色，所以直接取非）
			dfs(graph, j);
		}
		else {
			if (color[j] == color[i]) {	
				isOk = false;
				return;
			}
		}
	}
}

/* ------- BFS ------- */
bool isOk = true;
vector<int> visited, color;
bool isBipartite(vector<vector<int>>& graph) {
	int size = graph.size();
	visited.resize(size);
	color.resize(size);
	for (int i = 0; i < size; i++) {
		if (!isOk) {
			return false;
		}
		if (!visited[i]) {
			bfs(graph, i); 
		}
	}
	return true;
}
void bfs(vector<vector<int>>& graph, int start) {
	queue<int> q;
	visited[start] = true;    // !!!
	q.push(start);
	while (!q.empty()) {
		int cur = q.front();
		q.pop();
		for (int j : graph[cur]) {
			if (!visited[j]) {
				visited[j] = true;    // !!!
				color[j] = !color[cur];	// 进行染色（只有两种颜色，所以直接取非）
				q.push(j);
			}
			else {
				if (color[j] == color[cur]) {
					isOk = false;
					return;
				}
			}
		}
	}
}
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

并查集（Union-Find）

class UF {
private:
	int m_count;	// 连通分量个数
	vector<int> parent;	// 存储一棵树（以一维数组形式！）
public:
	UF(int n) {
		m_count = n;	// n 为图中节点的个数
		parent.resize(n, 0);
		for (int i = 0; i < n; i++) {
			parent[i] = i;
		}
	}
	void Union(int p, int q) {	// 将节点 p 和节点 q 连通
		int rootp = Find(p);	// ！
		int rootq = Find(q);	// ！
		if (rootp == rootq) {
			return;
		}
		parent[rootq] = rootp;	// parent[rootp] = rootq; 也可以！
		m_count--;	// 两个连通分量合并成一个连通分量，连通分量个数-1
	}
	bool Connected(int p, int q) {	// 判断节点 p 和节点 q 是否连通
		int rootp = Find(p);	// ！
		int rootq = Find(q);	// ！
		return rootp == rootq;
	}
	int Find(int x) {	// 返回节点 x 的连通分量根节点
		if (parent[x] != x) {
			parent[x] = Find(parent[x]);
		}
		return parent[x];
	}
	int Count() {	// 返回图中的连通分量个数
		return m_count;
	}
};
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

KRUSKAL最小生成树

int miniTree(int n, vector<vector<int>>& connections) {
	UF uf(n + 1);   // 注意：初始化了n + 1个节点（不是n个），而节点编号为1 ~ n，不包括 0！故之后0这个节点是没有进行连通操作（仅仅进行了初始化），故答案需独立算上验证：uf.Count() 是否 = 2
	sort(connections.begin(), connections.end(), [](vector<int>& a, vector<int>& b) {
		return a[2] < b[2];
		});	// 贪心思想
	int mst = 0;
	for (vector<int> edge : connections) {
		int u = edge[0], v = edge[1], weight = edge[2];
		if (uf.Connected(u, v)) {
			continue;
		}
		mst += weight;
		uf.Union(u, v);
	}
	return uf.Count() == 2 ? mst : -1;
}
class UF {
	// ...
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

DIJKSTRA最短路径

// 创建辅助状态类
struct State {
    State(int id, int distFromStart) :m_id(id), m_distFromStart(distFromStart) {}
    int m_id;	// 图节点的 id
    int m_distFromStart;	// 从 start 节点到当前节点的距离
};
// 输入一幅图和一个起点 start，计算 start 到其他节点的最短距离
vector<int> dijkstra(int start, vector<vector<pair<int, int>>>& graph) {
    int V = graph.length;	// 图中节点的个数  
    vector<int> distTo(V, INT_MAX);	// distTo[i]的定义(牢记！)：节点start到达节点i的【最短】路径权重。因为求最小值，所以 dp table 初始化为正无穷！
    distTo[start] = 0;	// base case，start到start的最短距离就是：0

    auto cmp = [](const State& a, const State& b) {	
        return a.m_distFromStart > b.m_distFromStart;	
    };
    priority_queue<State, vector<State>, decltype(cmp)> pq(cmp);	// 优先级队列，distFromStart 较小的排在前面
    pq.push(State(start, 0));	// 将起点start装入，从起点start开始进行BFS

    while (!pq.empty()) {
        State curState = pq.top();
        pq.pop();
        int curNodeId = curState.m_id;
        int curDistFromStart = curState.m_distFromStart;
        // 若只想计算到 end 的最短路径，在这里加一个判断就行了，其他代码不用改
        if (curNodeID == end) {
            return curDistFromStart;
        }
        
        if (curDistFromStart > distTo[curNodeID]) {	// 已经有一条更短的路径到达 curNode 节点了
            continue;
        }
        for (auto& neighbor : graph[curNodeId]) {	// 将 curNode 的相邻节点装入队列
            int nextNodeId = neighbor.first;
            int distToNextNode = distTo[curNodeId] + neighbor.second;	// 关键！邻节点的指标计算（根据具体题意！这里是权重和！）
            if (distTo[nextNodeId] > distToNextNode) {	// 看看从 curNode 达到 nextNode 的距离是否会【更】短
                distTo[nextNodeId] = distToNextNode;	// 更短则更新 dp table
                pq.push(State(nextNodeId, distToNextNode));	// 将这个节点以及距离放入队列继续之后的迭代遍历
            }
        }
    }
    return distTo;
}
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

------------------------

单调栈

vector<int> nextGreaterElement(vector<int>& nums) {
    vector<int> res(nums.size()); 	// 存放【单调递增】答案的数组
    stack<int> s;
    // 【倒着】往栈里放
    for (int i = nums.size() - 1; i >= 0; i--) {
        while (!s.empty() && s.top() <= nums[i]) { 	// 判定个子高矮：若求【单调递减】, 这里改为: s.top() >= nums[i]
            s.pop();	// 矮个起开，反正也被挡着了。。。
        }
        res[i] = s.empty() ? -1 : s.top();	// nums[i] 身后的 next great number
        s.push(nums[i]);	//将相对高个子入栈
    }
    return res;
}
// 「循环数组」处理策略
for (int i = 2 * n - 1; i >= 0; --i) {	// 将数组长度翻倍，通过 % 运算符求模（余数），来获得环形特效！
    while (!stk.empty() && nums[stk.top()] <= nums[i % n]) {
        stk.pop();
    }
    ans[i % n] = (stk.empty() ? -1 : nums[stk.top()]);
    stk.push(i % n);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

单调队列

vector<int> maxSlidingWindow(vector<int>& nums, int k) {	// T-239. 滑动窗口最大值，k表：窗口大小
    int n = nums.size();
    deque<int> q;	// 双端队列
    for (int i = 0; i < k; ++i) {
        while (!q.empty() && nums[i] >= nums[q.back()]) {	// 保证单调递减
            q.pop_back();
        }
        q.push_back(i);
    }
    vector<int> ans = {nums[q.front()]};
    for (int i = k; i < n; ++i) {
        while (!q.empty() && nums[i] >= nums[q.back()]) {	// 保证单调递减
            q.pop_back();
        }
        q.push_back(i);
        if (q.front() <= i - k) {	// 达到队容量时，需要弹出队首元素（重要结论：该队列中的数组下标一定是递增的！）
            q.pop_front();
        }
        ans.push_back(nums[q.front()]);	// 记录每个滑动窗口中的最大值
    }
    return ans;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

循环队列

class MyCycQueue {
private:
    int front;		// 队尾指针
    int rear;		// 队头指针
    int capacity;	// 循环队列可使用的总大小
    vector<int> elements;

public:
    MyCycQueue(int k) {
        this->capacity = k + 1;
        this->elements = vector<int>(capacity);
        rear = front = 0;
    }

    bool Push(int value) {	 // 模拟入队的函数
        if (isFull()) {
            return false;
        }
        elements[rear] = value;
        rear = (rear + 1) % capacity;	// 更新！！！
        return true;
    }

    bool Pop() {	// 模拟出队的函数
        if (isEmpty()) {
            return false;
        }
        front = (front + 1) % capacity;	// 更新！！！
        return true;
    }

    int Front() {
        if (isEmpty()) {
            return -1;
        }
        return elements[front];
    }

    int Rear() {
        if (isEmpty()) {
            return -1;
        }
        return elements[(rear - 1 + capacity) % capacity];
    }

    bool isEmpty() {
        return rear == front;
    }

    bool isFull() {
        return ((rear + 1) % capacity) == front;	
    }
};
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

栈 —> 队列

class MyQueue {
public:
	stack<int> s1;
	stack<int> s2;

	MyQueue() {
	}

	void Push(int x) {
		s1.push(x);
	}

	int Pop() {
		int delNum = Peek();
		s2.pop();
		return delNum;
	}

	int Peek() {
		if (s2.empty()) {
			while (!s1.empty()) {
				s2.push(s1.top());
				s1.pop();
			}
		}
		return s2.top();
	}

	bool Empty() {
		return s1.empty() && s2.empty();
	}
};
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

队列 —> 栈

class MyStack {
public:
	queue<int> q;
	int topVal;
	MyStack() {
		topVal = 0;
	}

	void Push(int x) {
		q.push(x);
	}

	int Pop() {
		int topSt = Top();
		while (q.front() != topSt) {	// 将队尾前的所有元素依次弹出并插入到队尾
			q.push(q.front());
			q.pop();
		}
		q.pop();	// 将原队尾元素弹出
		return topSt;	// 返回原队尾元素
	}

	int Top() {
		topVal = q.back();
		return topVal;
	}

	bool Empty() {
		return q.empty();
	}
};
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

------------------------

二分搜索

/*----------------------统一写为：左闭右闭型----------------------*/
int binary_search(int[] nums, int target) {		// 普通二分
    int left = 0, right = nums.length - 1; 
    while(left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1; 
        } else if(nums[mid] == target) {
            return mid;	// 直接返回！！！
        }	
    }
    return -1;	// 直接返回！！！
}

int left_bound(int[] nums, int target) {	// 左边界二分
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] == target) {
            right = mid - 1;
        }
    }
    if (left > nums.length - 1 || nums[left] != target)	// 最后要检查 left 越界的情况！！！
        return -1;
    return left;
}

int right_bound(int[] nums, int target) {	// 右边界二分
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] == target) {
            left = mid + 1;
        }
    }
    if (right < 0 || nums[right] != target)	// 最后要检查 right 越界的情况！！！
        return -1;
    return right;
}
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

滑动窗口

void slidingWindow(string s, string t) {
    unordered_map<char, int> window;
    int left = 0, right = 0, valid = 0;
    while (right < s.size()) {
        char c = s[right];	// c 是将移入窗口的字符
        right++;	// 右移窗口
        // ......	// 进行窗口内数据的一系列更新！！！——> (1)

        while (window needs shrink) {	// 判断左侧窗口是否要收缩 ——> (2)
            char d = s[left];	// d 是将移出窗口的字符
            left++;		// 左移窗口
            // ......	// 进行窗口内数据的一系列更新！！！——> (3)
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

KMP算法

class KMP {
private:
    vector<vector<int>> dp;
    string m_pat;
public:
    KMP(string pat) {
        m_pat = pat;
        int M = m_pat.size();
        int X = 0;	// 影子状态 X 初始为 0
        dp.resize(M, vector<int>(256));	 // dp[当前状态][字符] = 下个状态
        // base case
        dp[0][m_pat[0]] = 1;
        // 开始状态转移
        for (int j = 1; j < M; j++) {   // 注意：当前状态 j 从 1 开始
            for (int c = 0; c < 256; c++) {	// 当前是状态 j，遇到字符 c，pat 应该转移到哪个状态？
                if (c == m_pat[j]) {
                    dp[j][c] = j + 1;	// 更新目标状态dp[j][c](= dp[j][pat[j]])（对目标状态进行状态推进）
                }
                else {
                    dp[j][c] = dp[X][c];	// 其余状态dp[j][...]全用退回影子状态（状态重启）
                }
            }
            X = dp[X][m_pat[j]];  // 更新影子状态：当前是状态 X，遇到字符 pat[j]，pat 应该转移到哪个状态？
        }
    }
    int search(string txt) {
        int M = m_pat.size();
        int N = txt.size();
        int j = 0;  // 模式串 pat 的初始态为 0
        for (int i = 0; i < N; i++) {
            j = dp[j][txt[i]];  // 计算 pat 的下一个状态
            if (j == M) {
                return i + 1 - M;   // 到达终止态，返回结果
            }
        }
        return -1;  // 没到达终止态，匹配失败
    }
};
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

快速乘

int quickMulti(int A, int B) {
    int ans = 0;
    while (B > 0) {
        if ((B & 1) == 1) {
            ans += A;	// ！
        }
        A <<= 1;	// ！
        B >>= 1;
    }
    return ans;
}
1
2
3
4
5
6
7
8
9
10
11

快速幂

// 快速幂 的递归形式
double myPow(double x, int n) {
	long long N = n;
	return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);
}
double quickMul(double x, long long N) {
	if (N == 0) {
		return 1.0;
	}
	double y = quickMul(x, N / 2);
	return N % 2 == 0 ? y * y : y * y * x;
}

// 快速幂 的迭代形式
double myPow(double x, int n) {
	long long N = n;
	double ans = 1.0;
	double x_contribute = x;	// 贡献的初始值为 x
	if (N < 0) {
		x_contribute = 1 / x_contribute;
		N = -N;
	}
	while (N > 0) {
		if ((N & 1) == 1) {
			ans *= x_contribute;	// ！
		}
		x_contribute *= x_contribute;	// ！
		N >>= 1;
	}
	return ans;
}
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

------------------------

C++常见输入输出

https://blog.csdn.net/qq_42147969/article/details/117265956?spm=1001.2014.3001.5502 ——> C++笔试常见输入输出练习 ——> 重要！！！
https://blog.csdn.net/qq_33287871/article/details/107718789?spm=1001.2014.3001.5502 ——> 牛客网刷算法题的输入输出（C++）
https://blog.csdn.net/Daisy_Qw/article/details/124836921 ——> 牛客网C++输入输出汇总

// 输入任意组字符串，每组字符串包含一个匹配串s，一个文本串t
// 输入： xuda hjj
//		 xxuuda hujj
//		 xdaasdf jjxus
//		 ..... ——> 需要自定义设置退出输入的标志位
// 输出： x1
//		 x2
//		 x3
//		 .....
string input;
vector<vector<string>> store;
while (getline(cin, input)) {	// 注意：getline遇到回车结束一行输入，但不会保留回车符（'\n'）在流中。故：只输入一个回车符时，input为空。
    if (input.size() == 0) break;	// 设置两次回车后退出
    string str1, str2;
    istringstream iss(input);
    while (iss >> str1 >> str2) {
        store.push_back({ str1,str2 });
    }
}
for (int i = 0; i < store.size(); ++i) {
    string str1 = store[i][0], str2 = store[i][1];
    cout << fx(str1, str2) << endl;	// 处理函数
}
// 注意与如下形式的区别：
string in_1, in_2;
while (cin >> in_1 >> in_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

getline函数

注意：除了 getline() 全局函数外，C++ 还提供了一个同名的 getline() 成员函数，定义在 istream 类中，它也可以读取一行数据。这两个名称、功能都相同的函数。这里讲的 getline() 指的是全局函数！

此函数可读取整行，包括前导和嵌入的空格，并将其存储在字符串对象中。

getline(cin, inputLine);	// 其中 cin 是正在读取的输入流，而 inputLine 是接收输入字符串的 string 变量的名称。

int main() {
    string name;
    string city;
    cout << "Please enter your name: ";
    getline(cin, name);
    cout << "Enter the city you live in: ";
    getline(cin, city);
    cout << "Hello, " << name << endl;
    cout << "You live in " << city << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

详见：https://blog.csdn.net/qwq1503/article/details/125196085

------------------------

前缀和数组

class NumArray {
private:
	vector<int> preSum;
public:
	NumArray(vector<int>& nums) {
		preSum.resize(nums.size() + 1);
		for (int i = 1; i < preSum.size(); ++i) {
			preSum[i] = preSum[i - 1] + nums[i - 1];
		}
	}
    
	int SumRange(int left, int right) {
		return preSum[right + 1] - preSum[left];
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

差分数组

class Difference {
private:
	vector<int> diff;
public:
	Difference(vector<int>& nums) {
		diff.resize(nums.size());
		diff[0] = nums[0];
		for (int i = 1; i < nums.size(); ++i) {
			diff[i] = nums[i] - nums[i - 1];
		}
	}
	void Increment(int i, int j, int val) {
		diff[i] += val;
		if (j + 1 < diff.size()) {
			diff[j + 1] -= val;
		}
	}
	vector<int> Result() {
		vector<int> res(diff.size());
		res[0] = diff[0];
		for (int i = 1; i < diff.size(); ++i) {
			res[i] = res[i - 1] + diff[i];
		}
		return res;
	}
};
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

nSum问题

sort(nums.begin(), nums.end());	// 一定要先排序！！！
vector<vector<int>> nSumTarget(vector<int>& nums, int n, int start, int target) { // 求：目标和为target的n个数之和
    int sz = nums.size();
    vector<vector<int>> res;
    if (n < 2 || sz < n) 	// 至少是 2Sum，且数组大小不应该小于 n
        return res;
    if (n == 2) {	// 2Sum 是 base case
        int lo = start, hi = sz - 1;
        while (lo < hi) {	// 双指针操作
            int sum = nums[lo] + nums[hi];
            int left = nums[lo], right = nums[hi];
            if (sum < target) {
                while (lo < hi && nums[lo] == left) lo++;	// ！！！
            }
            else if (sum > target) {
                while (lo < hi && nums[hi] == right) hi--;	// ！！！
            }
            else {
                res.push_back({ left, right });
                while (lo < hi && nums[lo] == left) lo++;	// ！！！
                while (lo < hi && nums[hi] == right) hi--;	// ！！！
            }
        }
    }
    else {
        for (int i = start; i < sz; i++) {	// n > 2 时，递归计算 (n-1)Sum 的结果
            vector<vector<int>> sub = nSumTarget(nums, n - 1, i + 1, target - nums[i]);
            for (vector<int>& arr : sub) {
                arr.push_back(nums[i]);	// (n-1)Sum 加上 nums[i] 就是 nSum
                res.push_back(arr);
            }
            while (i < sz - 1 && nums[i] == nums[i + 1]) i++;	// ！注：i < sz - 1 类似 left < right 一样
        }
    }
    return res;
}
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

数组输入

未知多组 + 结束条件 + 0结束
- 输入描述:
  - 输入包括两个正整数a,b(1 <= a, b <= 10^9)
  - 输入数据有多组
  - 如果输入为0，则结束输入
- 输出描述:
  - 输出a+b的结果
- 思考：
  - 未知多组 + 两个输入均为 + 0结束的条件：while (cin >> a >> b && (a || b))
```
int main() {
	int a, b;
	while (cin >> a >> b && (a || b)) {
		cout << a + b << endl;
	}
	return 0;
}
1
2
3
4
5
6
7
```

其余详见：https://blog.csdn.net/weixin_44671418/article/details/125352042?spm=1001.2014.3001.5502

------------------------

智能指针 shared_ptr

template<typename T>
class SharedPtr {
public:
	SharedPtr(T* ptr = NULL) :_ptr(ptr), _pcount(new int(1)) {}	// 注：初始化将引用计数计为：1

	SharedPtr(const SharedPtr& s) :_ptr(s._ptr), _pcount(s._pcount) {	// 拷贝构造
		(*_pcount)++;
	}

	SharedPtr<T>& operator=(const SharedPtr& s) {	// 赋值运算符
		if (this != &s) {
			_ptr = s._ptr;
			_pcount = s._pcount;
			*(_pcount)++;
		}
		return *this;
	}

	T& operator*() {	// 解引用
		return *(this->_ptr);
	}

	T* operator->() {	// 指向符
		return this->_ptr;
	}

	~SharedPtr() {	// 析构函数
		--(*(this->_pcount));
		if (*(this->_pcount) == 0) {	// 模拟自动垃圾回收机制。一旦T类型对象的引用计数为0，就释放该对象。
			delete _ptr;
			_ptr = NULL;
			delete _pcount;
			_pcount = NULL;
		}
	}
    
private:
	T* _ptr;		// 裸指针
	int* _pcount;	// 指向引用计数的指针，多个SharedPtr之间可以同步修改
};
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

shared_ptr 循环引用

class A {
public:
	shared_ptr<B> bptr;
	A() {
		cout << "A constructed!" << endl;
	}
	~A() {
		cout << "A destructed!" << endl;
	}
};
class B {
public:
	shared_ptr<A> aptr;	// 改为：weak_ptr<A> aptr; 即可解决循环引用问题
	B() {
		cout << "B constructed!" << endl;
	}
	~B() {
		cout << "B destructed!" << endl;
	}
};
auto ap = make_shared<A>();
auto bp = make_shared<B>();
ap->bptr = bp;
bp->aptr = ap;
cout << "A: " << ap.use_count() << endl;
cout << "B: " << bp.use_count() << endl;
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

------------------------

死锁

pthread_mutex_t mutex_A = PTHREAD_MUTEX_INITIALIZER;	
pthread_mutex_t mutex_B = PTHREAD_MUTEX_INITIALIZER;

//线程函数 A
void* threadA_proc(void* data) {	// 锁序：A B B A
	cout << "thread A waiting get ResourceA " << endl;
	pthread_mutex_lock(&mutex_A);
	cout << "thread A got ResourceA " << endl;

	sleep(1);

	cout << "thread A waiting get ResourceB " << endl;
	pthread_mutex_lock(&mutex_B);
	cout << "thread A got ResourceB " << endl;

	pthread_mutex_unlock(&mutex_B);
	pthread_mutex_unlock(&mutex_A);
	return (void*)0;
}

//线程函数 B
void* threadB_proc(void* data) {	// 锁序：B A A B ——> 改为：A B B A 即可解决死锁！
	cout << "thread B waiting get ResourceB " << endl;
	pthread_mutex_lock(&mutex_B);
	cout << "thread B got ResourceB " << endl;

	sleep(1);

	cout << "thread B waiting get ResourceA " << endl;
	pthread_mutex_lock(&mutex_A);
	cout << "thread B got ResourceA " << endl;

	pthread_mutex_unlock(&mutex_A);
	pthread_mutex_unlock(&mutex_B);
	return (void*)0;
}

int main() {
	pthread_t tidA, tidB;
	//创建两个线程
	pthread_create(&tidA, NULL, threadA_proc, NULL);
	pthread_create(&tidB, NULL, threadB_proc, NULL);

	pthread_join(tidA, NULL);	// 主线程阻塞，等待线程A结束
	pthread_join(tidB, NULL);	// 主线程阻塞，等待线程B结束

	cout << "exit" << endl;

	return 0;
}

// C++实现：
#include <thread>
#include <mutex>
#include <stdlib.h>
mutex A, B;
//线程函数 A
void threadA_proc() {
	cout << "thread A waiting get ResourceA " << endl;
	A.lock();
	cout << "thread A got ResourceA " << endl;
	Sleep(1);
	cout << "thread A waiting get ResourceB " << endl;
	B.lock();
	cout << "thread A got ResourceB " << endl;
	B.unlock();
	A.unlock();
}
//线程函数 B
void threadB_proc() {	
	cout << "thread B waiting get ResourceB " << endl;
	B.lock();
	cout << "thread B got ResourceB " << endl;
	Sleep(1);
	cout << "thread B waiting get ResourceA " << endl;
	A.lock();
	cout << "thread B got ResourceA " << endl;
	A.unlock();
	B.unlock();
}
int main() {
	thread A(threadA_proc);   
	thread B(threadB_proc);		
	A.join();					// 暂停，直到第一个函数执行完成
	B.join();					// 暂停，直到第二个函数执行完成
	cout << "exit" << endl;
	return 0;
}
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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88

读写锁

// 读写锁要求：
// 	  多个读者同时读
// 	  一个写者孤单（互斥其他写者、读者）
// 	  写者优先于读者（一旦写时阻塞读、优先唤醒写）
class RWLock {
public:
	RWLock() :rd_cnt(0), wr_cnt(0) {
		pthread_mutex_init(&mxt, NULL);
		pthread_cond_init(&cond, NULL);
	}
	void ReadLock() {	// 读加锁
		pthread_mutex_lock(&mxt);

		++rd_cnt;
		while (wr_cnt > 0)
			pthread_cond_wait(&cond, &mxt);

		pthread_mutex_unlock(&mxt);
	}
	void ReadUnlock() {	// 读解锁
		pthread_mutex_lock(&mxt);

		--rd_cnt;
		if (rd_cnt == 0)
			pthread_cond_signal(&cond);

		pthread_mutex_unlock(&mxt);
	}
	void WriteLock() {	// 写加锁
		pthread_mutex_lock(&mxt);

		++wr_cnt;
		while (wr_cnt + rd_cnt >= 2)
			pthread_cond_wait(&cond, &mxt);

		pthread_mutex_unlock(&mxt);
	}
	void WriterUnlock() {	// 写解锁
		pthread_mutex_lock(&mxt);

		--wr_cnt;
		if (wr_cnt == 0)
			pthread_cond_signal(&cond);

		pthread_mutex_unlock(&mxt);
	}
private:
	pthread_mutex_t mxt;	// 互斥锁
	pthread_cond_t cond;	// 条件变量
	int rd_cnt;	// 等待读的数量  
	int wr_cnt;	// 等待写的数量  
};
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

读者 - 写者问题

// 读者-写者的问题描述：
//	「读-读」允许：同一时刻，允许多个读者同时读
//	「读-写」互斥：没有写者时读者才能读，没有读者时写者才能写
//	「写-写」互斥：没有其他写者时，写者才能写

// 读者优先（若想实现：公平竞争，则添加注释代码即可！）
typedef int semaphore;
semaphore count_mutex = 1;	// 控制对读操作数量rCount的互斥修改，初始值为 1
semaphore data_mutex = 1;	// 控制对写操作数据的互斥修改，初始值为 1
// semaphore flag;	// 用于实现公平竞争，初始值为 0
int rCount = 0;	// 正在读操作的读者个数，初始值为 0

void Reader() {
    while (TRUE) {
        // P(&flag);
        P(&count_mutex);
        rCount++;
        if (rCount == 1) P(&data_mutex);	// 第一个读者需要对数据进行加锁，防止写进程访问
        V(&count_mutex);
        // V(&flag);
        read();		// 读数据！！！
        P(&count_mutex);
        rCount--;
        if (rCount == 0) V(&data_mutex);	// 最后一个读者要对数据进行解锁，防止写进程无法访问
        V(&count_mutex);
    }
}

void Writer() {
    while (TRUE) {
        // P(&flag);
        P(&data_mutex);
        write();	// 写数据！！！
        V(&data_mutex);
        // V(&flag);
    }
}
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

生产者 - 消费者问题

#define N 100
semaphore mutex = 1;            // 互斥信号量，用于临界区的互斥访问
semaphore emptyBuffers = N;     // 表示缓冲区「空槽」的个数
semaphore fullBuffers = 0;      // 表示缓冲区「满槽」的个数

// 生产者线程函数
void Producer() {
    while (TRUE) {
        P(emptyBuffers);    // 将空槽的个数 -1
        P(mutex);           // 进入临界区
        bufffer_add();      // 将生成的数据放到缓冲区中
        V(mutex);           // 离开临界区
        V(fullBuffers);     // 将满槽的个数 +1
    }
}

// 消费者线程函数
void Consumer() {
    while (TRUE) {
        P(fullBuffers);     //将满槽的个数 -1
        P(mutex);           //进入临界区
        buffer_remove();    // 从缓冲区里读取数据
        V(mutex);           //离开临界区
        V(emptyBuffers);    // 将空槽的个数 +1
    }
}
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

------------------------

stack 的实现

template <class T, class Sequence = deque<T>>	// class Sequence = list<T>
class myStack {
public:
	typedef typename Sequence::value_type value_type;	// typename用来声明Sequence::value_type是一个类型参数
	typedef typename Sequence::size_type size_type;
	typedef typename Sequence::reference reference;
	typedef typename Sequence::const_reference const_reference;
protected:
	Sequence c;
public:
	bool empty() { return c.empty(); }
	size_type size() const { return c.size(); }
	reference top() { return c.back(); }	// ！！！
	const_reference top() const { return c.back(); }	// ！！！
	void push(const value_type& x) { c.push_back(x); }
	void pop() { c.pop_back(); }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

queue 的实现

template <class T, class Sequence = deque<T>>	// class Sequence = list<T>
class myQueue {
public:
	typedef typename Sequence::value_type value_type;
	typedef typename Sequence::size_type size_type;
	typedef typename Sequence::reference reference;
	typedef typename Sequence::const_reference const_reference;
protected:
	Sequence c;
public:
	bool empty() { return c.empty(); }
	size_type size() const { return c.size(); }
	reference front() { return c.front(); }		// ！！！
	const_reference front() const { return c.front(); }		// ！！！
	void push(const value_type& x) { c.push_back(x); }
	void pop() { c.pop_front(); }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

------------------------

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Guff_9hys/article/detail/784396