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:
.
  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).
Thanks you ! And see you later .

Nhận xét

Bài đăng phổ biến từ blog này

Hiểu về Norm Regularization

Những thuật toán nền tảng trong lĩnh vực Trí tuệ nhân tạo (Artificial Intelligence I)