一、活动安排

描述
给定n个活动，每个活动安排的时间为[ai,bi)。求最多可以选择多少个活动，满足选择的活动时间两两之间没有重合。
输入描述：
第一行输入一个整数n (1≤n≤2⋅10 ^5 )，表示可选活动个数。
接下来的n行，每行输入两个整数ai,bi(0≤ai )，表示第i个活动的时间。
输出描述：
输出一行一个整数，表示最多可选择的活动数。
示例1
输入：
3
1 4
1 3
3 5
复制
输出：
2

#include
#include
#include
using namespace std;
struct cmp{
    bool operator()(const pair<int,int> a,const pair<int,int> b){
        if(a.second > b.second)
            return a.second > b.second;
        else if(a.second == b.second)
            return a.first < b.first;
        return false;
    }
};
int main()
{
    int n,total = 0,time = 0,a,b;
    cin >> n;
    priority_queue<pair<int,int>,vector<pair<int,int>>,cmp> q;
    while(n--){
        cin >> a >> b;
        q.push(pair<int,int>(a,b));
    }
    while(!q.empty()){
        auto cur = q.top();
        q.pop();
        if(cur.first >= time){
            total++;
            time = cur.second;
        }
    }
    cout << total;
}

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

二、【模板】哈夫曼编码

描述
给出一个有n种字符组成的字符串，其中第ii种字符出现的次数为ai 。请你对该字符串应用哈夫曼编码，使得该字符串的长度尽可能短，求编码后的字符串的最短长度。
输入描述：
第一行输入一个整数n (1≤n≤2⋅10 ^5)，表示字符种数。
第二行输入n个整数ai(1≤ai≤10^9)，表示每种字符的出现次数。
输出描述：
输出一行一个整数，表示编码后字符串的最短长度。
示例1
输入：
3
1 2 3
复制
输出：
9
复制
说明：
三种字符的哈夫曼编码分别为[“00”,“01”,“1”]时，长度最短，最短长度为9。

#include 
#include
using namespace std;
typedef long long ll;
int n;

int main() {
    cin>>n;
    priority_queue<ll, vector<ll>, greater<ll> >q;
    ll num;
    for (int i = 0; i < n; i++) {
        cin>>num;
        q.push(num);
    }
    ll sum = 0;
    while (!q.empty()) {
        ll a = q.top();
        q.pop();
        if (q.empty()) {
            sum += a;
        } else {
            ll b = q.top();
            q.pop();
            sum += a + b;
            if (!q.empty()) {
                q.push(a + b);
            }
        }
    }
    cout<<sum<<endl;
    return 0;
}
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

三、通配符匹配

通过题目分析我们可以大致了解题目的意思，主要是比较两个字符串是否相等，但是还包括两个通配字符，'?‘表示可以匹配任何单个字符，’'可以匹配任何字符序列（包括空序列），已知两个字符串指针：s和p，设定两个存储位置的指针变量char spd主要用于存储S指针的位置和char* ppd用于存储p指针的位置，主要分为三种情况：

其一为，当s指针指向的字符与p指针指向的字符相等或者p指针为“？”代表两个字符匹配，直接进行下一轮的判断。比如"a", “?”，这两个字符串相等。

其二为，当p指针为“”时，为这道题的重点，也就是可以匹配任何字符序列（包括空序列），这时候，我们就需要spd和ppd记录s和p指针的位置，然后通过设定的标记位进行循环判断。比如"aa", ""返回true。

其三为，当两个字符串的值不相等时，可以直接返回false。比如"a",“b”。

/**
 *
 * @param s string字符串
 * @param p string字符串
 * @return bool布尔型
 */
int isMatch(char* s, char* p ) {
    // write code here
    char* spd;//设置指针,主要用于存储S指针的字符
    char* ppd;//存储p指针的字符
    
    int specil = 0;//标记为
    while(*s){
        if(*s == *p || *p == '?'){//当两个指针指向相等或者是p指针所指字符位通配符?时
            s++;//判断下一位
            p++;//判断下一位
        }
        else if(*p == '*'){
            spd = s;//将s中的字符位置赋给spd
            ppd = ++p;//p走向下一位，记录当前位置的值
            specil = 1;//标记为设置位1
        }
        else if(specil){
            s = ++spd;//s可以与*匹配
            p = ppd;//返回p的位置值
        }
        else{
            return 0;
        }
    }
    while(*p == '*'){//监测空字符
        p++;
    }
    return !*p;
}
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

因为该程序循环的是s的全部字符，故时间复杂度为O(N)，N为s的长度，M为p的长度，当p的字符串长度大于s的字符串长度时，时间复杂度为O(M)，空间复杂度为O(N + M)。