Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit10e8ef1

Browse files
committed
add more solutions
1 parent067b35b commit10e8ef1

15 files changed

+475
-86
lines changed

‎10 Regular Expresion Matching.js

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -53,7 +53,7 @@ var isMatch = function(s, p) {
5353
dp[i][j]=true;
5454
}
5555
}elseif(j>1){// '*' cannot be the first element
56-
if(dp[i][j-1]||dp[i][j-2]){
56+
if(dp[i][j-2]){// 0 Occurance
5757
dp[i][j]=true;
5858
}elseif(i>0&&(p[j-2]==s[i-1]||p[j-2]=='.')&&dp[i-1][j]){
5959

‎124 Binary Tree Maximum Path Sum.js

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -42,7 +42,7 @@ var maxPathSum = function(root) {
4242

4343
// maxVal as if we end counting value here, what will be the maximum val
4444
// leftVal and rightVal can be negative values
45-
maxVal=Math.max(maxVal,Math.max(ps1,ps2));
45+
maxVal=Math.max.apply(null,[maxVal,ps1,ps2]);
4646

4747
// return ps1 only since, ps2 cannot be combined with the parent node
4848
// leftVal and rightVal can be negative values, however, we can to see if combining with values down below can give higher number

‎133 Clone Graph.js

Lines changed: 10 additions & 13 deletions
Original file line numberDiff line numberDiff line change
@@ -21,6 +21,12 @@
2121
// / \
2222
// \_/
2323

24+
// Pocket Gems Google Uber Facebook
25+
// Hide Tags Depth-first Search Breadth-first Search Graph
26+
// Hide Similar Problems (H) Copy List with Random Pointer
27+
28+
29+
2430
/**
2531
* Definition for undirected graph.
2632
* function UndirectedGraphNode(label) {
@@ -42,21 +48,12 @@ var cloneGraph = function(graph) {
4248
}
4349

4450
functiondfs(node){
45-
varnewNode=null;
46-
47-
if(visited[node.label]){
48-
newNode=visited[node.label];
49-
}else{
50-
newNode=newUndirectedGraphNode(node.label);
51-
visited[node.label]=newNode;
52-
}
51+
varnewNode=visited[node.label] ?visited[node.label] :newUndirectedGraphNode(node.label);
52+
visited[node.label]=newNode;
5353

5454
for(vari=0;i<node.neighbors.length;i++){
55-
if(!visited[node.neighbors[i].label]){
56-
newNode.neighbors.push(dfs(node.neighbors[i]));
57-
}else{
58-
newNode.neighbors.push(visited[node.neighbors[i].label]);
59-
}
55+
varnewNeighbor=visited[node.neighbors[i].label] ?visited[node.neighbors[i].label] :dfs(node.neighbors[i]);
56+
newNode.neighbors.push(newNeighbor);
6057
}
6158
returnnewNode;
6259
}

‎207 Course Schedule.js

Lines changed: 62 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -2,6 +2,67 @@
22
// Language: Javascript
33
// Problem: https://leetcode.com/problems/course-schedule/
44
// Author: Chihung Yu
5+
6+
// Non-recursion version 144ms
7+
// more generic solution to problem that doesn't need information of numCourses and can deal with duplicated prerequisites
8+
9+
/**
10+
*@param {number} numCourses
11+
*@param {number[][]} prerequisites
12+
*@return {boolean}
13+
*/
14+
varcanFinish=function(numCourses,prerequisites){
15+
varcourseWithOtherCoursesDependOn={};
16+
varcourseDependsOnOtherCourses={};
17+
18+
prerequisites.forEach((prerequisite)=>{
19+
varprereqCourse=prerequisite[1];
20+
varcourseToTake=prerequisite[0]
21+
22+
23+
courseWithOtherCoursesDependOn[prereqCourse]=courseWithOtherCoursesDependOn[prereqCourse]||newSet();
24+
courseWithOtherCoursesDependOn[prereqCourse].add(courseToTake);
25+
26+
courseDependsOnOtherCourses[prereqCourse]=courseDependsOnOtherCourses[prereqCourse]||newSet();
27+
courseDependsOnOtherCourses[courseToTake]=courseDependsOnOtherCourses[courseToTake]||newSet();
28+
courseDependsOnOtherCourses[courseToTake].add(prereqCourse);
29+
});
30+
31+
varcourseWithNoDependencies=[];
32+
33+
for(variincourseDependsOnOtherCourses){
34+
if(courseDependsOnOtherCourses[i].size===0){
35+
courseWithNoDependencies.push(i);
36+
}
37+
}
38+
39+
while(courseWithNoDependencies.length>0){
40+
varrootCourse=courseWithNoDependencies.shift();
41+
42+
if(courseWithOtherCoursesDependOn[rootCourse]){
43+
courseWithOtherCoursesDependOn[rootCourse].forEach((childCourse)=>{
44+
courseDependsOnOtherCourses[childCourse].delete(parseInt(rootCourse));
45+
46+
if(courseDependsOnOtherCourses[childCourse].size===0){
47+
courseWithNoDependencies.push(childCourse+'');
48+
}
49+
});
50+
}
51+
}
52+
53+
for(iincourseDependsOnOtherCourses){
54+
if(courseDependsOnOtherCourses[i].size!==0){
55+
returnfalse;
56+
}
57+
}
58+
59+
returntrue;
60+
};
61+
62+
63+
64+
// recursion 132ms
65+
566
/**
667
*@param {number} numCourses
768
*@param {number[][]} prerequisites
@@ -53,10 +114,9 @@ var canFinish = function(numCourses, prerequisites) {
53114
varparent=[];
54115
varhasCycle=dfs(nodes[i],parent);
55116

56-
console.log(hasCycle,i,nodes[i],parent)
57117
if(hasCycle)returnfalse;
58118
}
59119
returntrue;
60120
};
61121

62-
canFinish(5,[[0,1],[1,2],[1,3],[1,4],[2,3]])
122+

‎210 Course Schedule II.js

Lines changed: 98 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,98 @@
1+
// There are a total of n courses you have to take, labeled from 0 to n - 1.
2+
3+
// 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]
4+
5+
// Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses.
6+
7+
// There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.
8+
9+
// For example:
10+
11+
// 2, [[1,0]]
12+
// There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1]
13+
14+
// 4, [[1,0],[2,0],[3,1],[3,2]]
15+
// There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is [0,1,2,3]. Another correct ordering is[0,2,1,3].
16+
17+
// Note:
18+
// The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
19+
20+
// click to show more hints.
21+
22+
// Hide Company Tags Facebook Zenefits
23+
// Hide Tags Depth-first Search Breadth-first Search Graph Topological Sort
24+
// Hide Similar Problems (M) Course Schedule (H) Alien Dictionary (M) Minimum Height Trees
25+
26+
27+
// 160ms
28+
29+
/**
30+
*@param {number} numCourses
31+
*@param {number[][]} prerequisites
32+
*@return {number[]}
33+
*/
34+
varfindOrder=function(numCourses,prerequisites){
35+
varcourseWithOtherCoursesDependOn={};
36+
varcourseDependsOnOtherCourses={};
37+
38+
prerequisites.forEach((prerequisite)=>{
39+
varprereqCourse=prerequisite[1];
40+
varcourseToTake=prerequisite[0]
41+
42+
43+
courseWithOtherCoursesDependOn[prereqCourse]=courseWithOtherCoursesDependOn[prereqCourse]||newSet();
44+
courseWithOtherCoursesDependOn[prereqCourse].add(courseToTake);
45+
46+
courseDependsOnOtherCourses[prereqCourse]=courseDependsOnOtherCourses[prereqCourse]||newSet();
47+
courseDependsOnOtherCourses[courseToTake]=courseDependsOnOtherCourses[courseToTake]||newSet();
48+
courseDependsOnOtherCourses[courseToTake].add(prereqCourse);
49+
});
50+
51+
varcourseWithNoDependencies=[];
52+
53+
for(variincourseDependsOnOtherCourses){
54+
if(courseDependsOnOtherCourses[i].size===0){
55+
courseWithNoDependencies.push(i);
56+
}
57+
}
58+
59+
60+
// pretty much the same as Course Schedule I. Just need to add those non root
61+
varcourseOrders=[];
62+
varhasCourseOrders={};
63+
64+
while(courseWithNoDependencies.length>0){
65+
varrootCourse=courseWithNoDependencies.shift();
66+
67+
courseOrders.push(parseInt(rootCourse));
68+
hasCourseOrders[parseInt(rootCourse)]=true;
69+
70+
if(courseWithOtherCoursesDependOn[rootCourse]){
71+
courseWithOtherCoursesDependOn[rootCourse].forEach((childCourse)=>{
72+
courseDependsOnOtherCourses[childCourse].delete(parseInt(rootCourse));
73+
74+
if(courseDependsOnOtherCourses[childCourse].size===0){
75+
courseWithNoDependencies.push(childCourse+'');
76+
}
77+
});
78+
}
79+
}
80+
81+
for(iincourseDependsOnOtherCourses){
82+
if(courseDependsOnOtherCourses[i].size!==0){
83+
return[];
84+
}
85+
}
86+
87+
if(courseOrders.length<numCourses){
88+
for(i=0;i<numCourses;i++){
89+
if(!hasCourseOrders[i]){
90+
courseOrders.push(i);
91+
}
92+
}
93+
}
94+
95+
returncourseOrders;
96+
};
97+
98+
console.log(findOrder(3,[[1,0]]));

‎252 Meeting Rooms.js

Lines changed: 39 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,39 @@
1+
// Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), determine if a person could attend all meetings.
2+
3+
// For example,
4+
// Given [[0, 30],[5, 10],[15, 20]],
5+
// return false.
6+
7+
// Hide Company Tags Facebook
8+
// Hide Tags Sort
9+
// Hide Similar Problems (H) Merge Intervals (M) Meeting Rooms II
10+
11+
12+
/**
13+
* Definition for an interval.
14+
* function Interval(start, end) {
15+
* this.start = start;
16+
* this.end = end;
17+
* }
18+
*/
19+
/**
20+
*@param {Interval[]} intervals
21+
*@return {boolean}
22+
*/
23+
24+
// 132 ms
25+
varcanAttendMeetings=function(intervals){
26+
// sort by starting time
27+
intervals.sort((interval1,interval2)=>interval1.start>interval2.start ?1 :-1);
28+
29+
for(vari=1;i<intervals.length;i++){
30+
varpre=intervals[i-1];
31+
varcur=intervals[i];
32+
33+
if(pre.end>cur.start){
34+
returnfalse;
35+
}
36+
}
37+
38+
returntrue;
39+
};

‎253 Meeting Rooms II.js

Lines changed: 50 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,50 @@
1+
// Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), find the minimum number of conference rooms required.
2+
3+
// For example,
4+
// Given [[0, 30],[5, 10],[15, 20]],
5+
// return 2.
6+
7+
// Hide Company Tags Google Facebook
8+
// Hide Tags Heap Greedy Sort
9+
// Hide Similar Problems (H) Merge Intervals (E) Meeting Rooms
10+
11+
12+
/**
13+
* Definition for an interval.
14+
* function Interval(start, end) {
15+
* this.start = start;
16+
* this.end = end;
17+
* }
18+
*/
19+
/**
20+
*@param {Interval[]} intervals
21+
*@return {number}
22+
*/
23+
24+
varminMeetingRooms=function(intervals){
25+
varschedule={};
26+
27+
intervals.forEach((interval)=>{
28+
schedule[interval.start]=schedule[interval.start]||0;
29+
schedule[interval.start]++;
30+
31+
schedule[interval.end]=schedule[interval.end]||0;
32+
schedule[interval.end]--;
33+
});
34+
35+
varmaxRooms=0;
36+
varrooms=0;
37+
38+
for(variinschedule){
39+
rooms+=schedule[i];
40+
maxRooms=Math.max(maxRooms,rooms);
41+
}
42+
43+
returnmaxRooms;
44+
};
45+
46+
vardata=[
47+
{start:2,end:7},
48+
]
49+
50+
console.log(minMeetingRooms(data));

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp