《LeetCode 顺序刷题》21 - 30

21、[简单] 合并两个有序链表

递归 链表

迭代

class Solution {
public:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
ListNode head;
ListNode *cur = &head, *cur1 = list1, *cur2 = list2;
while (cur1 && cur2) {
if (cur1->val < cur2->val) {
cur->next = cur1;
cur1 = cur1->next;
} else {
cur->next = cur2;
cur2 = cur2->next;
}
cur = cur->next;
}
if (cur1) {
cur->next = cur1;
} else {
cur->next = cur2;
}
return head.next;
}
};

递归

class Solution {
public:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
if (list1 == nullptr) {
return list2;
} else if (list2 == nullptr) {
return list1;
} else if (list1->val < list2->val) {
list1->next = mergeTwoLists(list1->next, list2);
return list1;
} else {
list2->next = mergeTwoLists(list1, list2->next);
return list2;
}
}
};

22、[中等] 括号生成

字符串 回溯

class Solution {
public:
vector<string> generateParenthesis(int n) {
vector<string> ret;
string path;
int left = 0, right = 0;
dfs(ret, path, left, right, n);
return ret;
}

void dfs(vector<string>& ret, string& path, int left, int right, int n) {
if (right == n) {
ret.push_back(path);
return;
}
if (left < n) {
path.push_back('(');
dfs(ret, path, left + 1, right, n);
path.pop_back();
}
if (right < left) {
path.push_back(')');
dfs(ret, path, left, right + 1, n);
path.pop_back();
}
}
};

23、[困难] 合并 K 个升序链表

链表 分治

顺序合并

class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
ListNode* ret = nullptr;
for (size_t i = 0; i < lists.size(); i++) {
ret = mergeTwoLists(ret, lists[i]);
}
return ret;
}

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if (!l1 || !l2) {
return l1 ? l1 : l2;
}

ListNode head, *cur = &head, *cur1 = l1, *cur2 = l2;
while (cur1 && cur2) {
if (cur1->val < cur2->val) {
cur->next = cur1;
cur1 = cur1->next;
} else {
cur->next = cur2;
cur2 = cur2->next;
}
cur = cur->next;
}

cur->next = cur1 ? cur1 : cur2;
return head.next;
}
};

合并分治

class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
return merge(lists, 0, lists.size() – 1);
}

ListNode* merge(vector<ListNode*>& lists, int left, int right) {
if (left > right) {
return nullptr;
}
if (left == right) {
return lists[left];
}
int mid = (left + right) >> 1;
return mergeTwoLists(merge(lists, left, mid), merge(lists, mid + 1, right));
}

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if (!l1 || !l2) {
return l1 ? l1 : l2;
}

ListNode head, *cur = &head, *cur1 = l1, *cur2 = l2;
while (cur1 && cur2) {
if (cur1->val < cur2->val) {
cur->next = cur1;
cur1 = cur1->next;
} else {
cur->next = cur2;
cur2 = cur2->next;
}
cur = cur->next;
}

cur->next = cur1 ? cur1 : cur2;
return head.next;
}
};

优先级队列

struct Status {
int val;
ListNode* ptr;

bool operator<(const Status& rhs) const { return val > rhs.val; }

Status(int x, ListNode* node) : val(x), ptr(node) {}
};

class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
priority_queue<Status> q;
for (const auto& node : lists) {
if (node) {
q.push({node->val, node});
}
}
ListNode head, *cur = &head;
while (!q.empty()) {
auto front = q.top();
q.pop();
cur->next = front.ptr;
cur = cur->next;
if (front.ptr->next) {
q.push({front.ptr->next->val, front.ptr->next});
}
}
return head.next;
}
};

24、[中等] 两两交换链表中的节点

链表

递归

class Solution {
public:
ListNode* swapPairs(ListNode* head) {
if (head == nullptr || head->next == nullptr) {
return head;
}

ListNode* newhead = head->next;
head->next = swapPairs(newhead->next);
newhead->next = head;

return newhead;
}
};

