LeetCode 21. 合并两个有序链表
题目类型
- 链表
- 升序序列的合并问题
题目链接
思路
- 遍历两个链表，每次选择最小的数添加到新链表的尾部即可
- 最后两个链表可能存在一个还有未插入序列，将该序列插入即可，这里有两种写法，一种是我自己写的不够精简，y总的写法比较精简（有时候看y总代码真是有种看艺术品感觉）
while (l1) cur->next = l1, l1 = l1->next, cur = cur->next;
while (l2) cur->next = l2, l2 = l2->next, cur = cur->next;
cur->next = (l1 == NULL ? l2 : l1);
AC代码
/**
* 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* dummy = new ListNode(-1);
ListNode* cur = dummy;
while (l1 && l2)
{
if (l1->val < l2->val)
{
cur->next = l1;
l1 = l1->next;
}
else
{
cur->next = l2;
l2 = l2->next;
}
cur = cur->next;
}
// while (l1) cur->next = l1, l1 = l1->next, cur = cur->next;
// while (l2) cur->next = l2, l2 = l2->next, cur = cur->next;
cur->next = (l1 == NULL ? l2 : l1);
return dummy->next;
}
};
LeetCode 22. 括号生成
题目类型
- dfs
- 括号匹配问题
题目链接
思路
AC代码
class Solution {
public:
vector<string> ans;
vector<string> generateParenthesis(int n) {
dfs(0, 0, "", n);
return ans;
}
// 满足lc < n 可以添加左括号
// 满足rc < n && rc < lc 可以添加右括号
void dfs(int lc, int rc, string seq, int n)
{
if (lc == n && rc == n)
{
ans.push_back(seq);
}
else
{
if (lc < n) dfs(lc + 1, rc, seq + '(', n);
if (rc < n && rc < lc) dfs(lc, rc + 1, seq + ')', n);
}
}
};
LeetCode 23. 合并K个排序链表
题目类型
- 链表
- 小根堆
- k路合并问题
虽然题目类型是困难，但是感觉难度不是很大
题目链接
思路
此题和21题类似，只不过21题是2路合并，该题是k路合并，思路如下：
- 每次取k个链表中首部最小的那个数
- 将该数插到结果链表
- 直到所有链表都插入完
很容易得知该时间复杂度为$O(K*N)$
此处可以用小根堆做优化
/**
* 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:
struct Cmp
{
bool operator()(ListNode* a, ListNode* b)
{
return a->val > b->val;
}
};
ListNode* mergeKLists(vector<ListNode*>& lists) {
priority_queue<ListNode*, vector<ListNode*>, Cmp> heap;
auto dummy = new ListNode(-1), p = dummy;
// 将每个链表的第一个元素（也就是最小数）放入堆中
for (auto l : lists) if (l) heap.push(l);
while (heap.size())
{
// 取堆顶
auto t = heap.top();
heap.pop();
p->next = t;
p = t;
if (t->next) heap.push(t->next);
}
return dummy->next;
}
};
LeetCode 24. 两两交换链表中的节点
题目类型
- 链表
- 交换问题
题目链接
思路
对于p->a->b，其中p为虚拟头结点
交换ab只需要
p->next = b;
a->next = b->next;
b->next = a;
AC代码
/**
* 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* swapPairs(ListNode* head) {
ListNode* dummy = new ListNode(-1);
dummy->next = head;
auto p = dummy;
while (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;
}
};
LeetCode 25. K 个一组翻转链表（***）
题目类型
- 链表
- k组翻转
题目链接
思路
此时看起来不难，实际实现的时候很容易出错，建议多刷几次
- 每次检验是否下一组足够k个元素，不够则break 够的话继续往下执行
- 对于 p->a->b->c->d 从a开始进行k-1次循环反转指针,而且注意在反转指针之前要把b->next存起来
auto c = b->next, b->next = a
- k-1次之后（也就是该组已经反转成功后） 此时将p->next->next = b，落到了下一组以b为开始的反转的前一个结点（可以看做是虚拟结点）
- 继续以上操作
AC代码
/**
* 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* reverseKGroup(ListNode* head, int k) {
ListNode* dummy = new ListNode(-1);
dummy->next = head;
for (auto p = dummy;;)
{
// 判断是否满足k个元素
auto q = p;
for (int i = 0; i < k && q; i ++) q = q->next;
if (!q) break; // 不满足直接跳出
// 满足有k个元素
auto a = p->next, b = a->next;
for (int i = 0; i < k - 1; i ++) // 内部交换k - 1次
{
auto c = b->next;
b->next = a;
a = b, b = c;
}
auto t = p->next;
p->next = a;
t->next = b;
p = t;
}
return dummy->next;
}
};
LeetCode 26. 删除排序数组中的重复项
题目类型
- 数组去重
题目链接
https://leetcode.cn/problems/remove-duplicates-from-sorted-array/
思路
此题比较简单
- 用k指向结果存储
- 遍历nums，每次nums[k] 和 nums[i]
- 如果相同说明出现重复 k不移动等待出现不重复的数将其覆盖
AC代码
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int k = 0; // k作为存储下标
for (int i = 1; i < nums.size(); i ++)
{
if (nums[i] != nums[k])
{
k ++;
nums[k] = nums[i];
}
}
return k + 1;
}
};
LeetCode 27. 移除元素
题目类型
- 去重通用法
- 双指针
题目链接
思路
跟上一题差不多，很简单，直接AC，注意上一题26是return k+1，这里是return k
或者使用双指针，前半部分存储有效数据，后半部分存储无用数据
AC代码1
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];
k ++;
}
}
return k ;
}
};
AC代码2
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int j = nums.size() - 1;
for (int i = 0; i <= j; i ++)
{
if (nums[i] == val) // 出现重复数 放到后面
{
swap(nums[i], nums[j]);
i --, j --;
}
}
return j + 1;
}
};
LeetCode 28. 实现 strStr()
题目类型
- 字符串匹配
- kmp
题目链接
思路
kmp算法
AC代码
class Solution {
public:
int strStr(string haystack, string needle) {
if (haystack.empty() || needle.empty()) return -1;
int n = haystack.size(), m = needle.size();
haystack = ' ' + haystack, needle = ' ' + needle;
vector<int> next(m + 1);
// 求next数组
for (int i = 2, j = 0; i <= m; i ++)
{
while (j && needle[i] != needle[j + 1]) j = next[j];
if (needle[i] == needle[j + 1]) j ++;
next[i] = j;
}
// kmmp
for (int i = 1, j = 0; i <= n; i ++)
{
while (j && haystack[i] != needle[j + 1]) j = next[j];
if (haystack[i] == needle[j + 1]) j ++;
if (j == m)
{
return i -m;
}
}
return -1;
}
};
LeetCode 29. 两数相除
题目类型
- 位运算
题目链接
思路
AC代码
class Solution {
public:
int divide(int x, int y) {
typedef long long LL;
vector<LL> exp;
bool is_minus = false;
if (x < 0 && y > 0 || x > 0 && y < 0) is_minus = true;
LL a = abs((LL)x), b = abs((LL)y);
for (LL i = b; i <= a; i = i + i) exp.push_back(i);
LL res = 0;
for (int i = exp.size() - 1; i >= 0; i --)
{
if (a >= exp[i])
{
a -= exp[i];
res += 1ll << i;
}
}
if (is_minus) res = -res;
if (res > INT_MAX || res < INT_MIN) res = INT_MAX;
return res;
}
};
LeetCode 30. 串联所有单词的子串
题目类型
- 哈希表
题目链接
https://leetcode.cn/problems/substring-with-concatenation-of-all-words/
思路
参考这位大佬的讲解
https://www.acwing.com/solution/content/3669/
AC代码
class Solution {
public:
vector<int> findSubstring(string s, vector<string>& words) {
unordered_map<string, int> hash;
vector<int> res;
int n = s.length(), m = words.size();
if (n == 0 || m == 0) return res;
int len = words[0].length(), end = n - m * len; // 此时不必让
if (n < m * len) return res;
for (auto word:words) hash[word] ++;
for (int i = 0; i <= end; i ++)
{
unordered_map<string, int> cur_hash;
int satisfy = 0;
for (int j = i; j <= n - len; j += len)
{
string cur = s.substr(j, len);
if (hash.find(cur) == hash.end())
break;
else
{
cur_hash[cur] ++;
if (cur_hash[cur] > hash[cur])
break;
else if (cur_hash[cur] == hash[cur])
satisfy++;
if (satisfy == hash.size())
{
res.push_back(i);
break;
}
}
}
}
return res;
}
};
