leetcode周赛 231

A:水题。

解法1：首先确定一个全为1的串，之后如果在出现1，就返回false

class Solution {
public:
    bool checkOnesSegment(string s) {
        bool flag=true;
        int n=s.size();
        for(int i=0;i<n;){
            if(s[i]=='1'&&flag){
                while(s[i]=='1'){
                    i++;
                }
                flag=false;
                continue;
            }else if(s[i]=='1'&&!flag) return false;
            i++;
        }
        return true;
    }
};

解法2：直接找到最前面的1和最后面的1，若中间的字符串被0分割开来的话，返回false

class Solution {
public:
    bool checkOnesSegment(string s) {
        int i=0,j=s.size()-1;
        while(s[i]=='0') i++;
        while(s[j]=='0') j--;
        for(int k=i;k<=j;k++) if(s[k]=='0') return false;
        return true;
    }
};

B:水题。给定一个数组，和一个goal，要求数组和等于goal，可以向数组内插入元素，但是插入元素x满足，abs(x)<limit;

　ans=abs(sum-goal+limit-1)/limit ; 

class Solution {
public:
    int minElements(vector<int>& nums, int limit, int goal) {
        long long sum=accumulate(nums.begin(),nums.end(),0ll);
        return (abs(sum-goal)+limit-1)/limit;
    }
};

C:题目很复杂，但是思路比较简单。

给定一张联通图，受限路径定义为从1到n中每一条边的前一个点到n的距离小于后一个点到n的距离的一条路径。

首先求出每一个点到n的最短路（spfa或者dijkstra），然后递推的求出1到n的受限路径数。

f [ i ] 定义为 i 到n的受限路径数，将{dist[i],i}按距离排序，那么每次算f [ i ] 的时候需要保证dis [ i ] < dis [ j ] （j<i），而小于i的点的受限路径数量已经被算出来了。

即f [ i ] 需要用到的值已经被算出来了，即递推关系是一个拓扑图，所以递推方案是可行的。

typedef pair<int,int> PII;
class Solution {
public:
    const int mod=1e9+7;
    const int INF=0x3f3f3f3f;
    vector<vector<PII>> g;
    vector<int> dis;
    vector<bool> st;
    vector<int> f;
    void spfa(int n,vector<vector<int>>& edges){
        g.resize(n+1),dis.resize(n+1,INF),st.resize(n+1);
        for(auto edge:edges){
            int a=edge[0],b=edge[1],c=edge[2];
            g[a].push_back({b,c});
            g[b].push_back({a,c});
        }
        queue<int> q;
        dis[n]=0;
        q.push(n);
        while(q.size()){
            int t=q.front();
            q.pop();
            st[t]=false;
            for(auto x:g[t]){
                int j=x.first,w=x.second;
                if(dis[j]>dis[t]+w){
                    dis[j]=dis[t]+w;
                    if(!st[j]){
                        q.push(j);
                        st[j]=true;
                    }
                }
            }
        }
    }

    int get_res(int n){
        f.resize(n+1);
        vector<PII> v;
        for(int i=1;i<=n;i++) v.push_back({dis[i],i});
        sort(v.begin(),v.end());
        f[n]=1;
        for(auto x:v){
            int d=x.first,u=x.second;
            for(auto p:g[u]){
                int j=p.first;
                if(d>dis[j]){
                    f[u]=(f[u]+f[j])%mod;
                }
            }
        }
        return f[1];
    }

    int countRestrictedPaths(int n, vector<vector<int>>& edges) {
        spfa(n,edges);
        return get_res(n);
    }
};

D:给定一个数组和一个k，问保证每个长度为k的区间异或和为0需要改变的数的最小数目。

class Solution {
public:
    const int M=1024,INF=1e8;
    int s[1024];
    int minChanges(vector<int>& nums, int k) {
        int n=nums.size(),m=(n+k-1)/k;
        vector<vector<int>> f(k+1,vector<int>(M,INF));
        f[0][0]=0;
        int sum=0,minv=INF;
        for(int i=1;i<=k;i++){
            memset(s,0,sizeof s);
            int len=m;
            if(n%k && n%k<i) len--;
            for(int j=0;j<len;j++){
                s[nums[j*k+i-1]]++;
            }
            int maxv=0;
            for(int j=0;j<M;j++){
                if(s[j]) maxv=max(maxv,s[j]);
            }
            sum+=len-maxv,minv=min(minv,maxv);
            for(int j=0;j<M;j++){
                for(int u=0;u<len;u++){
                    int x=nums[u*k+i-1],cost=len-s[x];
                    f[i][j]=min(f[i][j],f[i-1][j^x]+cost);
                }
            }
        }
        return min(sum+minv,f[k][0]);
    }
};