220406-天然货仓

样例3
输入：
2
7
0,-1,0,-1,0,-1,0
输出：
0
样例4
输入：
2
7
0,-1,-1,-1,-1,-1,0
输出：
2

//单调栈，接雨水变形
#include <iostream>
#include <string>
#include <vector>
#include <stack>
using namespace std;

vector<int> my_split(string s, char p)
{
    vector<int> res;
    for(int i = 0; i < s.size(); i ++)
    {
        string t = "";
        while(i < s.size() && s[i] != p)
        {
            t.push_back(s[i]);
            i ++;
        }
        res.push_back(stoi(t));
    }

    return res;
}

int main() {
    int n, m;//n货物长度，m台阶个数
    cin >> n >> m;
    string str;
    cin >> str;
    vector<int> step(m, 0);
    step = my_split(str, ',');

    stack<int> stk;//栈存横坐标
    int res = 0;

    for(int i = 0; i < step.size(); i ++)
    {
        int last = 0;

        while(stk.size() && (step[stk.top()] <= step[i]))
        {
            int pit_w = i - stk.top() - 1;//坑长
            if( pit_w >= n && last < 0) //坑长度大于货物长度
            {
                int pit_h  = min(0, step[stk.top()])- last;//地平面下坑高
                res += (pit_w/n) * pit_h;
            }
            last = step[stk.top()];
            stk.pop();
        }

        if(stk.size())
        {
            int pit_w = i - stk.top() - 1;
            if(pit_w >= n && step[i] < 0)
            {
                int pit_h = min(0, last) - step[i];
                res += (pit_w/n) * pit_h;
            }
        }

        stk.push(i);
    }

    cout << res << endl;

    return 0;
}

和为sum的最长连续子序列

题目描述：
有N个正整数组成的一个序列，给定一个整数sum
求长度最长的的连续子序列使他们的和等于sum
返回次子序列的长度，如果没有满足要求的序列 返回-1
备注：
输入序列仅由数字和英文逗号构成，数字之间采用英文逗号分割
序列长度 1<=N<=200，输入序列不考虑异常情况
由题目保证输入序列满足要求

示例
输入：
1,2,3,4,2
6
输出：
3
解析：1,2,3和4,2两个序列均能满足要求，所以最长的连续序列为1,2,3 因此结果为3
输入：
1,2,3,4,2
20
输出：
-1
解释：没有满足要求的子序列，返回-1

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


int MaxLen(vector<int> &nums, int sum)
{
    int resLen = 0, tmpSum = 0;
    int i = 0, j = 0;//滑动窗口左右边界，左开右闭
    while(i < nums.size())
    {
        if(tmpSum < sum)
            tmpSum += nums[j ++];
        else if(tmpSum > sum)
            tmpSum -= nums[i ++];
        else
        {
            resLen = max(resLen, j - i);
            tmpSum -= nums[i ++];
        }
    }
    if(resLen == 0) return -1;
    return resLen;
}

int main()
{
    vector<int> nums;
    int num, sum;
    while(cin >> num)
    {
        nums.push_back(num);
        if(cin.get() == '\n') break;
    }

    cin >> sum;

    int res = MaxLen(nums, sum);
    cout << res << endl;

    return 0;
}

数组删除重复元素，按频率从高到低排序

乱序数组，删除所有重复元素 使得每个元素只出现一次，
并且按照出现的次数的由高到低进行排序
相同出现次数，按照第一次出现的顺序进行先后排序（要求稳定）

//按照出现的次数由高到低排序，更新nums  1 2 1 2，排序后还是 1 2 1 2
//遍历nums，判断nums[i]是否在哈希表中，如果在，加入结果数组res中，并在哈希表中删除；
//如果不在，不操作。保证删除重复元素
#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;

vector<int> frequencysort(vector<int> &nums)
{
    vector<int> res;
    unordered_map<int, int> n_count;
    for(auto &n : nums) n_count[n] ++;
    sort(nums.begin(), nums.end(), [&](int a, int b)//[&]传引用，可以修改nums的值
         {
             return n_count[a] > n_count[b];
         });
    for(int i = 0; i < nums.size(); i ++)
    {
        if(n_count.count(nums[i]) > 0)
        {
            res.push_back(nums[i]);
            n_count.erase(nums[i]);
        }
    }
    return res;
}