迭代

class Solution {
public:
ListNode* swapPairs(ListNode* head) {
ListNode newhead;
newhead.next = head;
ListNode* cur = &newhead;
while (cur->next && cur->next->next) {
ListNode* node1 = cur->next;
ListNode* node2 = cur->next->next;
cur->next = node2;
node1->next = node2->next;
node2->next = node1;
cur = node1;
}
return newhead.next;
}
};

class Solution {
public:
ListNode* swapPairs(ListNode* head) {
if (head == nullptr || head->next == nullptr) {
return head;
}

ListNode newhead;
newhead.next = head;
ListNode* prev = &newhead;
ListNode* cur = prev->next;
ListNode* next = cur->next;

while (cur && next) {
prev->next = next;
cur->next = next->next;
next->next = cur;

prev = cur;
cur = cur->next;
if (cur) {
next = cur->next;
}
}

return newhead.next;
}
};

25、[困难] K 个一组翻转链表

链表

class Solution {
public:
ListNode* reverseKGroup(ListNode* head, int k) {
// 1. 先求出需要逆序多少组
int n = 0;
ListNode* cur = head;
while (cur) {
cur = cur->next;
n++;
}
n /= k;

// 2. 重复 n 次：长度为 k 的链表的逆序即可
ListNode newhead;
ListNode* pre = &newhead;
cur = head;
for (int i = 0; i < n; i++) {
ListNode* tmp = cur;
for (int j = 0; j < k; j++) {
ListNode* next = cur->next;
cur->next = pre->next;
pre->next = cur;
cur = next;
}
pre = tmp;
}

// 3. 把不需要翻转的接上
pre->next = cur;
return newhead.next;
}
};

26、[简单] 删除有序数组中的重复项

数组 双指针

双指针

class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int n = nums.size();
if (n == 0)
return 0;

int i = 0, j = 1;
int dst = 0;
while (j < n) {
if (nums[i] == nums[j]) {
j++;
} else {
nums[dst++] = nums[i];
i = j;
j++;
}
}
nums[dst++] = nums[i];

return dst;
}
};

class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int n = nums.size();
if (n == 0)
return 0;

int fast = 1, slow = 1;
while (fast < n) {
if (nums[fast] != nums[fast – 1]) {
nums[slow++] = nums[fast];
}
++fast;
}

return slow;
}
};

27、[简单] 移除元素

数组 双指针

双指针

class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int n = nums.size();
int src = 0, dst = 0;
while (src < n) {
if (nums[src] != val)
nums[dst++] = nums[src++];
else
++src;
}
return dst;
}
};

双指针优化

class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int left = 0, right = nums.size();
while (left < right) {
if (nums[left] == val) {
nums[left] = nums[–right];
} else {
left++;
}
}
return left;
}
};

28、[简单] 找出字符串中第一个匹配项的下标

双指针 字符串 字符串匹配

class Solution {
public:
int strStr(string haystack, string needle) {
int n = haystack.size();
for (int i = 0; i < n; i++) {
if (haystack[i] == needle[0]) {
int start = 0;
while (i + start < n && start < needle.size()) {
if (haystack[i + start] == needle[start]) {
start++;
} else {
break;
}
}
if (start == needle.size()) {
return i;
}
}
}
return -1;
}
};

class Solution {
public:
int strStr(string haystack, string needle) {
int n = haystack.size();
int m = needle.size();
for (int i = 0; i <= n – m; i++) {
int j = i, k = 0;
while (k < m && haystack[j] == needle[k]) {
j++;
k++;
}
if (k == m) {
return i;
}
}
return -1;
}
};

KMP

class Solution {
public:
int strStr(string haystack, string needle) {
int n = haystack.size(), m = needle.size();
if (m == 0) {
return 0;
}
// 设置哨兵
haystack.insert(haystack.begin(), ' ');
needle.insert(needle.begin(), ' ');
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;
}
// 匹配过程
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;
}
};

29、[中等] 两数相除

