MayChallenge (59) (60) | Course Schedule And K Closest To Point Origin

There are a total of numCourses courses you have to take, labeled from 0 to numCourses-1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

Example 1:

Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: There are a total of 2 courses to take. 
             To take course 1 you should have finished course 0. So it is possible.

Example 2:

Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Explanation: There are a total of 2 courses to take. 
             To take course 1 you should have finished course 0, and to take course 0 you should
             also have finished course 1. So it is impossible.

Constraints:

• The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
• You may assume that there are no duplicate edges in the input prerequisites.
• 1 <= numCourses <= 10^5

I can't complete this problem utils i read suggestion from Leetcode use Topological Sort.

This is input is a graph. If possible finish all course then not exitst cycle directed on graph. Topological Sort is algorithm is a linear ordering of vertical such that for every directed egde uv, vertect u come before vertect v in ordering.  Topological Sort is working when Graph Not Exist Cycle.

Example graph:

Image from thuytrangcoding

Array visit have 3 status is : 0 (not visit), 1 (visiting), 2 (visited). If dfs graph a vertect = 1 then graph exists Cycle Directed, the result of math is false.

My code:

	class Solution {
	public boolean canFinish(int numCourses, int[][] prerequisites) {
	HashMap<Integer,ArrayList<Integer>> graph = new HashMap<>();
	int[] visit = new int[numCourses];
	for (int[] i:prerequisites){
	if (graph.containsKey(i[0])){
	graph.get(i[0]).add(i[1]);
	}
	else{
	ArrayList<Integer> l = new ArrayList<>();
	l.add(i[1]);
	graph.put(i[0],l);
	}
	}
	for (int i=0; i<numCourses; i++){
	if (!dfs(graph,visit,i)){
	return false;
	}
	}
	return true;
	}
	public boolean dfs(HashMap<Integer,ArrayList<Integer>> graph, int[] visit, int v){
	if (visit[v] == 1){
	return false;
	}
	if (visit[v] == 2){
	return true;
	}
	visit[v] = 1;
	if (graph.containsKey(v)){
	for (int i:graph.get(v)){
	if (!dfs(graph,visit,i)){
	return false;
	}
	}
	}
	visit[v] = 0;
	return true;
	}
	}

view raw CourseSchedule.java delivered with ❤ by emgithub

.

  K Closest Points to Origin

We have a list of points on the plane.  Find the K closest points to the origin (0, 0).

(Here, the distance between two points on a plane is the Euclidean distance.)

You may return the answer in any order.  The answer is guaranteed to be unique (except for the order that it is in.)

Example 1:

Input: points = [[1,3],[-2,2]], K = 1
Output: [[-2,2]]
Explanation: 
The distance between (1, 3) and the origin is sqrt(10).
The distance between (-2, 2) and the origin is sqrt(8).
Since sqrt(8) < sqrt(10), (-2, 2) is closer to the origin.
We only want the closest K = 1 points from the origin, so the answer is just [[-2,2]].

Example 2:

Input: points = [[3,3],[5,-1],[-2,4]], K = 2
Output: [[3,3],[-2,4]]
(The answer [[-2,4],[3,3]] would also be accepted.)

Note:

1. 1 <= K <= points.length <= 10000
2. -10000 < points[i][0] < 10000
3. -10000 < points[i][1] < 10000

This problem can implement with time complex is O(N) use Divide and Conquer, but now i don't understand this. So, i implement it with Max Heap, O(NlogN).

	class Solution {
	public int[][] kClosest(int[][] points, int K) {
	PriorityQueue<int[]> pq = new PriorityQueue<>((a,b)->((b[0]*b[0]+b[1]*b[1]) - (a[0]*a[0]+a[1]*a[1])));
	for (int[] point:points){
	pq.add(point);
	if (pq.size() > K){
	pq.remove();
	}
	}
	int[][] res = new int[K][2];
	while (K--!=0){
	res[K] = pq.remove();
	}
	return res;
	}
	}

view raw KClosestPointToOrigin.java delivered with ❤ by emgithub

Thanks you ! And see you later .