头像

yxc

北京大学




在线 


活动打卡代码 AcWing 142. 前缀统计

yxc
5小时前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1000010;

int n, m;
char str[N];
int son[N][26], cnt[N], idx;

void insert(char *str)  // 插入字符串
{
    int p = 0;
    for (int i = 0; str[i]; i ++ )
    {
        int u = str[i] - 'a';
        if (!son[p][u]) son[p][u] = ++ idx;
        p = son[p][u];
    }
    cnt[p] ++ ;
}

int query(char *str)  // 查询字符串出现次数
{
    int p = 0, res = 0;
    for (int i = 0; str[i]; i ++ )
    {
        int u = str[i] - 'a';
        if (!son[p][u]) return res;
        p = son[p][u];
        res += cnt[p];
    }
    return res;
}

int main()
{
    scanf("%d%d", &n, &m);
    while (n -- )
    {
        scanf("%s", str);
        insert(str);
    }

    while (m -- )
    {
        scanf("%s", str);
        printf("%d\n", query(str));
    }
    return 0;
}



yxc
5小时前
class Trie {
public:
    struct Node {
        Node* son[26];
        bool is_end;

        Node() {
            for (int i = 0; i < 26; i ++ ) son[i] = NULL;
            is_end = false;
        }
    }*root;

    /** Initialize your data structure here. */
    Trie() {
        root = new Node();
    }

    /** Inserts a word into the trie. */
    void insert(string word) {
        auto p = root;
        for (auto c: word) {
            int u = c - 'a';
            if (!p->son[u]) p->son[u] = new Node();
            p = p->son[u];
        }
        p->is_end = true;
    }

    /** Returns if the word is in the trie. */
    bool search(string word) {
        auto p = root;
        for (auto c: word) {
            int u = c - 'a';
            if (!p->son[u]) return false;
            p = p->son[u];
        }
        return p->is_end;
    }

    /** Returns if there is any word in the trie that starts with the given prefix. */
    bool startsWith(string prefix) {
        auto p = root;
        for (auto c: prefix) {
            int u = c - 'a';
            if (!p->son[u]) return false;
            p = p->son[u];
        }
        return true;
    }
};

/**
 * Your Trie object will be instantiated and called as such:
 * Trie* obj = new Trie();
 * obj->insert(word);
 * bool param_2 = obj->search(word);
 * bool param_3 = obj->startsWith(prefix);
 */


活动打卡代码 AcWing 71. 二叉树的深度

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



yxc
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:
    int ans, last;
    bool is_first;

    int minDiffInBST(TreeNode* root) {
        ans = INT_MAX, is_first = true;
        dfs(root);
        return ans;
    }

    void dfs(TreeNode* root) {
        if (!root) return;
        dfs(root->left);
        if (is_first) {
            is_first = false;
            last = root->val;
        } else {
            ans = min(ans, root->val - last);
            last = root->val;
        }
        dfs(root->right);
    }
};


活动打卡代码 AcWing 1453. 移掉K位数字

yxc
2天前
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int main()
{
    string num;
    int k;
    cin >> num >> k;

    string res = "0";
    for (auto c: num)
    {
        while (k && c < res.back())
        {
            res.pop_back();
            k -- ;
        }
        res += c;
    }

    while (k -- ) res.pop_back();
    k = 0;
    while (k + 1 < res.size() && res[k] == '0') k ++ ;
    cout << res.substr(k) << endl;

    return 0;
}


活动打卡代码 AcWing 179. 最大数

yxc
2天前
class Solution {
public:
    string largestNumber(vector<int>& nums) {
        sort(nums.begin(), nums.end(), [](int x, int y) {
            auto a = to_string(x), b = to_string(y);
            return a + b > b + a;
        });
        string res;
        for (auto x: nums) res += to_string(x);
        int k = 0;
        while (k + 1 < res.size() && res[k] == '0') k ++ ;
        return res.substr(k);
    }
};


活动打卡代码 AcWing 782. 变为棋盘

yxc
3天前
class Solution {
public:
    const int INF = 1e8;

    int get_count(int x) {
        int res = 0;
        while (x) res += x & 1, x >>= 1;
        return res;
    }

