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

Commited0990f

Browse files
committed
add more solution
1 parentbbf5af3 commited0990f

13 files changed

+605
-85
lines changed

‎101 Symmetric Tree.js

Lines changed: 43 additions & 33 deletions
Original file line numberDiff line numberDiff line change
@@ -1,3 +1,26 @@
1+
// Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).
2+
3+
// For example, this binary tree [1,2,2,3,4,4,3] is symmetric:
4+
5+
// 1
6+
// / \
7+
// 2 2
8+
// / \ / \
9+
// 3 4 4 3
10+
// But the following [1,2,2,null,3,null,3] is not:
11+
// 1
12+
// / \
13+
// 2 2
14+
// \ \
15+
// 3 3
16+
// Note:
17+
// Bonus points if you could solve it both recursively and iteratively.
18+
19+
// Hide Company Tags LinkedIn Bloomberg Microsoft
20+
// Hide Tags Tree Depth-first Search Breadth-first Search
21+
22+
23+
124
/**
225
* Definition for a binary tree node.
326
* function TreeNode(val) {
@@ -10,55 +33,42 @@
1033
*@return {boolean}
1134
*/
1235
varisSymmetric=function(root){
13-
if(root===null){
14-
returntrue;
15-
}
16-
1736
varqueue=[];
1837
queue.push(root);
1938

20-
vartemp=[];
21-
varcurCnt=1;
22-
varnextCnt=0;
23-
24-
while(queue.length!==0){
25-
varp=queue.shift();
39+
while(queue.length!==0){
40+
varlen=queue.length;
2641

27-
if(p!==null){
28-
temp.push(p.left);
29-
temp.push(p.right);
42+
if(!isLevelSymmetric(queue)){
43+
returnfalse;
3044
}
3145

32-
if(queue.length===0){
33-
if(isPalindrome(temp)){
34-
queue=temp;
35-
temp=[];
36-
}else{
37-
returnfalse;
46+
for(vari=0;i<len;i++){
47+
varnode=queue.shift();
48+
49+
if(node!==null){
50+
queue.push(node.left);
51+
queue.push(node.right);
3852
}
3953
}
4054
}
4155

4256
returntrue;
4357
};
4458

45-
46-
varisPalindrome=function(arr){
47-
varhead=0;
48-
vartail=arr.length-1;
59+
functionisLevelSymmetric(nodes){
60+
varlen=nodes.length;
61+
varbeg=0;
62+
varend=len-1;
4963

50-
while(head<tail){
51-
if(arr[head]&&arr[tail]){
52-
if(arr[head].val!==arr[tail].val){
53-
returnfalse;
54-
}
55-
}elseif(arr[head]||arr[tail]){
64+
while(beg<end){
65+
if(nodes[beg]===null&&nodes[end]===null||(nodes[beg]&&nodes[end]&&nodes[beg].val===nodes[end].val)){
66+
beg++;
67+
end--;
68+
}else{
5669
returnfalse;
5770
}
58-
59-
head++;
60-
tail--;
6171
}
6272

6373
returntrue;
64-
}
74+
}
Lines changed: 31 additions & 26 deletions
Original file line numberDiff line numberDiff line change
@@ -1,37 +1,42 @@
1-
// Leetcode #150
2-
// Language: Javascript
3-
// Problem: https://leetcode.com/problems/evaluate-reverse-polish-notation/
4-
// Author: Chihung Yu
1+
// Evaluate the value of an arithmetic expression in Reverse Polish Notation.
2+
3+
// Valid operators are +, -, *, /. Each operand may be an integer or another expression.
4+
5+
// Some examples:
6+
// ["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
7+
// ["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6
8+
// Hide Company Tags LinkedIn
9+
// Hide Tags Stack
10+
// Hide Similar Problems (H) Basic Calculator (H) Expression Add Operators
11+
512
/**
613
*@param {string[]} tokens
714
*@return {number}
815
*/
916
varevalRPN=function(tokens){
1017
varstack=[];
1118

12-
for(vari=0;i<tokens.length;i++){
13-
vart=tokens[i];
14-
15-
if(t==='+'){
16-
varx=parseInt(stack.pop());
17-
vary=parseInt(stack.pop());
18-
stack.push(x+y);
19-
}elseif(t==='-'){
20-
x=parseInt(stack.pop());
21-
y=parseInt(stack.pop());
22-
stack.push(y-x);
23-
}elseif(t==='*'){
24-
x=parseInt(stack.pop());
25-
y=parseInt(stack.pop());
26-
stack.push(parseInt(y*x));
27-
}elseif(t==='/'){
28-
x=parseInt(stack.pop());
29-
y=parseInt(stack.pop());
30-
stack.push(parseInt(y/x));
19+
for(vari=0;i<tokens.length;i++){
20+
vartoken=tokens[i];
21+
varval1,val2;
22+
varval=parseInt(token);
23+
if(!isNaN(val)){
24+
stack.push(val);
3125
}else{
32-
stack.push(t);
26+
val2=stack.pop();
27+
val1=stack.pop();
28+
29+
if(token==='*'){
30+
stack.push(parseInt(val1*val2));
31+
}elseif(token==='/'){
32+
stack.push(parseInt(val1/val2));
33+
}elseif(token==='-'){
34+
stack.push(val1-val2);
35+
}elseif(token==='+'){
36+
stack.push(val1+val2);
37+
}
3338
}
3439
}
35-
varnum=stack.pop();
36-
returnparseInt(num);
40+
41+
returnstack.pop();
3742
};

‎152 Maximum Product Subarray.js

Lines changed: 12 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,12 +1,22 @@
1+
// Find the contiguous subarray within an array (containing at least one number) which has the largest product.
2+
3+
// For example, given the array [2,3,-2,4],
4+
// the contiguous subarray [2,3] has the largest product = 6.
5+
6+
// Hide Company Tags LinkedIn
7+
// Hide Tags Array Dynamic Programming
8+
// Show Similar Problems
9+
10+
11+
112
// Leetcode #152
213
// Language: Javascript
314
// Problem: https://leetcode.com/problems/maximum-product-subarray/
4-
// Author: Chihung Yu
515
/**
616
*@param {number[]} nums
717
*@return {number}
818
*/
9-
// http://www.programcreek.com/2014/03/leetcode-maximum-product-subarray-java/
19+
//reference: http://www.programcreek.com/2014/03/leetcode-maximum-product-subarray-java/
1020
varmaxProduct=function(nums){
1121
if(nums===null||nums.length===0){
1222
return0;

‎156 Binary Tree Upside Down.js

Lines changed: 86 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,86 @@
1+
// Given a binary tree where all the right nodes are either leaf nodes with a sibling (a left node that shares the same parent node) or empty, flip it upside down and turn it into a tree where the original right nodes turned into left leaf nodes. Return the new root.
2+
3+
// For example:
4+
// Given a binary tree {1,2,3,4,5},
5+
// 1
6+
// / \
7+
// 2 3
8+
// / \
9+
// 4 5
10+
// return the root of the binary tree [4,5,2,#,#,3,1].
11+
// 4
12+
// / \
13+
// 5 2
14+
// / \
15+
// 3 1
16+
// confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.
17+
18+
// Hide Company Tags LinkedIn
19+
// Hide Tags Tree
20+
// Show Similar Problems
21+
22+
23+
24+
/**
25+
* Definition for a binary tree node.
26+
* function TreeNode(val) {
27+
* this.val = val;
28+
* this.left = this.right = null;
29+
* }
30+
*/
31+
/**
32+
*@param {TreeNode} root
33+
*@return {TreeNode}
34+
*/
35+
varupsideDownBinaryTree=function(root){
36+
varnewRoot=root;
37+
38+
generateUpsideDownHelper(root);
39+
40+
functiongenerateUpsideDownHelper(root){
41+
if(!root){
42+
returnroot;
43+
}
44+
45+
if(!root.left&&!root.right){
46+
newRoot=root;
47+
returnroot;
48+
}
49+
50+
if(root.left){
51+
varret=generateUpsideDownHelper(root.left);
52+
ret.left=root.right;
53+
ret.right=root;
54+
root.left=null;
55+
root.right=null;
56+
}
57+
58+
returnroot;
59+
}
60+
returnnewRoot;
61+
};
62+
63+
64+
// simpler solution
65+
varupsideDownBinaryTree=function(root){
66+
// second condition ensure the left most child will be the new root
67+
if(!root||(!root.left&&!root.right)){
68+
returnroot;
69+
}
70+
71+
letnewRoot=upsideDownBinaryTree(root.left);
72+
console.log(newRoot.val,root.left)
73+
74+
root.left.left=root.right;
75+
root.left.right=root;
76+
77+
// cannot work if we sub root.left with newRoot
78+
// since new root is always the left most child
79+
// [doesn't work] newRoot.left = root.right;
80+
// [doesn't work] newRoot.right = root;
81+
82+
root.left=null;
83+
root.right=null;
84+
85+
returnnewRoot;
86+
};

‎187 Repeated DNA Sequences.js

Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
// All DNA is composed of a series of nucleotides abbreviated as A, C, G, and T, for example: "ACGAATTCCG". When studying DNA, it is sometimes useful to identify repeated sequences within the DNA.
2+
3+
// Write a function to find all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule.
4+
5+
// For example,
6+
7+
// Given s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT",
8+
9+
// Return:
10+
// ["AAAAACCCCC", "CCCCCAAAAA"].
11+
// Hide Company Tags LinkedIn
12+
// Hide Tags Hash Table Bit Manipulation
13+
14+
15+
/**
16+
*@param {string} s
17+
*@return {string[]}
18+
*/
19+
varfindRepeatedDnaSequences=function(s){
20+
varhash={};
21+
varresult=[];
22+
23+
for(vari=10;i<=s.length;i++){
24+
varsubstr=s.substring(i-10,i);
25+
if(hash[substr]===undefined){
26+
hash[substr]=1;
27+
}elseif(hash[substr]===1){
28+
hash[substr]++;
29+
result.push(substr);
30+
}
31+
}
32+
33+
returnresult;
34+
};

‎236 Lowest Common Ancestor of a Binary Tree.js

Lines changed: 5 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -30,8 +30,12 @@
3030
*@param {TreeNode} q
3131
*@return {TreeNode}
3232
*/
33+
34+
// Amazon LinkedIn Apple Facebook Microsoft
35+
// Hide Tags Tree
36+
// Hide Similar Problems
3337

34-
// http://www.cnblogs.com/anne-vista/p/4815076.html
38+
//reference: http://www.cnblogs.com/anne-vista/p/4815076.html
3539
varlowestCommonAncestor=function(root,p,q){
3640
if(root===null||root===p||root===q){
3741
returnroot;

0 commit comments

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