1.27#
二叉树的最近公共祖先 (掌握程度：中)#
中间的处理还是有点忘记了， 而且在进了界面就瞥了几眼结果还是记不太清😓
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (root == nullptr || root == p || root == q) return root;
TreeNode* left = lowestCommonAncestor(root->left, p, q);
TreeNode* right = lowestCommonAncestor(root->right, p, q);
if (left != nullptr && right != nullptr) return root;
if (left != nullptr) return left;
return right;
}
};环形链表 (掌握程度：高)#
简单的快慢指针，简单题还是比较easy的
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
bool hasCycle(ListNode *head) {
ListNode* slow = head;
ListNode* fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) {
return true;
}
}
return false;
}
};最长递增子序列 (掌握程度： 中)#
把这道题和另外一个搞混了，这个是dp，另一个是set，动态规划还是恶心啊
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int n = nums.size();
int ans = 0;
vector<int> dp(n + 1, 1);
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
ans = max(ans, dp[i]);
}
return ans;
}
};螺旋矩阵 (掌握程度：中)#
知道怎么写，就是有一些跟矩阵相关的不熟，还有dirs[4] [2]的方向还是记不太清，后续估计得多花些功夫在这上面
class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
int m = matrix.size(), n = matrix[0].size();
int dirs[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
vector<int> ans(m * n);
int dir = 0, i = 0, j = 0;
for (int k = 0; k < m * n; k++) {
ans[k] = matrix[i][j];
matrix[i][j] = INT_MAX;
int x = i + dirs[dir][0], y = j + dirs[dir][1];
if (x < 0 || x >= m || y < 0 || y >= n || matrix[x][y] == INT_MAX) dir = (dir + 1) % 4;
i += dirs[dir][0];
j += dirs[dir][1];
}
return ans;
}
};重排链表 (掌握程度： 中)#
就是快慢指针找中点，然后断开，再反转，然后一个一个接上
/**
* 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:
void reorderList(ListNode* head) {
if (!head || !head->next) return;
ListNode* slow = head;
ListNode* fast = head;
while (fast->next && fast->next->next) {
slow = slow->next;
fast = fast->next->next;
}
ListNode* head2 = reverseList(slow->next);
slow->next = nullptr;
ListNode* p1 = head;
ListNode* p2 = head2;
while (p2) {
ListNode* n1 = p1->next;
ListNode* n2 = p2->next;
p1->next = p2;
p2->next = n1;
p1 = n1;
p2 = n2;
}
}
ListNode* reverseList(ListNode* node) {
ListNode* pre = nullptr;
while (node) {
ListNode* nxt = node->next;
node->next = pre;
pre = node;
node = nxt;
}
return pre;
}
};