力扣周赛321题解
找出中枢整数
暴力即可
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14class Solution {
public:
int pivotInteger(int n) {
int tot = n * (n + 1) / 2;
int s = 0;
for(int x = 1; x <= n; x++){
s += x;
if(s == tot - s + x){
return x;
}
}
return -1;
}
};
追加字符以获得子序列
找最的序列$P$满足 $P$ 同时是 $S$和$T$的子序列，答案为$|T|- |P|$
双指针扫一遍即可
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16class Solution {
public:
int appendCharacters(string s, string t) {
int maxx = 0;
int n = (int)s.size();
int m = (int)t.size();
int j = 0;
for(int i = 0; i < n; i++){
if(s[i] == t[j]){
++maxx;
++j;
}
}
return m - maxx;
}
};
从链表中移除节点
倒着遍历判断当前节点是否是最大值即可，如果不是则移除
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44/**
* 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* removeNodes(ListNode* head) {
if(head == nullptr) return nullptr;
ListNode* ptr = head;
vector<int> temp;
while(ptr != nullptr){
temp.push_back(ptr->val);
ptr=ptr->next;
}
int n = (int)temp.size();
vector<int> ans;
int maxx = temp[n - 1];
ans.push_back(maxx);
for(int i = n - 2; i >= 0; --i){
if(maxx <= temp[i]){
ans.push_back(temp[i]);
maxx = temp[i];
}
}
reverse(ans.begin(), ans.end());
if(ans.empty()) return nullptr;
ListNode *rt = new ListNode(ans[0]);
ListNode *p = rt;
for(int i = 1; i < (int)ans.size(); i++){
ListNode *now = new ListNode(ans[i]);
p->next = now;
p = now;
}
return rt;
}
};
统计中位数为 K 的子数组
题面
给你一个长度为 n 的数组 nums ，该数组由从 1 到 n 的 不同 整数组成。另给你一个正整数 k 。
统计并返回 num 中的 中位数 等于 k 的非空子数组的数目。
注意：
- 数组的中位数是按递增顺序排列后位于中间的那个元素，如果数组长度为偶数，则中位数是位于中间靠左的那个元素。
- 例如，
[2,3,1,4]的中位数是2，[8,4,3,5,1]的中位数是4。
- 例如，
- 子数组是数组中的一个连续部分。
题解：
- 若当前元素大于k, 则置其为1，若小于k则置其为-1，若等于k则置其为0
- 问题转化为和为0和1的并且包含0元素的子数组数目
- 使用前缀和，记录前面与当前前缀相等或者小1的数目累加即可
代码
1 | class Solution { |