int main()
{
    vector<int> nums;
    int num;
    while(cin >> num)
    {
        nums.push_back(num);
        if(cin.get() == '\n') break;
    }

    vector<int> res = frequencysort(nums);
    for(auto r : res) cout << r << ' ';
    cout << endl;

    return 0;
}

最短路径

有N个网络结点，和M条路径，给一个时延表，表的每个元素为[源节点，目的结点，路径长度]
然后提供一个要求的源节点，和目的结点，求出源节点到目的结点的最短路径

示例
输入：
N个网络结点，M条路径：5 6
[源节点，目的结点，路径长度] :  
1 2 1
2 4 2
1 5 3
5 3 5
2 3 7
3 4 8
求出给定源节点到目的结点的最短路径：5 4
输出：13

//朴素dijkstra求最短路
//有向图
//稠密图，点少边多，n=500,m=1e5
#include <cstring>
#include <iostream>
#include <iostream>

using namespace std;

const int N = 510;
const int M = 2e5 + 10;//无向图等于有向图a->b,b->a
int n, m;
int g[N][M];//稠密图用邻接矩阵存边
int dist[N];//记录每个点到s的最短路径
bool st[N];//存储每个点的最短路是否已经确定

int dijkstra(int s, int d)
{
    memset(dist, 0x3f, sizeof dist);
    dist[s] = 0;

    //循环n次，每次将一个点加入【确定最短路的点的集合】，置st[t]=true
    for(int i = 0; i < n - 1; i ++)
    {
        //在还未确定最短路的点中，寻找距离s最小的点t
        int t = -1;
        for(int j = 1; j <= n; j ++)//遍历节点1~n
        {
            if(!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;
        }

        //用t更新其他点的dist
        for(int j = 1; j <= n; j ++)
        {
            dist[j] = min(dist[j], dist[t] + g[t][j]);
        }

        st[t] = true;
    }

    if(dist[d] == 0x3f3f3f3f) return -1;
    return dist[d];
}

int main()
{
    scanf("%d%d", &n, &m);
    memset(g, 0x3f, sizeof g);//初始化邻接矩阵，0x3f3f3f3f表示极大值
    while(m --)
    {
        int a ,b, c;
        scanf("%d%d%d", &a, &b, &c);
        g[a][b] = min(g[a][b], c);//除去重边,只保留权重最小的边
    }
    int src, dest;
    scanf("%d%d", &src, &dest);

    printf("%d\n", dijkstra(src, dest));

    return 0;
}

//堆优化dijkstra求最短路
//有向图
//稀疏图，点多边少，n=m=1.5*1e5
#include <cstring>
#include <iostream>
#include <iostream>
#include <queue>

using namespace std;
typedef pair<int, int> PII;

const int N = 1.5*1e5;
int n, m;
int h[N], w[N], e[N], ne[N], idx;//稀疏图用邻接表存边
int dist[N];//记录每个点到s的最短路径
bool st[N];//存储每个点的最短路是否已经确定

void add(int a, int b, int c)
{
    //头插法 节点b插入到节点a之后
    //1.节点b的属性，e[idx] = b, w[idx] = c
    //2.ne[idx] = h[a];节点b指向头节点a后面的一个节点h[a]
    //3. 节点a指向b，h[a] = idx, idx ++;
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}

int dijkstra(int s, int d)
{
    memset(dist, 0x3f, sizeof dist);
    dist[s] = 0;

    priority_queue<PII, vector<PII>, greater<PII>>heap;//小根堆
    heap.push({0, s});//pair<当前点到s的最短距离，当前点的编号>,小根堆以first元素排序

    //循环n次，每次将一个点加入【确定最短路的点的集合】，置st[t]=true
    while(heap.size())
    {
        //在还未确定最短路的点中，寻找距离s最小的点t
        auto t = heap.top();
        heap.pop();
        int ver = t.second, distance = t.first;

        if(st[ver]) continue;
        st[ver] = true;

        for(int i = h[ver]; i != -1; i = ne[i])
        {
            int j = e[i];
            if(dist[j] > distance + w[i])
            {
                dist[j] = distance + w[i];
                heap.push({dist[j], j});
                //可能会有重边进堆，若1->2有两条边3和2，若3先进堆，2也会进堆
            }
        }
    }

    if(dist[d] == 0x3f3f3f3f) return -1;
    return dist[d];
}

int main()
{
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);//初始化邻接表的所有头节点为-1
    while(m --)
    {
        int a ,b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }
    int src, dest;
    scanf("%d%d", &src, &dest);

    printf("%d\n", dijkstra(src, dest));

    return 0;
}

