Lizq的个人博客

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

带限制的最短路

错误示例（Dijkstra）

全局的dist记录着最短距离，但它并未记录是几跳获得的。例如，到达终点的前一跳，从X->dst，我的代码中只限制了到达X最多k+1跳，此时更新了dist[X]，当更新到dst时，利用的dist[X]是经过k跳的X作为跳板，则结果是经过了k+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
class Item {
public:
    int node, skip, dis;
    Item(int a, int b, int c):node(a),skip(b),dis(c){}
    bool operator>(const Item& R) const {
        return this->dis > R.dis;
    }
};
class Solution {
public:
    int INF = 0x3f3f3f3f;
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
        vector<vector<pair<int, int>>> g(n);
        for (auto& e : flights) g[e[0]].push_back({ e[1], e[2] });
        vector<int> dist(n, INF);
        dist[src] = 0;
        priority_queue<Item, vector<Item>, greater<Item>> pq;
        pq.emplace(src, 0, 0);
        while (!pq.empty()) {
            auto cur = pq.top(); pq.pop();
            int node = cur.node;
            int dis = cur.dis;
            int skip = cur.skip;
            if (skip > k) continue;
            for (auto& e : g[node]) {
                int w_node = e.first;
                int w_weight = e.second;
                if (dist[w_node] > dist[node] + w_weight) {
                    dist[w_node] = dist[node] + w_weight;
                    pq.emplace(w_node, skip + 1, dist[w_node]);
                }
            }
        }
        return dist[dst];
    }
};

再次尝试Dijkstra（完全没必要）

阅读全文 »

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

逆序对计算

1 归并排序

归并排序天然就可统计逆序对，在归并时有以下两种方式统计：

当左侧当前指针指向位置的数字CUR较小时，本轮将其加入归并后的数组，注意到右数组当前指针左边的都是小于CUR的，但是他们位置却在其右侧，所以逆序对贡献为l2-old_l2

1
2
3
4
5
6
if (a <= b) { // 这里包含等于 可以用全1数组模拟想想
    trr[p++] = arr[l1++];
    ret += (l2-old_l2);
}
else 
    trr[p++] = arr[l2++];
阅读全文 »

发表于 更新于 本文字数： 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

阅读全文 »
0%