7. 前缀树和贪心算法

7.1 前缀树

一个字符串类型的数组arr1，另一个字符串类型的数组arr2。arr2中有哪些字符，是arr1中出现的？请打印。arr2中有哪些字符，是作为arr1中某个字符串前缀出现的？请打印。请打印 arr2中出现次数最大的前缀。

class TrieNode{
public:
    TrieNode(){
        pass = 0;
        end = 0;
        for(int i = 0; i < 26; i++){
            // next[0] == nullptr   没有走向'a'的路
            // next[0] != nullptr   有走向'a'的路
            // ...
            // next[25] != nullptr   有走向'z'的路
            nexts.push_back(nullptr);
        }
    }

    int pass;   //节点通过了多少次
    int end;    //是多少个字符串的结尾节点
    vector<TrieNode*> nexts;
    // 字符类型很多时
    //unordered_map<char, TrieNode*> nexts; 
    //map<char, TrieNode*> nexts;
};

class Trie{
public:
    TrieNode* root;

    Trie(){
        root = new TrieNode();
    }

    void insertWord(string word){
        if(word.size() < 1){
            return;
        }
        TrieNode* node = root;
        node->pass++;
        int index = 0;
        for(auto ch : word){
            index = ch - 'a';
            if(node->nexts[index] == nullptr){
                node->nexts[index] = new TrieNode();
            }
            node = node->nexts[index];
            node->pass++;
        }
        node->end++;
    }

    // word 这个单词之前加入过了几次
    int searchWord(string word){
        if(word.size() < 1){
            return;
        }
        TrieNode* node = root;
        int index = 0;
        for(auto ch : word){
            index = ch - 'a';
            if(node->nexts[index] == nullptr){
                return 0;
            }
            node = node->nexts[index];
        }
        return node->end;
    }

    // 所有加入的字符串中，有几个是以 pre 这个字符串作为前缀的
    int prefixNumber(string pre){
        if(pre.size() < 1){
            return 0;
        }
        TrieNode* node = root;
        int index = 0;
        for(auto ch : pre){
            index = ch - 'a';
            if(node->nexts[index] == nullptr){
                return 0;
            }
            node = node->nexts[index];
        }
        return node->pass;
    }

    void deleteWord(string word){
        if(searchWord(word) != 0){
            TrieNode* node = root;
            node->pass--;
            int index = 0;
            for(auto ch : word){
                index = ch - 'a';
                if(--node->nexts[index]->pass == 0){
                    node->nexts[index] = nullptr;   
                    // todo: 内存管理
                    return;
                }
                node = node->nexts[index];
            }
            node->end--;
        }
    }
};

7.2 贪心算法

在某一个标准下，优先考虑最满足标准的样本，最后考虑最不满足标准的样本，最终得到一个答案的算法，叫作贪心算法。

也就是说，不从整体最优上加以考虑，所做出的是在某种意义上的局部最优解。

局部最优 -?-> 整体最优

1. 会议安排

一些项目要占用一个会议室宣讲，会议室不能同时容纳两个项目的宣讲。

给你每一个项目开始的时间和结束的时间（给你一个数组，里面是一个个具体的项目），你来安排宣讲的日程，要求会议室进行的宣讲的场次最多。

返回这个最多的宣讲场次。

贪心策略: 哪个会议结束时间早就先安排

class Program{
public:
    Program(int s, int e) : start(s), end(e) { }

    int start;
    int end;
};
// 谓词
class ProgramComparator{
public:
    bool operator()(Program& p1, Program& p2){
        return p1.end < p2.end;
    }
};
int bestArrange(vector<Program*>& programs, int timePoint){
    sort(programs.begin(), programs.end(), ProgramComparator());
    int result = 0;
    // 从左往右依次遍历所有的会议
    for(int i = 0; i < programs.size(); i++){
        if(timePoint <= programs[i]->start){
            result++;
            timePoint = programs[i]->end;
        }
    }
    return result;
}

2. 贪心算法的笔试套路

实现一个不依靠贪心策略的解法X，可以用最暴力的尝试
脑补出贪心策略A、贪心策略B、贪心策略C
用解法X和对数器，去验证每一个贪心策略，用实验的方式得知哪个贪心策略正确
不要去纠结贪心策略的证明

3. 贪心算法的证明

一个有很多字符串的数组, 决定一种字符串的拼接顺序, 将数组中的字符串全部拼接起来, 如何让最后拼接成的字符串保证最小的字典序

贪心策略: a.b ≤ b.a ? a.b : b.a;

class MyComparator{
public:
    bool operator()(string& p1, string& p2){
        return p1 + p2 <= p2 + p1;
    }
};
string lowestString(vector<string>& strs){
    if(strs.size() < 1){
        return "";
    }
    sort(strs.begin(), strs.end(), MyComparator());
    string res;
    for(int i = 0; i < strs.size(); i++){
        res += strs[i];
    }
    return res;
}

4. 贪心策略在实现时，经常使用的技巧

根据某标准建立一个比较器来排序
根据某标准建立一个比较器来组成堆

5. 分金条

