Leetcode第240場周賽題解
【GiantPandaCV導(dǎo)語】本次周賽做得還算順利，主要考察了模擬，二分，單調(diào)棧，拓?fù)渑判蛞约皹湫蜠P等知識點，這里記錄一下題解。
A. 人口最多的年份
解題思路：數(shù)據(jù)范圍比較小，可以直接模擬，從年份開始循環(huán)，然后再循環(huán)logs數(shù)組，如果年份在出生和死亡年份之間就記錄。
AC代碼：
class Solution {
public:
int maximumPopulation(vector<vector<int>>& logs) {
int mx = 0, ans = 0;
for(int i=1950; i<=2050; i++){
int t = 0;
for(int j=0; j<logs.size(); j++){
if(logs[j][0]<=i&&i<logs[j][1]){
t++;
}
}
if(t > mx){
mx = t;
ans = i;
}
}
return ans;
}
};
B. 下標(biāo)對中的最大距離
解題思路：看一下數(shù)據(jù)量1e5，并且數(shù)組是有序的，那么枚舉一個下標(biāo)，二分另外一個下標(biāo)就可以了。不過更好的做法是雙指針，我更擅長寫二分，這里只接寫的二分法的代碼。
AC代碼：
class Solution {
public:
int maxDistance(vector<int>& nums1, vector<int>& nums2) {
int ans = 0;
for(int i=0; i<nums1.size(); i++){
int l = i, r = nums2.size()-1;
int now = -1;
while(l <= r){
int mid=(l+r)>>1;
if(nums2[mid]>=nums1[i]){
l=mid+1;
now=mid;
}
else{
r=mid-1;
}
}
if(now!=-1){
ans = max(ans, now-i);
}
}
return ans;
}
};
C. 子數(shù)組最小乘積的最大值
解題思路：以當(dāng)前為中心，往左往右找不小于最遠(yuǎn)處和，這樣最大，最大。需要注意結(jié)果要取模。
AC代碼:
class Solution {
public:
long long sum[100010];
int mod=1e9+7;
int maxSumMinProduct(vector<int>& nums) {
long long maxx = 0;
int n = nums.size();
for(int i=1; i<=n; i++){
sum[i] = sum[i-1] + nums[i-1];
}
stack <int> s;
for(int i=0; i<=n; i++){
int now = i == n ? -1 : nums[i];
while(!s.empty() && now < nums[s.top()]){
int id = s.top();
s.pop();
int num = nums[id];
if(s.empty()){
maxx = max(maxx, sum[i] * num);
}
else{
maxx = max(maxx, (sum[i] - sum[s.top()+1]) * num);
}
}
s.push(i);
}
maxx %= mod;
return (int)maxx;
}
};
D. 有向圖中最大顏色值
解題思路：顯然，當(dāng)這個有向圖有回路的話結(jié)果無限大，輸出-1。我們可以通過拓?fù)渑判虻姆椒ㄅ袛嘤邢驁D是否有環(huán)，若這個有向圖不具有拓?fù)浯涡?，那么就說明有環(huán)。然后就是對結(jié)果的求解，我們依次枚舉每一個字母，求出這個字母在所有路中的某一條中出現(xiàn)次數(shù)的最大值。根據(jù)前面求出的拓?fù)浯涡駾P一下即可，dp[i]表示以i點為起點的路徑中，當(dāng)前字母c的最大出現(xiàn)次數(shù)，那么轉(zhuǎn)移就是，其中j是i的兒子節(jié)點。
#define mst(a,b) memset((a),(b),sizeof(a))
typedef long long ll;
const int maxn = 300005;
const ll mod = 1e9+7;
const ll INF = 1e9;
const double eps = 1e-9;
int n,m;
int degree[maxn];
char s[maxn];
int dp[maxn];
vector<int>vec[maxn];
vector<int>mp;
bool check()
{
mp.clear();
queue<int>q;
for(int i=1;i<=n;i++)
{
if(degree[i]==0) q.push(i);
}
while(q.size())
{
int u=q.front();
q.pop();
mp.push_back(u);
for(int i=0;i<vec[u].size();i++)
{
degree[vec[u][i]]--;
if(degree[vec[u][i]]==0) q.push(vec[u][i]);
}
}
return mp.size()==n;
}
int solve(int x)
{
mst(dp,0);
char c=x+'a';
int cnt=0;
for(int i=mp.size()-1;i>=0;i--)
{
int u=mp[i];
for(int j=0;j<vec[u].size();j++)
{
dp[u]=max(dp[u],dp[vec[u][j]]);
}
if(s[u-1]==c) dp[u]++;
cnt=max(cnt,dp[u]);
}
return cnt;
}
class Solution {
public:
int largestPathValue(string colors, vector<vector<int>>& edges) {
for(int i=0; i<colors.size(); i++) s[i] =colors[i];
n = colors.size();
for(int i=1;i<=n;i++) vec[i].clear();
m = edges.size();
mst(degree,0);
for(int i=0; i<m; i++){
edges[i][0]++;
edges[i][1]++;
vec[edges[i][0]].push_back(edges[i][1]);
degree[edges[i][1]]++;
}
if(!check()) return -1;
int ans = 0;
for(int i=0;i<26;i++)
{
ans=max(ans,solve(i));
}
return ans;
}
};
總的來說，是一次比較好的周賽體驗QAQ。
歡迎關(guān)注GiantPandaCV, 在這里你將看到獨家的深度學(xué)習(xí)分享，堅持原創(chuàng)，每天分享我們學(xué)習(xí)到的新鮮知識。( ? ?ω?? )?
有對文章相關(guān)的問題，或者想要加入交流群，歡迎添加BBuf微信：