Lizq的个人博客

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

需求

  • 数组区间内经常发生修改，但是又要频繁求得区间的各类统计信息例如最大值、最小值、区间和等等。
  • 对于一个数组频繁求区间和和修改的情况下：
    • 普通操作：修改：O(1)；区间和：O(n)
    • 前缀和：修改：O(n)；区间和：O(1)
    • 线段树：修改：O(nlogn)；区间和：O(nlogn)

线段树

  • 将数组以二分的形式建成一棵二叉树，叶子节点为数组的值，非叶子节点保存相应的统计信息。这棵树近似完全二叉树的结构，所以可以用数组来构建
  • 下面所列举的代码只需要改变给tree[node]赋值相关代码即可实现求最大值、最小值、区间和，肥肠方便
  • 307. 区域和检索 - 数组可修改

1、数组版

阅读全文 »

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

需求

  • 随机修改数组中一个数字
  • 求前缀和
  • 以上操作需要频繁操作

预备知识：lowbit

lowbit指数字的二进制最低位1及后续0取出后的数字

1
2
3
int lowbit(int a){
    return a & -a;
}
阅读全文 »

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

const要点

  • C的const是虚假的，就是个只读量，只是说不能通过变量名进行修改，但是拿到指针就可修改；
  • C++的const会保险一些，会有类似符号表的东西；但是类内的const普通成员变量则依旧会被通过指针改变
  • 静态const和全局const虽然可以通过指针修改，编译时期可能不会报错，但是运行到那个地方就会报错
  • const只在编译期间保证常量被使用时的不变性，无法保证运行期间的行为。
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
class A {
public:
    const int val2 = 22;
    static int val3;
    static const int val4 = 44; // !
};
int A::val3 = 33;
const int val5 = 55;
int val6 = 66;
int main() {
    const int val1 = 11;
    int* p1 = (int*)&val1; // 栈区，拿到地址随便改，但是符号表会覆盖
    *p1 = 1111;
    cout << &val1 << " " << val1 << endl;
    cout << p1 << " " << *p1 << endl;
    cout << "===" << endl;

    A ins;
    int* p2 = (int*)&ins.val2;
    *p2 = 2222; // 栈区，拿到地址随便改
    cout << &ins.val2 << " " << ins.val2 << endl;
    cout << p2 << " " << *p2 << endl;
    cout << "===" << endl;

    int* p3 = (int*)&A::val3;
    *p3 = 3333; // 全局数据区，但是不在常量区，可以修改
    cout << p3 << " " << *p3 << endl;
    cout << &A::val3 << " " << A::val3 << endl;
    cout << "===" << endl;

    int* p4 = (int*)&A::val4;
    //*p4 = 4444; // 编译不出错，运行会异常（常量区不能修改）
    cout << p4 << " " << *p4 << endl;
    cout << &A::val4 << " " << A::val4 << endl;
    cout << "===" << endl;

    int* p5 = (int*)&val5;
    //*p5 = 5555; // 编译不出错，运行会异常（常量区不能修改）
    cout << p5 << " " << *p5 << endl;
    cout << &val5 << " " << val5 << endl;
    cout << "===" << endl;

    int* p6 = (int*)&val6;
    *p6 = 6666; // 全局数据区，但是不在常量区，可以修改
    cout << p6 << " " << *p6 << endl;
    cout << &val6 << " " << val6 << endl;
    return 0;
}

输出结果：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/*
00EFFD98 11
00EFFD98 1111
===
00EFFD80 2222
00EFFD80 2222
===
0027C038 3333
0027C038 3333
===
00279B38 44
00279B38 44
===
00279B30 55
00279B30 55
===
0027C03C 6666
0027C03C 6666
*/
阅读全文 »

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

1 状态模式

  • 在软件构建过程中，某些对象的状态如果改变，其行为也会随之改变，比如文档处于只读状态，其支持的行为和读写状态支持的行为可能完全不同
  • 允许一个对象在其内部状态改变时改变它的行为。从而使对象看起来似乎修改了其行为
  • 用类表示状态，通过切换类改变对象状态
  • 跟Strategy模式很像，区别是：状态模式采用单例模式，抽象类包含指向下一个状态的指针

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
42
43
44
45
enum NetworkState{
    Network_Open,
    Network_Close,
    Network_Connect
    // 假设未来有新状态：Network_Wait，怎么办？
};

class NetworkProcessor{
    NetworkState state;

public:
    void Operation1(){
        if (state == Network_Open){
            //**********
            state = Network_Close;
        }
        else if (state == Network_Close){
            //..........
            state = Network_Connect;
        }
        else if (state == Network_Connect){
            //$$$$$$$$$$
            state = Network_Open;
        }
    }

