头像

wzhe




离线:5天前



wzhe
4个月前
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode* cur = new ListNode();
        ListNode* head = cur;

        while(l1 || l2) {
            if (l1 && l2) {
                if (l1->val < l2->val) {
                    cur->next = l1;
                    cur = cur->next;
                    l1 = l1->next;
                }
                else {
                    cur->next = l2;
                    cur = cur->next;
                    l2 = l2->next;
                }
            } else if (l1) {
                cur->next = l1;
                cur = cur->next;
                l1 = l1->next;
            } else if (l2) {
                cur->next = l2;
                cur = cur->next;
                l2 = l2->next;
            }
        }
        return head->next;
    }
};


活动打卡代码 LeetCode 143. Reorder List

wzhe
4个月前
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    void display(ListNode* head) {
        while (head) {
            cout << head->val << " -> ";
            head = head->next;
        }
        cout << endl;
    }
    ListNode* split(ListNode* head) {
        ListNode* fast = head;
        ListNode* pre = nullptr;
        ListNode* slow = head;
        while(fast && fast->next) {
            pre = slow;
            fast = fast->next->next;
            slow = slow->next;
        }
        if (pre != nullptr) pre->next = nullptr;
        return slow;
    }
    ListNode* reverse(ListNode* head) {
        ListNode* pre = nullptr;
        ListNode* cur = head;
        while (cur) {
            ListNode* n = cur->next;
            cur->next = pre;
            pre = cur;
            cur = n;
        }
        return pre;
    }
    ListNode* merge(ListNode* l, ListNode* r) {
        ListNode* head = l;
        while(l != nullptr && r != nullptr) {
            if (l->next == nullptr) {
                l->next = r;
                break;
            }
            ListNode* rn = r->next;
            r->next = l->next;
            l->next = r;
            l = r->next;
            r = rn;
        }
        return head;
    }
    void reorderList(ListNode* head) {
        ListNode* right = split(head);
        //display(head);
        //display(right);
        if (head == right) return;
        right = reverse(right);
        merge(head, right);
       // display(head);
    }
};



wzhe
7个月前
class MinStack {
public:
    /** initialize your data structure here. */
    stack<int> stk;
    stack<int> stk_min;
    MinStack() {

    }

    void push(int x) {
        stk.push(x);
        if (stk_min.empty() || x <= stk_min.top()) {
            stk_min.push(x);
        }
    }

    void pop() {
        int t = stk.top();
        stk.pop();
        if (t == stk_min.top()) stk_min.pop();
    }

    int top() {
        if (stk.size()) return stk.top();
        return -1;
    }

    int getMin() {
        if (stk_min.size()) return stk_min.top();
        return -1;
    }
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(x);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */


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

wzhe
7个月前
#include <bits/stdc++.h>

using namespace std;

class Trie {
public:
    Trie(){
        root_ = new TrieNode();
    }
    ~Trie(){
        root_->clear();
        delete root_;
    }

    int insert(const string& word) {
        if (word.empty()) return 0;
        TrieNode* p = root_;
        for (auto x : word) {
            int index = x - 'a';
            if (index < 0 || index > 25) return 0;
            if (p->pChild[index] == nullptr) p->pChild[index] = new TrieNode;
            p = p->pChild[index];
            p->path++;
        }
        p->path--;
        p->end++;
        return p->end;
    }

    int search(const string& word) {
        if (word.empty()) return 0;
        TrieNode* p = root_;
        for (auto x : word) {
            int index = x - 'a';
            if (0 > index || index > 25) return 0;
            if (p->pChild[index] == nullptr) return 0;
            p = p->pChild[index];
        }
        return p->end;
    }

    int searchPre(const string& word) {
        if (word.empty()) return 0;
        TrieNode* p = root_;
        int cnt = 0;
        for (auto x : word) {
            int index = x - 'a';
            if (0 > index || index > 25) return 0;
            if (p->pChild[index] == nullptr) break;
            p = p->pChild[index];
            cnt += p->end;
        }
        return cnt;
    }
    int startwith(const string& word) {
        if (word.empty()) return 0;
        TrieNode* p = root_;
        for (auto x : word) {
            int index = x - 'a';
            if (0 > index || index > 25) return 0;
            if (p->pChild[index] == nullptr) return 0;
            p = p->pChild[index];
        }
        return p->path;
    }


public:
    struct TrieNode{
        int end;
        int path;
        TrieNode* pChild[26];
        TrieNode():end(0),path(0){
            for (auto &c : pChild) {
                c = nullptr;
            }
        }
        void clear() {
            for (auto &c : pChild) {
                if (c != nullptr) {
                    c->clear();
                    delete c;
                }
            }
        }
    };
private:
   TrieNode* root_;
};


int main()
{
    int n,m;
    cin >> n >> m;
    Trie trie;
    string word;

    for (int i = 0; i < n; i++) {
        cin >> word;
        trie.insert(word);
    }
    string s;
    for (int i = 0; i < m; i++) {
        cin >> s;
        cout << trie.searchPre(s) << endl;
    }
    return 0;

}



wzhe
7个月前
class Solution {
public:
    const int MOD = 1e9 + 7;
    vector<vector<int>> C;
    int numOfWays(vector<int>& nums) {
        int n = nums.size();
        C = vector<vector<int>> (n+1, vector<int>(n+1));
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= i; j++) {
                if (!j) C[i][j] = 1;
                else C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;
            }
        }
        int ans = f(nums);
        ans = (ans + MOD - 1) % MOD;
        return ans;
    }

    int f(vector<int> num) {
        int n = num.size();
        if (n == 0) return 1;
        int k = num[0];
        vector<int> left, right;
        for (int i = 1; i < n; i++) {
            if (num[i] < k) left.push_back(num[i]);
            else if (num[i] > k) right.push_back(num[i] - k);
        }
        return (long long)C[n-1][k-1] * f(left) % MOD * f(right) % MOD;
    }
};



