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

Commit7499c58

Browse files
committed
add 56, 57, 105
1 parent70b974c commit7499c58

File tree

4 files changed

+104
-0
lines changed

4 files changed

+104
-0
lines changed

‎Hard/56-MergeIntervals.js‎

Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
/**
2+
* Definition for an interval.
3+
* function Interval(start, end) {
4+
* this.start = start;
5+
* this.end = end;
6+
* }
7+
*/
8+
/**
9+
* Solution: Sort intervals first, then merge. See inline comments.
10+
*
11+
*@param {Interval[]} intervals
12+
*@return {Interval[]}
13+
*/
14+
varmerge=function(intervals){
15+
if(intervals.length<=0)returnintervals;
16+
intervals.sort(function(a,b){
17+
returna.start-b.start;
18+
});
19+
varresult=[];
20+
varpre=intervals[0];
21+
for(vari=1,length=intervals.length;i<length;i++){
22+
if(intervals[i].start>pre.end){
23+
result.push(pre);
24+
// this pre inteval may not be merged, this is why there is a push after this loop
25+
pre=intervals[i];
26+
}else{
27+
pre=newInterval(pre.start,Math.max(pre.end,intervals[i].end));
28+
// don't push to result yet, because this pre can be merged next round.
29+
}
30+
}
31+
32+
result.push(pre);
33+
returnresult;
34+
};

‎Hard/57-insertInterval.js‎

Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,29 @@
1+
/**
2+
* Definition for an interval.
3+
* function Interval(start, end) {
4+
* this.start = start;
5+
* this.end = end;
6+
* }
7+
*/
8+
/**
9+
*@param {Interval[]} intervals
10+
*@param {Interval} newInterval
11+
*@return {Interval[]}
12+
*/
13+
varinsert=function(intervals,newInterval){
14+
varresult=[];
15+
for(vari=0,length=intervals.length;i<length;i++){
16+
if(intervals[i].end<newInterval.start){
17+
result.push(intervals[i]);
18+
}elseif(intervals[i].start>newInterval.end){
19+
result.push(newInterval);
20+
newInterval=intervals[i];
21+
}elseif(intervals[i].end>=newInterval.start||intervals[i].start<=newInterval.end){
22+
newInterval.start=Math.min(intervals[i].start,newInterval.start);
23+
newInterval.end=Math.max(intervals[i].end,newInterval.end);
24+
}
25+
}
26+
27+
result.push(newInterval);
28+
returnresult;
29+
};

‎Medium/105-constructBinaryTree.js‎

Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,38 @@
1+
/**
2+
* Definition for a binary tree node.
3+
* function TreeNode(val) {
4+
* this.val = val;
5+
* this.left = this.right = null;
6+
* }
7+
*/
8+
/**
9+
* e.g. preorder 12453768, inorder: 42516738,
10+
* from preorder, we know the first element is the root, then find root's index in
11+
* inorder, then the left side (in inorder) of root is the left subtree, and right side
12+
* after root is the right subtree.
13+
*
14+
*@param {number[]} preorder
15+
*@param {number[]} inorder
16+
*@return {TreeNode}
17+
*/
18+
varbuildTree=function(preorder,inorder){
19+
returnhelper(preorder,0,preorder.length-1,inorder,0,inorder.length-1);
20+
};
21+
22+
varhelper=function(preorder,preStart,preEnd,inorder,inStart,inEnd){
23+
if(preStart>preEnd||inStart>inEnd)returnnull;
24+
vark=0;
25+
for(vari=0,length=inorder.length;i<length;i++){
26+
if(preorder[preStart]===inorder[i]){
27+
k=i;
28+
break;
29+
}
30+
}
31+
32+
varroot=newTreeNode(preorder[preStart]);
33+
// make sure inEnd - inStart === preEnd - preStart
34+
root.left=helper(preorder,preStart+1,preStart+k-inStart,inorder,inStart,k-1);
35+
root.right=helper(preorder,preEnd-inEnd+k+1,preEnd,inorder,k+1,inEnd);
36+
37+
returnroot;
38+
};

‎README.md‎

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -118,6 +118,7 @@
118118
*[96. Unique Binary Search Trees](https://leetcode.com/problems/unique-binary-search-trees/) -[Solution](./Medium/96-uniqueBinarySearchTrees.js)
119119
*[98. Validate Binary Search Tree](https://leetcode.com/problems/validate-binary-search-tree/) -[Solution](./Medium/98-validateBST.js)
120120
*[103. Binary Tree Zigzag Level Order Traversal](https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/) -[Solution](./Medium/103-BSTZigzagLevelTraversal.js)
121+
*[105. Construct Binary Tree from Preorder and Inorder Traversal](https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/) -[Solution](./Medium/105-constructBinaryTree.js)
121122
*[108. Convert Sorted Array to Binary Search Tree](https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/) -[Solution](./Medium/108-convertSortedArraytoBST.js)
122123
*[109. Convert Sorted List to Binary Search Tree](https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/) -[Solution](./Medium/109-convertSortedListToBST.js)
123124
*[113. Path Sum II](https://leetcode.com/problems/path-sum-ii/) -[Solution](./Medium/113-pathSumII.js)
@@ -154,5 +155,7 @@
154155
*[25. Reverse Nodes in k-Group](https://leetcode.com/problems/reverse-nodes-in-k-group/) -[Solution](./Hard/25-reverseNodesInKGroup.js)
155156
*[32. Longest Valid Parentheses](https://leetcode.com/problems/longest-valid-parentheses/) -[Solution](./Hard/32-longestValidParentheses.js)
156157
*[33. Search in Rotated Sorted Array](https://leetcode.com/problems/search-in-rotated-sorted-array/) -[Solution](./Hard/33-searchRotatedSortedArray.js)
158+
*[56. Merge Intervals](https://leetcode.com/problems/merge-intervals/) -[Solution](./Hard/56-MergeIntervals.js)
159+
*[57. Insert Interval](https://leetcode.com/problems/insert-interval/) -[Solution](./Hard/57-insertInterval.js)
157160
*[123. Best Time to Buy and Sell Stock III](https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/) -[Solution](./Hard/123-bestTimeBuySellStockIII.js)
158161
*[154.Find Minimum in Rotated Sorted Array II](https://leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii/) -[Solution](./Hard/154-findMinimumInRotatedSortedArray-II.js)

0 commit comments

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