Tags » BF's

Course Schedule II

https://leetcode.com/problems/course-schedule-ii/

  • Cool! Following that idea, I wrote this one completely by myself, nice!
  • Idea:
    • use a queue to hold all zero-degree vertex
    • loop through all other vertices, whenever one vertex’s indegree becomes zero, offer it into the q…
  • 172 more words
Leetcode MEDIUM

Codechef July'16 long challenge

1. Andrash and Stipendium (EGRANDR)
Simulate the problem description. Output is “No” if the student has failed in at least one subject or hasn’t got full score in at least one subject or the subject average is below 4. 349 more words

Codechef

Remove Invalid Parentheses

https://leetcode.com/problems/remove-invalid-parentheses/

I attempted to solve it on my own, but didn’t sort out the ideas, turned to Discuss: jeantimex@ post is easy to follow: https://discuss.leetcode.com/topic/28827/share-my-java-bfs-solution… 228 more words

2016/07

Shortest Distance from All Buildings

https://leetcode.com/problems/shortest-distance-from-all-buildings/

Inspired by this post: https://discuss.leetcode.com/topic/31925/java-solution-with-explanation-and-time-complexity-analysis

Kind of complex BFS, I guess this is why it’s rated as HARD.

As that post explains, it’s pretty straightforward to follow, I just need to be bold to think that we’ll have to do BFS for every single  305 more words

2016/07

Find K Pairs with Smallest Sums

https://leetcode.com/problems/find-k-pairs-with-smallest-sums/

StefanPochmann won again, amazed by his post: https://discuss.leetcode.com/topic/50450/slow-1-liner-to-fast-solutions

First off, as StefanPochmann pointed out, “I found it helpful to visualize the input as an m×n matrix of sums, for example for nums1=, and nums2=:” 472 more words

Leetcode MEDIUM

Serialize and Deserialize Binary Tree

https://leetcode.com/problems/serialize-and-deserialize-binary-tree/

Very excited that I got this problem AC’ed completely by myself. Hooray!

My algorithm: use BFS to do level order traversal, and use Integer.MAX_VALUE to denote terminator. 364 more words

2016/07

UVa : 459 - Graph Connectivity

/*
*   UNION FIND DISJOINT SETS !!
*   Read the code below and relate to family tree !!
*/
#include<bits/stdc++.h>
using namespace std ;
int daddy,dRank;
void make_set(int n){
	for(int i=0;i<n;i++){
		daddy[i]=i;
		dRank[i]=(0);
	}	
}

int findSet(int set){
	if(daddy==set)return set;
	else return (daddy=findSet(daddy));
}

void unionSet(int &babyA , int &babyB){
	//union by rank
	int baby1=findSet(babyA),baby2=findSet(babyB);
	if(dRank>dRank){
		daddy=baby1;
	}
	else {
		daddy=baby2;
		if(dRank==dRank){
			dRank++;
		}
	}
}

int main(){
	int t;
	cin>>t;
	int test=t;
	while(t--){
		string first;
		cin>>ws;
		getline(cin,first);
		int n=first[0]-'A'+1;
		int ans=n;
		make_set(n);
		while(true){
			string s;
			if(!getline(cin,s)||s.empty()) break;
			int A=s[0]-'A';
			int B=s[1]-'A';
			if(findSet(A)!=findSet(B)){
				unionSet(A,B);
				ans--;
			}
		}
		if(t!=test-1) printf("\n");
		cout<<ans<<endl;
	}
	
} 10 more words
Data Structures