这周周赛没有什么过多难的 也是可以自己写完的 (芜湖)
第一道题
6245. 找出中枢整数
给你一个正整数 n ，找出满足下述条件的 中枢整数 x ：
1 和 x 之间的所有元素之和等于 x 和 n 之间所有元素之和。
返回中枢整数 x 。如果不存在中枢整数，则返回 -1 。题目保证对于给定的输入，至多存在一个中枢整数。
示例 1：
输入：n = 8
输出：6
解释：6 是中枢整数，因为 1 + 2 + 3 + 4 + 5 + 6 = 6 + 7 + 8 = 21 。
思路： 这道题 一看就要用到前缀和 的知识 这道题在比赛的时候我用的是 前缀和数组 和 后缀和数组一起加逼 得到答案其实并不需要
比赛时候的代码：
class Solution {
public:
int pivotInteger(int n) {
vector<int> presum(n);
vector<int> postsum(n);
for(int i=0;i<n;++i)
{
presum[i]=i+1;
postsum[i]=i+1;
}
for(int i=1;i<n;++i)
{
presum[i]+=presum[i-1];
postsum[n-1-i]+=postsum[n-1-i+1];
}
for(int i=0;i<n;++i)
{
if(presum[i]==postsum[i]) return i+1;
}
return -1;
}
};
多了一个后缀和的代码 其实没必要 统计一下sum是多少就好了 然后再减一下就ok
代码如下：
class Solution {
public:
int pivotInteger(int n) {
vector<int> presum(n+1);
int sum=0;
for(int i=0;i<=n;++i)
{
presum[i]=i+1;
if(i) presum[i]+=presum[i-1];
sum+=i;
}
for(int i=1;i<=n;++i)
{
if(presum[i]==sum-presum[i-1]) return i+1;
}
return -1;
}
};
第二题
6246. 追加字符以获得子序列
给你两个仅由小写英文字母组成的字符串 s 和 t 。
现在需要通过向 s 末尾追加字符的方式使 t 变成 s 的一个 子序列 ，返回需要追加的最少字符数。
子序列是一个可以由其他字符串删除部分（或不删除）字符但不改变剩下字符顺序得到的字符串。输入：s = "coaching", t = "coding"
输出：4
解释：向 s 末尾追加字符串 "ding" ，s = "coachingding" 。
现在，t 是 s ("coachingding") 的一个子序列。
可以证明向 s 末尾追加任何 3 个字符都无法使 t 成为 s 的一个子序列。
思路：
这道题也并不难 一开始理解错了 以为是找子串问题 然后就用了 kmp 提交之后看了 错误示例 我就知道哪里错了 然后 就发现 想复杂了
好了 闲话不多说 讲思路了 这道题的意思就是 寻找在s 中的 t的 子串 含义 s中含有的t的字符串可以不连贯 但必须是 t的 顺序 意思就是 s=ktr t = kr t就是 s的子序列 但是 如果 s=ing t=ni 那s需要补充一个i 才能实现 所以很好实现这道题
代码如下：
class Solution {
public:
int appendCharacters(string s, string t) {
int i=0,j=0;
while(i<s.size())
{
if(j==t.size()) return 0;
if(s[i]==t[j]) j++;
i++;
}
return t.size()-j;
}
};
第三题
6247. 从链表中移除节点
给你一个链表的头节点 head 。
对于列表中的每个节点 node ，如果其右侧存在一个具有 严格更大 值的节点，则移除 node 。
返回修改后链表的头节点 head 。
思路 ： 利用单调栈 可以维护一个单调小栈 通过维护这个单调小栈 就可以知道 哪些点需要留 哪些点 需要扔掉
deque<int> mp;
while(h)
{
while(!mp.empty() && h->val > mp.back()) mp.pop_back();
mp.push_back(h->val);
h=h->next;
}
再从链表头开始遍历链表 如果他是单调栈中的元素 就保留 不是就删除
if(s->val!=mp.front())
{
s->next==NULL;
delete s;
}
如果他是单调栈的元素 就需要判断他是不是头节点 我们可以引入一个pre变量 初始化为NULL 可以通过这个来重新将链表串起来
//第一个点
if(pre==NULL) {
head=s;
pre=s;
}
//后续节点
else {
pre->next=s;
pre=s;
}
完整代码如下：
class Solution {
public:
ListNode* removeNodes(ListNode* head) {
ListNode* h=head;
deque<int> mp;
while(h)
{
while(!mp.empty() && h->val > mp.back()) mp.pop_back();
mp.push_back(h->val);
h=h->next;
}
ListNode* pre=NULL;
ListNode* temp=head;
while(temp)
{
ListNode* s=temp;
temp=temp->next;
if(s->val!=mp.front()) {
s->next==NULL;
delete s;
}
else {
mp.pop_front();
//第一个点
if(pre==NULL) {
head=s;
pre=s;
}
//后续节点
else {
pre->next=s;
pre=s;
}
}
}
return head;
}
};
第四题
6248. 统计中位数为 K 的子数组
给你一个长度为 n 的数组 nums ，该数组由从 1 到 n 的 不同 整数组成。另给你一个正整数 k 。
统计并返回 num 中的 中位数 等于 k 的非空子数组的数目。
注意：
数组的中位数是按 递增 顺序排列后位于 中间 的那个元素，如果数组长度为偶数，则中位数是位于中间靠 左 的那个元素。
例如，[2,3,1,4] 的中位数是 2 ，[8,4,3,5,1] 的中位数是 4 。
子数组是数组中的一个连续部分。
示例 1：
输入：nums = [3,2,1,4,5], k = 4
输出：3
解释：中位数等于 4 的子数组有：[4]、[4,5] 和 [1,4,5] 。
思路： 这道题 利用的前后缀和 来解题
#1找到k的位置 同时将 nums数组分别分为 大于 k的(1) 等于k的 (0) 和 小于k的(-1) 方便来计数
// 找出k所在下标idx
for(int i=0;i<n;i++)
{
if(nums[i]==k)
{
index = i;
}
if(nums[i]<k)
nums[i] = -1;
else if(nums[i]==k)
nums[i] = 0;
else
nums[i] = 1;
}
#2 先遍历 idx之后的数 看有几个大于k的 有几个小于k的 利用一张hash_map来计数 分别记录 从idx开始 有几种情况
// 枚举idx之后的数与idx+idx之前后缀和的和，和为0或1的数目可计入答案
unordered_map<int,int> m;
int s = 0;
for(int i=index+1;i<n;i++)
{
s += nums[i];
m[s] += 1;
}
题目说偶数是记录上中位数的 所以我们可以看2个点 0或者1 的点 这两个点都符合题意
// 枚举idx与idx之前后缀和的和，和为0或1的数目可计入答案
for(int i=index;i>=0;i--)
{
s += nums[i];
if(m.find(-s)!=m.end())
{
res += m[-s];
}
if(m.find(1-s)!=m.end())
{
res += m[1-s];
}
}
完整代码如下：
class Solution {
public:
int countSubarrays(vector<int>& nums, int k) {
int index = 0;
int res = 0;
int n = nums.size();
// 找出k所在下标idx
for(int i=0;i<n;i++)
{
if(nums[i]==k)
{
index = i;
}
if(nums[i]<k)
nums[i] = -1;
else if(nums[i]==k)
nums[i] = 0;
else
nums[i] = 1;
}
// 枚举idx之后的数与idx+idx之前后缀和的和，和为0或1的数目可计入答案
unordered_map<int,int> m;
int s = 0;
for(int i=index+1;i<n;i++)
{
s += nums[i];
m[s] += 1;
}
m[0] += 1;
s = 0;
// 枚举idx与idx之前后缀和的和，和为0或1的数目可计入答案
for(int i=index;i>=0;i--)
{
s += nums[i];
if(m.find(-s)!=m.end())
{
res += m[-s];
}
if(m.find(1-s)!=m.end())
{
res += m[1-s];
}
}
return res;
}
};