一块金条切成两半，是需要花费和长度数值一样的铜板的。比如长度为20的金条，不管切成长度多大的两半，都要花费20个铜板。

一群人想整分整块金条，怎么分最省铜板？

例如，给定数组 [10，20，30], 代表一共三个人，整块金条长度为10+20+30=60。金条要分成10，20，30三个部分。如果先把长度60的金条分成10和50，花费60；再把长度50的金条分成20和30，花费50；一共花费110铜板。

但是如果先把长度60的金条分成30和30，花费60；再把长度30金条分成10和20，花费30；一共花费90铜板。

输入一个数组，返回分割的最小代价。

[提示] 哈夫曼编码问题

✅tested

int lessMoney(vector<int>& arr) {
    // 小根堆
    priority_queue<int, vector<int>, greater<int>> pQ(arr.begin(), arr.end());
    int sum = 0;
    int cur = 0;
    while (pQ.size() > 1) {
        int cur1 = pQ.top();
        pQ.pop();
        cout << cur1 << endl;

        int cur2 = pQ.top();
        pQ.pop();
        cout << cur2 << endl;

        cur = cur1 + cur2;
        sum += cur;
        pQ.push(cur);
    }
    return sum;
}

6. 做任务，得利润

[输入]：

正数数组costs, 正数数组profits, 正数k, 正数m

[含义]：

costs[i] 表示i号项目的花费
profits[i] 表示i号项目在扣除花费之后还能挣到的钱（利润）
k 表示最多做k个项目
m 表示初始的资金

[说明]：

你每做完一个项目，马上获得的收益，可以支持你去做下一个项目。

[输出]：

你最后获得的最大钱数。

✅tested

class Node {
public:
    Node(int p, int c) : profit(p), cost(c){ }

    int profit;
    int cost;
};
class MinCostComparator {
public:
    bool operator()(Node* o1, Node* o2) {
        return o1->cost > o2->cost;
    }
};
class MinProfitComparator {
public:
    bool operator()(Node* o1, Node* o2) {
        return o1->profit < o2->profit;
    }
};
// k: 最多做k个项目，w: 初始资金
int findMaxCapital(int k, int w, vector<int>& Profits, vector<int>& Capital) {
    priority_queue<Node*, vector<Node*>, MinCostComparator> minCostQ;
    priority_queue<Node*, vector<Node*>, MinProfitComparator> maxProfitQ;
    // 所有项目放在被锁池中，根据 cost 组织的小根堆
    for (int i = 0; i < Profits.size(); i++) {
        minCostQ.push(new Node(Profits[i], Capital[i]));
    }
    for (int i = 0; i < k; i++) {
        // 能力所及的项目，全解锁
        while (!minCostQ.empty() && minCostQ.top()->cost <= w) {
            maxProfitQ.push(minCostQ.top());
            minCostQ.pop();
        }
        if (maxProfitQ.empty()) {
            return w;
        }
        w += maxProfitQ.top()->profit;
        maxProfitQ.pop();
    }
    return w;
}

7.3 堆的应用

一个数据流中，随时可以取得中位数

[提示] 大根堆与小根堆的配合

第一个数字入大根堆
cur <= 大根堆堆顶 ? cur入大根堆 : cur入小根堆;
比较大根堆和小根堆的size, 当两者的size相差2时, size较大者的堆顶入另一个堆

效果：较小的一半数在大根堆中，较大的一半数在小根堆中

剑指offer: 数据流中的中位数

✅tested

class Solution {
public:
    void Insert(int num) {
        if(max_q.size() < 1){
            max_q.push(num);
            return;
        }
        if(num <= max_q.top()){
            max_q.push(num);
        }else{
            min_q.push(num);
        }
        if(max_q.size() - min_q.size() == 2){
            min_q.push(max_q.top());
            max_q.pop();
        }else if(min_q.size() - max_q.size() == 2){
            max_q.push(min_q.top());
            min_q.pop();
        }
    }

    double GetMedian() { 
        if((max_q.size() + min_q.size()) % 2 == 0){
            return ((double)max_q.top() + (double)min_q.top())/2;
        }
        if(max_q.size() < min_q.size()){
            return min_q.top();
        }
        return max_q.top();
    }
private:
    priority_queue<int> max_q; // 大顶推
    priority_queue<int, vector<int>, greater<int>> min_q; // 小顶堆
};

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Files

基础07.md

基础07.md

7. 前缀树和贪心算法

7.1 前缀树

7.2 贪心算法

1. 会议安排

2. 贪心算法的笔试套路

3. 贪心算法的证明

4. 贪心策略在实现时，经常使用的技巧

5. 分金条

6. 做任务，得利润

7.3 堆的应用

Files

基础07.md

Latest commit

History

基础07.md

File metadata and controls

7. 前缀树和贪心算法

7.1 前缀树

7.2 贪心算法

1. 会议安排

2. 贪心算法的笔试套路

3. 贪心算法的证明

4. 贪心策略在实现时，经常使用的技巧

5. 分金条

6. 做任务，得利润

7.3 堆的应用