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

Commite3c86bc

Browse files
committed
add more solutions
1 parentaa76f90 commite3c86bc

19 files changed

+787
-73
lines changed

‎124 Binary Tree Maximum Path Sum.js

Lines changed: 18 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,3 +1,16 @@
1+
// Given a binary tree, find the maximum path sum.
2+
3+
// For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path does not need to go through the root.
4+
5+
// For example:
6+
// Given the below binary tree,
7+
8+
// 1
9+
// / \
10+
// 2 3
11+
// Return 6.
12+
13+
114
// http://bangbingsyb.blogspot.com/2014/11/leetcode-binary-tree-maximum-path-sum.html
215
/**
316
* Definition for a binary tree node.
@@ -22,13 +35,17 @@ var maxPathSum = function(root) {
2235

2336
varleftVal=Math.max(findMaxPath(node.left),0);
2437
varrightVal=Math.max(findMaxPath(node.right),0);
25-
38+
2639
varps1=node.val+Math.max(leftVal,rightVal);
2740
// ps2 means taking this current node as parent node and stop there
2841
varps2=node.val+leftVal+rightVal;
2942

43+
// maxVal as if we end counting value here, what will be the maximum val
44+
// leftVal and rightVal can be negative values
3045
maxVal=Math.max(maxVal,Math.max(ps1,ps2));
46+
3147
// return ps1 only since, ps2 cannot be combined with the parent node
48+
// leftVal and rightVal can be negative values, however, we can to see if combining with values down below can give higher number
3249
returnps1;
3350
}
3451
};

‎224 Basic Calculator.js

Lines changed: 53 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,53 @@
1+
/**
2+
Implement a basic calculator to evaluate a simple expression string.
3+
4+
The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces .
5+
6+
You may assume that the given expression is always valid.
7+
8+
Some examples:
9+
"1 + 1" = 2
10+
" 2-1 + 2 " = 3
11+
"(1+(4+5+2)-3)+(6+8)" = 23
12+
Note: Do not use the eval built-in library function.
13+
*/
14+
/**
15+
*@param {string} s
16+
*@return {number}
17+
*/
18+
varcalculate=function(s){
19+
varstack=[],
20+
len=s.length,
21+
sum=0,
22+
num,
23+
ch,
24+
j,
25+
i;
26+
27+
stack.push(1);
28+
stack.push(1);
29+
30+
for(i=0;i<len;i++){
31+
ch=s.charAt(i);
32+
33+
if(!isNaN(parseInt(ch))){
34+
num=parseInt(ch);
35+
36+
for(j=i+1;j<len&&!isNaN(parseInt(s.charAt(j)));j++){
37+
num=num*10+parseInt(s.charAt(j));
38+
}
39+
40+
sum+=stack.pop()*num;
41+
42+
i=j-1;
43+
}elseif(ch==='+'||ch==='('){
44+
stack.push(stack[stack.length-1]);
45+
}elseif(ch==='-'){
46+
stack.push(stack[stack.length-1]*(-1));
47+
}elseif(ch===')'){
48+
stack.pop();
49+
}
50+
}
51+
52+
returnsum;
53+
};

‎23 Merge k Sorted Lists.js

Lines changed: 60 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,60 @@
1+
// Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
2+
// http://www.cnblogs.com/springfor/p/3869217.html
3+
/**
4+
* Definition for singly-linked list.
5+
* function ListNode(val) {
6+
* this.val = val;
7+
* this.next = null;
8+
* }
9+
*/
10+
/**
11+
*@param {ListNode[]} lists
12+
*@return {ListNode}
13+
*/
14+
varmergeKLists=function(lists){
15+
returnmergeHelper(lists,0,lists.length-1);
16+
};
17+
18+
functionmergeHelper(lists,l,r){
19+
if(l===r){
20+
returnlists[l];
21+
}
22+
23+
if(l>r){
24+
returnnull;
25+
}
26+
27+
varmid=Math.floor((l+r)/2);
28+
varleft=mergeHelper(lists,l,mid);
29+
varright=mergeHelper(lists,mid+1,r);
30+
31+
returnmergeTwoLists(left,right);
32+
}
33+
34+
35+
functionmergeTwoLists(l1,l2){
36+
vardummy=newListNode(0);
37+
varcur=dummy;
38+
39+
while(l1&&l2){
40+
if(l1.val<l2.val){
41+
cur.next=l1;
42+
l1=l1.next;
43+
}else{
44+
cur.next=l2;
45+
l2=l2.next;
46+
}
47+
48+
cur=cur.next;
49+
}
50+
51+
if(l1){
52+
cur.next=l1;
53+
}
54+
55+
if(l2){
56+
cur.next=l2;
57+
}
58+
59+
returndummy.next;
60+
}

‎239 Sliding Window Maximum.js

