wzhe

3580

wzhe
4个月前
/**
* 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();

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


wzhe
4个月前
/**
* 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:
cout << head->val << " -> ";
}
cout << endl;
}
ListNode* pre = nullptr;
while(fast && fast->next) {
pre = slow;
fast = fast->next->next;
slow = slow->next;
}
if (pre != nullptr) pre->next = nullptr;
return slow;
}
ListNode* pre = nullptr;
while (cur) {
ListNode* n = cur->next;
cur->next = pre;
pre = cur;
cur = n;
}
return pre;
}
ListNode* merge(ListNode* l, ListNode* r) {
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;
}
}
//display(right);
right = reverse(right);
}
};


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();
*/


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


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


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