本周完成事项
- 通过进组考核。
- LeetCode周赛第一次完成三题。
- 在教程指引下完成了Mint + Anaconda + Pytorch + Pycharm的环境配置。
- 完成代码随想录的二叉树专题。
- 学习了图相关问题的基本处理方法。
- 利用GParted对
home目录进行扩容，避免浪费时间重装系统。
LeetCode 第 321 场周赛
第一次完成了三题，但应该承认的是，这次的中等题确实偏简单。
找出中枢整数
思路
分析题意，不难发现返回值总在有限区间内，且判断值是否符合限制也比较简单，仅需要常数空间和时间，因此想到二分法查找答案。当固定 x 的值，可以很容易求出左右两部分的和（等差数列），验证是否相等，若不等，则根据大小关系缩小区间即可。
代码
class Solution {
public:
int pivotInteger(int n) {
int low = 1, high = n;
while (low <= high) {
int mid = (low + high) / 2;
int res1 = (1 + mid) * mid / 2;
int res2 = (mid + n) * (n - mid + 1) / 2;
if (res1 == res2) return mid;
else if (res1 < res2) low = mid + 1;
else high = mid - 1;
}
return -1;
}
};追加字符以获得子序列
思路
看到之后没有细想，以为直接求最长公共子序列，然后用 t 的长度减掉子序列的长度即可。测试发现输出不对，才反应过来，应该求的是以 t 的首部开始的连续子串在 s 中出现的长度，然后再用 t的长度减去它。
因为看到熟悉的算法所以兴奋地忘了先去手动验证用例，急着先去代码实现，所以后面改代码又浪费了时间。
代码
class Solution {
public:
int appendCharacters(string s, string t) {
int i = 0, j = 0;
for (; i < s.size() && j < t.size();) {
if (s[i] == t[j]) {
++i;
++j;
} else {
++i;
}
}
return t.size() - j;
}
};从链表中移除节点
思路
之前遇到题目总是一根筋正着去想。昨天刚写了一些题，认识到逆向思维的重要性。具体到这道题，初看下，如果顺着链表正向走，那么要知道当前结点是否应当删除，是有些麻烦的。但是如果反着来，就变得异常容易，只要记录和更新遍历过程中的最大元素，在遍历过程中遇到小于最大元素的值，就将其记录为需要删除，最后再正向遍历删除这些结点即可。
先将结点值记录在一个数组中，方便反向遍历，然后将需要删除的值放到栈中，最后遍历链表去依次删除栈内元素对应的结点即可。时间、空间复杂度均为 O(n) 。
代码
class Solution {
public:
ListNode* removeNodes(ListNode* head) {
ListNode* dummy = new ListNode;
dummy->next = head;
vector<int> nums;
ListNode* cur = head;
while (cur) {
nums.push_back(cur->val);
cur = cur->next;
}
if (nums.size() == 1) return head;
int rightMaxNum = nums[nums.size() - 1];
stack<int> toBeDel;
for (int i = nums.size() - 2; i >= 0; --i) {
if (rightMaxNum > nums[i]) toBeDel.push(nums[i]);
else rightMaxNum = max(rightMaxNum, nums[i]);
}
ListNode* pre = dummy;
cur = head;
while (cur) {
if (!toBeDel.empty() && cur->val == toBeDel.top()) {
toBeDel.pop();
pre->next = cur->next;
cur = cur->next;
} else {
pre = cur;
cur = cur->next;
}
}
return dummy->next;
}
};这题描述是有点坑的，我一开始以为 head 是空结点，写完才发现是它也是含有元素的，所以再改了个 dummy 结点出来。
统计中位数为 K 的子数组
思路
应该说这题我的思路是正确的，但不知道怎么实现。
对于一个子数组，k 能否作为其中位数，取决于子数组中有多少元素大于它、小于它。如果前者跟后者数量一样（k 在正中间），或者前者比后者多一个（总共偶数个元素，k处于中间靠左），都可以满足条件。所以问题在于如何计算满足上述条件的情况总数。
Comments NOTHING