数学 二分查找

二分查找

class Solution {
public:
int divide(int dividend, int divisor) {
// 考虑被除数为最小值的情况
if (dividend == INT_MIN) {
if (divisor == 1) {
return INT_MIN;
}
if (divisor == -1) {
return INT_MAX;
}
}
// 考虑除数为最小值的情况
if (divisor == INT_MIN) {
return dividend == INT_MIN ? 1 : 0;
}
// 考虑被除数为 0 的情况
if (dividend == 0) {
return 0;
}

// 一般情况，使用二分查找
// 将所有的正数取相反数，这样就只需要考虑一种情况
bool rev = false;
if (dividend > 0) {
dividend = -dividend;
rev = !rev;
}
if (divisor > 0) {
divisor = -divisor;
rev = !rev;
}

// 快速乘
auto quickAdd = [](int y, int z, int x) {
// x 和 y 是负数，z 是正数
// 需要判断 z * y >= x 是否成立
int result = 0, add = y;
while (z) {
if (z & 1) {
// 需要保证 result + add >= x
if (result < x – add) {
return false;
}
result += add;
}
if (z != 1) {
// 需要保证 add + add >= x
if (add < x – add) {
return false;
}
add += add;
}
// 不能使用除法
z >>= 1;
}
return true;
};

int left = 1, right = INT_MAX, ret = 0;
while (left <= right) {
// 注意溢出，并且不能使用除法
int mid = left + ((right – left) >> 1);
bool check = quickAdd(divisor, mid, dividend);
if (check) {
ret = mid;
// 注意溢出
if (mid == INT_MAX) {
break;
}
left = mid + 1;
} else {
right = mid – 1;
}
}

return rev ? -ret : ret;
}
};

类二分查找

class Solution {
public:
int divide(int dividend, int divisor) {
// 考虑被除数为最小值的情况
if (dividend == INT_MIN) {
if (divisor == 1) {
return INT_MIN;
}
if (divisor == -1) {
return INT_MAX;
}
}
// 考虑除数为最小值的情况
if (divisor == INT_MIN) {
return dividend == INT_MIN ? 1 : 0;
}
// 考虑被除数为 0 的情况
if (dividend == 0) {
return 0;
}

// 一般情况，使用类二分查找
// 将所有的正数取相反数，这样就只需要考虑一种情况
bool rev = false;
if (dividend > 0) {
dividend = -dividend;
rev = !rev;
}
if (divisor > 0) {
divisor = -divisor;
rev = !rev;
}

vector<int> candidates = {divisor};
// 注意溢出
while (candidates.back() >= dividend – candidates.back()) {
candidates.push_back(candidates.back() + candidates.back());
}
int ans = 0;
for (int i = candidates.size() – 1; i >= 0; –i) {
if (candidates[i] >= dividend) {
ans += (1 << i);
dividend -= candidates[i];
}
}

return rev ? -ans : ans;
}
};

30、[困难] 串联所有单词的字串

哈希表 字符串 滑动窗口

class Solution {
public:
vector<int> findSubstring(string s, vector<string>& words) {
unordered_map<string, int> hash1; // 保存 words 里面所有单词的频次
for (const auto& s : words) {
hash1[s]++;
}
vector<int> ret;

int len = words[0].size(), m = words.size();
for (int i = 0; i < len; i++) {
unordered_map<string, int> hash2; // 维护窗口内单词的频次
for (int left = i, right = i, count = 0; right + len <= s.size();
right += len) {
// 进窗口 + 维护 count
string in = s.substr(right, len);
hash2[in]++;
if (hash1.count(in) && hash2[in] <= hash1[in]) {
count++;
}

// 判断
if (right – left + 1 > len * m) {
// 出窗口 + 维护 count
string out = s.substr(left, len);
if (hash1.count(out) && hash2[out] <= hash1[out]) {
count–;
}
hash2[out]–;
left += len;
}

// 更新结果
if (count == m) {
ret.push_back(left);
}
}
}

return ret;
}
};