Lizq的个人博客

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

1 工厂模式

  • 父类决定实例的生成方式，但并不决定所要生成具体的类，具体处理全部交给子类处理。 将生成实例的框架与具体的实例类解耦。
  • 在软件系统中，经常面临创建对象的工作，由于需求的变化，需要创建的对象的具体类型经常变化
  • 如何应对这种变化？如何绕过常规的对象创建方法(new)，提供一种“封装机制”来避免客户程序和这种“具体对象创建工作”的紧耦合？

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
// FileSplitter.cpp
class ISplitter{
public:
    virtual void split()=0;
    virtual ~ISplitter(){}
};

// 多个具体的文件分割器
class BinarySplitter : public ISplitter{
    virtual void split(){
        // ...
    }
};

class TxtSplitter: public ISplitter{
    virtual void split(){
        // ...
    }
};

class PictureSplitter: public ISplitter{
    virtual void split(){
        // ...
    }
};

class VideoSplitter: public ISplitter{
    virtual void split(){
        // ...
    }
};
1
2
3
4
5
6
7
8
9
// MainForm.cpp
class MainForm : public Form{
public:
	void Button1_Click(){
		// 抽象依赖* ptr = new 具体依赖(); 违背依赖倒置原则，这样肯定不行的！
		ISplitter * splitter = new BinarySplitter(); //依赖具体类
        splitter->split();
	}
};
阅读全文 »

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

1 策略模式

  • 定义一系列算法，把它们一个个封装起来，并且使它们可互相替换（变化）。该模式使得算法可独立于使用它的客户程序（稳定）而变化（扩展，子类化）。
  • 将算法与其它部分分离开，只定义与算法相关的接口，然后在程序中以委托的方式来使用。使用委托这种弱关联关系可以很方便地整体替换算法。程序运行过程中也可以替换算法
  • 策略模式是一种行为设计模式， 它能让你定义一系列算法， 并将每种算法分别放入独立的类中， 以使算法的对象能够相互替换。

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
enum TaxBase {
	CN_Tax,
	US_Tax,
	DE_Tax,
	FR_Tax //更改：新添加
};

class SalesOrder{
    TaxBase tax;
public:
    double CalculateTax(){
        //...
        
        if (tax == CN_Tax){
            //CN***********
        }
        else if (tax == US_Tax){
            //US***********
        }
        else if (tax == DE_Tax){
            //DE***********
        }
		else if (tax == FR_Tax){  //更改
			//...
		}
        //....
     }
};

3 策略v1

阅读全文 »

发表于 更新于 本文字数： 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);
}
阅读全文 »
0%