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

Commitaa76f90

Browse files
committed
add more solutions
1 parent43b4e6c commitaa76f90

17 files changed

+1093
-264
lines changed

‎124 Binary Tree Maximum Path Sum.js

Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
// http://bangbingsyb.blogspot.com/2014/11/leetcode-binary-tree-maximum-path-sum.html
2+
/**
3+
* Definition for a binary tree node.
4+
* function TreeNode(val) {
5+
* this.val = val;
6+
* this.left = this.right = null;
7+
* }
8+
*/
9+
/**
10+
*@param {TreeNode} root
11+
*@return {number}
12+
*/
13+
varmaxPathSum=function(root){
14+
varmaxVal=-Infinity;
15+
findMaxPath(root);
16+
returnmaxVal;
17+
18+
functionfindMaxPath(node){
19+
if(!node){
20+
return0;
21+
}
22+
23+
varleftVal=Math.max(findMaxPath(node.left),0);
24+
varrightVal=Math.max(findMaxPath(node.right),0);
25+
26+
varps1=node.val+Math.max(leftVal,rightVal);
27+
// ps2 means taking this current node as parent node and stop there
28+
varps2=node.val+leftVal+rightVal;
29+
30+
maxVal=Math.max(maxVal,Math.max(ps1,ps2));
31+
// return ps1 only since, ps2 cannot be combined with the parent node
32+
returnps1;
33+
}
34+
};

‎139 Word Break.js

