头像

sy123




离线:21小时前


活动打卡代码 AcWing 1631. 后序遍历

sy123
1天前
#include <iostream>
#include <unordered_map>

using namespace std;

const int N = 50010;

int n;
int pre[N], in[N];
unordered_map<int, int> pos;
int post;

void build(int il, int ir, int pl, int pr)
{
    int root = pre[pl];
    int k = pos[root];

    if (il < k) build(il, k - 1, pl + 1, pl + 1 + k - 1 - il);
    if (ir > k) build(k + 1, ir, pl + 1 + k - 1 - il + 1, pr);

    if (!post) post = root;
}

int main()
{
    cin >> n;

    for (int i = 0; i < n; i ++ ) cin >> pre[i];
    for (int i = 0; i < n; i ++ )
    {
        cin >> in[i];
        pos[in[i]] = i;
    }

    build(0, n - 1, 0, n - 1);

    cout << post << endl;
    return 0;
}


活动打卡代码 AcWing 1497. 树的遍历

sy123
1天前
#include<iostream>
#include<algorithm>
#include<unordered_map>
#include<vector>
#include<queue>
using namespace std;

const int N=30+10;

//记录中序遍历的点
vector<int>inorder(N,0);    
//记录后序遍历的点
vector<int>postorder(N,0);  
//记录中序遍历序列每个点的相应位置 第一维表示值 第二维其在中序序列中的具体位置
unordered_map<int,int>pos;
//记录原本的树的信息 第一维为表示树结点的值 第二维表示树节点指向的节点
unordered_map<int,int>l,r;  


//返回值为当前所在节点区间的根
int build(int il,int ir,int pl,int pr){
    int root=postorder[pr];
    int k=pos[root];


    //存在左子树
    if(il<k)
        l[root]=build(il,k-1,pl,pl+(k-1)-il);
    //存在右子树
    if(ir>k)
        r[root]=build(k+1,ir,pl+(k-1-il)+1,pr-1);

    /**
    * 关于递归的区间划分问题
    * 很显然递归的目的是进入左右然后再次寻找根
    * 所以对于中序遍历很简单结合数轴就可以理解
    * 因为k为根节点的位置 所以k左右两边左右子树即对应(il,k-1)(k+1,ir)
    * 而对于后序遍历则稍微要绕一下
    * 由于后序遍历区间的节点数与中序遍历是相等的(这是因为每次划分都是以后序树确定的根为依据)
    * 所以每次划分后 后序树的左右树也会有与中序树相对应的区间范围
    * 即(pl,pl+(k-1)-il)(pl+(k-1-il)+1,pr-1)
    */
    return root;
}

void bfs(int root){
    queue<int>q;
    q.push(root);
    cout<<root;
    while(q.size()){
        int t = q.front();
        if(t!=root)
        cout<<' '<<t;
        q.pop();
        if(l.count(t))
            q.push(l[t]);
        if(r.count(t))
            q.push(r[t]);
    }
}


int main(){
    int n;

    cin>>n;

    for(int i=0;i<n;i++)
        cin>>postorder[i];

    for(int i=0;i<n;i++){
        cin>>inorder[i];
        pos[inorder[i]]=i;
    }

    int root=build(0,n-1,0,n-1);

    bfs(root);

    return 0;
}




sy123
1天前
class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        string res;
        if (strs.empty()) return res;

        for (int i = 0;; i ++ ) {
            if (i >= strs[0].size()) return res;
            char c = strs[0][i];
            int flag=1;
            for (auto& str: strs){
                if (i< str.size()&&str[i] == c)
                    flag=1;
                    else{
                    flag=0;
                    break;
                    }
            }
            if(flag==0)return res;
            else res+=c;
        }

        return res;
    }
};


活动打卡代码 LeetCode 14. 最长公共前缀

sy123
1天前
class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        string res;
        if (strs.empty()) return res;

        for (int i = 0;; i ++ ) {
            if (i >= strs[0].size()) return res;
            char c = strs[0][i];
            int flag=1;
            for (auto& str: strs){
                if (i< str.size()&&str[i] == c)
                    flag=1;
                    else{
                    flag=0;
                    break;
                    }
            }
            if(flag==0)return res;
            else res+=c;
        }

        return res;
    }
};




sy123
1天前
class Solution {
public:
    int romanToInt(string s) {
        unordered_map<char, int> hash;
        hash['I'] = 1, hash['V'] = 5;
        hash['X'] = 10, hash['L'] = 50;
        hash['C'] = 100, hash['D'] = 500;
        hash['M'] = 1000;

        int res = 0;
        for (int i = 0; i < s.size(); i ++ ) {
            if (i + 1 < s.size() && hash[s[i]] < hash[s[i + 1]])
                res -= hash[s[i]];
            else
                res += hash[s[i]];
        }

        return res;
    }
};





