Leetcode Weekly Contest #76

23 Mar 2018

Reading time ~3 minutes

800. Similar RGB Color

For any given six digits hexadecimal number, return a closest shorthand convertible number (#AABBCC <-> #ABC). Example : #09f166 -> #11ee66

Solution

Considering a hexadecimal shorthand number #a, the difference between #a and #a±1 is (16+1)/2, so if there’s a number who’s difference with #a is larger than 8, then it doesn’t belong to the shorthand. Based on this property, we can determine whether a 2 digit hexadecimal belongs to its first digit’s shorthand.

class Solution:
    def similarRGB(self, color):
        digits = []
        for i in range(1, 7, 2):
            digits.append(int(color[i+1],16) - int(color[i],16))

        out = []
        for i in range(3):
            if digits[i] > 8:
                out.append(hex(int(color[1+2*i],16)+1).split('x')[-1])
            elif abs(digits[i]) <= 8:
                out.append(hex(int(color[1+2*i],16)).split('x')[-1])
            else:
                out.append(hex(int(color[1+2*i],16)-1).split('x')[-1])

        return '#' + out[0] + out[0] + out[1] + out[1] + out[2] + out[2]

Status

Time Complexity : O(n)

Accepted

801. Minimum Swaps To Make Sequences Increasing

Given two sequences, return the minimum number of swaps to make both sequences strictly increasing. It is guaranteed that the given input always makes it possible.

Solution

class Solution:
    def minSwap(self, A, B):
        """
        :type A: List[int]
        :type B: List[int]
        :rtype: int
        """
        n0 = 0
        s0 = 1
        for i in range(len(A) - 1):
            n1 = 1001
            s1 = 1001
            if A[i] < A[i+1] and B[i] < B[i+1]:
                n1 = min(n1,n0)
                s1 = min(s1,s0+1)
            if A[i] < B[i+1] and B[i] < A[i+1]:
                n1 = min(n1,s0)
                s1 = min(s1,n0+1)
            n0 = n1
            s0 = s1
            
        return min(n1,s1)

Status

Time Complexity : O(n)

Accepted

802. Find Eventual Safe States

Solution

class Solution:
    def eventualSafeNodes(self, graph):
        
        def build_rev(graph):
            rev = [[] for i in range(len(graph))]
            for i, edges in enumerate(graph):
                for j, edge in enumerate(edges):
                    rev[edge].append(i)
            return rev

        def dfs(graph,rev,vis,i):
            vis[i] = True
            for edge in graph[i]:
                if vis[edge] == False:
                    dfs(graph,rev,vis,edge)
            if len(graph[i])== 0:
                for edge in rev[i]:
                    graph[edge].remove(i)
                    dfs(graph,rev,vis,edge)
                rev[i] = []

        rev = build_rev(graph)
        vis = [False]*len(graph)
        save = []
        
        for i in range(len(graph)):
            dfs(graph,rev,vis,i)
            if len(graph[i]) == 0:
                save.append(i)
               
        return save

Status

Time Complexity : O(V+E)

Accepted

803. Bricks Falling When Hit

Solution

#define pb push_back
int parent[40001];
int size[40001];
int sgrid[40001];

class Solution {
public:
    int find(int i){
        if (parent[parent[i]] != i)
            parent[i] = find(parent[i]);
        return parent[i];
    }

    void dsu(int a,int b){
        int parent_a = find(a);
        int parent_b = find(b);
        if (parent_a == parent_b)
            return;
        else if(size[parent_a] >= size[parent_b] || parent_a == 0){
            size[parent_a] += size[parent_b];
            parent[parent_b] = parent_a;
        }
        else if(size[parent_a] <  size[parent_b] || parent_b == 0){
            size[parent_b] += size[parent_a];
            parent[parent_a] = parent_b;
        }
        return;
    }     
    vector<int> hitBricks(vector<vector<int>>& grid, vector<vector<int>>& hits) {
        vector<int> sgrid,shits,ret;
        int row = grid.size(), col = grid[0].size();

        sgrid.pb(1);   
        size[0] = 1;
        parent[0] = 0;
        for (int i = 0;i < row; ++i)
            for (int j = 0;j < col; ++j)
                sgrid.pb(grid[i][j]);

        for (int i = 0;i < hits.size(); ++i){
            int ij = 1 + (col * hits[i][0]) + hits[i][1];
            if (sgrid[ij] == 0)
                shits.pb(-1);
            else{
                shits.pb(ij);
                sgrid[ij] = 0;
            }
        }

        for (int i = 1;i < sgrid.size(); ++i){
            if(sgrid[i] == 1){
                size[i] = 1;
                parent[i] = i;
                if ((i-1) / col == 0)
                    dsu(0,i);
                if ((i-1) / col > 0)
                    if (sgrid[i - col] == 1)
                        dsu(i-col,i);
                if ((i-1) % col > 0)
                    if (sgrid[i - 1] == 1)
                        dsu(i-1,i);
            }
        }

        for (int x = shits.size() - 1; x >= 0; --x){
            if (shits[x] == -1)
                ret.insert(ret.begin(),0);
            else{
                int i = shits[x];
                int old_size = size[0], new_size;
                sgrid[i] = 1;
                parent[i] = i;
                size[i] = 1;
                
                if ((i-1)/col == 0)
                    dsu(0,i);
                if ((i-1)/col < row - 1)
                    if(sgrid[i + col] == 1)
                        dsu(i,i+col);
                if ((i-1)/col > 0)
                    if(sgrid[i - col] == 1)
                        dsu(i-col,i);
                if ((i-1)%col < col - 1)
                    if(sgrid[i + 1] == 1)
                        dsu(i,i+1);
                if ((i-1)%col > 0)
                    if(sgrid[i - 1] == 1)
                        dsu(i-1,i);

                if (find(i) == 0){
                    new_size = size[0];
                    ret.insert(ret.begin(),(new_size - old_size - 1));
                }
                else
                    ret.insert(ret.begin(),0);
            }
        }
        return ret;
    }
};

Status

Time Complexity : O(N^2)

Accepted