Lines changed: 15 additions & 19 deletions
Original file line numberDiff line numberDiff line change
@@ -1,32 +1,28 @@
1-
// Leetcode #139
2-
// Language: Javascript
3-
// Problem: https://leetcode.com/problems/word-break/
4-
// Author: Chihung Yu
51
/**
62
*@param {string} s
73
*@param {set<string>} wordDict
4+
* Note: wordDict is a Set object, see:
5+
* https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Set
86
*@return {boolean}
97
*/
108
varwordBreak=function(s,wordDict){
11-
if(wordDict===null||wordDict.size===0){
9+
if(wordDict===null||wordDict.size===0){
1210
returnfalse;
1311
}
14-
15-
vart=[];
16-
t[0]=true;
1712

18-
for(vari=0;i<s.length;i++){
19-
if(t[i]){
20-
for(varj=i+1;j<=s.length;j++){
21-
varstr=s.substring(i,j);
22-
23-
if(wordDict.has(str)){
24-
t[j]=true;
13+
varpossible=[];
14+
possible[0]=true;
15+
16+
for(vari=0;i<s.length;i++){
17+
if(possible[i]){
18+
for(varj=i+1;j<=s.length;j++){
19+
varstr=s.substring(i,j);
20+
if(wordDict.has(str)){
21+
possible[j]=true;
2522
}
26-
}
23+
}
2724
}
2825
}
2926

30-
returnt[s.length]===true;
31-
32-
}
27+
returnpossible[s.length]===true;
28+
};

‎14 Longest Common Prefix.js

Lines changed: 17 additions & 20 deletions
Original file line numberDiff line numberDiff line change
@@ -2,32 +2,29 @@
22
*@param {string[]} strs
33
*@return {string}
44
*/
5-
65
varlongestCommonPrefix=function(strs){
7-
varresult="";
6+
varlen=strs.length;
7+
varresult='';
88

9-
if(strs===null||strs.length===0){
9+
if(len===0){
1010
returnresult;
1111
}
1212

13-
varminLen=Infinity;
14-
15-
for(vari=0;i<strs.length;i++){
16-
if(strs[i].length<minLen){
17-
minLen=strs[i].length;
18-
}
19-
}
20-
varstrIndex=0;
21-
vararrIndex=1;
22-
23-
24-
for(varx=0;x<minLen;x++){
25-
for(vary=0;y<strs.length;y++){
26-
if(strs[0][x]!==strs[y][x]){
27-
returnstrs[0].substring(0,x);
13+
for(vari=0;i<strs[0].length;i++){
14+
varcurChar=strs[0][i];
15+
16+
for(varj=1;j<len;j++){
17+
if(curChar!==strs[j][i]){
18+
returnresult;
19+
}
20+
21+
if(strs[j].length===i){
22+
returnresult;
2823
}
2924
}
25+
26+
result+=curChar;
3027
}
31-
32-
returnstrs[0].substring(0,minLen);
28+
29+
returnresult;
3330
};

‎140 Word Break II.js

Lines changed: 53 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,53 @@
1+
// http://fisherlei.blogspot.com/2013/11/leetcode-wordbreak-ii-solution.html
2+
/**
3+
*@param {string} s
4+
*@param {set<string>} wordDict
5+
* Note: wordDict is a Set object, see:
6+
* https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Set
7+
*@return {string[]}
8+
*/
9+
varwordBreak=function(s,wordDict){
10+
varresult=[];
11+
varsolutions=[];
12+
varlen=s.length;
13+
varpossible=[];
14+
15+
for(vari=0;i<=s.length;i++){
16+
possible.push(true);
17+
}
18+
19+
getAllSolutions(0,s,wordDict,result,solutions,possible);
20+
returnsolutions;
21+
};
22+
23+
functiongetAllSolutions(start,s,wordDict,result,solutions,possible){
24+
if(start===s.length){
25+
solutions.push(result.join(' '))// remove the last space
26+
return;
27+
}
28+
29+
// loop through string from i to s.length
30+
for(vari=start;i<s.length;i++){
31+
varpiece=s.substring(start,i+1);
32+
33+
// possible is to mark step whether i+1 to s.length have any possible words
34+
if(wordDict.has(piece)&&possible[i+1]){// eliminate unnecessary search
35+
result.push(piece);
36+
varbeforeChange=solutions.length;
37+
getAllSolutions(i+1,s,wordDict,result,solutions,possible);
38+
if(solutions.length===beforeChange){
39+
possible[i+1]=false;
40+
}
41+
result.pop();
42+
}
43+
}
44+
}
45+
46+
47+
vardict=newSet();
48+
dict.add('leet');
49+
dict.add('code');
50+
dict.add('cod');
51+
dict.add('de');
52+
53+
wordBreak('leetcode',dict)

‎144 Binary Tree Preorder Traversal My Submissions Question.js

Lines changed: 50 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -14,21 +14,60 @@
1414
*@return {number[]}
1515
*/
1616

17+
// var preorderTraversal = function(root) {
18+
// var result = [];
19+
20+
// traverse(root, result);
21+
22+
// return result;
23+
// };
24+
25+
// function traverse(node, result) {
26+
// if(!node) {
27+
// return;
28+
// }
29+
30+
// result.push(node.val);
31+
32+
// traverse(node.left, result);
33+
// traverse(node.right, result);
34+
// }
35+
36+
37+
38+
/**
39+
* Definition for a binary tree node.
40+
* function TreeNode(val) {
41+
* this.val = val;
42+
* this.left = this.right = null;
43+
* }
44+
*/
45+
/**
46+
*@param {TreeNode} root
47+
*@return {number[]}
48+
*/
1749
varpreorderTraversal=function(root){
1850
varresult=[];
51+
52+
if(root===null){
53+
returnresult;
54+
}
55+
56+
varstack=[];
57+
stack.push(root);
1958

20-
traverse(root,result);
59+
while(stack.length){
60+
varnode=stack.pop();
61+
result.push(node.val);
62+
63+
if(node.right!==null){
64+
stack.push(node.right);
65+
}
66+
if(node.left!==null){
67+
stack.push(node.left);
68+
}
69+
}
2170

2271
returnresult;
2372
};
2473

25-
functiontraverse(node,result){
26-
if(!node){
27-
return;
28-
}
29-
30-
result.push(node.val);
31-
32-
traverse(node.left,result);
33-
traverse(node.right,result);
34-
}
Lines changed: 48 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,48 @@
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+
*@param {TreeNode} root
10+
*@return {number[]}
11+
*/
12+
varpostorderTraversal=function(root){
13+
varresult=[];
14+
varstack=[];
15+
varprev=null;
16+
varcurr=null;
17+
18+
if(root===null){
19+
returnresult;
20+
}
21+
22+
stack.push(root);
23+
24+
// use prev and curr to figure out the direction of tree traversal
25+
while(stack.length!==0){
26+
curr=stack[stack.length-1];
27+
28+
if(prev===null||prev.left===curr||prev.right===curr){// traverse down the tree
29+
if(curr.left!==null){
30+
stack.push(curr.left);
31+
}elseif(curr.right!==null){
32+
stack.push(curr.right);
33+
}
34+
}elseif(curr.left===prev){//traverse up the tree from the left
35+
if(curr.right!==null){
36+
stack.push(curr.right);
37+
}
38+
}else{
39+
// it means that curr === prev
40+
result.push(curr.val);
41+
stack.pop();
42+
}
43+
44+
prev=curr;
45+
}
46+
47+
returnresult;
48+
};

‎249 Group Shifted Strings.js

Lines changed: 45 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,45 @@
1+
// Given a string, we can "shift" each of its letter to its successive letter, for example: "abc" -> "bcd". We can keep "shifting" which forms the sequence:
2+
3+
// "abc" -> "bcd" -> ... -> "xyz"
4+
// Given a list of strings which contains only lowercase alphabets, group all strings that belong to the same shifting sequence.
5+
6+
// For example, given: ["abc", "bcd", "acef", "xyz", "az", "ba", "a", "z"],
7+
// A solution is:
8+
9+
// [
10+
// ["abc","bcd","xyz"],
11+
// ["az","ba"],
12+
// ["acef"],
13+
// ["a","z"]
14+
// ]
15+
// reference: http://blog.csdn.net/pointbreak1/article/details/48780345
16+
17+
/**
18+
*@param {string[]} strings
19+
*@return {string[][]}
20+
*/
21+
vargroupStrings=function(strings){
22+
varresult=[];
23+
varmap=newMap();
24+
25+
for(vari=0;i<strings.length;i++){
26+
varshift='';
27+
varstring=strings[i]
28+
for(varj=0;j<string.length;j++){
29+
shift+=(string.charCodeAt(j)-string.charCodeAt(0)+26)%26;
30+
shift+=' ';
31+
}
32+
if(map.has(shift)){
33+
map.get(shift).push(string);
34+
}else{
35+
map.set(shift,[string]);
36+
}
37+
}
38+
39+
map.forEach((value,key)=>{
40+
result.push(value);
41+
});
42+
43+
44+
returnresult;
45+
};

0 commit comments

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