這周周賽沒有什麼過多難的 也是可以自己寫完的 (蕪湖)
第一道題
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;
}
};
![【趨高機器視覺】機器視覺技術原了解析及解決方案[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)