1.23#
三数之和 (掌握程度： 中)#
忘记了部分如要先排序还有剪枝部分出现了问题
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<vector<int>> ans;
int n = nums.size();
for (int i = 0; i < n - 2; i++) {
if (i > 0 && nums[i] == nums[i - 1]) continue;
if (nums[i] + nums[i + 1] + nums[i + 2] > 0) break;
if (nums[i] + nums[n - 2] + nums[n - 1] < 0) continue;
int left = i + 1, right = n - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum > 0) right--;
else if (sum < 0) left++;
else {
ans.push_back({nums[i], nums[left], nums[right]});
left++;
right--;
while (left < right && nums[left] == nums[left - 1]) left++;
while (left < right && nums[right] == nums[right + 1]) right--;
}
}
}
return ans;
}
};最大子数组和 (掌握程度：高)#
其实看到题还是有点懵的，但是还是觉得是前缀和，结果还真是
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int n = nums.size();
int ans = INT_MIN;
int minPre = 0, pre = 0;
for (int i = 0; i < n; i++) {
pre += nums[i];
ans = max(ans, pre - minPre);
minPre = min(minPre, pre);
}
return ans;
}
};手撕快排 (掌握程度：中)#
跟前面的快速选择一样的写法，但是还是不太熟
class Solution {
public:
vector<int> sortArray(vector<int>& nums) {
srand(time(0));
quickSort(nums, 0, nums.size() - 1);
return nums;
}
void quickSort(vector<int>& nums, int left, int right) {
if (left == right) return;
int random = left + rand() % (right - left + 1);
swap(nums[left], nums[random]);
int pivot = nums[left];
int i = left - 1, j = right + 1;
while (true) {
do i++; while (nums[i] < pivot);
do j--; while (nums[j] > pivot);
if (i >= j) break;
swap(nums[i], nums[j]);
}
quickSort(nums, left, j);
quickSort(nums, j + 1, right);
}
};最长回文子串 (掌握程度： 中)#
这个就是中心扩散算法了，但是在中心扩散的while循环条件的条件处理的不是特别好
class Solution {
public:
string longestPalindrome(string s) {
int n = s.size();
int start = 0, end = 0;
for (int i = 0; i < n; i++) {
auto [l1, r1] = expandFromCenter(s, i, i);
auto [l2, r2] = expandFromCenter(s, i, i + 1);
if (r1 - l1 > end - start) {
start = l1;
end = r1;
}
if (r2 - l2 > end - start) {
start = l2;
end = r2;
}
}
return s.substr(start, end - start + 1);
}
pair<int, int> expandFromCenter(const string& s, int left, int right) {
while (left >= 0 && right < s.size() && s[left] == s[right]) {
left--;
right++;
}
return {left + 1, right - 1};
}
};合并两个有序链表 (掌握程度： 高)#
依旧简单题
/**
* 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* list1, ListNode* list2) {
ListNode* dummy = new ListNode(0);
ListNode* cur = dummy;
while (list1 && list2) {
if (list1->val < list2->val) {
cur->next = list1;
list1 = list1->next;
} else {
cur->next = list2;
list2 = list2->next;
}
cur = cur->next;
}
if (list1) cur->next = list1;
else cur->next = list2;
return dummy->next;
}
};