    void Operation2(){
        if (state == Network_Open){
            //**********
            state = Network_Connect;
        }
        else if (state == Network_Close){
            //..........
            state = Network_Open;
        }
        else if (state == Network_Connect){
            //$$$$$$$$$$
            state = Network_Close;
        }
    }

    void Operation3(){
        // ...
    }
};

3 状态v1

阅读全文 »

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

1 适配器模式

  • 在软件系统中，由于应用环境的变化，常常需要将“一些现存的对象”放在新的环境中应用，但是新环境要求的接口是这些现存对象所不满足的。
  • 将一个类的接口转换成客户希望的另一个接口，Adapter模式使得原本由于接口不兼容而不能一起工作的那些类可以一起工作

2 适配器v1

适配器模式

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
// 目标接口（新接口）
class ITarget{
public:
    virtual void process() = 0;
};

// 遗留接口（老接口）
class IAdaptee{
public:
    virtual void foo(int data) = 0;
    virtual int bar() = 0;
};

// 遗留类型
class OldClass: public IAdaptee{
public:
    virtual void foo(int data){
        // ...
    }
    virtual int bar(){
        // ...
    }
};

// 对象适配器（推荐）
class Adapter: public ITarget{ // 继承
protected:
    IAdaptee* pAdaptee; // 组合（多态）
    
public:
    Adapter(IAdaptee* pAdaptee){
        this->pAdaptee=pAdaptee;
    }
    
    virtual void process(){
        int data=pAdaptee->bar();
        pAdaptee->foo(data);
    }
};

// 类适配器（十分不推荐）
class Adapter: public ITarget, protected OldClass{ // 多继承（无复用性，绑死OldClass）
    // ...
}

int main(){
    IAdaptee* pAdaptee = new OldClass(); // 老接口
    ITarget* pTarget = new Adapter(pAdaptee);
    pTarget->process();
}

class stack{ // STL中stack包含deque，看作是种适配器
    deqeue container;
    // ...
};

class queue{ // STL中queue包含deque，看作是种适配器
    deqeue container;
    // ...
};
阅读全文 »

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

Prim：从一颗小树长大

思路和Dijkstra基本一致，唯一不同就是dist记录的是与集合的距离而非与起点的距离

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
// Leetcode 1584 连接所有点的最小费用
// points = [[0,0],[2,2],[3,10],[5,2],[7,0]] 求坐标轴上这几个点的最小生成树的路径和
struct Node{ // 用来在优先队列里用
    int node;
    int dis;
    bool operator>(const Node& ano) const {
        return this->dis > ano.dis;
    }
};

class Solution {
public:
    int minCostConnectPoints(vector<vector<int>>& points) {
        int n = points.size(); // 节点数
        vector<vector<int>> graph(n, vector<int>(n, INT_MAX));
        for (int i = 0; i < n; ++i){ // 建图
            for (int j = 0; j < i; ++j){
                graph[i][j] = abs(points[i][0]-points[j][0]) + abs(points[i][1]-points[j][1]);
                graph[j][i] = graph[i][j];
            }
        }  
        priority_queue<Node, vector<Node>, greater<Node>> pq;
        vector<int> dist(n, INT_MAX);
        pq.push(Node({0, 0})); // 从0开始， 0到0的距离是0
        int ret = 0;
        while(!pq.empty()){
            Node cur = pq.top(); pq.pop();
            // 跟Dijkstra一样，但人家遇到终点直接可以break
            // 因为采用优先队列的方式，队列里会有重复，第一次接触的肯定是最优解，后面
            // 重复的都是大于最优解的，直接跳过，或者你用一个数组，存储对应节点最优dist
            // 每次存储比较取最小值，但是空间浪费太大了，不如这样好
            if(dist[cur.node] == 0) continue;
            dist[cur.node] = 0;
            ret += cur.dis;
            for(int i=0; i<n; ++i){
                if(dist[i] > graph[cur.node][i]){
                    dist[i] = graph[cur.node][i];
                    pq.push(Node({i, graph[cur.node][i]}));
                }
            }
        }
        return ret;
    }
};

Kruskal

利用并查集的思想

阅读全文 »

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

1 模板方法模式

  • 模板方法模式是一种行为设计模式， 它在超类中定义了一个算法的框架， 允许子类在不修改结构的情况下重写算法的特定步骤。
  • 在父类中定义处理流程的框架，在子类中实现具体处理
  • 在软件构建过程中，对于某一项任务，它常常有稳定的整体操作结构，但各个子步骤却有很多改变的需求，或者由于固有的原因（比如框架与应用之间的关系）而无法和任务的整体结构同时实现。
  • 定义一个操作中的算法的骨架 (稳定)，而将一些步骤延迟(变化)到子类中。Template Method使得子类可以不改变(复用)一个算法的结构即可重定义(override 重写)该算法的某些特定步骤。

