Lizq的个人博客

发表于 更新于 本文字数： 403 阅读时长 ≈ 1 分钟

并查集

  • 一般用于快速判断两个元素是否同属于一个集合
  • 数组形式表示树结构
  • 插入元素会被映射到从0开始的顺序整数中

实现技巧

  • 路径压缩：在find时，通过递归并返回找到的祖宗节点并赋值，可以达成find后降低树高的功效
  • 按秩归并：在unite时，其中一方会挂在另一方的门下，所以希望“小的挂到大的上面”，以此来产生结果高度更小的树，有两种方式：
    • 高度：树高：S[Root]=-树高，代码多一步判断：即：两个树相同高度时，增加树高
    • 数目（推荐）：S[Root]=-元素个数。子孙节点数目，可以通过利用根节点来达成，根节点之前是-1，现在改为-n，其中n是包含根节点的整个树的节点数目

LC.990

阅读全文 »

发表于 更新于 本文字数： 1.4k 阅读时长 ≈ 5 分钟

1. 缓存雪崩：

布隆过滤器(1970)、分布式锁

比如说双十一某宝，redis缓存中key大面积失效，导致某宝直接和数据库进行沟通，把请求直接打到数据库
解决方法：

  1. 随机初始化缓存失效时间，让其不要在同一时间失效
  2. redis一般都是集群部署，我们把热点key放到不同的节点上去，让热点的缓存平均的分布在不同的redis节点上
  3. 最暴力的方法：不设置缓存的失效时间，让它永远不失效，或者跑定时任务，让它定时刷这个缓存让其不失效

2. 缓存穿透：

阅读全文 »

发表于 更新于 本文字数： 1.2k 阅读时长 ≈ 5 分钟

1 观察者模式

  • 在软件构建过程中，我们需要为某些对象建立一种“通知依赖关系” ——一个对象（目标对象）的状态发生改变，所有的依赖对象（观察者对象）都将得到通知。如果这样的依赖关系过于紧密，将使软件不能很好地抵御变化。
  • 定义对象间的一种一对多（变化）的依赖关系，以便当一个对象(Subject)的状态发生改变时，所有依赖于它的对象都得到通知并自动更新。
  • 观察对象的状态发生变化时，通知给观察者。 观察者模式适用于根据对象状态进行相应处理的场景。

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
// FileSplitter.cpp
class FileSplitter{
	string m_filePath;
	int m_fileNumber;
	ProgressBar* m_progressBar; // 不能应对变化，和具体某个平台的进度条绑死：例如UI进度条、无界面的Shell进度条等等

public:
	FileSplitter(const string& filePath, int fileNumber, ProgressBar* progressBar) :
		m_filePath(filePath), 
		m_fileNumber(fileNumber),
		m_progressBar(progressBar){
	}

