构建哈夫曼

struct node {
	int w;
	char index;
	node* lchild,* rchild;
	node(int w, char index = '\0', node* l = nullptr, node* r = nullptr) :w(w), index(index), lchild(l), rchild(r) {}
};
struct cmp {
	bool operator()(node a, node b) {
		return a.w > b.w;//注意，如果要大顶堆，那么意味着降序，符号连接应该翻一下，为<
		//反之，小顶堆为升序，翻一下，连接为>
	}
};
priority_queue<node, vector<node>, cmp>q;

主要就是优先队列存储结构体，需要注意一下 

struct node {
	int w;
	char c;
	node* lchild, * rchild;
	node(int x, char c = '\0', node* l = nullptr, node* r = nullptr) :w(x), c(c), lchild(l), rchild(r) {}
};
struct cmp {
	bool operator()(node* a, node* b) {
		return a->w > b->w;//由此形成大顶堆
	}
};
node* build(vector<int>ws, vector<char>cs) {
	priority_queue<node*, vector<node*>, cmp>q;
	for (int i = 0; i < ws.size(); i++) {
		node* n = new node(ws[i], cs[i]);
		q.push(n);
	}
	while (q.size() > 1) {//注意终止条件为>1,而不是为空
		node* a = q.top();
		q.pop();
		node* b = q.top();
		q.pop();
		node* mer = new node(a->w + b->w, '\0', a, b);
		q.push(mer);
	}
	return q.top();
}

void huf(node* root, string code, vector<pair<char, string>>& a) {
	if (!root) { return; }
	if (root->c != '\0') {
		a.push_back({ root->c,code });
	}
	else {
		huf(root->lchild, code + '0', a);
		huf(root->rchild, code + '1', a);
	}
}
vector<int>w = { 5,2,7,4,9 };
vector<char>chars = { 'A', 'B', 'C', 'D', 'E' };
node* root = build(w, chars);
vector<pair<char, string>>d;
huf(root, "", d);
for (auto dp : d) {
	cout << dp.first << ":" << dp.second << endl;
}

 括号合法

P1739 表达式括号匹配

假设一个表达式有英文字母（小写）、运算符（+、-、*、/）和左右小（圆）括号构成，以 @ 作为表达式的结束符。请编写一个程序检查表达式中的左右圆括号是否匹配，若匹配，则输出 YES；否则输出 NO。表达式长度小于 255255，左圆括号少于 2020 个。

输入格式

一行：表达式。

输出格式

一行：YES 或 NO。

题解

只是初级的，因为只涉及到一种括号；另外栈内存储的不一定就得是相应的括号，可以转为数字编码，比如（用1表示，【用2表示；遇到左括号就入栈，遇到右括号就出栈，遇到右括号不往栈里进行入栈操作，只进行出栈操作

	char t;
	stack<char>s;
	while (cin >> t && t != '@') {
		if (t == '(') {
			s.push(t);
		}
		if (t == ')') {
			if (s.empty()) {
				cout << "NO";
				return 0;
			}
			else {
				s.pop();
			}
		}
	}
	if (s.empty())cout << "YES";//如果最后栈为空，就说明刚好匹配
	else cout << "NO";//有剩余的话，说明左括号过量，不匹配

表达式求值

P1449 后缀表达式

所谓后缀表达式是指这样的一个表达式：式中不再引用括号，运算符号放在两个运算对象之后，所有计算按运算符号出现的顺序，严格地由左而右新进行（不用考虑运算符的优先级）。

本题中运算符仅包含 +-*/+-*/。保证对于 // 运算除数不为 0。特别地，其中 // 运算的结果需要向 0 取整（即与 C++ / 运算的规则一致）。

如：3*(5-2)+73*(5-2)+7 对应的后缀表达式为：3.5.2.-*7.+@3.5.2.-*7.+@。在该式中，@ 为表达式的结束符号。. 为操作数的结束符号。

输入格式

输入一行一个字符串 �s，表示后缀表达式。

输出格式

输出一个整数，表示表达式的值。

题解