最深的重复子树

297. 二叉树的序列化与反序列化-层序遍历

#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>
#include <queue>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

//层序数组构建二叉树
// https://leetcode-cn.com/problems/xu-lie-hua-er-cha-shu-lcof/solution/zha-zha-fa-xian-de-wen-ti-xi-wang-geng-duo-ren-kan/

TreeNode* deserialize(string data)
{
    if(data.size() == 0) return NULL;
    int len = data.size();
    int i  = 0;
    vector<TreeNode*> vec;//存储节点到数组中
    while(i < len)
    {
        string str = "";
        //将当前逗号之间的字符串存入str
        while(i < len && data[i] != ',')
        {
            str.push_back(data[i]);
            i ++;
        }

        if(str == "null")
        {
            TreeNode* temp = NULL;
            vec.push_back(temp);
        }
        else//str为数字字符串
        {
            int temp = stoi(str);
            TreeNode* cur = new TreeNode(temp);
            vec.push_back(cur);
        }
        i ++;
    }

    //层序i从0开始，父节点i,左子节点2i+1，右子节点2i+2
    int j = 1;
    for(int i = 0; j < vec.size(); i ++)
    {
        if(vec[i] == NULL) continue;
        if(j < vec.size()) vec[i] ->left = vec[j++];
        if(j < vec.size()) vec[i] ->right = vec[j++];
    }
    return vec[0];
}

//序列化二叉树 bfs 队列
string serialize(TreeNode* root) {
    string res = "";//存结果字符串
    //构造队列，并插入非空根节点
    queue<TreeNode *> q;
    if (root) q.push(root);
    else return "";
    //队列非空时循环
    while (q.size()) {
        //队列长度
        int len = q.size();
        while (len--) {
            auto cur = q.front();
            q.pop();
            if (cur) res.append(to_string(cur->val));
            else res.append("null");
            res.push_back(',');
            if (cur) {
                q.push(cur->left);
                q.push(cur->right);
            }
        }
    }

    res.pop_back();//删去末尾逗号
    while(!isdigit(res.back())) res.pop_back();//删去末尾的null，isdigit()判断是不是数字
    return res;
}

int main()
{
    //输入string转为树
    string data;
    getline(cin, data);
    TreeNode *t = deserialize(data);
    //层序遍历树转换为string
    string s = serialize(t);
    cout << s;
}

652. 寻找重复的子树

• 用三元组代表子树

  /**
  * Definition for a binary tree node.
  * struct TreeNode {
  *     int val;
  *     TreeNode *left;
  *     TreeNode *right;
  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  * };
  */
  class Solution {
  public:
    unordered_map<string, int> ids;//(三元组, id)
    unordered_map<int, int> hash;//(id, 频数)
    vector<TreeNode*> ans;//存重复子树根节点
    int cnt = 0;//id
  
    int dfs(TreeNode* root)
    {
        if (!root) return 0;
        int left = dfs(root->left);
        int right = dfs(root->right);
        //三元组key表示子树（根节点的值，左子树映射的id，右子树映射的id）
  
        string key = to_string(root->val) + ' ' + to_string(left) + ' ' + to_string(right);
        //如果key没有id，则给key新的id为cnt
        if (ids.count(key) == 0) ids[key] = ++ cnt; 
        int id = ids[key];
        //如果当前id出现了两次，
        if(++ hash[id] == 2) ans.push_back(root);
        return id;
    }
  
    vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
        dfs(root);
        return ans;
    }
  };
  

