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

Commita12c922

Browse files
author
Chihung Yu
committed
add more
1 parent73fca78 commita12c922

4 files changed

+300
-1
lines changed

‎127 Word Ladder II.jsrenamed to‎127 Word Ladder.js

Lines changed: 0 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -32,7 +32,6 @@ var ladderLength = function(beginWord, endWord, wordDict) {
3232
curLvlCnt--;
3333

3434
for(vari=0;i<cur.length;i++){
35-
3635
for(varj=0;j<26;j++){
3736
varchar=String.fromCharCode('a'.charCodeAt(0)+j);
3837
varword=cur.replaceAt(i,char);

‎208 Implement Trie (Prefix Tree).js

Lines changed: 86 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,86 @@
1+
/**
2+
*@constructor
3+
* Initialize your data structure here.
4+
*/
5+
// http://www.cnblogs.com/Liok3187/p/4626730.html
6+
varTrieNode=function(key){
7+
return{
8+
key:key,
9+
isWord:false,
10+
children:{}
11+
}
12+
};
13+
14+
varTrie=function(){
15+
this.root=TrieNode();
16+
};
17+
18+
/**
19+
*@param {string} word
20+
*@return {void}
21+
* Inserts a word into the trie.
22+
*/
23+
Trie.prototype.insert=function(word){
24+
vartree=this.root;
25+
vari,curr;
26+
27+
for(i=0;i<word.length;i++){
28+
curr=word[i];
29+
if(!tree.children[curr]){
30+
tree.children[curr]=TrieNode(curr);
31+
}
32+
tree=tree.children[curr];
33+
}
34+
35+
tree.isWord=true;
36+
};
37+
38+
/**
39+
*@param {string} word
40+
*@return {boolean}
41+
* Returns if the word is in the trie.
42+
*/
43+
Trie.prototype.search=function(word){
44+
vartree=this.root;
45+
46+
for(vari=0;i<word.length;i++){
47+
varcurr=word[i];
48+
49+
if(!tree.children[curr]){
50+
returnfalse;
51+
}
52+
53+
tree=tree.children[curr];
54+
}
55+
56+
returntree.isWord;
57+
};
58+
59+
/**
60+
*@param {string} prefix
61+
*@return {boolean}
62+
* Returns if there is any word in the trie
63+
* that starts with the given prefix.
64+
*/
65+
Trie.prototype.startsWith=function(prefix){
66+
vartree=this.root;
67+
68+
for(vari=0;i<prefix.length;i++){
69+
varcurr=prefix[i];
70+
71+
if(!tree.children[curr]){
72+
returnfalse;
73+
}
74+
75+
tree=tree.children[curr];
76+
}
77+
78+
returntrue;
79+
};
80+
81+
/**
82+
* Your Trie object will be instantiated and called as such:
83+
* var trie = new Trie();
84+
* trie.insert("somestring");
85+
* trie.search("key");
86+
*/
Lines changed: 183 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,183 @@
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+
/**
10+
* Encodes a tree to a single string.
11+
*
12+
*@param {TreeNode} root
13+
*@return {string}
14+
*/
15+
// http://fisherlei.blogspot.com/2013/03/interview-serialize-and-de-serialize.html
16+
varserialize=function(root){
17+
varresult=[];
18+
serializer(root,result);
19+
20+
returnresult.join(",");
21+
};
22+
23+
varserializer=function(node,output){
24+
if(node===null){
25+
output.push("#");
26+
return;
27+
}
28+
29+
output.push(node.val);
30+
serializer(node.left,output);
31+
serializer(node.right,output);
32+
}
33+
34+
/**
35+
* Decodes your encoded data to tree.
36+
*
37+
*@param {string} data
38+
*@return {TreeNode}
39+
*/
40+
vardeserialize=function(data){
41+
data=data.split(",");
42+
varindex=0;
43+
44+
functiondeserializer(data){
45+
if(index>data.length||data[index]==="#"){
46+
returnnull;
47+
}
48+
49+
varnode=newTreeNode(parseInt(data[index]));
50+
index++;
51+
node.left=deserializer(data,index);
52+
index++;
53+
54+
node.right=deserializer(data,index);
55+
returnnode;
56+
}
57+
58+
returndeserializer(data);
59+
};
60+
61+
62+
63+
/**
64+
* Your functions will be called as such:
65+
* deserialize(serialize(root));
66+
*/
67+
68+
69+
/*
70+
* Definition for a binary tree node.
71+
* function TreeNode(val) {
72+
* this.val = val;
73+
* this.left = this.right = null;
74+
* }
75+
*/
76+
77+
/**
78+
* Encodes a tree to a single string.
79+
*
80+
*@param {TreeNode} root
81+
*@return {string}
82+
*/
83+
// var serialize = function(root) {
84+
// if(!root) {
85+
// return "";
86+
// }
87+
88+
// var result = [];
89+
// var curLvl = [];
90+
// var nextLvl = [];
91+
// curLvl.push(root);
92+
93+
// while(curLvl.length) {
94+
// var node = curLvl.shift();
95+
96+
// if(node) {
97+
// result.push(node.val);
98+
99+
// if(node.left) {
100+
// nextLvl.push(node.left);
101+
// } else {
102+
// nextLvl.push(null);
103+
// }
104+
105+
// if(node.right) {
106+
// nextLvl.push(node.right);
107+
// } else {
108+
// nextLvl.push(null);
109+
// }
110+
// } else {
111+
// result.push(null);
112+
// }
113+
114+
// if(curLvl.length === 0) {
115+
// curLvl = nextLvl;
116+
// nextLvl = [];
117+
// }
118+
// }
119+
120+
// console.log('serialize: ',result)
121+
122+
// return result.join(',');
123+
// };
124+
125+
/**
126+
* Decodes your encoded data to tree.
127+
*
128+
*@param {string} data
129+
*@return {TreeNode}
130+
*/
131+
// var deserialize = function(data) {
132+
// if(data === "") {
133+
// return null
134+
// }
135+
136+
// data = data.split(',');
137+
138+
// var val = data.shift();
139+
// var root = new TreeNode(val);
140+
141+
// var curLvlCnt = 1;
142+
// var nextLvlCnt = 0;
143+
// var lvl = [];
144+
// lvl.push(root);
145+
146+
// while(data.length) {
147+
// var node = lvl.shift();
148+
// curLvlCnt--;
149+
150+
// var leftVal = data.shift();
151+
// var rightVal = data.shift();
152+
153+
// if(leftVal) {
154+
// node.left = new TreeNode(leftVal);
155+
// nextLvlCnt++;
156+
// lvl.push(node.left);
157+
// } else {
158+
// node.left = null;
159+
// }
160+
161+
// if(rightVal) {
162+
// node.right = new TreeNode(rightVal);
163+
// nextLvlCnt++;
164+
// lvl.push(node.right);
165+
// } else {
166+
// node.right = null;
167+
// }
168+
169+
// if(curLvlCnt === 0) {
170+
// curLvlCnt = nextLvlCnt;
171+
// nextLvlCnt = 0;
172+
// }
173+
// }
174+
175+
// console.log('deserialize: ',root)
176+
177+
// return root;
178+
// };
179+
180+
/**
181+
* Your functions will be called as such:
182+
* deserialize(serialize(root));
183+
*/

‎322 Coin Change.js

Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
/**
2+
*@param {number[]} coins
3+
*@param {number} amount
4+
*@return {number}
5+
*/
6+
varcoinChange=function(coins,amount){
7+
vardp=[0];
8+
for(vari=1;i<=amount;i++){
9+
dp.push(-1);
10+
}
11+
12+
for(vara=0;a<amount;a++){
13+
if(dp[a]<0){
14+
continue;
15+
}
16+
17+
for(varc=0;c<coins.length;c++){
18+
varcoin=coins[c];
19+
20+
if((a+coin)>amount){
21+
continue;
22+
}
23+
24+
if(dp[a+coin]<0||dp[a+coin]>dp[a]+1){
25+
dp[a+coin]=dp[a]+1;
26+
}
27+
}
28+
}
29+
30+
returndp[amount];
31+
};

0 commit comments

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