ZhCoding

1.2万

ZhCoding
13天前
class Solution {
public:
vector<int> findSubstring(string s, vector<string>& words) {
if (words.empty()) return {};
vector<int> res;
int n = s.size(), w = words[0].size(), m = words.size();
unordered_map<string, int> tot; // 统计words中每个单词的数量
for (auto word : words) tot[word]++;
for (int i = 0; i < w; ++i) { // 所有单词的长度相同, 所以s有w种切分方式, 每种方式的起点不同
unordered_map<string, int> wd; // 统计s切分后得到单词
int cnt = 0;
for (int j = i; j + w <= n; j += w) {
if (j >= i + w * m) {
// 删除开头的单词
auto word = s.substr(j - w * m, w);
wd[word]--;
if (wd[word] < tot[word]) --cnt;
}
auto word = s.substr(j, w);
wd[word]++;
if (wd[word] <= tot[word]) ++cnt;
if (cnt == m) res.push_back(j - w * (m - 1));
}
}
return res;
}
};


ZhCoding
16天前
class Solution {
public:
int divide(int dividend, int divisor) {
bool isMinus = (dividend > 0) ^ (divisor > 0);
int a = dividend, b = divisor;
// 均转为负数防止溢出
if (dividend > 0) a = -a;
if (divisor > 0) b = -b;
const int halfIntMin = -1073741824;
vector<pair<int, int>> vec;
for (int t1 = b, t2 = -1; t1 >= a; t1 += t1, t2 += t2) {
vec.push_back({t1, t2});
if (t1 < halfIntMin) break;
}
int res = 0;
for (int i = vec.size() - 1; i >= 0; --i) {
if (a <= vec[i].first) {
a -= vec[i].first;
res += vec[i].second;
}
}
if (!isMinus && res == INT_MIN) return INT_MAX;
if (!isMinus) return -res;
return res;
}
};


ZhCoding
17天前
class Solution {
public:
int strStr(string haystack, string needle) {
if (needle.empty()) return 0;
int n = needle.size();
int m = haystack.size();
vector<int> nx(n);
nx[0] = -1;
// 首字母没有前缀, 故从1开始
for (int i = 1, j = -1; i < n; ++i) {
while (j > -1 && needle[i] != needle[j + 1]) j = nx[j];
if (needle[i] == needle[j + 1]) ++j;
nx[i] = j;
}

for (int i = 0, j = -1; i < m; ++i) {
while (j > -1 && haystack[i] != needle[j + 1]) j = nx[j];
if (haystack[i] == needle[j + 1]) ++j;
if (j == n - 1) return i - n + 1;
}
return -1;
}
};


ZhCoding
20天前
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int k = 0;
for (int i = 0; i < nums.size(); ++i) {
if (nums[i] != val) {
nums[k++] = nums[i];
}
}
return k;
}
};


ZhCoding
20天前
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int k = 0;
for (int i = 0; i < nums.size(); ++i) {
if (i > 0 && nums[i] == nums[i - 1]) continue;
nums[k++] = nums[i];
}
return k;
}
};


ZhCoding
21天前
/**
* 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* reverseKGroup(ListNode* head, int k) {
ListNode *dummy = new ListNode(-1);
ListNode *cur = dummy;
while (cur->next) {
ListNode *first = cur->next, *end = cur;
for (int i = 0; end && i < k; ++i) {
end = end->next;
}
if (!end) {
break;
}
ListNode *pr = first, *p = first->next;
while (pr != end) {
ListNode* pn = p->next;
p->next = pr;
pr = p;
p = pn;
}
first->next = p;
cur->next = pr;
cur = first;
}
return dummy->next;
}
};


ZhCoding
23天前
/**
* 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 *dummy = new ListNode(-1), *p = dummy;
while (p->next && p->next->next) {
ListNode *a = p->next, *b = p->next->next;
p->next = b;
a->next = b->next;
b->next = a;
p = a;
}
return dummy->next;
}
};


ZhCoding
24天前
/**
* 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:
struct cmp {
bool operator() (const ListNode *a, ListNode *b) {
return a->val > b->val;
}
};

ListNode* mergeKLists(vector<ListNode*>& lists) {
priority_queue<ListNode*, vector<ListNode*>, cmp> pq;
for (auto l : lists) {
if (l) pq.push(l);
}
ListNode *dummy = new ListNode(-1), *tail = dummy;
while (!pq.empty()) {
ListNode *t = pq.top();
pq.pop();
tail->next = t;
tail = tail->next;
if (t->next) pq.push(t->next);
}
return dummy->next;
}
};


ZhCoding
25天前
class Solution {
public:
void dfs(int u, int n, int countL, string path, vector<string> &res) {
if (u == 2 * n) {
res.push_back(path);
return;
}
if (countL == n) {
dfs(u + 1, n, countL, path + ")", res);
} else if (countL > u - countL) {
dfs(u + 1, n, countL + 1, path + "(", res);
dfs(u + 1, n, countL, path + ")", res);
} else {
dfs(u + 1, n, countL + 1, path + "(", res);
}

}
vector<string> generateParenthesis(int n) {
vector<string> res;
dfs(0, n, 0, "", res);
return res;
}
};


ZhCoding
1个月前
/**
* 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* dummy = new ListNode();
ListNode* p = dummy;
while (l1 && l2) {
if (l1->val < l2->val) {
p->next = l1;
l1 = l1->next;
} else {
p->next = l2;
l2 = l2->next;
}
p = p->next;
}
if (l1) p->next = l1;
if (l2) p->next = l2;
return dummy->next;
}
};