$\color{Orange}{题目1：最大公共子串长度}$

题目标签

dp，11出过且更难

题目描述

给定两个字符串，求最大公共子串的长度。

输入样例：

输入：fdfdfd42543 232fdfdfdjlkj

输出样例：

输出：6

模板题链接

参考代码

解法1：暴解

#include <iostream>
#include <string>
using namespace std;

int main() {
    string str1, str2;
    cin >> str1 >> str2;
    int max = -1;
    for (int i = 0; i < str1.length(); i++) {
        for (int j = 1; j < str1.length() - i - 1; j++) {
            int pos = str2.find(str1.substr(i, j));
            if ((pos >= 0)&& j > max) {
                max = j;
            }
        }
    }
    cout << max << endl;
    return 0;
}

解法2:动态规划

#include <iostream>
#include <string>
#include <cstdio>
using namespace std;
const int MAXN = 10010;
int dp[MAXN][MAXN];

int main() {
    string str1, str2;
    cin >> str1 >> str2;
    //边界
    for (int i = 0; i < str1.size(); i++){
        dp[i][0] = 0;
    }
    for (int j = 0; j < str2.size(); j++){
        dp[0][j] = 0;
    }
    //状态转移方程
    int max = -1;
    for (int i = 1; i <= str1.size(); i++){
        for (int j = 1; j <= str2.size(); j++){
            if (str1[i - 1] != str2[j - 1]){
                dp[i][j] = 0;
            } else {
                dp[i][j] = dp[i-1][j-1] + 1;
            }
            if (dp[i][j] > max){
                max = dp[i][j];
            }
        }
    }
    cout << max;
    return 0;
}

$\color{Orange}{题目2：后缀序列}$

题目标签

栈

题目描述

给定一个后缀序列，要求求值，只有加减（根据题目描述，自己编的用例）

输入样例：

23+1+

输出样例：

输出：6

原题链接

参考代码

#include <cstdio>
#include <iostream>
#include <string>
#include <stack>
using namespace std;

int main(){
    int temp1, temp2;
    char cur;
    string str;
    getline(cin, str);
    int i = 0;
    stack<int> st;
    while (i < str.size()){
        cur = str[i];
        if (cur >= '0' && cur <= '9') st.push(cur - '0');
        else {
            temp2 = st.top();
            st.pop();
            temp1 = st.top();
            st.pop();
            if (cur == '+') st.push(temp1 + temp2);
            else if (cur == '-') st.push(temp1 - temp2);
        }
        i++;
    }
    cout << st.top();
    return 0;
}

$\color{Orange}{题目3：哈夫曼编码}$

题目标签

树

题目描述

给定一个字符串，求哈夫曼编码的最短长度。

输入描述

输出描述

输入样例：

aaaaabbbbcccdde

输出样例：

33

原题链接

参考代码

#include<cstring>
#include<iostream>
#include<map>
#include<vector>
#include<set>
#include<algorithm>
using namespace std;

typedef struct node{
    int val;
    struct node *parent;
    bool leaf;
}node;


int main(){
    string input;
    cin >> input;
    map<char,int> charnum;
    for(auto x: input){
        if(charnum.find(x) != charnum.end()) charnum[x] += 1;
        else charnum.insert({x,1});
    }

    vector<node *> nodes; 
    for(auto x : charnum)
    {
        node *temp = new node;
        temp->val = x.second;
        temp->leaf = true;
        nodes.push_back(temp);
     } 

     vector<node *> tree;

     while(nodes.size() != 1){
        sort(nodes.begin(),nodes.end(),[](node * a,node *b){return a->val > b->val;});
        node *a = nodes[nodes.size() - 1];
        nodes.pop_back();
        node *b = nodes[nodes.size() - 1];
        nodes.pop_back();
        node *c = new node;
        c-> val = a->val + b->val;
        a->parent = c;
        b->parent = c;
        nodes.push_back(c);
        tree.push_back(a);
        tree.push_back(b);
    }
    int sum = 0;
    for(auto x : tree){
        int count = 0,data = x->val;
        if(x->leaf){
            while(x->parent){
                x = x->parent;
                count++;
            }
        }
        sum += count * data;
    }
    cout << sum;


}