Leetcode: Walls ang Gates

You are given a m x n 2D grid initialized with these three possible values.
-1 – A wall or an obstacle.
0 – A gate.
INF – Infinity means an empty room. We use the value to represent INF as you may assume that the distance to a gate is less than 2147483647.
Fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, it should be filled with INF.


 public class Solution {
    public static final int[] d = {0, 1, 0, -1, 0};

    public void wallsAndGates(int[][] rooms) {
        if (rooms.length == 0) return;
        for (int i = 0; i < rooms.length; ++i)
            for (int j = 0; j < rooms[0].length; ++j)
                if (rooms[i][j] == 0) bfs(rooms, i, j);
    }

    private void bfs(int[][] rooms, int i, int j) {
        int m = rooms.length, n = rooms[0].length;
        Deque queue = new ArrayDeque<>();
        queue.offer(i * n + j); // Put gate in the queue
        while (!queue.isEmpty()) {
            int x = queue.poll();
            i = x / n; j = x % n;
            for (int k = 0; k < 4; ++k) {
                int p = i + d[k], q = j + d[k + 1];
                if (0 <= p && p < m && 0 <= q && q < n && rooms[p][q] > rooms[i][j] + 1) {
                    rooms[p][q] = rooms[i][j] + 1;
                    queue.offer(p * n + q);
                }
            }
        }
    }
}



 public class Solution {
    private static int[] d = {0, 1, 0, -1, 0};

    public void wallsAndGates(int[][] rooms) {
        for (int i = 0; i < rooms.length; i++)
            for (int j = 0; j < rooms[0].length; j++)
                if (rooms[i][j] == 0) dfs(rooms, i, j);
    }

    public void dfs(int[][] rooms, int i, int j) {
        for (int k = 0; k < 4; ++k) {
            int p = i + d[k], q = j + d[k + 1];
            if (0<= p && p < rooms.length && 0<= q && q < rooms[0].length &&
                rooms[p][q] > rooms[i][j] + 1) {
                rooms[p][q] = rooms[i][j] + 1;
                dfs(rooms, p, q);
            }
        }
    }
}

recover the height from relative array

recover the height from input array, firstly create one array which has order from hight to low

Implementation max heap

implementation max heap (1)

Leetcode: course scheule

// Class to represent a graph
class Graph
{
private:
    int V;    // No. of vertices'

    // Pointer to an array containing adjacency listsList
    vector> adj;
    vector result; // the order for vertics being sorted.
    vectorinDegree;
    int count;
public:
    Graph(int _V)// Constructor
    {
        V = _V;
        adj = vector>(V);
        inDegree = vector(V,0);
        count = 0;
    };  

    // function to add an edge to graph
    void addEdge(int v, int w)
    {
        adj[w].push_back(v);
        inDegree[v]++;
    };

    // prints a Topological Sort of the complete graph
    void topologicalSort()
    {
        // find all in_degree==0, and mark them as visited(set inDegree to -1)
        queue stack;
        for(int i=0; i            if(!inDegree[i]){
                stack.push(i);
                result.push_back(i);
                inDegree[i]=-1; // maked as visited
                count++;
            }
        }
        // pop a node from queue, decrease the degree of the neighbours and push the degree==0   
        while(!stack.empty()){
            int cur=stack.front();
            stack.pop();
            for(int i=0; i                inDegree[adj[cur][i]]--;
                if(inDegree[adj[cur][i]]==0){
                    count++;
                    stack.push(adj[cur][i]);
                    result.push_back(adj[cur][i]);
                    inDegree[adj[cur][i]]=-1;
                }
            }
        }
    };
  
    vector output()
    {
        if(count==V)    return result;
        else return vector();
    }
};


class Solution {
public:
    vector findOrder(int numCourses, vector>& prerequisites) {
        Graph  graph(numCourses);
        vector result;
        for(auto it = prerequisites.begin();it!=prerequisites.end();it++ )
            graph.addEdge((*it).first,(*it).second);
           
        graph.topologicalSort(); // sorting
      
        result = graph.output();
        return result;
    }
};

WeightedUnion2DFind algorithm