	void split(){
		//1.读取大文件
		// ...

		//2.分批次向小文件中写入
		for (int i = 0; i < m_fileNumber; i++){
			//...
			float progressValue = m_fileNumber;
			progressValue = (i + 1) / progressValue;
			m_progressBar->setValue(progressValue);
		}
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
// MainForm.cpp
class MainForm : public Form{
	TextBox* txtFilePath;
	TextBox* txtFileNumber;
	ProgressBar* progressBar;

public:
	void Button1_Click(){
		string filePath = txtFilePath->getText();
		int number = atoi(txtFileNumber->getText().c_str());
		FileSplitter splitter(filePath, number, progressBar);
		splitter.split();
	}
};
阅读全文 »

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

函数介绍

  • lock_guard：锁定互斥锁后，生命周期结束后会自动释放，不需要手动解锁，也无法手动解锁
  • unique_lock：多数情况与上面一个可以相互替代，但是其更具功能性（付出一些代价）。unique_lock可以进行unlock操作，因此可以和条件变量搭配使用

多线程输出数字

多个线程互斥输出: 0 1 2 3 4 5 6 ...

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <vector>
#include <thread>
#include <mutex>
using namespace std;
int idx = 0;
mutex _mutex;
void func(int n) {
	while (idx < n) { // 改成true一样的
		lock_guard<mutex> tmp(_mutex);
		if (idx >= n) break; // 必须，否则多输出几个数才停
		cout << idx++ << " ";
	}
}
int main() {
	vector<thread> arr;
	for (int i = 0; i < 10; ++i)
		arr.push_back(thread(func, 1000));
	for (auto& e : arr)
		e.join();
	return 0;
}
阅读全文 »

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

问题

  1. 临时对象非必要的昂贵的拷贝操作
  2. 在模板函数中如何按照参数的实际类型进行转发
  • 关键字：右值、纯右值、将亡值、universal references、引用折叠、移动语义、move语义、完美转发
  • 以下用四条代码来阐述C++的右值引用及其思想

1. 第一行代码

1
int i = getVal();
阅读全文 »

发表于 更新于 本文字数： 1.1k 阅读时长 ≈ 4 分钟

辅助代码（全局变量）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
typedef pair<int, int> node;
vector<vector<int>> G = {
    {1,1,1,1,1,1,1,1,1,1,1},
    {1,1,1,1,1,1,1,1,1,1,1},
    {1,1,1,1,1,2,1,1,1,1,1},
    {1,1,1,1,2,3,2,1,1,1,1},
    {1,1,1,2,3,4,3,2,1,1,1},
    {1,1,2,3,4,5,4,3,2,1,1},
    {1,1,1,2,3,4,3,2,1,1,1},
    {1,1,1,1,2,3,2,1,1,1,1},
    {1,1,1,1,1,2,1,1,1,1,1},
    {1,1,1,1,1,1,1,1,1,1,1},
    {1,1,1,1,1,1,1,1,1,1,1}
};
int row = (int)G.size();
int col = (int)G[0].size();
node S = { 5,0 };
node E = { 5,10 };
int dir[] = { -1, 0, 1, 0, -1 };

DFS

  • DFS是无法找到最优路径的（理论上可以，但是复杂度巨高，如果是四个方向搜索的话，那么就是四叉树，高度是图中结点数，也就是说如果是10x10的图，那就是大约4^100复杂度）
  • 下面代码只表示找到任意一条路后直接返回
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
vector<vector<bool>> visited(row, vector<bool>(col, false));
vector<node> path;
bool END = false;
void dfs(node cur) {
    if (cur == E) 
        END = true;
    visited[cur.first][cur.second] = true;
    path.push_back(cur);
    for (int i = 0; i < 4 && !END; ++i) {
        int ix = cur.first + dir[i];
        int iy = cur.second + dir[i + 1];
        if (ix < 0 || ix >= row || iy < 0 || iy >= col || visited[ix][iy]) continue;
        dfs({ ix, iy });
    }
    if (END) return; // 保留路径
    path.pop_back();
    visited[cur.first][cur.second] = false;
}
阅读全文 »

发表于 更新于 本文字数： 777 阅读时长 ≈ 3 分钟

BF(Brute Force)算法

  • BF是最符合人类直觉的字符串匹配算法，但是主串的下标i经常要往回走，无法利用已匹配信息，效率不够好
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int bruteForce(const string& t, const string& p) {
    int i = 0, j = 0;
    // i和j都是非负数，所以可以和无符号直接比较
    while (i < t.size() && j < p.size()) {
        if (t[i] == p[j]) {
            ++i; ++j;
        } else {
            i = i - j + 1;
            j = 0;
        }
    }
    if (j == p.size())
        return i - j;
    else
        return -1;
}

KMP算法

  • 思想：“利用已部分匹配的信息，保持i指针不回溯，通过修改j指针，让模式串尽量移动到有效的位置”
  • 定义next数组： next[j] = d 表示当 t[i] != p[j] 时，j下一次匹配的位置。注意到，下标从0开始，d值实际上是下标j前的最长前后缀子串的长度
  • 求取next的过程本身就是p串与自己匹配的过程
    1. 当 p[i]==p[j] ，则 p[++i] = ++j
    2. 当 p[i]!=p[j] ，则利用前面已求得的next数组，j=next[j] ；直到无法找到，此时 j=-1 ，自动进入第一个if语句，此时i往后走一步，妙
阅读全文 »

发表于 更新于 本文字数： 316 阅读时长 ≈ 1 分钟

功能说明

  • 实现+、-、*、/、括号的整数运算
  • 实现处理多余空格

实现1（更高效）

  • 用引用l指针的方式逐步处理
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
int core(string& s, int& l) {
    stack<int> stk;
    int n = s.size();
    int num = 0;
    char sign = '+';
    for (; l < n; ++l) {
        char c = s[l];
        if (isdigit(c)) 
            num = num * 10 + (c - '0');
        // if(c == ' ') continue是不对的，因为l=n-1时一定要最后来一次
        if ((!isdigit(c) && c != ' ') || l == n - 1) {
            if (c == '(') 
                num = core(s, ++l); // 理解这种递归思想很重要
            int prev;
            switch (sign) {
            case '+':
                stk.push(num); break;
            case '-':
                stk.push(-num); break;
            case '*':
                prev = stk.top(); stk.pop();
                stk.push(prev * num);
                break;
            case '/':
                prev = stk.top(); stk.pop();
                stk.push(prev / num);
                break;
            default: break;
            }
            sign = c;
            num = 0;
            if (c == ')') 
                break;
        }
    }
    int ret = 0;
    while (!stk.empty()) {
        ret += stk.top();
        stk.pop();
    }
    return ret;
}

int caculator(string s) {
    int tmp = 0;
    return core(s, tmp);
}
阅读全文 »

发表于 更新于 本文字数： 1k 阅读时长 ≈ 4 分钟

1. 插入排序

  • 只要注意每次判断比前面的大那就不需要回头
  • 否则需要从头找合适的位置
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
ListNode* insertSort(ListNode* head) {
    if (!head || !head->next) return head;
    ListNode dummy; dummy.next = head;
    ListNode* prev = head;
    ListNode* curr = head->next;
    while (curr) {
        if (prev->val <= curr->val) {
            prev = curr;
            curr = curr->next;
        } else {
            ListNode* t = &dummy;
            while (t->next && t->next->val <= curr->val) t = t->next;
            prev->next = curr->next;
            curr->next = t->next;
            t->next = curr;
            curr = prev->next;
        }
    }
    return dummy.next;
}

2. 归并排序

  • 不论是主递归还是merge都要求两个链表以nullptr结尾
  • 也就是在合适的地方断开
阅读全文 »

发表于 更新于 本文字数： 5.9k 阅读时长 ≈ 21 分钟

一、简单排序

  • 定义：对于下标$i<j$，如果$A[i]>A[j]$，则称$(i,j)$是一对逆序对（inversion）
  • 定理：任意$N$个不同元素组成的序列平均具有$N(N-1)/4$个逆序对。
  • 定理：任何仅以交换相邻两元素来排序的算法，其平均时间复杂度为$Ω(N^2)$

1. 冒泡排序

  • 时间复杂度：$O(N^2)$
  • 最好情况下的时间复杂度，有序$O(N)$
  • 空间复杂度：$O(1)$
  • 稳定（比较相等时，是不做交换的）
  • end标记可以提前结束
  • 链表也可用
  • 每次交换都会消除一对逆序对
    • 如果$I$是逆序对的个数，时间复杂度是$O(N+I)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void bubbleSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n - 1; ++i) {
        int end = 1;
        for (int j = 0; j < n - 1 - i; ++j) {
            if (arr[j] > arr[j + 1])
            {
                swap(arr[j], arr[j + 1]);
                end = 0;
            }
        }
        if (end)
            break;
    }
}
阅读全文 »
0%