2.1#
删除链表的倒数第 N 个结点 (掌握程度：中)#
没有想起来要用哨兵节点，后面如果都是删除的话，就把哨兵先创建出来
/**
* 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* removeNthFromEnd(ListNode* head, int n) {
ListNode* dummy = new ListNode(0);
dummy->next = head;
ListNode* fast = dummy;
ListNode* slow = dummy;
for (int i = 0; i < n; i++) {
fast = fast->next;
}
while(fast->next) {
slow = slow->next;
fast = fast->next;
}
slow->next = slow->next->next;
return dummy->next;
}
};环形链表 II (掌握程度：中)#
边界处理还是记得不太清楚啊，还有那个公式也有点忘记了
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode* fast = head;
ListNode* slow = head;
while (fast && fast->next) {
fast = fast->next->next;
slow = slow->next;
if (fast == slow) {
while (head != slow) {
head = head->next;
slow = slow->next;
}
return head;
}
}
return nullptr;
}
};寻找两个正序数组的中位数 (掌握程度：低)#
一点不会的二分hard题，这个得花点功夫看了
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int n1 = nums1.size(), n2 = nums2.size();
if (n1 > n2) return findMedianSortedArrays(nums2, nums1);
int left = 0, right = n1;
while (left <= right) {
int i = (left + right) / 2;
int j = (n1 + n2 + 1) / 2 - i;
int L1, R1, L2, R2;
// nums1 左边界
if (i == 0) L1 = INT_MIN; // nums1 左边没有元素
else L1 = nums1[i - 1]; // nums1 左边最后一个元素
// nums1 右边界
if (i == n1) R1 = INT_MAX; // nums1 右边没有元素
else R1 = nums1[i]; // nums1 右边第一个元素
// nums2 左边界
if (j == 0) L2 = INT_MIN; // nums2 左边没有元素
else L2 = nums2[j - 1]; // nums2 左边最后一个元素
// nums2 右边界
if (j == n2) R2 = INT_MAX; // nums2 右边没有元素
else R2 = nums2[j]; // nums2 右边第一个元素
if (L1 <= R2 && L2 <= R1) {
if ((n1 + n2) % 2 == 1) {
return max(L1, L2);
} else {
return (max(L1, L2) + min(R1, R2)) / 2.0;
}
}
else if (L1 > R2) {
right = i - 1;
}
else {
left = i + 1;
}
}
return 0.0;
}
};二叉树的右视图 (掌握程度： 中)#
记得有点不是很清楚了，后续需要花功夫重新复习一下
/**
* 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<int> ans;
void dfs(TreeNode* node, int depth) {
if (node == nullptr) return;
if (depth == ans.size()) ans.push_back(node->val);
dfs(node->right, depth + 1);
dfs(node->left, depth + 1);
}
vector<int> rightSideView(TreeNode* root) {
if (root == nullptr) return {};
dfs(root, 0);
return ans;
}
};比较版本号 (掌握程度： 中)#
难度不高的，其实就是字符串比大小，只不过是这种类型的接触到的比较少，后续还是得要花功夫去详细熟悉一下
class Solution {
public:
int compareVersion(string version1, string version2) {
int m =version1.size(), n = version2.size();
int i = 0, j = 0;
while (i <= m || j <= n) {
int num1 = 0, num2 = 0;
while (i < m && version1[i] != '.') {
num1 = num1 * 10 + (version1[i] - '0');
i++;
}
while (j < n && version2[j] != '.') {
num2 = num2 * 10 + (version2[j] - '0');
j++;
}
if (num1 > num2) return 1;
if (num1 < num2) return -1;
i++;
j++;
}
return 0;
}
};