[LeetCode 周赛179]

1374. 生成每种字符都是奇数个的字符串

这道贼简单的题把我一天的郁闷心情搞没了= =

class Solution {
public:
    string generateTheString(int n) {
        if(n%2) return string(n,'a');
        else return string(n-1,'a')+'b';
    }
};

1375. 灯泡开关 III

直接照题意模拟就行，很慢

class Solution {
public:
    int numTimesAllBlue(vector<int>& light) {
        int n=light.size();
        int isl[n]={0};
        int res=0,last=0,curmax=-1;
        for(auto i:light){
            isl[i-1]=1;
            curmax=max(i,curmax);
            int flag=1;
            for(int j=last;j<curmax;j++){
                if(isl[j]==0){
                    flag=0;break;
                }
            }
            if(flag)last=i;
            res+=flag;
        }
        return res;
    }
};

牛逼的y总做法

class Solution {
public:
    int numTimesAllBlue(vector<int>& light) {
        int res=0,last=0,curmax=-1;
        for(int i=0;i<light.size();i++){
            curmax=max(light[i],curmax);
            res+=(i+1==curmax);
        }
        return res;
    }
};

1376. 通知所有员工所需的时间

class Solution {
public:
    vector<vector<int>> son;
    int numOfMinutes(int n, int headID, vector<int>& manager, vector<int>& informTime) {
        son=vector<vector<int>>(n);
        for(int i=0;i<manager.size();i++){
            if(i==headID)continue;
            son[manager[i]].push_back(i);
        }
        return dfs(headID,informTime);
    }
    
    int dfs(int u,vector<int>& informTime){
        int res=0;
        for(auto s:son[u]){
            res=max(res,dfs(s,informTime));
        }
        return res+informTime[u];
    }
};

1377. T 秒后青蛙的位置

困难，海星，就dfs，一开始我以为的思路是bfs，但是bfs和dfs能解决的问题一样，dfs能解决的bfs能解决，反过来也一样。

class Solution {
public:
    vector<vector<int>> e;
    double frogPosition(int n, vector<vector<int>>& edges, int t, int target) {
        e=vector<vector<int>>(n+1);
        for(auto edge:edges){
            int a=edge[0],b=edge[1];
            // 题目上是无向树，需要双向加边
            e[a].push_back(b);
            e[b].push_back(a);
        }
        return dfs(1,-1,t,target,1);        
        
    }
    
    double dfs(int u,int father,int t,int target,double p){
        if(!t){//时间用完
            if(u==target)return p;
            return 0;
        }
        int k=e[u].size();
        if(u!=1)k--;
        
        if(!k){//是叶节点
            if(u==target)return p;
            return 0;
        }
        
        double res=0;
        for(auto s :e[u]){
            if(s!=father){
                //除了有概率的那一条路是概率值，其他的路都是0
                res=max(res,dfs(s,u,t-1,target,p*1.0/k));
            }
        }
        return res;
    }
};