1.28#
合并K个升序链表 (掌握程度：低)#
合并两个有序链表＋归并，一点都没印象这个后面得二刷一遍
/**
* 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* mergeKLists(vector<ListNode*>& lists) {
if (lists.empty()) return nullptr;
int n = lists.size();
while (n > 1) {
int k = (n + 1) / 2;
for (int i = 0; i < n / 2; i++) {
lists[i] = merge2Lists(lists[i], lists[i + k]);
}
n = k;
}
return lists[0];
}
ListNode* merge2Lists(ListNode* node1, ListNode* node2) {
ListNode* dummy = new ListNode(0);
ListNode* cur = dummy;
while (node1 && node2) {
if (node1->val < node2->val) {
cur->next = node1;
node1 = node1->next;
} else {
cur->next = node2;
node2 = node2->next;
}
cur = cur->next;
}
if (node1) cur->next = node1;
else cur->next = node2;
return dummy->next;
}
};字符串相加 (掌握程度：中)#
难度不大，不过确实触及到我的盲区了有点了
class Solution {
public:
string addStrings(string num1, string num2) {
int n1 = num1.size(), n2 = num2.size();
int i = n1 - 1, j = n2 - 1;
int carry = 0;
string ans = "";
while (i >= 0 || j >= 0 || carry > 0) {
int x = 0, y = 0;
if (i >= 0) x = num1[i] - '0';
if (j >= 0) y = num2[j] - '0';
int sum = x + y + carry;
ans.push_back(sum % 10 + '0');
carry = sum / 10;
i--;
j--;
}
reverse(ans.begin(), ans.end());
return ans;
}
};合并区间 (掌握程度： 高)#
写过很多次了，虽然不能做到百分百正确，但是就一个n > 0 没有处理到，就算我自己是高吧
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
vector<vector<int>> ans;
sort(intervals.begin(), intervals.end());
for (vector<int> interval : intervals) {
int n = ans.size();
if (n > 0 && interval[0] <= ans[n - 1][1]) {
ans[n - 1][1] = max(ans[n - 1][1], interval[1]);
} else {
ans.push_back(interval);
}
}
return ans;
}
};相交链表 (掌握程度： 中)#
记得是两个连表交替走如果相交就会走到一起，但是循环的条件记得不太清楚
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
if (headA == nullptr || headB == nullptr) return nullptr;
ListNode* p = headA;
ListNode* q = headB;
while (p != q) {
if (p == nullptr) p = headB;
else p = p->next;
if (q == nullptr) q = headA;
else q = q->next;
}
return p;
}
};编辑距离 (掌握程度： 中)#
这个dp写了很多次，但是转移方程和边界的初始化还是有点略微忘记了
class Solution {
public:
int minDistance(string word1, string word2) {
int m = word1.size(), n = word2.size();
vector<vector<int>> dp(m + 1, vector<int> (n + 1));
for (int i = 0; i <= m; i++) dp[i][0] = i;
for (int j = 0; j <= n; j++) dp[0][j] = j;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (word1[i] == word2[j]) {
dp[i + 1][j + 1] = dp[i][j];
} else {
dp[i + 1][j + 1] = min({dp[i + 1][j], dp[i][j + 1], dp[i][j]}) + 1;
}
}
}
return dp[m][n];
}
};