这个比较弱，因为后缀表达式，不考虑运算符的优先级，所以就直接操作即可

遇到数字就入栈，遇到操作符就出栈操作

 while(ch!='@')
    {
        ch=getchar();
        switch(ch)
        {
            case '+':x=n.top();n.pop();y=n.top();n.pop();n.push(x+y);break;
            case '-':x=n.top();n.pop();y=n.top();n.pop();n.push(y-x);break;
            case '*':x=n.top();n.pop();y=n.top();n.pop();n.push(x*y);break;
            case '/':x=n.top();n.pop();y=n.top();n.pop();n.push(y/x);break;
            case '.':n.push(s);s=0;break;
            default :s=s*10+ch-'0';break;
        }
    }
    printf("%d\n",n.top())

#include <iostream>
#include <vector>
#include <algorithm>
#include<stack>
#include<queue>
#include <map>
#include<string>
using namespace std;
struct node {
    int x;
    node* next;
};
long long stk[1000];
int main() {
    char op;
    long long i = 0, now = 0;
    while (cin >> op && op != '@') {
        if (op >= '0' && op <= '9') {//如果是数字
            now *= 10;
            now += op - '0';//字符转数字要-'0';数字转字符为+'0'
        }
        else if (op == '.') {
            stk[++i] = now;
            now = 0;
        }
        else if (op == '+') {
            stk[i - 1] = stk[i - 1] + stk[i];
            stk[i] = 0;
            i--;
        }
        else if (op == '-') {
            stk[i - 1] = stk[i - 1] - stk[i];
            stk[i] = 0;
            i--;
        }
        else if (op == '*') {
            stk[i - 1] = stk[i - 1] * stk[i];
            stk[i] = 0;
            i--;
        }
        else if (op == '/') {
            stk[i - 1] = stk[i - 1] / stk[i];
            stk[i] = 0;
            i--;
        }
    }
    cout << stk[i];
    return 0;
}

   stack<long long>s;
    char op;
    long long now = 0;
    while (cin >> op && op != '@') {
        if (op >= '0' && op <= '9') {
            now *= 10;
            now += op - '0';
        }
        else if (op == '.') {
            s.push(now);
            now = 0;
        }
        else if (op == '+') {
            long long num1 = s.top();
            s.pop();
            long long num2 = s.top();
            s.pop();
            s.push(num1 + num2);
        }
        else if (op == '-') {
            long long num1 = s.top();
            s.pop();
            long long num2 = s.top();
            s.pop();
            s.push(num2 - num1);
        }
        else if (op == '*') {
            long long num1 = s.top();
            s.pop();
            long long num2 = s.top();
            s.pop();
            s.push(num1 * num2);
        }
        else if (op == '/') {
            long long num1 = s.top();
            s.pop();
            long long num2 = s.top();
            s.pop();
            s.push(num2 / num1);
        }
    }
    cout << s.top();

 P1981 [NOIP2013 普及组] 表达式求值

题目描述

给定一个只包含加法和乘法的算术表达式，请你编程计算表达式的值。

输入格式

一行，为需要你计算的表达式，表达式中只包含数字、加法运算符 + 和乘法运算符 *，且没有括号，所有参与运算的数字均为 00 到 231−1231−1 之间的整数。

输入数据保证这一行只有 0123456789+* 这 1212 种字符。

输出格式

一个整数，表示这个表达式的值。

注意：当答案长度多于 4 位时，请只输出最后 4 位，前导 00 不输出。

题解

1e4是指1后面有4个0，1e5是后面有5个0

多于4位只输出最后4位，就是通过取模的运算，就是取模10000，即1e4

对于乘法与除法，遇到就直接运算，对于加法与减法，就先存起来，最后再统一运算

    stack<int>x;
    int a, b, m = 10000;
    char c;
    cin >> a;
    a = a % m;
    x.push(a);
    while (cin >> c >> b) {
        if (c == '*') {//如果是乘法就直接操作
            a = x.top();
            x.pop();
            x.push(a * b % m);//
        }
        else {
            x.push(b);//不然就先入栈，最后再统一结算
        }
    }
    a = 0;
    while (!x.empty()) {
        a += x.top();
        a %= m;
        x.pop();
    }
    cout << a << endl;

