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

Commitf198219

Browse files
committed
add sort linkedlist 147, 148, add 150 reverse polish notation
1 parent4923264 commitf198219

File tree

5 files changed

+134
-0
lines changed

5 files changed

+134
-0
lines changed

‎Medium/129-sumRootToLeafNumbers.js‎

Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -47,3 +47,19 @@ var helper = function(root, sum) {
4747
returnhelper(root.left,10*sum+root.val)
4848
+helper(root.right,10*sum+root.val);
4949
};
50+
51+
// a third DFS method. Top-down
52+
varsumNumbers=function(root){
53+
if(!root)return0;
54+
returnhelper(root,0,0);
55+
};
56+
57+
functionhelper(root,currNum,sum){
58+
if(!root)returnsum;
59+
currNum=root.val+10*currNum;
60+
if(!root.left&&!root.right){
61+
sum+=currNum;
62+
returnsum;
63+
}
64+
returnhelper(root.left,currNum,sum)+helper(root.right,currNum,sum)
65+
}

‎Medium/147-insertionSortList.js‎

Lines changed: 37 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,37 @@
1+
/**
2+
* Definition for singly-linked list.
3+
* function ListNode(val) {
4+
* this.val = val;
5+
* this.next = null;
6+
* }
7+
*/
8+
/**
9+
*@param {ListNode} head
10+
*@return {ListNode}
11+
*/
12+
varinsertionSortList=function(head){
13+
if(!head)returnhead;
14+
vardummyHead=newListNode(null);
15+
dummyHead.next=head;
16+
varfirst=dummyHead;
17+
varsecond=head;
18+
19+
while(second.next){
20+
if(second.next.val<second.val){
21+
varsmallNode=second.next;
22+
second.next=second.next.next;
23+
while(first.next&&first.next.val<smallNode.val){
24+
first=first.next;
25+
}
26+
smallNode.next=first.next;
27+
first.next=smallNode;
28+
first=dummyHead;
29+
}else{
30+
second=second.next;
31+
if(!second)break;
32+
}
33+
34+
}
35+
36+
returndummyHead.next;
37+
};

‎Medium/148-sortList.js‎

Lines changed: 48 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,48 @@
1+
/**
2+
* Definition for singly-linked list.
3+
* function ListNode(val) {
4+
* this.val = val;
5+
* this.next = null;
6+
* }
7+
*/
8+
/**
9+
* sort, then merge. In fact, this method use O(logN) space for recursive function calls.
10+
* needs to be improved.
11+
*
12+
*@param {ListNode} head
13+
*@return {ListNode}
14+
*/
15+
varsortList=function(head){
16+
if(!head||!head.next)returnhead;
17+
varfast=head;
18+
varslow=head;
19+
20+
while(fast.next&&fast.next.next){
21+
slow=slow.next;
22+
fast=fast.next.next;
23+
}
24+
fast=slow.next;
25+
slow.next=null;
26+
varsecondHalf=sortList(fast);
27+
varfirstHalf=sortList(head);
28+
returnmerge(firstHalf,secondHalf);
29+
};
30+
31+
varmerge=function(l1,l2){
32+
varl3=newListNode();
33+
varl3Head=l3;
34+
while(l1&&l2){
35+
if(l1.val<=l2.val){
36+
l3.next=l1;
37+
l1=l1.next;
38+
}else{
39+
l3.next=l2;
40+
l2=l2.next;
41+
}
42+
l3=l3.next;
43+
}
44+
if(!l1)l3.next=l2;
45+
if(!l2)l3.next=l1;
46+
47+
returnl3Head.next;
48+
};
Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
/**
2+
*@param {string[]} tokens
3+
*@return {number}
4+
*/
5+
// seems like it is not a good solution
6+
varevalRPN=function(tokens){
7+
varstack=[];
8+
for(vari=0;i<tokens.length;i++){
9+
vartoken=tokens[i];
10+
if(!isNaN(token)){
11+
stack.push(token);
12+
}else{
13+
varnum1=stack.pop();
14+
varnum2=stack.pop();
15+
varresult=getResult(num2,num1,token);
16+
stack.push(result);
17+
}
18+
}
19+
20+
returnMath.floor(parseInt(stack[stack.length-1]));
21+
};
22+
23+
vargetResult=function(num1,num2,operator){
24+
vara=parseInt(num1);
25+
varb=parseInt(num2);
26+
if(operator==='+')returna+b;
27+
if(operator==='-')returna-b;
28+
if(operator==='/')returna/b;
29+
if(operator==='*')returna*b;
30+
};

‎README.md‎

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -138,6 +138,9 @@
138138
*[141. Linked List Cycle](https://leetcode.com/problems/linked-list-cycle/) -[Solution](./Medium/141-linkedListCycle.js)
139139
*[142. Linked List Cycle II](https://leetcode.com/problems/linked-list-cycle-ii/) -[Solution](./Medium/142-linkedListCycleII.js)
140140
*[144. Binary Tree Preorder Traversal](https://leetcode.com/problems/binary-tree-preorder-traversal/) -[Solution](./Medium/144-binaryTreePreorder.js)
141+
*[147. Insertion Sort List](https://leetcode.com/problems/insertion-sort-list/) -[Solution](./Medium/147-insertionSortList.js)
142+
*[148. Sort List](https://leetcode.com/problems/sort-list/) -[Solution](./Medium/148-sortList.js)
143+
*[150. Evaluate Reverse Polish Notation](https://leetcode.com/problems/evaluate-reverse-polish-notation/) -[Solution](./Medium/150-reversePolishNotation.js)
141144
*[151. Reverse Words in a String](https://leetcode.com/problems/reverse-words-in-a-string/) -[Solution](./Medium/151-reverseWordsInAString.js)
142145
*[152. Maximum Product Subarray](https://leetcode.com/problems/maximum-product-subarray/) -[Solution](./Medium/152-MaxProductSubarray.js)
143146
*[153.Find Minimum in Rotated Sorted Array](https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/) -[Solution](./Medium/153-findMinimumInRotatedSortedArray.js)

0 commit comments

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