class WeightedUnion2DFind
{
public:
    WeightedUnion2DFind(int m, int n,int cnt)
    {
        for(int i = 0;i        for(int i = 0;i        count = cnt;
        M = m;
        N = n;
    }
    int size(){return count++;}
   
    // find root id for current node
    int find(int p)
    {
         while(p!=ids[p]) p= ids[p];
         return p;
    }
    bool connected(int p,int q)
    {
        return find(p) == find(q);
    }
    void Union(int p, int q) //replace the sets containing two items by their union.
    {
        int rootP = find(p);
        int rootQ = find(q);
        if (rootP == rootQ)
            return;
       
        if (szs[rootP] < szs[rootQ]) ids[rootP] = rootQ;
        else if (szs[rootP] == szs[rootQ]) {
            ids[rootQ] = rootP;
            szs[rootP] += 1;
        }
        else
            ids[rootQ] = rootP;
        count--;
    }
private:
      vector ids; // id[i] = parent of i
      vector szs; // sz[i] = number of objects in subtree rooted at i
      int M,N,count;
};

class Solution {
public:
    int numIslands(vector>& grid) {
        int m = grid.size();
        if(m == 0) return 0;
        int n = grid[0].size();
        int count = 0;
        for(int i = 0;i            for(int j = 0;j                if(grid[i][j]=='1') count++;
        WeightedUnion2DFind UF(m,n,count);
        vector> visited(m,vector(n));
        int direction[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
        for(int i = 0;i            for(int j = 0;j            {
                if(grid[i][j]=='1')
                {
                   
                    //check all neigboring pixels.
                    for(int k = 0;k<4 br="" k="">                    {
                        int dx = i+direction[k][0];
                        int dy = j+direction[k][1];
                        if(!(dx>=0 && dx=0 && dy                        if( grid[dx][dy]=='1')
                            UF.Union(i*n+j,dx*n+dy);
                    }
                }
            }
        return UF.size();
    }   
};

Trie Implementation

class TrieNode {
public:
    TrieNode* dict[26];
    bool hasWord;   
    // Initialize your data structure here.
    TrieNode() {
        memset(dict,0,sizeof(dict));
        hasWord = false;
    }
};

class Trie {
public:
    Trie() {
        root = new TrieNode();
    }

// Inserts a word into the trie.
void insert(string word) {
    int i = 0;
    TrieNode * curr = root;
    while(i
        if( curr->dict[word[i] - 'a'] == nullptr){
            curr->dict[word[i]-'a'] = new TrieNode();
        }
        if(i == word.size()-1){
        curr->dict[word[i]-'a']->hasWord = true;
        }
        curr = curr->dict[word[i] - 'a'];
        i++;
    }
    return;
}

// Returns if the word is in the trie.
    bool search(string word) {
        int i = 0;
        TrieNode *curr = root;
        while(i            if(curr->dict[word[i]-'a'] == nullptr){
                return false;
            }
            if( i == word.size()-1){
                return curr->dict[word[i]-'a']->hasWord;
            }
            curr = curr->dict[word[i] - 'a'];
            i++;
        }
        return false;       
    }

    // Returns if there is any word in the trie
    // that starts with the given prefix.
    bool startsWith(string prefix) {
        TrieNode *curr = root;
        for(auto c:prefix){
            if(curr->dict[c-'a'] == nullptr)
                return false;
            curr = curr->dict[c-'a'];   
        }
        return true;
    }

private:
    TrieNode* root;
};

KMP algorithm

LeetCode: KMP algorithm
	#include
	#include
	#include
	int *compute_prefix_function(char *pattern, int psize)
	{
	int k = -1;
	int i = 1;
	int *pi = malloc(sizeof(int)*psize);
	if (!pi)
	return NULL;
	pi[0] = k;
	for (i = 1; i < psize; i++) {
	while (k > -1 && pattern[k+1] != pattern[i])
	k = pi[k];
	if (pattern[i] == pattern[k+1])
	k++;
	pi[i] = k;
	}
	return pi;
	}
	int kmp(char *target, int tsize, char *pattern, int psize)
	{
	int i;
	int *pi = compute_prefix_function(pattern, psize);
	int k = -1;
	if (!pi)
	return -1;
	for (i = 0; i < tsize; i++) {
	while (k > -1 && pattern[k+1] != target[i])
	k = pi[k];
	if (target[i] == pattern[k+1])
	k++;
	if (k == psize - 1) {
	free(pi);
	return i-k;
	}
	}
	free(pi);
	return -1;
	}
	int main(int argc, const char *argv[])
	{
	char target[] = "ABC ABCDAB ABCDABCDABDE";
	char *ch = target;
	char pattern[] = "ABCDABD";
	int i;
	i = kmp(target, strlen(target), pattern, strlen(pattern));
	if (i >= 0)
	printf("matched @: %s\n", ch + i);
	return 0;
	}

Jump to Line