P4387 【深基15.习9】验证栈序列

题目描述

给出两个序列 pushed 和 poped 两个序列，其取值从 1 到 �(�≤100000)n(n≤100000)。已知入栈序列是 pushed，如果出栈序列有可能是 poped，则输出 Yes，否则输出 No。为了防止骗分，每个测试点有多组数据。

输入格式

第一行一个整数 �q，询问次数。

接下来 �q 个询问，对于每个询问：

第一行一个整数 �n 表示序列长度；

第二行 �n 个整数表示入栈序列；

第三行 �n 个整数表示出栈序列；

输出格式

对于每个询问输出答案。

题解

就是火车重排，怎么判断该出栈能否由指定的入栈顺序得到

就是在输入时做文章，输入一个就判断当前的栈顶元素，判断相不相同，如果相同就一直出栈，直到栈里没元素，不相同就接着入栈输入；用一个计数器cnt记录出栈顺序到哪了

	const int maxn = 1e5 + 3;
	int q, n, push[maxn], pop[maxn];
	cin >> q;
	while (q--) {
		cin >> n;
		stack<int>s;
		int cnt = 1;
		for (int i = 1; i <= n; i++)cin >> push[i];
		for (int i = 1; i <= n; i++)cin >> pop[i];
		for (int i = 1; i <= n; i++) {
			s.push(push[i]);
			while (!s.empty() && s.top() == pop[cnt]) {
				s.pop();
				cnt++;
			}
		}
		if (s.empty())cout << "Yes" << endl;
		else cout << "No" << endl;
	}

入栈顺序不一定是递增的，所以在检验的时候也没办法有特判剪枝

就是入栈一个元素后，判断与当前的出栈头头一样不一样，一样就一直出，直到不一样或为空，最后如果栈里还有剩余，就说明按照指定的出栈顺序出不干净，所以是不行的，做不到指定的出栈顺序，如果为空就说明可以。

P3613 【深基15.例2】寄包柜 题解

超市里有 �(1≤�≤105)n(1≤n≤105) 个寄包柜。每个寄包柜格子数量不一，第 �i 个寄包柜有 ��(1≤��≤105)ai​(1≤ai​≤105) 个格子，不过我们并不知道各个 ��ai​ 的值。对于每个寄包柜，格子编号从 1 开始，一直到 ��ai​。现在有 �(1≤�≤105)q(1≤q≤105) 次操作：

• 1 i j k：在第 �i 个柜子的第 �j 个格子存入物品 �(0≤�≤109)k(0≤k≤109)。当 �=0k=0 时说明清空该格子。
• 2 i j：查询第 �i 个柜子的第 �j 个格子中的物品是什么，保证查询的柜子有存过东西。

已知超市里共计不会超过 107107 个寄包格子，��ai​ 是确定然而未知的，但是保证一定不小于该柜子存物品请求的格子编号的最大值。当然也有可能某些寄包柜中一个格子都没有。

输入格式

第一行 2 个整数 �n 和 �q，寄包柜个数和询问次数。

接下来 �q 个整数，表示一次操作。

输出格式

对于查询操作时，输出答案，以换行隔开。

题解

查找，建立一一映射的关系；

要存储三个信息，两个信息确定位置，一个信息确定数据

对于二维的数据，有两种方法，一种是通过运算折合成一维的

一种方法是用pair

    int n, q, t, x, y, z;
    map <pair< int, int >, int > p;
    cin >> n >> q;
    for (int i = 1; i <= q; i++) {
        cin >> t;
        if (t == 1) {
            cin >> x >> y >> z;
            p[{x, y}] = z;
        }
        if (t == 2) {
            cin >> x >> y;
            cout << p[{x, y}] << endl;
        }
    }

收纳盒装法 