• 用树的前序遍历代表子树

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    string dfs(TreeNode* root, unordered_map<string, int>& hash, vector<TreeNode*> &ans)
    {
        if(!root) return "";
        string cur = "";//cur存树root的前序遍历
        cur += to_string(root->val) + ",";
        cur += dfs(root->left, hash, ans) + ",";
        cur += dfs(root->right, hash, ans);
        if(++ hash[cur] == 2) ans.push_back(root);
        return cur; 
    }

    vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
        unordered_map<string, int> hash;//string存前序子树，int存出现频率
        vector<TreeNode*> ans;//存重复的子树根节点
        dfs(root, hash, ans);//hash，ans都是全局变量
        return ans;
    }
};

104. 二叉树的最大深度

dfs

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(!root) return 0;
        return max(maxDepth(root->left), maxDepth(root->right)) + 1;
    }
};

不同路径升级版

给一个地图的长宽，给起点和终点的坐标，给障碍物个数和坐标，求最短路径长度和个数
输入：
5 5
0 1
3 3
1
1 2
输出：
5 4

#include <queue>
#include <iostream>
using namespace std;
typedef pair<int, int> PII;

//bfs 第一次到这个点必是最短路径

int main()
{
    int n, m;//行数n,列数m
    cin >> n >> m;
    vector<vector<int>> a(n, vector<int>(m, 0));//初始化n*m数组为0
    int st[2], ed[2];//起点st,终点ed
    cin >> st[0] >> st[1] >> ed[0] >> ed[1];
    int k ,p1, p2;//障碍物个数 k
    while(k --)
    {
        cin >> p1 >> p2;
        a[p1][p2] = 1;
    }

    int cnt = 0, path = 0;//路径长度path, 最短路径个数cnt


    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, -1, 0, 1};//上左下右，逆时针
    queue<PII> q;
    q.push({st[0], st[1]});//起点加入队列

    while(q.size())
    {
        path ++;//路径长度
        bool flag = false;
        int len = q.size();
        while(len --)
        {
            auto cur = q.front();
            q.pop();
            int x = cur.first, y = cur.second;
            for(int j = 0; j < 4; j ++)
            {
                int nx = x + dx[j], ny = y + dy[j];
                if(nx < 0 || ny < 0 || nx >= n || ny >= m || a[nx][ny] == 1)
                    continue;
                if(nx == ed[0] && ny == ed[1])//如果到达终点
                {
                    cnt ++;
                    flag = true;//到达终点置flag为true
                }
                q.push({nx, ny});
            }
        }
        if(flag) break;//到达终点的路径都找到后，结束循环
    }
    cout << path << " "<< cnt << endl;
    return 0;
}

芯片业务

芯片上可以承载A、B两种业务，其中每一个芯片为10G容量，A业务需要2.5G，B业务需要10G，A和B业务不能同时在一块芯片上运行（大概是这个意思）
输入：
芯片个数M
业务个数N
业务种类：A B A【类似】
输出：
最后一个业务所在的芯片数和在该芯片上的顺序号
例如：
输入：
5
6
A B A B A A
输出：
1 4

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int m, n;
    cin >> m;
    cin >> n;
    char x;
    vector<char> work;
    for(int i = 0; i < n; i ++)
    {
        cin >> x;
        work.push_back(x);
    }
    int cnta = 0, ta = 0;//当前A在第cnta块芯片，第ta个A业务
    int cntb = 0;//当前B在第cntb块芯片

    for(int i = 0; i < n; i ++)
    {
        if(work[i] == 'A')
        {
            ta ++;
            if(ta % 4 == 1)
                cnta = max(cnta, cntb) + 1;
        }
        if(work[i] == 'B')
            cntb = max(cnta, cntb) + 1;
    }

    int res, order;//第res块芯片，顺序号为order
    if(cnta > m || cntb > m) res = 0, order = 0;
    else{
        if(work.back() == 'A')
        {
            res = cnta;
            order = ta % 4;
            if(order == 0) order += 4;
        }
        else res = cntb, order = 1;
    }

    cout << res << " " << order << endl;

    return 0;
}

HJ88 扑克牌大小

#include <bits/stdc++.h>
using namespace std;