sy123
1天前
class Solution {
public:
    string intToRoman(int num) {
        int values[] = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        string reps[] = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};

        string res;
        for (int i = 0; i < 13; i ++ )
            while(num >= values[i])
            {
                num -= values[i];
                res += reps[i];
            }
        return res;
    }
};





sy123
2天前
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

int n, m;
vector<int>v[110];
int cnt[110], max_depth;//记录每层叶子结点个数和最大深度
int high[110];//记录每个节点的深度
void bfs(int u)
{
    queue<int>q;
    q.push(u);
    high[u]=0;
    while(q.size()){
        int top=q.front();
        q.pop();
        if (v[top].size() == 0)  // 说明u是叶子节点
        {
        cnt[high[top]] ++ ;
        continue;
      }
    for (int i = 0; i<v[top].size(); i++){
        int e=v[top][i];
        high[e]=high[top]+1;
        max_depth = max(max_depth,high[e]);
        q.push(e);
      }
   }
}


int main()
{
    cin >> n >> m;
    for (int i = 0; i < m; i ++ )
    {
        int id, k;
        cin >> id >> k;
        while (k -- )
        {
            int son;
            cin >> son;
            v[id].push_back(son);
        }
    }

    bfs(1);
    cout << cnt[0];
    for (int i = 1; i <= max_depth; i ++ ) cout << ' ' << cnt[i];
    cout << endl;

    return 0;
}


活动打卡代码 AcWing 1476. 数叶子结点

sy123
2天前
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

int n, m;
vector<int>v[110];
int cnt[110], max_depth;//记录每层叶子结点个数和最大深度
int high[110];//记录每个节点的深度
void bfs(int u)
{
    queue<int>q;
    q.push(u);
    high[u]=0;
    while(q.size()){
        int top=q.front();
        q.pop();
        if (v[top].size() == 0)  // 说明u是叶子节点
        {
        cnt[high[top]] ++ ;
        continue;
      }
    for (int i = 0; i<v[top].size(); i++){
        int e=v[top][i];
        high[e]=high[top]+1;
        max_depth = max(max_depth,high[e]);
        q.push(e);
      }
   }
}


int main()
{
    cin >> n >> m;
    for (int i = 0; i < m; i ++ )
    {
        int id, k;
        cin >> id >> k;
        while (k -- )
        {
            int son;
            cin >> son;
            v[id].push_back(son);
        }
    }

    bfs(1);
    cout << cnt[0];
    for (int i = 1; i <= max_depth; i ++ ) cout << ' ' << cnt[i];
    cout << endl;

    return 0;
}



活动打卡代码 AcWing 836. 合并集合

sy123
2天前
#include <iostream>

using namespace std;

const int N = 100010;

int n, m;
int p[N];

int find(int x) // 返回x的祖宗节点 + 路径压缩
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main()
{
    scanf("%d%d", &n, &m);

    for (int i = 1; i <= n; i ++ ) p[i] = i;

    while (m -- )
    {
        char op[2];
        int a, b;
        scanf("%s%d%d", op, &a, &b);

        if (op[0] == 'M') p[find(a)] = find(b);
        else
        {
            if (find(a) == find(b)) puts("Yes");
            else puts("No");
        }
    }

    return 0;
}



活动打卡代码 AcWing 826. 单链表

sy123
2天前
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

int head, e[N], ne[N], idx;

void init()
{
    head = -1;
}

void add_head(int x)
{
    e[idx] = x, ne[idx] = head, head = idx ++ ;
}

void add_k(int k, int x)
{
    e[idx] = x, ne[idx] = ne[k], ne[k] = idx ++ ;
}

void remove(int k)
{
    ne[k] = ne[ne[k]];
}

int main()
{
    init();

    int m;
    cin >> m;
    while (m -- )
    {
        char op;
        int k, x;
        cin >> op;
        if (op == 'H')
        {
            cin >> x;
            add_head(x);
        }
        else if (op == 'I')
        {
            cin >> k >> x;
            add_k(k - 1, x);
        }
        else
        {
            cin >> k;
            if (!k) head = ne[head];
            else remove(k - 1);
        }
    }

    for (int i = head; i != -1; i = ne[i]) cout << e[i] << ' ';
    cout << endl;

    return 0;
}