现在有一个大小n1的收纳盒，我们手里有无数个大小为11和2*1的小方块，我们需要用这些方块填满收纳盒，请问我们有多少种不同的方法填满这个收纳盒

输入描述:
第一行是样例数T
第2到2+T-1行每行有一个整数n（n<=80），描述每个样例中的n。

输出描述:
对于每个样例输出对应的方法数

const int maxn = 90;
int dp[maxn];
int t, n;
int fdp(int n) {
    if (dp[n])return dp[n];//那么对于每个可达状态的方法数，要么是由n-1得到，要么n-2得到，则路径方法数就是两种方法数并起来，即+
    dp[n] = fdp(n - 1) + fdp(n - 2);//每个状态有两种选择，即走一步或走两步
    return dp[n];
}
cin >> t;
dp[1] = 1;
dp[2] = 2;
while (t--) {
    cin >> n;
    cout << fdp(n) << endl;
}

链表反转

有两种反转方式，一种是用虚指针的区间反转，一种是整体全部反转，整体全部反转的话，就直接让原来正向的指针都变为逆向即可，然后再不断移动两个指针；如果是区间反转，就需要控制住队头，然后把队列尾部的元素一个一个移动到队头处

反转和交换位置并无关系，交换相邻的两个元素并不能实现链表的反转

交换相邻的两个元素是类似于冒泡排序的，反转是类似于选择排序的

交换的思想是，每次把一个节点不断交换，交换到区间的终点，一共迭代n次

然后每次交换的时候，各个初始位置的节点（都是从区间位置的起点开始），往后不断地交换，但是交换的次数越来越少，因为经过不断的交换前面的都是已经反转好后的节点；然后分别就只需要交换n,n-1,n-2……次

就是交换的思想是从区间点开始直接移到区间末尾

整体反转

struct node {
    int x;
    node* next;
};
node* reverse(node* head) {
    if (!head)return nullptr;
    node* pre = nullptr;
    node* cur = head;
    while (cur) {
        node* nx = cur->next;
        cur->next = pre;
        pre = cur;
        cur = nx;
    }
    return pre;
}

区间反转 

用起点指针去接受反转后的头结点 

类似于选择排序的过程，是不断的把区间最后的节点放到区间最开始的位置，就是反转，

让cur指向这个区间最开始的节点，固定pre不动，然后不断把cur后面所指向的节点移到区间最开始的位置，这样就会把cur最后挤到区间的末尾，然后就完成了区间的反转

这种交换就并不是相邻的，即不是一个节点逐渐冒泡到末尾的，虽然类似于冒泡，但是是直接跳到末尾的，能这样做的原因就在于固定了pre指针，就是Pre指针的后继就是末尾，那么就省却了后续的节点不断往前交换直至起点的过程，而是可以直接通过pre->next跳到区间节点，这样的话每个节点都只需要跳一次就行，就是On的复杂度

相比于逐渐冒泡，直接冒泡的操作方式也是固定的；对于逐渐冒泡，每次冒泡的终点在变化，因为前一个冒完后在反转后的终点位置就已经确定，如果不改变的话，相当于又重新滑了一遍滑回来了。直接冒泡的方向是反向的，这样化实际上就是每次从队尾取出元素放到队头，最后得到的就是反转后的队列

队尾的确定就是通过cur,即逐渐增大队列（区间）长度的一个过程，cur->next是要加入到队列中的下一个元素，队头的确定就是通过pre->next

之所以是这种写法，是因为头结点可能也参与到运算当中，如果头结点参与到运算当中，那么返回头结点时，就只是头结点后面的一截；说到底，头结点也只是链表中的一个指针，只不过是其指向链表的头部而已；如果在运算当中，这个指针所指的节点运算后不再是第一个节点，那么返回这个指针，返回的也就不再是头结点，所以才需要用res保存头结点，然后让res->next为头结点，这样就允许cur和head相等时参与运算，这样修改后，也就是res->next做出修改，也就能保证返回的始终是链表的第一个元素

就是说如果头结点指针的位置不变，那么返回head是正确的；如果head参与运算且位置发生变化，那么返回head就是错误的

