1.26#
合并两个有序数组 (掌握程度： 中)#
这个我记得是从后往前的进行算（原地算法），但是详细有点忘记了
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
int p1 = m - 1, p2 = n - 1, p = m + n - 1;
while (p2 >= 0) {
if (p1 >= 0 && nums1[p1] > nums2[p2]) {
nums1[p] = nums1[p1];
p1--;
} else {
nums1[p] = nums2[p2];
p2--;
}
p--;
}
}
};有效的括号 (掌握程度：中)#
典型的括号栈的题
class Solution {
public:
bool isValid(string s) {
unordered_map<char,char> map = {
{')', '('},
{']', '['},
{'}', '{'}
};
int n = s.size();
stack<char> st;
if (n % 2 != 0) return false;
for (int i = 0; i < n; i++) {
if (map.count(s[i]) == 0) {
st.push(s[i]);
} else {
if (st.empty() || st.top() != map[s[i]]) return false;
st.pop();
}
}
return st.empty();
}
};买卖股票的最佳时机 (掌握程度： 中)#
简单的贪心题，除了边界处理的不太好
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n = prices.size();
int ans = 0;
int minPrices = INT_MAX;
for (int i = 0; i < n; i++) {
ans = max(ans, prices[i] - minPrices);
minPrices = min(minPrices, prices[i]);
}
return ans;
}
};反转链表Ⅱ (掌握程度： 中)#
这个是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* reverseBetween(ListNode* head, int left, int right) {
ListNode* dummy = new ListNode(0);
dummy->next = head;
ListNode* p0 = dummy;
for (int i = 0; i < left - 1; i++) {
p0 = p0->next;
}
ListNode* pre = nullptr;
ListNode* cur = p0->next;
ListNode* tail = cur;
for (int i = 0; i < right - left + 1; i++) {
ListNode* nxt = cur->next;
cur->next = pre;
pre = cur;
cur = nxt;
}
p0->next = pre;
tail->next = cur;
return dummy->next;
}
};二叉树的锯齿形层序遍历 (掌握程度：中)#
这个就跟层序遍历没啥区别就是中间加了一点判断，但是边界处理和中间的判断还是不熟
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
if (root == nullptr) return {};
vector<vector<int>> ans;
queue<TreeNode*> q;
q.push(root);
while(!q.empty()) {
int n = q.size();
vector<int> vals(n);
for (int i = 0; i < n; i++) {
TreeNode* node = q.front();
q.pop();
if (ans.size() % 2 == 0) {
vals[i] = node->val;
} else {
vals[n - i - 1] = node->val;
}
if (node->left != nullptr) q.push(node->left);
if (node->right != nullptr) q.push(node->right);
}
ans.push_back(vals);
}
return ans;
}
};