LeetCode的第230場周賽題解
【GiantPandaCV導(dǎo)語】這是LeetCode的第230場周賽的題解，本期考察的知識點(diǎn)有暴力，搜索，貪心，單調(diào)棧等等。
比賽鏈接
https://leetcode-cn.com/contest/weekly-contest-230/
題目一：統(tǒng)計匹配檢索規(guī)則的物品數(shù)量
解題思路：先用一個flag記錄下ruleKey是哪一種類型，然后根據(jù)ruleValue判斷一下即可。時間復(fù)雜度：解題代碼如下：
class Solution {
public:
int countMatches(vector<vector<string>>& items, string ruleKey, string ruleValue) {
int flag=0;
if(ruleKey=="color")
flag=1;
else if(ruleKey=="name")
flag=2;
int ans=0;
for(int i=0;i<items.size();i++)
if(ruleValue==items[i][flag])
ans++;
return ans;
}
};
題目二：最接近目標(biāo)價格的甜點(diǎn)成本
解題思路：首先看數(shù)據(jù)范圍基料和配料都最多只有10種，而對于每種配料只有三種可能：不放，放一份，放兩份。這里就直接采取暴力搜索把配料的可能性都存下來，然后直接暴力枚舉基料與所有配料的結(jié)果，維護(hù)答案即可。時間復(fù)雜度：解題代碼如下：
class Solution {
public:
vector<int> tot;
void count(vector<int>& toppingCosts,int pos,int tmp)
{
tot.push_back(tmp);
if(pos==toppingCosts.size())
return ;
for(int i=0;i<=2;i++)
count(toppingCosts,pos+1,tmp+toppingCosts[pos]*i);
}
int closestCost(vector<int>& baseCosts, vector<int>& toppingCosts, int target) {
count(toppingCosts,0,0);
int ans=9999999;
for(int i=0;i<baseCosts.size();i++)
for(int j=0;j<tot.size();j++)
{
int now=baseCosts[i]+tot[j];
if(abs(now-target)<abs(ans-target)||(abs(now-target)==abs(ans-target)&&now<ans))
ans=now;
}
return ans;
}
};
題目三：通過最少操作次數(shù)使數(shù)組的和相等
解題思路：首先判斷不可能的情況，如果兩個數(shù)組長度大于6倍，那么一定不可能，否者就是存在答案的，然后來判斷最少操作次數(shù)，假設(shè)A數(shù)組的和大于B數(shù)組的和，那么對于A數(shù)組需要對里面的數(shù)進(jìn)行減小，對B數(shù)組的數(shù)進(jìn)行增大，每次操作即可縮小兩個數(shù)組間的差值，為了使得操作次數(shù)最小化，每次操作都需要貪心選取縮小的差值最大化，那么對兩個數(shù)組維護(hù)一下差值最大化，然后排個序，從大到小枚舉直到數(shù)組間的差值小于0。
時間復(fù)雜度：解題代碼如下：
class Solution {
public:
int minOperations(vector<int>& nums1, vector<int>& nums2) {
if(min(nums1.size(),nums2.size())*6<max(nums1.size(),nums2.size()))
return -1;
int ans1=0,ans2=0;
for(int i=0;i<nums1.size();i++)
ans1+=nums1[i];
for(int i=0;i<nums2.size();i++)
ans2+=nums2[i];
vector<int> v;
if(ans1>ans2)
swap(nums1,nums2);
for(int i=0;i<nums1.size();i++)
v.push_back(abs(6-nums1[i]));
for(int i=0;i<nums2.size();i++)
v.push_back(abs(nums2[i]-1));
int tot=abs(ans1-ans2),pos=0;
sort(v.rbegin(),v.rend());
while(tot>0)
tot -= v[pos++];
return pos;
}
};
題目四：車隊(duì) II
解題思路：給出了n個車的起始位置和初速度，每個車的方向相同，如果車輛相遇會合并成一個車隊(duì)，此時車隊(duì)的速度為車隊(duì)里的最慢速度。由于是求每輛車與下一輛車的相遇時間，那么首先想到的是能否與下一輛車相遇，那么就需要這輛車的速度大于下一輛車，否則就需要下一輛車被相遇后拖慢，除此之外就不能相遇，那么對于這輛車與后面相遇，對于前面的車是沒有關(guān)系的，我們用一個單調(diào)棧來從左往右存車，車速逐漸降低，棧底最慢，棧頂最快，那么對于這輛車，如果棧頂快，就只能一直pop到慢車才能相遇，此時棧頂就是慢車了，如果這輛車不會消失，那么就肯定能相遇，如果它會消失，則是需要計算在它消失之前能否追上它這輛車，如果能追上，那么就與這輛車相遇，否則那就只有繼續(xù)pop判斷下一輛車。時間復(fù)雜度：解題代碼如下：
class Solution {
public:
vector<double> getCollisionTimes(vector<vector<int>>& cars) {
vector<double>ans(cars.size());
stack<int>S;
for(int i=cars.size()-1;i>=0;i--)
{
while(S.size())
{
if(cars[S.top()][1]>=cars[i][1]) //棧頂車速太快追不上，判斷下一輛車
S.pop();
else
{
if(ans[S.top()]<0) //還存在
break;
if(ans[S.top()]*(cars[i][1]-cars[S.top()][1])>cars[S.top()][0]-cars[i][0]) //已經(jīng)消失了，但是在消失前就追上了
break;
//否則與這輛車就遇不到，那就看下一輛車
S.pop();
}
}
//維護(hù)這輛車的答案
if(S.empty())
ans[i]=-1;
else
ans[i]=(double(cars[S.top()][0]-cars[i][0]))/(cars[i][1]-cars[S.top()][1]);
S.push(i);
}
return ans;
}
};
歡迎關(guān)注GiantPandaCV, 在這里你將看到獨(dú)家的深度學(xué)習(xí)分享，堅(jiān)持原創(chuàng)，每天分享我們學(xué)習(xí)到的新鮮知識。( ? ?ω?? )?
有對文章相關(guān)的問題，或者想要加入交流群，歡迎添加BBuf微信：
為了方便讀者獲取資料以及我們公眾號的作者發(fā)布一些Github工程的更新，我們成立了一個QQ群，二維碼如下，感興趣可以加入。