头像

ChaseAug_0




离线:3小时前



ChaseAug_0
17小时前
class Trie {
public:
static const int N = 1e5 + 10;
int son[N][26],cnt[N],idx;
    /** Initialize your data structure here. */
    Trie() {
        memset(son,0,sizeof son);
        memset(cnt,0,sizeof cnt);
        idx = 0;
    }

    /** Inserts a word into the trie. */
    void insert(string word) {
        int p = 0;
        for(auto x : word)
        {
            int& s = son[p][x - 'a'];
            if(!s) s = ++ idx;
            p = s;
        }
        cnt[p] = 1;
    }

    /** Returns if the word is in the trie. */
    bool search(string word) {
        int p = 0;
        for(auto x : word)
        {
            int& s = son[p][x - 'a'];
            if(!s) return false;
            p = s; 
        }
        return cnt[p] >= 1;
    }

    /** Returns if there is any word in the trie that starts with the given prefix. */
    bool startsWith(string prefix) {
        int p = 0;
        for(auto x : prefix)
        {
            int& s = son[p][x - 'a'];
            if(!s) return false;
            p = s;
        }
        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 142. 前缀统计

#include<iostream>
using namespace std;

const int N = 1e6 + 10,M = 5e5 + 10;
int son[M][26],cnt[N],idx;
char str[N];
void insert()
{
    int p = 0;
    for(int i = 0;i < str[i];i ++)
    {
        int &s = son[p][str[i] - 'a'];
        if(!s) s = ++ idx;
        p = s;
    }
    cnt[p] ++;
}
int query()
{
    int p = 0,res = 0;
    for(int i = 0;str[i];i ++)
    {
        int &s = son[p][str[i] - 'a'];
        if(!s) break;
        p = s;
        res += cnt[p];
    }
    return res;
}
int main()
{
    int n,m;
    cin >> n >> m;
    while(n --)
    {
        cin >> str;
        insert();
    }
    while(m --)
    {
        cin >> str;
        cout << query() << endl;        
    }

    return 0;
}


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

#include<iostream>
using namespace std;

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

    string s = "0";
    for(auto c : n)
    {
        while(k && s.back() > c)
        {
            s.pop_back();
            k --;
        }
        s += c;
    }
    while(k --) s.pop_back();
    k = 0;
    while(k + 1 < s.size() && s[k] == '0') k ++;

    cout << s.substr(k) << endl;
    return 0;
}



/**
 * 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:
    void dfs(TreeNode* root,int& ans,int& pre)
    {
        if(root == nullptr) return ;

        dfs(root->left,ans,pre);
        if(pre == -1)
        {
            pre = root->val;
        }else {
            ans = min(ans,root->val - pre);
            pre = root->val;
        }
        dfs(root->right,ans,pre);
    }
    int minDiffInBST(TreeNode* root) {
        int ans = 0x3f3f3f3f,pre = -1;
        dfs(root,ans,pre);
        return ans;
    }
};


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

/**
 * 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;
    }
};


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

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;
        });
        int k = 0;
        string res;
        for(auto x : nums) res += to_string(x);

        while(k + 1 < res.size() && res[k] == '0') k ++;

        return res.substr(k);
    }
};



约瑟夫环是一个经典的数学问题,我们不难发现这样的依次报数,似乎有规律可循
问题: N个人编号为1,2,……,N,依次报数,每报到M时,杀掉那个人,求最后胜利者的编号。

递推公式:

F(N,M) = (F(N − 1,M) + M ) % N
F(N,M)表示: N个人报数,每报到M时被杀,最终幸存者的编号

问题1:

leetcode-5275题
https://leetcode-cn.com/problems/find-the-winner-of-the-circular-game/

int findTheWinner(int n, int k) {
        //f[0] = 1;
        // f[N,K] = (f[N-1,K] + K) % N;
        int x = 0;
        for(int i = 1;i <= n;i ++)
            x = (x + k) % i;

        return x + 1;
}

问题2:

Acwing - 1455招聘
https://www.acwing.com/problem/content/description/1457/

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

void solve()
{
    int n,m;
    cin >> n >> m;

    vector<int> cnt(m);
    for(int i = 0; i < m; i ++)
    {
        int x;
        cin >> x;
        cnt[i] = x;
    }

    int x = 0;
    for(int i = 2; i <= n; i ++)
    {
        x = (x + cnt[(n - i) % m]) % i;
    }
    cout << x << endl;
    return ;
}
int main()
{
    int t = 1;
    cin >> t;
    while(t --)
    {
        solve();
    }
    return 0;
}


活动打卡代码 AcWing 62. 丑数

class Solution {
public:
    int getUglyNumber(int n) {
        if(n == 1) return 1;
        vector<int> res(1,1);
        int i = 0,j = 0,k = 0;
        while(-- n)
        {
            int t = min(res[i]*2,min(res[j]*3,res[k] * 5));
            res.push_back(t);
            if(res[i] * 2 == t) i ++;
            if(res[j] * 3 == t) j ++;
            if(res[k] * 5 == t) k ++;
        }
        return res.back();
    }
};


活动打卡代码 LeetCode 263. 丑数

class Solution {
public:
    bool isUgly(int n) {
        if(n <= 0) return false;
        int res[3] = {2,3,5};
        for(auto x : res)
        {
            while(n % x == 0)
                n /= x;
        }
        return n == 1;
    }
};



class Solution {
public:
    int findMin(vector<int>& nums) {
        int l = 0,r = nums.size() - 1;
        while(r > 0 && nums[r] == nums[r - 1]) r --;
        if(r == 0) return nums[0];
        while(l < r)
        {
            int mid = l + r >> 1;
            if(nums[mid] < nums[0]) r = mid;
            else l = mid + 1;
        }
        if(nums[l] > nums[0]) return nums[0];
        return nums[l];
    }
};