wzhe
7个月前
const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};
class Solution {
public:
    void dfs(vector<vector<int>>& g, int x, int y) {
        for (int i = 0;i < 4; i++) {
            int a = x + dx[i];
            int b = y + dy[i];
            if (a < 0 || a >= g.size() || b < 0 || b >= g[0].size()) continue;
            if (g[a][b] == 1) {
                g[a][b] = 0;
                dfs(g, a, b);
            }
        }
    }
    int numIslands(vector<vector<int>> grid) {
        int n = grid.size();
        if (n == 0) return 0;
        int m = grid[0].size();
        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 1) {
                    ans++;
                    grid[i][j] = 0;
                    dfs(grid, i, j);
                }
            }
        }
        return ans;
    }
    int minDays(vector<vector<int>>& grid) {
        int n = numIslands(grid);
        if (n == 0 || n > 1) return 0;
        for (int i = 0; i < grid.size(); i ++) {
            for (int j = 0; j < grid[0].size(); j ++) {
                if (grid[i][j] == 1) {
                    grid[i][j] = 0;
                    n = numIslands(grid);
                    if (n > 1) return 1;
                    grid[i][j] = 1;
                }
            }
        }
        return 2;
    }
};


活动打卡代码 LeetCode 1563. 石子游戏 V

wzhe
7个月前

#define MAXN 500 + 50

int dp[MAXN][MAXN];

class Solution {
public:
    int dfs(int l, int r, vector<int>& V) {
        if (l == r) return 0;
        if (dp[l][r] != -1) return dp[l][r];

        int sum = 0;
        for (int i = l; i <= r; i++) sum += V[i];
        int cur = 0;
        int ret = 0;
        for (int mid = l; mid <= r; mid++) {
            cur += V[mid];
            int now = 0;
            if (cur < sum - cur) {
                now = cur + dfs(l, mid, V);
            } else if (cur > sum - cur) {
                now = sum - cur + dfs(mid + 1, r, V);
            } else {
                now = cur + max(dfs(l, mid, V), dfs(mid + 1, r, V));
            }
            ret = max(ret, now);
        }
        return dp[l][r] = ret;
    }
    int stoneGameV(vector<int>& V) {
        int n = V.size();
        memset(dp, -1, sizeof(dp));

        return dfs(0, n - 1, V);
    }
};



wzhe
7个月前
class Solution {
public:
    int getMaxLen(vector<int>& nums) {
        int n = nums.size();
        vector<int> f(n + 1), g(n + 1);
        if (nums[0] > 0) f[0] = 1;
        else if (nums[0] < 0) g[0] = 1;
        int res = f[0];
        for (int i = 1; i < n; i++) {
            if (nums[i] > 0) {
                f[i] = f[i - 1] + 1;
                if (g[i - 1]) g[i] = g[i-1] + 1;
            } else if (nums[i] < 0) {
                if (g[i - 1]) f[i] = g[i-1] + 1;
                g[i] = f[i - 1] + 1;
            }
            res = max(res, f[i]);
        }
        return res;
    }
};



wzhe
7个月前
class Solution {
public:
    string arr2str(vector<int>& arr, int l, int r) {
        string s;
        for (int i = l; i < r; i++) {
            s += to_string(arr[i]);
        }
        return s;
    }
    bool containsPattern(vector<int>& arr, int m, int k) {
        int n = arr.size();
        if (m * k > n) return false;

        string all = arr2str(arr, 0, n);
        for (int i = 0; i + m <= n; i++) {
            string s = arr2str(arr, i, i + m);
            int x = k;
            string f;
            while (x) {
                if (x & 1) {
                    f += s;
                }
                s += s;
                x >>= 1;
            }
            if (all.find(f) != -1) return true;
        }

        return false;
    }
};
class Solution {
public:
    bool containsPattern(vector<int>& arr, int m, int k) {
        int n = arr.size();
        for (int i = 0; i + k * m <= n; i++) {
            bool flag = true;
            for (int j = i; j < i + k * m; j++) {
                if (arr[j] != arr[i + (j - i) % m]) {
                    flag = false;
                    break;
                }
            }
            if (flag) return true;
        }
        return false;
    }
};


活动打卡代码 AcWing 3. 完全背包问题

wzhe
7个月前
#include <iostream>

using namespace std;

#define N 1010

int v[N], w[N];

int f[N];

int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];

    for (int i = 1;i <= n; i++ ) {
        for (int j = v[i]; j <= m ; j++) {
            f[j] = max(f[j], f[j-v[i]] + w[i]);
        }
    }
    cout << f[m] << endl;
    return 0;
}