//计算空格个数，用空格个数+1代替牌数
int CaculateSpace(string s)
{
    int cnt = 1;
    for(int i = 0; i < s.size(); i ++)
    {
        if(s[i] == ' ') cnt ++;
    }
    return cnt;
}

int firstcard(string s)
{
    int res;
    if(s[0] == '3') res = 3;
    else if(s[0] == '4') res = 4;
    else if(s[0] == '5') res = 5;
    else if(s[0] == '6') res = 6;
    else if(s[0] == '7') res = 7;
    else if(s[0] == '8') res = 8;
    else if(s[0] == '9') res = 9;
    else if(s[0] == '1') res = 10;
    else if(s[0] == 'J') res = 11;
    else if(s[0] == 'Q') res = 12;
    else if(s[0] == 'K') res = 13;
    else if(s[0] == 'A') res = 14;
    else if(s[0] == '2') res = 15;
    return res;
}

//0 不能比较,s1,s2长度不同; 1 s1>s2; 2 s2>s1;
int cmp(string& s1, string& s2)
{
    int space1 = CaculateSpace(s1);
    int space2 = CaculateSpace(s2);
    if(s1 == "joker JOKER") return 1;
    if(s2 == "joker JOKER") return 2;
    if(space1 == space2)
    {
        if(s1 == "JOKER") return 1;
        if(s2 == "JOKER") return 2;
        int f1 = firstcard(s1), f2 = firstcard(s2);
        if(f1 > f2) return 1;
        else return 2;
    }
    if(space1 == 4) return 1;//3个空格，4个，s1是炸弹s2不是，s1,s2长度不一样
    if(space2 == 4) return 2;
    return 0;//剩余情况ERROR
}

int main()
{
    string s;
    getline(cin, s);
    auto k = s.find('-');
    auto n = s.size();
    string s1 = s.substr(0, k);
    string s2 = s.substr(k + 1);
    int res = cmp(s1, s2);
    if(res == 0) cout << "ERROR" << endl;
    else if(res == 1) cout << s1 << endl;
    else if(res == 2) cout << s2 << endl;
    return 0;
}

HJ75 公共子串计算

1. 暴力 ```cpp //暴力

   include

   using namespace std;

int main() { string s1, s2; cin >> s1 >> s2; if(s1.size() < s2.size()) swap(s1, s2);//保证s1是长串

//遍历短串的子串长度 从大到小
for(int i = s2.size(); i >= 0; i --)
{
    for(int j = 0; j <= s2.size() - i; j ++)
    {
        string cur = s2.substr(j, i);
        //substr(pos, len),pos的默认值是0，len的默认值是s.size() - pos
        if(s1.find(cur) != s1.npos) 
        {
            cout << i << endl;//npos是last iterator，表示找不到
            return 0;
        }
    }
}
return 0;

}

2. 动态规划

状态表示：<br />集合：f[i][j]，表示以s1[i]、s2[j]为最后一个元素的公共子串长度（s1[i] == s2[j]）<br />属性：max<br />状态计算：<br />初始：字符串索引从1开始，初始化f[0][j] = 0, f[i][0] = 0<br />如果s1[i] == s2[j]，f[i][j] = f[i-1][j-1] + 1;<br />如果s1[i] == s2[j]，f[i][j] = 0;<br />记录最大的f[i][j]
```cpp
//动态规划

#include <bits/stdc++.h>
using namespace std;

int main()
{
    string s1, s2;
    cin >> s1 >> s2;//下标从0开始
    int f[160][160];//因为有i-1,j-1,f下标从1开始
    int res = 0;

    for(int i = 0; i <= s1.size(); i ++) f[i][0] = 0;
    for(int j = 0; j <= s2.size(); j ++) f[0][j] = 0;
    for(int i = 1; i <= s1.size(); i ++)
        for(int j = 1; j <= s2.size(); j ++)
        {
            //s1,s2下标比f下标小1
            if(s1[i - 1] == s2[j - 1]) f[i][j] = f[i-1][j-1] + 1;
            else f[i][j] = 0;
            res = max(res, f[i][j]);
        } 

    cout << res << endl;
    return 0;
}