头像

Ninja@珏




离线:1天前


最近来访(18)
用户头像
RyanMoriarty
用户头像
龚子昂
用户头像
Loki
用户头像
RE_MAKE
用户头像
wehiders
用户头像
JasonQ1an
用户头像
lu_ren
用户头像
想胖成肥牛
用户头像
空号AcWing
用户头像
pjc1234567
用户头像
BlackAtao
用户头像
卡塔利亚的骑士
用户头像
大家好今天是
用户头像
whelve
用户头像
神秘人3hd
用户头像
Eartha
用户头像
thunderclouds
用户头像
acWing_lbwnb


生成二叉树的题目还是有点思考量的,所以在这里存个档

1. 前序遍历+中序遍历。生成二叉树

leetcode版本1

/**
 * 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<int, int> pos;
    vector<int> preorder, inorder;
    TreeNode* buildTree(vector<int>& preorder_, vector<int>& inorder_) {
        preorder = preorder_;
        inorder = inorder_;
        int n = inorder_.size();
        for (int i = 0; i < n; i ++ ) pos[inorder_[i]] = i;

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

    TreeNode* build(int il, int ir, int pl, int pr) {
        TreeNode* root = new TreeNode(preorder[pl]);

        int k = pos[root->val];

        // x - (pl + 1) = k - 1 - il;
        if (il < k) root->left = build(il, k - 1, pl + 1, pl + 1 + k - 1 - il);
        if (k < ir) root->right = build(k + 1, ir, pl + 1 + k - 1 - il + 1, pr);
        return root;
    }
};

leetcode 版本2, 这种方法好像更快

/**
 * 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<int, int> pos;
    vector<int> preorder, inorder;
    TreeNode* buildTree(vector<int>& preorder_, vector<int>& inorder_) {
        preorder = preorder_;
        inorder = inorder_;
        int n = inorder_.size();
        for (int i = 0; i < n; i ++ ) pos[inorder_[i]] = i;

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

    TreeNode* build(int il, int ir, int pl, int pr) {
        if (pl > pr) return nullptr;

        TreeNode* root = new TreeNode(preorder[pl]);

        int k = pos[root->val];

        // x - (pl + 1) = k - 1 - il;
        root->left = build(il, k - 1, pl + 1, pl + 1 + k - 1 - il);
        root->right = build(k + 1, ir, pl + 1 + k - 1 - il + 1, pr);
        return root;
    }
};

acwing 版本

2. 后序遍历+中序遍历。生成二叉树

leetcode版本

/**
 * 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<int, int> pos;
    vector<int> inorder, postorder;

    TreeNode* buildTree(vector<int>& inorder_, vector<int>& postorder_) {
        inorder = inorder_;
        postorder = postorder_;
        for (int i = 0; i < inorder.size(); i ++ ) pos[inorder[i]] = i;

        return build(0, inorder.size() - 1, 0, inorder.size() - 1);
    }

    TreeNode* build(int il, int ir, int pl, int pr) {
        if (pl > pr) return nullptr;

        TreeNode* root = new TreeNode(postorder[pr]);
        int k = pos[root->val];
        // x - pl = k - 1 - il
        root->left = build(il, k - 1, pl, pl + k - 1 - il);
        root->right = build(k + 1, ir, pl + k - 1 - il + 1, pr - 1);
        return root;
    }
};

acwing 版本



活动打卡代码 AcWing 2019. 拖拉机

#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>

using namespace std;

const int N = 1010;

bool g[N][N], st[N][N];
int dist[N][N];

#define x first
#define y second


using PII = pair<int, int>;


int bfs(int sx, int sy)
{
    memset(dist, 0x3f, sizeof dist);
    dist[sx][sy] = 0;
    deque<PII> q;
    q.push_back({sx, sy});

    while (q.size()) 
    {
        auto t = q.front();
        q.pop_front();

        if (st[t.x][t.y]) continue;
        st[t.x][t.y] = true;
        if (!t.x && !t.y) break;
        int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

        for (int i = 0; i < 4; i ++ )
        {
            auto x = t.x + dx[i], y = t.y + dy[i];
            if (x >= 0 && x < N && y >= 0 && y < N)
            {

            }
            else continue;

            int w = 0;
            if (g[x][y]) w = 1;
            if (dist[x][y] > dist[t.x][t.y] + w)
            {
                dist[x][y] = dist[t.x][t.y] + w;
                if (!w) q.push_front({x, y});
                else q.push_back({x, y});
            }
        }
    }
    return dist[0][0];
}


int main()
{
    int n, x, y;
    cin >> n >> x >> y;
    for (int i = 0; i < n; i ++ ) 
    {
        int a, b;
        cin >> a >> b;
        g[a][b] = true;
    }

    cout << bfs(x, y) << endl;
    return 0;
}


活动打卡代码 AcWing 2060. 奶牛选美

#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
using namespace std;

const int N =55;

char g[N][N];
int n, m;
#define x first
#define y second
using PII = pair<int, int>;
bool st[N][N];
int dist[N][N];



int bfs(int a, int b)
{
    memset(dist, 0x3f, sizeof dist);
    deque<PII> q;
    q.push_front({a, b});
    dist[a][b] = 0;

    int res = 1e9;

    while (q.size())
    {
        auto t = q.front();
        q.pop_front();
        st[t.x][t.y] = true;

        int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

        for (int i = 0; i < 4; i ++ )
        {
            int x = t.x + dx[i], y = t.y + dy[i];
            if (x < 0 || x >= n || y < 0 || y >= m) continue;
            if (st[x][y]) continue;
            st[x][y] = true;

            int w = 1;
            if (g[x][y] == 'X') w = 0;

            if (dist[x][y] > dist[t.x][t.y] + w)
            {
                dist[x][y] = dist[t.x][t.y] + w;

                if (!w) 
                {
                    q.push_front({x, y});
                    if (dist[x][y] > 0)
                    {
                        res = min(res, dist[x][y]);
                        //cout << dist[x][y] << endl;
                    }
                }
                else 
                {
                    q.push_back({x, y});
                }
            }

        }
    }
    return res;
}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i ++ ) cin >> g[i];

    int x, y;
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < m; j ++ )
        {
            if (g[i][j] == 'X')
            {
                cout << bfs(i, j) << endl;
                return 0;
            }
        }
    return 0;
}


活动打卡代码 AcWing 2041. 干草堆

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1000010;

int a[N];
int b[N];

int main()
{
    int n, k;
    cin >> n >> k;
    for (int i = 0; i < k; i ++ ) 
    {
        int l, r;
        cin >> l >> r;
        a[l]++;
        a[r + 1]--;
    }
    for (int i = 1; i <= n; i ++) 
        a[i + 1] += a[i];
    sort(a + 1, a + n + 1);
    int m = n / 2 + 1;
    cout << a[m] << endl;
    return 0;
}


活动打卡代码 AcWing 2058. 笨拙的手指

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_set>


using namespace std;
const int N = 100010;

int two10(string x) {
    int res = 0;
    reverse(x.begin(), x.end());
    for (int i = 0; i < x.size(); i ++)
    {
        if (x[i] == '1')
            res |=  1 << i;
    }
    return res;
}

int base(string x) {
    int res = 0;
    int p = 1;
    reverse(x.begin(), x.end());

    for (int i = 0; i < x.size(); i ++ ) 
    {
        res += (x[i] - '0') * p;
        p *= 3;
    }
    return res;
}

int main()
{
    string a, b;
    cin >> a >> b;
    unordered_set<int> st;
    //cout << two10(a) << endl;
   // cout << base(b) << endl;

    for (int i = 0; i < a.size(); i ++ ) {
        string x = a;
        if (x[i] == '0') x[i] = '1';
        else x[i] = '0';
        st.insert(two10(x));
    }

    for (int i = 0; i < b.size(); i ++ ) {
        string x = b;
        if (x[i] == '0') {
            x[i] = '1';
            if (st.count(base(x))) {
                cout << base(x) << endl;
                return 0;
            }
            x[i] = '2';
            if (st.count(base(x))) {
                cout << base(x) << endl;
                return  0;
            }
        }
        else if (x[i] == '1') {
            x[i] = '0';
            if (st.count(base(x))) {
                cout << base(x) << endl;
                return 0;
            }
            x[i] = '2';
            if (st.count(base(x))) {
                cout << base(x) << endl;
                return 0;
            }
        }
        else if (x[i] == '2') {
            x[i] = '1';
            if (st.count(base(x))) {
                cout << base(x) << endl;
                return 0;
            }
            x[i] = '0';
            if (st.count(base(x))) {
                cout << base(x) << endl;
                return 0;
            }
        }
    }

    return 0;
}



Ninja@珏
10天前
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;

const int mod = 200907;

int qmi(int a, int k, int p)  // 求a^k mod p
{
    int res = 1 % p;
    while (k)
    {
        if (k & 1) res = (LL)res * a % p;
        a = (LL)a * a % p;
        k >>= 1;
    }
    return res;
}

int main()
{
    int n;
    cin >> n;
    while (n -- )
    {
        int a, b, c, k;
        cin >> a >> b >> c >> k;
        if (a + c == 2 * b)
        {
            cout << (a + (b - a ) * (LL)(k - 1)) % mod << endl;
        }
        else
        {
            cout << ((LL)a * qmi(b/a, k - 1, mod)) % mod << endl;
        }
    }
    return 0;
}


活动打卡代码 AcWing 197. 阶乘分解

Ninja@珏
10天前
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1000010;

int primes[N], cnt;
bool st[N];

void init(int n)
{
    for (int i = 2; i <= n; i ++)
    {
        if (!st[i]) primes[cnt++] = i;
        for (int j = 0; primes[j] * i <= n; j ++)
        {
            st[i * primes[j]] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

int main()
{
    int n;
    cin >> n;
    init(n);
    for (int i = 0; i < cnt; i ++ )
    {
        int p = primes[i];
        int s = 0;
        for (int j = n; j ; j /= p) s += j / p;
        printf("%d %d\n", p, s);
    }
    return 0;
}


活动打卡代码 AcWing 1142. 繁忙的都市

Ninja@珏
1个月前
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 310, M = 10010;
int n, m;
struct Edge
{
    int a, b , w;
    bool operator<(const Edge& t) const 
    {
        return w < t.w;
    }
}e[M];

int p[N];

int find(int x)  // 并查集
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) p[i] = i;
    for (int i = 0; i < m; i ++ )
    {
        cin >> e[i].a >> e[i].b >> e[i].w;
    }
    sort(e, e + m);
    int res = 0;
    for (int i = 0; i < m; i ++ )
    {
        int a = find(e[i].a), b = find(e[i].b);
        if (a == b) continue;
        p[a] = b;
        res = e[i].w;
    }
    cout << n - 1 << ' ' << res << endl;
    return 0;
}


活动打卡代码 AcWing 1141. 局域网

Ninja@珏
1个月前
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110, M = 210;
int n, k;
int p[N];

int find(int x)
{
    if (x != p[x]) p[x] = find(p[x]);
    return p[x];
}

struct Edge
{
    int a, b, w;
    bool operator<(const Edge& e) const 
    {
        return w < e.w;
    }
}E[M];

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

    int res = 0;
    for (int i = 1; i <= k; i ++ )
    {
        int a = E[i].a, b = E[i].b, w = E[i].w;
        if (find(a) == find(b)) continue;

        p[find(a)] = find(b);
        res += w;   
    }
    return res;
}

int main()
{
    cin >> n >> k;
    int tot = 0;


    for (int i = 1; i <= k; i ++ )
    {
        cin >> E[i].a >> E[i].b >> E[i].w;
        tot += E[i].w;
    }
    sort(E + 1, E + k + 1);

    cout << tot - kruskal() << endl;
    return 0;
}


活动打卡代码 AcWing 1140. 最短网络

Ninja@珏
1个月前
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110;

int g[N][N];
int n;
bool st[N];
int dist[N];
int res ;

int prim()
{
    memset(dist, 0x3f, sizeof dist);
    memset(st, 0, sizeof st);
    dist[1] = 0;

    for (int i = 0; i < n; i ++ )
    {
        int t = -1;
        for (int j = 1; j <= n; j ++ )
            if (!st[j] && (t == -1 ||  dist[t] > dist[j]))
                t = j;

        st[t] = true;
        //printf("t=%d dist =%d\n", t, dist[t]);

        res += dist[t];
        for (int j = 1; j <= n; j ++ )
            dist[j] = min(dist[j], g[t][j]);
    }
    return res;
}

int main()
{
    cin >> n;

    for (int i = 1 ;i <= n; i ++ )
        for (int j = 1; j <= n; j ++)
        {
            cin >> g[i][j];
        }

    memset(st, 0, sizeof st);

    cout << prim() << endl;

    return 0;
}