tags: Weekly Contest

Weekly Contest 345

2682. Find the Losers of the Circular Game(Easy)

限制 :

• 1 <= k <= n <= 50

Solution

注意題目，第

$t$ 輪的下一個人是當前位置的下

$k\ast t$ 個人，模擬整個過程即可。

時間複雜度:

$O(n)$

空間複雜度:

$O(n)$

程式碼:

class Solution {
public:
    vector<int> circularGameLosers(int n, int k) {
        vector<bool> chosed(n);
        int now=0;
        for(int i=0;i<n;i++){
            if(chosed[now])
                break;
            chosed[now]=true;
            now=(now+(i+1)*k)%n;
        }

        vector<int> ans;
        for(int i=0;i<n;i++){
            if(!chosed[i])
                ans.push_back(i+1);
        }
        return ans;
    }
};

2683. Neighboring Bitwise XOR(Medium)

限制 :

• n == derived.length
• 1 <= n <= 105
• The values in derived are either 0's or 1's

Solution

$\{\begin{array}{l}derived[i]=original[i]\oplus original[0],\text{if}i=n-1\\ derived[i]=original[i]\oplus original[i+1],\text{if}i\ne n-1\end{array}$

根據上述條件得知若要使original存在的必要條件是:

$derived[0]\oplus derived[1]\oplus ...\oplus derived[n-2]\oplus derived[n-1]=0$

所以只要計算該條件即可得知答案。

時間複雜度:

$O(n)$

空間複雜度:

$O(1)$

程式碼:

class Solution {
public:
    bool doesValidArrayExist(vector<int>& derived) {
        bool ans=0;
        for(auto &num: derived)
            ans^=num;
        return !ans;
    }
};

2684. Maximum Number of Moves in a Grid(Medium)

限制 :

• m == grid.length
• n == grid[i].length
• 2 <= m, n <= 1000
• 4 <= m * n <= 105
• 1 <= grid[i][j] <= 106

Solution

用dp解，每一個cell可以往右上、右、右下走，所以只要得到右上、右、右下三個cell的答案取max就可以得到當前cell最多可以走多遠，dp式子如下:

$dp[i][j]=max(dp[i-1][j+1],dp[i][j+1],dp[i+1][j+1])+1$

但題目還需要額外判定下一個cell的值要大於當前cell的值，把這個條件加入dp判斷式即可。

最終查詢第一個column裡的最大值即是答案。

時間複雜度:

$O(n\ast m)$

空間複雜度:

$O(n\ast m)$

程式碼:

class Solution {
public:
    int maxMoves(vector<vector<int>>& grid) {
        int n=grid.size(), m=grid[0].size();
        vector<vector<int> > mat(n, vector<int>(m));
        
        for(int j=m-1;j>=1;j--){
            for(int i=0;i<n;i++){
                if(i !=0&&grid[i-1][j-1]<grid[i][j])
                    mat[i-1][j-1]=max(mat[i-1][j-1], mat[i][j]+1);
                if(grid[i][j-1]<grid[i][j])
                    mat[i][j-1]=max(mat[i][j-1], mat[i][j]+1);
                if(i !=n-1&&grid[i+1][j-1]<grid[i][j])
                    mat[i+1][j-1]=max(mat[i+1][j-1], mat[i][j]+1);
            }
        }
        int ans=0;
        for(int i=0;i<n;i++)
            ans=max(ans, mat[i][0]);
        return ans;
    }
};

2685. Count the Number of Complete Components(Medium)

限制 :

• 1 <= n <= 50
• 0 <= edges.length <= n * (n - 1) / 2
• edges[i].length == 2
• 0 <= ai, bi <= n - 1
• ai != bi
• There are no repeated edges.

Solution

對於每個connected component，計算是否每個node都連到這個component的其他node，如果符合就是complete connected component。

確認每個connected component即可算出答案。

時間複雜度:

$O(n^3)$

空間複雜度:

$O(n^2)$

程式碼:

class Solution {
public:
    vector<bool> isvisited;
    set<int> si;
    void dfs(int now, vector<vector<bool> > &graph){
        isvisited[now]=true;
        si.insert(now);
        for(int i=0;i<graph.size();i++){
            if(!isvisited[i]&&graph[now][i])
                dfs(i, graph);
        }
    }
    bool check(vector<vector<bool> > &graph){
        for(auto it=si.begin();it !=si.end();it++){
            auto ir=it;
            ir++;
            for(;ir !=si.end();ir++)
                if(!graph[*it][*ir])
                    return false;
        }
        return true;
    }
    int countCompleteComponents(int n, vector<vector<int>>& edges) {
        vector<vector<bool> > graph(n, vector<bool>(n));
        for(auto &edge: edges){
            graph[edge[0]][edge[1]]=true;
            graph[edge[1]][edge[0]]=true;
        }
        isvisited.resize(n);
        for(int i=0;i<n;i++)
            isvisited[i]=false;
        int ans=0;
        for(int i=0;i<n;i++){
            if(!isvisited[i]){
                dfs(i, graph);
                ans += check(graph);
                si.clear();
            }
        }
        return ans;
    }
};

Optimized Solution - dfs

參考這篇，主要優化的地方是簡化check function的邏輯。

對於一個節點數為

$n$ 的connected component，如果其擁有

$\frac{n\ast (n-1)}{2}$ 條edge，那他就是一個complete connected component。

所以只要計算目前的connected component有幾個node以及有幾條edge，根據上述定理判斷是否是complete connected component即可。

m = edges.length

時間複雜度:

$O(n+m)$

空間複雜度:

$O(n+m)$

程式碼:

class Solution {
public:
    vector<bool> isvisited;
    int number_of_nodes;
    int number_of_edges;
    void dfs(int now, vector<vector<int> > &graph, vector<bool> &isvisited){
        isvisited[now]=true;
        number_of_nodes++;
        number_of_edges+=graph[now].size();

        for(int i=0;i<graph[now].size();i++){
            int next = graph[now][i];
            if(!isvisited[next])
                dfs(next, graph, isvisited);
        }
    }
    int countCompleteComponents(int n, vector<vector<int>>& edges) {
        vector<vector<int> > graph(n);
        for(auto &edge: edges){
            graph[edge[0]].push_back(edge[1]);
            graph[edge[1]].push_back(edge[0]);
        }

        vector<bool> isvisited(n);
        int ans=0;
        for(int i=0;i<n;i++){
            if(!isvisited[i]){
                number_of_edges = 0, number_of_nodes = 0;
                dfs(i, graph, isvisited);
                ans += number_of_nodes*(number_of_nodes-1) == number_of_edges;
            }
        }
        return ans;
    }
};

Optimized Solution - disjoint set

參考這篇。

判斷是否是complete connected component的方法與上一個解答一樣。

與上個解答不同的是，使用disjoint set來快速計算每個connected component的node與edge的數量。

disjoint set的完整說明可以參考這一篇

m = edges.length

時間複雜度:

$O(n+m)$

空間複雜度:

$O(n)$

程式碼:

class Solution {
    #define MAX 55
public:
    int dsu[MAX], rank[MAX], number_of_edge[MAX];
    int dsu_find(int idx){
        return dsu[idx]==idx?idx:dsu[idx]=dsu_find(dsu[idx]);
    }
    void dsu_union(int a, int b){
        int pa=dsu_find(a), pb=dsu_find(b);
        number_of_edge[pa]++;
        if(pa !=pb){
            dsu[pa]=pb;
            rank[pb]+=rank[pa];
            number_of_edge[pb]+=number_of_edge[pa];
        }
    }
    int countCompleteComponents(int n, vector<vector<int>>& edges) {
        for(int i=0;i<n;i++){
            dsu[i]=i;
            rank[i]=1;
        }
        for(auto &edge: edges)
            dsu_union(edge[0], edge[1]);

        int ans=0;
        for(int i=0;i<n;i++){
            if(dsu[i]==i){
                ans+=rank[i]*(rank[i]-1)/2==number_of_edge[i];
            }
        }
        return ans;
    }
};