2 问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//程序库开发人员
class Library{
public:
	void Step1(){
		//...
	}

    void Step3(){
		//...
    }

    void Step5(){
		//...
    }
};
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
//应用程序开发人员
class Application{
public:
	bool Step2(){
		//...
    }

    void Step4(){
		//...
    }
};

int main(){
	Library lib();
	Application app();
	
	lib.Step1();
	if (app.Step2()){
		lib.Step3();
	}
	for (int i = 0; i < 4; i++){
		app.Step4();
	}
	lib.Step5();
}
阅读全文 »

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

01背包

经典动态规划问题，输入重量数组weight、价值数组value和背包可承载的最大重量整数maxW

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
	int knapsack(vector<int>& weight, vector<int>& value, int maxW) {
		// 物品数目
		int kinds = weight.size();
		// dp数组初始化为二维数组
		vector<vector<int>> dp(kinds + 1, vector<int>(maxW + 1, 0));
		// 状态一：可选的目标：0个可选，前一个可选、前两个可选、前三个可选，以此类推（与找零钱不同，物品不能重复选）
		for (int c = 1; c <= kinds; c++) {
			// 状态二：当前的可承载重量，0、1、2...maxW
			for (int w = 1; w <= maxW; w++) {
				// 该物品太大以至于当前重量超标：下标越界，直接赋值为“没有该物品时的最优答案”
				if (w - weight[c - 1] < 0) 
					dp[c][w] = dp[c - 1][w];
				// 比较，“不选择该物品”和“选择该物品”时，哪个价值大
				else
					dp[c][w] = max(dp[c - 1][w], dp[c - 1][w - weight[c - 1]] + value[c - 1]);
			}
		}
		return dp[kinds][maxW];
	}
};

完全背包

标准DP

阅读全文 »

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

1 迭代器模式

  • 在软件构建过程中，集合对象内部结构常常变化各异。但对于这些集合对象，我们希望在不暴露其内部结构的同时，可以让外部客户代码透明地访问其中包含的元素;同时这种“诱明遍历”也为“同一种算法在多种集合对象上进行操作”提供了可能。
  • 提供一种方法顺序访问一个聚合对象中的各个元素，而又不暴露（稳定）该对象的内部表示
  • 访问一个聚合对象的内容而无需暴露其内部实现；支持对聚合对象的多种遍历；为遍历不同的聚合结构提供统一的接口；健壮性考虑：遍历的同时更改迭代器所在聚合结构，会导致问题
  • 该篇介绍的是基于面向对象的迭代器实现，但是C++泛型编程迭代器已经淘汰掉面向对象的迭代器，然而思想一样，技术更新而已

2 迭代器v1

迭代器模式

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
/*
C++现在都是基于模板的迭代器，模板又称为编译时多态，速度肯定比虚函数的运行时多态要好很多
但是java、C#、PHP、Swift还是这种基于虚函数的迭代器（因为不支持编译时的模板机制）
*/
template<typename T>
class Iterator{
public:
    virtual void first() = 0;
    virtual void next() = 0;
    virtual bool isDone() const = 0;
    virtual T& current() = 0;
};

template<typename T>
class MyCollection{
public:
    Iterator<T>* GetIterator(){
        // ...
    }
};

template<typename T>
class CollectionIterator : public Iterator<T>{
    MyCollection<T> mc;
public:
    CollectionIterator(const MyCollection<T>& c): mc(c){ }
    
    void first() override {
        // ...
    }
    void next() override {
        // ...
    }
    bool isDone() const override{
        // ...
    }
    T& current() override{
        // ...
    }
};

void MyAlgorithm(){
    MyCollection<int> mc;
    Iterator<int>* iter = mc.GetIterator();
    for (iter->first(); !iter->isDone(); iter->next()){ // 多态
        cout << iter->current() << endl; // 多态
    }
}
阅读全文 »

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

1 抽象工厂模式

  • 在软件系统中，经常面临着“一系列相互依赖的对象”的创建工作；同时，由于需求的变化，往往存在更多系列对象的创建工作。
  • 如何应对这种变化？如何绕过常规的对象创建方法(new)，提供一种“封装机制”来避免客户程序和这种“多系列具体对象创建工作”的紧耦合？
  • 提供一个接口，让该接口负责创建一系列“相关或者相互依赖的对象”，无需指定它们具体的类。

2 问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class EmployeeDAO{
public:
    vector<EmployeeDO> GetEmployees(){
        SqlConnection* connection = new SqlConnection(); // 耦合
        connection->ConnectionString("...");

        SqlCommand* command = new SqlCommand(); // 耦合
        command->CommandText("...");
        command->SetConnection(connection);

        SqlDataReader* reader = command->ExecuteReader();
        while (reader->Read()){
            // ...
        }
    }
};

3 尝试简单工厂模式

阅读全文 »
0%