    int get(int a, int b) {
        if (get_count(a) != get_count(b)) return INF;
        return get_count(a ^ b) / 2;
    }

    int movesToChessboard(vector<vector<int>>& board) {
        set<int> row, col;
        int n = board.size();
        for (int i = 0; i < n; i ++ ) {
            int r = 0, c = 0;
            for (int j = 0; j < n; j ++ ) {
                r = r << 1 | board[i][j];
                c = c << 1 | board[j][i];
            }
            row.insert(r), col.insert(c);
        }
        if (row.size() != 2 || col.size() != 2) return -1;
        int r1 = *row.begin(), r2 = *row.rbegin();
        int c1 = *col.begin(), c2 = *col.rbegin();
        if ((r1 ^ r2) != (1 << n) - 1 || (c1 ^ c2) != (1 << n) - 1) return -1;
        int s1 = 0;
        for (int i = 0; i < n; i += 2) s1 |= 1 << i;
        int s2 = ((1 << n) - 1) ^ s1;
        int r_cost = min(get(r1, s1), get(r1, s2));
        int c_cost = min(get(c1, s1), get(c1, s2));
        int res = r_cost + c_cost;
        if (res >= INF) return -1;
        return res;
    }
};



yxc
3天前
typedef long long LL;

class MKAverage {
public:
    struct Range {
        multiset<int> s;
        LL sum = 0;
        void insert(int x) {
            s.insert(x);
            sum += x;
        }
        void remove(int x) {
            s.erase(s.find(x));
            sum -= x;
        }
    }L, M, R;
    int m, k;
    vector<int> q;

    MKAverage(int _m, int _k) {
        m = _m, k = _k;
    }

    void addElement(int num) {
        q.push_back(num);
        if (q.size() < m) return;
        if (q.size() == m) {
            auto w = q;
            sort(w.begin(), w.end());
            for (int i = 0; i < k; i ++ ) L.insert(w[i]);
            for (int i = k; i < m - k; i ++ ) M.insert(w[i]);
            for (int i = m - k; i < m; i ++ ) R.insert(w[i]);
        } else {
            M.insert(num);
            if (*L.s.rbegin() > *M.s.begin()) {
                int x = *M.s.begin(), y = *L.s.rbegin();
                M.remove(x), L.insert(x);
                L.remove(y), M.insert(y);
            }
            if (*M.s.rbegin() > *R.s.begin()) {
                int x = *M.s.rbegin(), y = *R.s.begin();
                M.remove(x), R.insert(x);
                R.remove(y), M.insert(y);
            }

            num = q[q.size() - 1 - m];
            if (M.s.count(num)) M.remove(num);
            else if (L.s.count(num)) {
                L.remove(num);
                int x = *M.s.begin();
                M.remove(x), L.insert(x);
            } else {
                R.remove(num);
                int x = *M.s.rbegin();
                M.remove(x), R.insert(x);
            }
        }
    }

    int calculateMKAverage() {
        if (q.size() < m) return -1;
        return M.sum / M.s.size();
    }
};

/**
 * Your MKAverage object will be instantiated and called as such:
 * MKAverage* obj = new MKAverage(m, k);
 * obj->addElement(num);
 * int param_2 = obj->calculateMKAverage();
 */



yxc
3天前
const int N = 500010, INF = 1e8;

int f[N][3];

class Solution {
public:
    int minSideJumps(vector<int>& b) {
        f[0][1] = 0, f[0][0] = f[0][2] = 1;

        int n = b.size() - 1;
        for (int i = 1; i <= n; i ++ )
            for (int j = 0; j < 3; j ++ ) {
                f[i][j] = INF;
                if (b[i] == j + 1) continue;
                for (int k = 0; k < 3; k ++ ) {
                    if (b[i] == k + 1) continue;
                    int cost = 0;
                    if (k != j) cost = 1;
                    f[i][j] = min(f[i][j], f[i - 1][k] + cost);
                }
            }
        return min(f[n][0], min(f[n][1], f[n][2]));
    }
};



yxc
3天前
class Solution {
public:
    int f(int n, int k) {
        if (n == 1) return 0;
        return (f(n - 1, k) + k) % n;
    }

    int findTheWinner(int n, int k) {
        return f(n, k) + 1;
    }
};