还需要注意，初始时不应该设置pre为空指针，因为空指针没有节点的后继指针，就是要设置出一个空类型的节点指针，然后才能保证pre指针有后继节点指针

也体现为第一个节点不断往后冒的过程

node* reverse(node* head,int m,int n) {
    if (!head)return nullptr;//所以如果用<=m的话，会多操作一次；现在希望先到起点的前一个位置，那就是m-i-1
    node* cur = head;//实际上希望的是移动到区间的起点，需要移动与头结点的距离这么多次，如果起点在2，要移1次；在3要移2次
    for (int i = 1; i <= m - 2; i++) {//如果是=的话，就意味着要操作m次，但是m代表的是区间起点
        cur = cur->next;
    }
    node* pre = cur;
    cur = cur->next;//得到区间中的第一个节点//区间节点数为end-begin+1
    for (int i = 1; i <= n - m; i++) {//cur初始为区间的第一个节点，如果区间内有n个节点，那么就是要移动后续的n-1个节点
        node* temp = cur->next;//得到要加入队列中的节点
        cur->next = temp->next;//断开指针，由于保存了，所以不会丢失，
        temp->next = pre->next;//放在队头
        pre->next = temp;//嵌在队头
    }
    return head;
}

如果头结点就是区间的起点

这样写的目的是让cur得到操作区间的前一个位置，但如果一开始就是操作区间，那么就无法通过这种方式得到前一个位置，因为根本就得不到；cur要为区间的第一个元素，pre为区间的前一个元素，

之前不会出问题是因为，样例不用动是因为那个cur正好指向区间的前第一个元素，而如果头结点就是要操作的节点，同样也不会动

        ListNode*res=new ListNode(0);
        res->next=head;
        ListNode*cur=head,*pre=res;
        for(int i=1;i<=m-1;i++){
            pre=cur;
            cur=cur->next;
        }
        for(int i=1;i<=n-m;i++){
            ListNode*temp=cur->next;
            cur->next=temp->next;
            temp->next=pre->next;
            pre->next=temp;
        }
        return res->next;

 每K个一组进行反转（？）

node* rg(node* head, int k) {
    node* tail = head;
    for (int i = 0; i < k; i++) {
        if (!tail)return head;
        tail = tail->next;
    }
    node* pre = nullptr, * cur = head;
    while (cur != tail) {
        node* temp = cur->next;
        cur->next = pre;//反转方向，初始时pre为空，每次只改变一个节点的指针指向
        pre = cur;//向后移动两个指针
        cur = temp;
    }
    head->next = rg(tail, k);
    return pre;
}

合并两个链表 （二路归并）

node* merge(node* p1, node* p2) {
    if (!p1)return p2;
    if (!p2)return p1;
    node* head = new node;
    node* cur = head;
    while (p1 && p2) {
        if (p1->x <= p2->x) {
            cur->next = p1;
            p1 = p1->next;
        }
        else {
            cur->next = p2;
            p2 = p2->next;
        }
        cur = cur->next;
    }
    if (p1)cur->next = p1;
    if (p2)cur->next = p2;
    return head->next;
}

合并多个链表 （多路归并）

node* merge2(node* p1, node* p2) {
    if (!p1)return p2;
    if (!p2)return p1;
    node* head = new node;
    node* cur = head;
    while (p1 && p2) {
        if (p1->x <= p2->x) {
            cur->next = p1;
            p1 = p1->next;
        }
        else {
            cur->next = p2;
            p2 = p2->next;
        }
        cur = cur->next;
    }
    if (p1)cur->next = p1;
    if (p2)cur->next = p2;
    return head->next;
}
node* dm(vector<node*>& lists, int left, int right) {
    if (left > right) {
        return nullptr;
    }
    else if (left == right) {
        return lists[left];
    }
    int mid = (left + right) / 2;
    return merge2(dm(lists, left, mid), dm(lists, mid + 1, right));
}
node* merge(vector<node*>& lists) {
    return dm(lists, 0, lists. Size() - 1);
}