- lc 21~30
- [21. 合并两个有序链表](https://leetcode-cn.com/problems/merge-two-sorted-lists)
- 单链表
- [22. 括号生成](https://leetcode-cn.com/problems/generate-parentheses)
- DFS
- [23. 合并K个升序链表](https://leetcode-cn.com/problems/merge-k-sorted-lists)
- 1.暴力遍历就完事了,584ms，O(n * k),n为总节点数，k为链表个数
- 2.优先队列, O(n * logk)
- [24. 两两交换链表中的节点](https://leetcode-cn.com/problems/swap-nodes-in-pairs)
- 单链表，三点记录更新，迭代
- y总的代码
- [25. K 个一组翻转链表](https://leetcode-cn.com/problems/reverse-nodes-in-k-group)
- 单链表,k反转
- [26. 删除有序数组中的重复](https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array)
- 双指针
- [27. 移除元素](https://leetcode-cn.com/problems/remove-element)
- 双指针，简单
- [28. 实现 strStr()](https://leetcode-cn.com/problems/implement-strstr)
- KMP模板
- [29. 两数相除](https://leetcode-cn.com/problems/divide-two-integers)
- 二进制位
- [30. 串联所有单词的子串](https://leetcode-cn.com/problems/substring-with-concatenation-of-all-words)
- 哈希表 + 滑动窗口
class Solution {
public:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
auto dummy = new ListNode(-1), head = dummy;
while(list1 || list2){
int x = list1 != nullptr? list1->val : INT_MAX;
int y = list2 != nullptr? list2->val : INT_MAX;
if(x <= y)
head = head->next = list1, list1 = list1->next;
else
head = head->next = list2, list2 = list2->next;
//只要有哪个数为INF就说明其中一个链表已经全部加入了
//因此刚才直接连接上剩下的一个链表，就可以结束了
if(x == INT_MAX || y == INT_MAX) break;
}
return dummy->next;
}
};
22. 括号生成 DFS
class Solution {
public:
vector<string> ans;
vector<string> generateParenthesis(int n) {
//首先明确有效括号性质：任意前缀左括号数目大于等于右括号数目
//最终的字符串左括号数等于右括号数都为n
dfs("", 0, 0, n);
return ans;
}
void dfs(string temp, int lc, int rc, int n){
if(lc == n && rc == n){
ans.push_back(temp);
return;
}
if(lc < n) dfs(temp + '(', lc + 1, rc, n);
if(rc < n && lc > rc) dfs(temp + ')', lc, rc + 1, n);
}
};
23. 合并K个升序链表 1.暴力遍历就完事了,584ms，O(n * k),n为总节点数，k为链表个数
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
auto dummy = new ListNode(-1), head = dummy;
int len = lists.size();
while(1){
int minValm = INT_MAX, seq = 0;//记录最小的节点值，序号
for(int i = 0; i < len; i++){
if(lists[i] && lists[i]->val < minValm){
minValm = lists[i]->val;
seq = i;
}
}
//说明所以链表都遍历完了
if(minValm == INT_MAX) break;
head = head->next = lists[seq];
lists[seq] = lists[seq]->next;
}
return dummy->next;
}
};
class Solution {
public:
struct Cmp{
//优先队列与sort排序是相反的
bool operator()(ListNode* x, ListNode* y){
return x->val > y ->val;//升序
}
};
ListNode* mergeKLists(vector<ListNode*>& lists) {
auto dummy = new ListNode(-1), tail = dummy;
//优先队列，底层为堆,会自动将里面的元素按规则排序,这里堆顶永远为最小值
priority_queue<ListNode*, vector<ListNode*>, Cmp> heap;
for(auto node : lists)
if(node) heap.push(node);
while(heap.size()){
auto temp = heap.top();
heap.pop();
tail = tail->next = temp;
if(temp->next) heap.push(temp->next);
}
return dummy->next;
}
};
24. 两两交换链表中的节点 单链表，三点记录更新，迭代
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
//长度0或1直接返回就行
if(!head || !head->next) return head;
auto dummy = new ListNode(-1);//虚拟头节点大法，因为交换后head就不是新的头节点了
dummy->next = head;
auto pre = dummy, cur = head, ne = head->next;
while(cur && ne){
cur->next = ne->next;
ne->next = cur;
pre->next = ne;
pre = cur;
cur = cur->next;
//如果新的cur节点非空，才能更新ne
if(cur) ne = cur->next;
}
return dummy->next;
}
};
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
auto dummy = new ListNode(-1);
dummy->next = head;
for(auto p = dummy; p->next && p->next->next;){
auto a = p->next, b = a->next;
p->next = b;
a->next = b->next;
b->next = a;
p = a;
}
return dummy->next;
}
};
25. K 个一组翻转链表 单链表,k反转
class Solution {
public:
ListNode* reverseKGroup(ListNode* head, int k) {
auto dummy = new ListNode(-1);
dummy->next = head;
for(auto p = dummy;;){
auto pp = p;
//检查p后面是否有k个节点
for(int i = 0; i < k && pp; i++) pp = pp->next;
if(!pp) break;//没有k个
//先将后面的k个节点内部进行指向反转(k-1次)
auto a = p->next, b = a->next;//双指针
for(int j = 0; j < k - 1; j++){
auto c = b->next;
b->next = a;
a = b, b = c;
}
pp = p->next;
pp->next = b;
p->next = a;
p = pp;
}
return dummy->next;
}
};
26. 删除有序数组中的重复 双指针
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int len = nums.size();
int j = 0;
for(int i = 0; i < len; i++){
if(!i || nums[i] != nums[i - 1])
nums[j++] = nums[i];
}
return j;
}
};
27. 移除元素 双指针，简单
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int index = 0, len = nums.size();
for(int i = 0; i < len; i++)
if(nums[i] != val)
nums[index++] = nums[i];
return index;
}
};
28. 实现 strStr() KMP模板
class Solution {
public:
int strStr(string haystack, string needle) {
//如果s的长度小于p,必不可能匹配上(如果没有这个，当needle空时就出错了)
//现在力扣长度都改为1~10^4,这样就不会出现y总做的时候那个情况了
if(haystack.length() < needle.length()) return -1;
int len1 = haystack.length(), len2 = needle.length();
string s = ' ' + haystack, p = ' ' + needle;
vector<int> ne(len2 + 1);//c++普通数组不让用非常数的值创建大小
//求next
next(ne, p);
//匹配,从1开始
for(int i = 1, j = 0; i <= len1; i++){
while(j && s[i] != p[j + 1]) j = ne[j];
if(s[i] == p[j + 1]) j++;
if(j == len2) return i - j;
}
return -1;
}
void next(vector<int>& ne, string p){
int len = p.length() - 1, j = 0;
//从2开始，因为j + 1与 i匹配，所以i从2开始
for(int i = 2; i <= len; i++){
while(j && p[i] != p[j + 1]) j = ne[j];
if(p[i] == p[j + 1]) j++;
ne[i] = j;
}
}
};
29. 两数相除 二进制位
class Solution {
public:
int divide(int dividend, int divisor) {
//二进制位思想,要注意溢出，(-2^31 / -1 = 2^31 溢出)
//将两个数都取下绝对值，并记录商的符号
typedef long long LL;
bool is_minus = false;
if((dividend < 0 && divisor > 0) || (dividend > 0 && divisor < 0))
is_minus = true;
//转LL，防止上面那样溢出
LL a = abs((LL)dividend), b = abs((LL)divisor), res = 0;
vector<LL> exp;
for(LL c = b; c <= a; c += c) exp.push_back(c);
for(int i = exp.size() - 1; i >= 0; i--){
if(a >= exp[i]){
a -= exp[i];
//这里一定要让1是LL,左移31位就会造成溢出int,如 -2147483648 -1
res += 1LL << i;
}
}
if(is_minus) res = -res;
if(res > INT_MAX || res < INT_MIN) return INT_MAX;
return res;
}
};
30. 串联所有单词的子串 哈希表 + 滑动窗口
class Solution {
public:
vector<int> findSubstring(string s, vector<string>& words) {
vector<int> ans;
if(words.empty()) return ans; //不过看数据范围，没有空的，所以不需要
//很难，终于弄懂了，分组一段一段的匹配，哈希表，cnt记录滑动窗口有效的子串个数
int len = s.length(), n = words.size(), w = words[0].length(), cnt = 0;
unordered_map<string, int> tot; //维护一个总的哈希表
for(auto& s : words) tot[s]++;
//将偏移量i从0~w-1分为w组，维护一个滑动窗口,j左边n*w长度才为窗口内容(也就是j不包含)
for(int i = 0; i < w; i++){
cnt = 0;//每走完一层就将cnt清零，麻了找了好久的错
unordered_map<string, int> window;//存放窗口内的子串出现次数
for(int j = i; j + w <= len; j += w){
//左边出窗口一个单词
if(j >= i + n * w){//此时左边才至少有m*w长度
auto word = s.substr(j - n * w, w);
if(tot[word] >= window[word]) cnt--;//说明是有效的子串，出表,cnt--
window[word]--;
}
//右边入窗口一个单词
auto word = s.substr(j, w);
window[word]++;
if(window[word] <= tot[word]) cnt++;//说明是有效子串++
if(cnt == n) ans.push_back(j - (n - 1) * w);
//为什么是n-1,是因为右边窗口已经进入，但j还没更新
}
}
return ans;
}
};
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）