Lines changed: 56 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,56 @@
1+
// Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.
2+
3+
// For example,
4+
// Given nums = [1,3,-1,-3,5,3,6,7], and k = 3.
5+
6+
// Window position Max
7+
// --------------- -----
8+
// [1 3 -1] -3 5 3 6 7 3
9+
// 1 [3 -1 -3] 5 3 6 7 3
10+
// 1 3 [-1 -3 5] 3 6 7 5
11+
// 1 3 -1 [-3 5 3] 6 7 5
12+
// 1 3 -1 -3 [5 3 6] 7 6
13+
// 1 3 -1 -3 5 [3 6 7] 7
14+
// Therefore, return the max sliding window as [3,3,5,5,6,7].
15+
16+
/**
17+
*@param {number[]} nums
18+
*@param {number} k
19+
*@return {number[]}
20+
*/
21+
varmaxSlidingWindow=function(nums,k){
22+
varresult=[],
23+
linkedListWithTwoEndsOps=[],
24+
len=nums.length,
25+
i;
26+
27+
if(k>len||k===0){
28+
returnresult;
29+
}
30+
31+
for(i=0;i<len;i++){
32+
// Remove anything that is less than the current value
33+
// so linkedListWithTwoEndsOps maintains values greater than the curret value
34+
while(linkedListWithTwoEndsOps.length>0&&nums[linkedListWithTwoEndsOps[linkedListWithTwoEndsOps.length-1]]<nums[i]){
35+
varval=linkedListWithTwoEndsOps.pop();
36+
}
37+
38+
// In case that all elements in the linkedListWithTwoEndsOps are all greater than the current one (descending order)
39+
// Shift out the
40+
if(linkedListWithTwoEndsOps[0]<i-k+1){
41+
linkedListWithTwoEndsOps.shift();
42+
}
43+
44+
linkedListWithTwoEndsOps.push(i);
45+
46+
// For each sliding window movement, we record the highest value in that sliding window
47+
// i >= k - 1 to ensure that we don't prematurely record values before we get to the full range of the first sliding window
48+
// e.g. [1 3 -1] -3 5 3 6 7 3
49+
// this ensure that i is at least at -1 (index 2)
50+
if(i>=k-1){
51+
result.push(nums[linkedListWithTwoEndsOps[0]]);
52+
}
53+
}
54+
55+
returnresult;
56+
};

‎242 Valid Anagram.js

Lines changed: 34 additions & 24 deletions
Original file line numberDiff line numberDiff line change
@@ -1,31 +1,41 @@
1-
// Leetcode #242
2-
// Language: Javascript
3-
// Problem: https://leetcode.com/problems/valid-anagram/
4-
// Author: Chihung Yu
1+
// Given two strings s and t, write a function to determine if t is an anagram of s.
2+
3+
// For example,
4+
// s = "anagram", t = "nagaram", return true.
5+
// s = "rat", t = "car", return false.
6+
7+
8+
59
/**
610
*@param {string} s
711
*@param {string} t
812
*@return {boolean}
913
*/
1014
varisAnagram=function(s,t){
11-
if((s===null||t===null)||(s.length!==t.length)){
12-
returnfalse;
13-
}
14-
15-
varhash={};
16-
17-
for(vari=0;i<s.length;i++){
18-
hash[s[i]]=hash[s[i]]||0;
19-
hash[s[i]]++;
20-
}
21-
22-
for(varj=0;j<t.length;j++){
23-
if(!hash[t[j]]){
24-
returnfalse;
25-
}
26-
27-
hash[t[j]]--;
28-
}
29-
30-
returntrue;
15+
varslen=s.length;
16+
vartlen=t.length;
17+
18+
if(slen!==tlen){
19+
returnfalse;
20+
}
21+
22+
varhash={};
23+
24+
for(vari=0;i<slen;i++){
25+
varchar=s[i];
26+
hash[char]=hash[char]||0;
27+
hash[char]++;
28+
}
29+
30+
for(i=0;i<tlen;i++){
31+
char=t[i];
32+
33+
if(hash[char]===undefined||hash[char]===0){
34+
returnfalse;
35+
}
36+
37+
hash[char]--;
38+
}
39+
40+
returntrue;
3141
};

‎25 Reverse Nodes in k-Group.js

Lines changed: 64 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,64 @@
1+
2+
// Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.
3+
4+
// If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.
5+
6+
// You may not alter the values in the nodes, only nodes itself may be changed.
7+
8+
// Only constant memory is allowed.
9+
10+
// For example,
11+
// Given this linked list: 1->2->3->4->5
12+
13+
// For k = 2, you should return: 2->1->4->3->5
14+
15+
// For k = 3, you should return: 3->2->1->4->5
16+
17+
18+
/**
19+
* Definition for singly-linked list.
20+
* function ListNode(val) {
21+
* this.val = val;
22+
* this.next = null;
23+
* }
24+
*/
25+
/**
26+
*@param {ListNode} head
27+
*@param {number} k
28+
*@return {ListNode}
29+
*/
30+
31+
// http://www.geeksforgeeks.org/reverse-a-list-in-groups-of-given-size/
32+
varreverseKGroup=function(head,k){
33+
varcur=head;
34+
varpre=null;
35+
varpost=null;
36+
varcount=0;
37+
38+
while(cur!==null&&count<k){
39+
cur=cur.next;
40+
count++;
41+
}
42+
43+
if(count!==k){
44+
returnhead;
45+
}
46+
47+
cur=head;
48+
49+
while(cur!==null&&count>0){
50+
post=cur.next;
51+
cur.next=pre;
52+
pre=cur;
53+
cur=post;
54+
count--;
55+
}
56+
57+
// post is now a pointer to (k+1)th node
58+
// recursively call for the list starting from cur
59+
if(post!==null){
60+
head.next=reverseKGroup(post,k);
61+
}
62+
63+
returnpre;
64+
};

0 commit comments

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