第97场周赛

用户1145562

发布于 2020-10-23 04:10:45

22700

代码可运行

文章被收录于专栏：LC刷题LC刷题

运行总次数：0

代码可运行

传送门

####

884. 两句话中的不常见单词

题解：根据藐视，只需要正确分割统计字符串A和字符串B，之后进行比较得出次数为一的子串即可。

vector<string> uncommonFromSentences(string A, string B) {
        vector<string>ret;
        map<string,int>tmp_A;
        for(int i=0,j=0;i<A.size()&&j<A.size();j++){
            if(A[j]==' '){
                tmp_A[A.substr(i,j-i)]++;
                i = j+1;
            }
            if(j==A.size()-1){
                tmp_A[A.substr(i,j-i+1)]++;
            }     
        }
    
        for(int i=0,j=0;i<B.size()&&j<B.size();j++){
            if(B[j]==' '){
                tmp_A[B.substr(i,j-i)]++;
                i = j+1;
            }
            if(j==B.size()-1)
                tmp_A[B.substr(i,j-i+1)]++;
        }
    
        for(auto i:tmp_A){
            if(i.second==1) ret.push_back(i.first);
        }
        return ret;
    }

885. 螺旋矩阵 III

题解：只要定义好方向，在合适的地方转向即可。

vector<vector<int>> spiralMatrixIII(int R, int C, int r0, int c0) {
        vector<vector<int>>ret = {{r0,c0}};
        int dx = 0,dy=1,n=0,step=1;
        while(ret.size()<R*C){
            for(int i=0;i<step;i++){
                r0+=dx;
                c0+=dy;
                if(r0>=0&&r0<R&&c0>=0&&c0<C)ret.push_back({r0,c0});
            }
            n++;
            if(n%2==0) step++;
            swap(dx,dy);
            dy  = -1*dy;
        }
        return ret;
    }

886. 可能的二分法

题解：根据描述，本质上是要如何对图进行二分，使用DFS进行染色划分即可。

bool possibleBipartition(int N, vector<vector<int>>& dislikes) {
        vector<int>color(N+1,-1);
        vector<vector<int>>graph(N+1);
        for(auto i:dislikes){
            graph[i[0]].push_back(i[1]);
            graph[i[1]].push_back(i[0]);
        }
        
        for(int i=1;i<N+1;i++){
            DFS(color,i,graph);
        }
        for(auto i:dislikes){
            if(color[i[0]]==color[i[1]]){
                return false;
            }
        }
        return true;
    }
    void DFS(vector<int>&color,int n,vector<vector<int>>&graph){
        if(color[n]==-1){
            color[n]=1;
        }
        for(auto point:graph[n]){
            if(color[point]==-1) {
                color[point]=!color[n];
                DFS(color,point,graph);  
            }
        }
    }