LeetCode Weekly Contest 231

21443 ワード
leetcode ps テキストリンク
A.Check if Binary String Has at Most One Segment of Ones
これは「1」に連続する部分があるかどうかを確認する問題です.
class Solution {
public:
    bool checkOnesSegment(string s) {
        int last=-1;
        for(int i=s.size()-1;i>0;i--) {
            if(s[i]=='1') {
                last=i;
                break;
            }
        }
        for(int i=1;i<=last;i++) {
            if(s[i]=='0') return false;
        }
        return true;
    }
};
B. Minimum Elements to Add to Form a Given Sum
これは、nums配列の総和をgoalにするために加えなければならないlimit整数以下の最小数の問題である.numsとgoalの差を簡単に求めた後、limitに分けて、残りは1を加える方法で求めることができます.
class Solution {
public:
    int minElements(vector<int>& nums, int limit, int goal) {
        long long sum=0;
        for(auto it : nums) sum+=it;
        long long diff=abs(goal-sum);
        limit=abs(limit);
        return diff/(long long)(limit)+(diff%limit!=0);
    }
};
C. Number of Restricted Paths From First to Last Node
最短距離を表すdistanceToLastNode(x)を与えられた図において求め、distanceToLastNode(zi) > distanceToLastNode(zi+1), 0 <= i <= k-1を満たす経路数の問題を求める.
多項式で最短距離を求めた後,dfsで上記式を満たす経路数を求めればよい.
class Solution {
public:
    vector<pair<int,int>> graph[20001];
    const long long mod=1e9+7;
    long long dist[20001];
    long long dp[20001];
    
    void dijkstra(int n) {
        priority_queue<pair<long long,int>> pq;
        pq.push({0,n});
        dist[n]=0;
        while(!pq.empty()) {
            long long distance=-pq.top().first;
            int node=pq.top().second;
            pq.pop();
            if(dist[node]<distance) continue;
            for(int i=0;i<graph[node].size();i++) {
                int next=graph[node][i].first;
                long long next_distance=graph[node][i].second+distance;
                if(dist[next]>next_distance) {
                    dist[next]=next_distance;
                    pq.push({-next_distance,next});
                }
            }
        }
    }
    
    long long dfs(int n) {
        if(n==1) {
            return 1;
        }
        
        long long &ret=dp[n];
        if(ret!=-1) return ret%mod;
        ret=0;
        
        for(int i=0;i<graph[n].size();i++) {
            int next=graph[n][i].first;
            if(dist[next]>dist[n]) {
                ret+=dfs(next);
                ret%=mod;
            }
        }
        
        return ret%mod;
    }
    
    int countRestrictedPaths(int n, vector<vector<int>>& edges) {
        for(int i=0;i<edges.size();i++) {
            int u=edges[i][0], v=edges[i][1], w=edges[i][2];
            graph[u].push_back({v,w});
            graph[v].push_back({u,w});
        }
        
        memset(dist,mod,sizeof(dist));
        dijkstra(n);
        
        memset(dp,-1,sizeof(dp));
        
        return (int)(dfs(n)%mod);
    }
};
D. Make the XOR of All Segments Equal to Zero
Mybatis【20】--Mybatis遅延ロードはどのように処理しますか?
Raileloadのレール6を構成する