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

Commit3fad038

Browse files
committed
add some new files
1 parent0736064 commit3fad038

16 files changed

+818
-158
lines changed

‎10 Regular Expresion Matching.js

Lines changed: 74 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,74 @@
1+
// https://www.youtube.com/watch?v=l3hda49XcDE#t=211.113333
2+
3+
// Implement regular expression matching with support for '.' and '*'.
4+
5+
// '.' Matches any single character.
6+
// '*' Matches zero or more of the preceding element.
7+
8+
// The matching should cover the entire input string (not partial).
9+
10+
// The function prototype should be:
11+
// bool isMatch(const char *s, const char *p)
12+
13+
// Some examples:
14+
// isMatch("aa","a") → false
15+
// isMatch("aa","aa") → true
16+
// isMatch("aaa","aa") → false
17+
// isMatch("aa", "a*") → true
18+
// isMatch("aa", ".*") → true
19+
// isMatch("ab", ".*") → true
20+
// isMatch("aab", "c*a*b") → true
21+
22+
23+
/**
24+
*@param {string} s
25+
*@param {string} p
26+
*@return {boolean}
27+
*/
28+
varisMatch=function(s,p){
29+
varm=s.length;
30+
varn=p.length;
31+
vardp=[];
32+
33+
for(vari=0;i<=m;i++){
34+
vartmp=[];
35+
36+
for(varj=0;j<=n;j++){
37+
tmp.push(false);
38+
}
39+
40+
dp.push(tmp);
41+
}
42+
43+
dp[0][0]=true;
44+
45+
for(i=0;i<=m;i++){
46+
for(j=0;j<=n;j++){
47+
if(p[j-1]!=='.'&&p[j-1]!=='*'){
48+
if(i>0&&s[i-1]===p[j-1]&&dp[i-1][j-1]){
49+
dp[i][j]=true;
50+
}
51+
}elseif(p[j-1]==='.'){
52+
if(i>0&&dp[i-1][j-1]){
53+
dp[i][j]=true;
54+
}
55+
}elseif(j>1){// '*' cannot be the first element
56+
if(dp[i][j-1]||dp[i][j-2]){
57+
dp[i][j]=true;
58+
}elseif(i>0&&(p[j-2]==s[i-1]||p[j-2]=='.')&&dp[i-1][j]){
59+
60+
// example
61+
// xa and xa*
62+
// s[i-1] === a
63+
// p[j-2] === a
64+
// a === a
65+
// so we can now compare x, xa*
66+
// and x here is dp[i-1][j]
67+
dp[i][j]=true;
68+
}
69+
}
70+
}
71+
}
72+
73+
returndp[m][n];
74+
};

‎146 LRU Cache.js

Lines changed: 101 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,101 @@
1+
// Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.
2+
3+
// get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
4+
// set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.
5+
classNode{
6+
constructor(key,val){
7+
this.key=key;
8+
this.val=val;
9+
this.next=null;
10+
this.prev=null;
11+
}
12+
}
13+
/**
14+
*@constructor
15+
*/
16+
varLRUCache=function(capacity){
17+
this.list=null;
18+
this.map=newMap();
19+
this.head=null;
20+
this.tail=null;
21+
this.size=capacity;
22+
this.curSize=0;
23+
};
24+
25+
/**
26+
*@param {number} key
27+
*@returns {number}
28+
*/
29+
LRUCache.prototype.get=function(key){
30+
if(!this.map.get(key)){
31+
return-1;
32+
}
33+
34+
letnode=this.map.get(key);
35+
36+
if(node===this.head){
37+
returnnode.val;
38+
}
39+
40+
// remove node from list
41+
if(node===this.tail){
42+
this.tail.prev.next=null;
43+
this.tail=this.tail.prev;
44+
}else{
45+
node.prev.next=node.next;
46+
node.next.prev=node.prev;
47+
}
48+
49+
// insert node to head
50+
node.next=this.head;
51+
this.head.prev=node;
52+
this.head=node;
53+
54+
returnnode.val;
55+
};
56+
57+
/**
58+
*@param {number} key
59+
*@param {number} value
60+
*@returns {void}
61+
*/
62+
LRUCache.prototype.set=function(key,value){
63+
letnewNode=newNode(key,value);
64+
65+
if(this.curSize===0){
66+
this.tail=newNode;
67+
}else{
68+
newNode.next=this.head;
69+
this.head.prev=newNode;
70+
}
71+
72+
this.head=newNode;
73+
this.curSize++;
74+
75+
// update
76+
if(this.map.get(key)){
77+
letoldNode=this.map.get(key);
78+
79+
// remove node
80+
if(oldNode===this.tail){
81+
this.tail=this.tail.prev;
82+
this.tail.next=null;
83+
}else{
84+
oldNode.prev.next=oldNode.next;
85+
oldNode.next.prev=oldNode.prev;
86+
}
87+
88+
this.curSize--;
89+
90+
}else{
91+
if(this.curSize>this.size){
92+
//delete tail
93+
this.map.delete(this.tail.key);
94+
this.tail=this.tail.prev;
95+
this.tail.next=null;
96+
this.curSize--;
97+
}
98+
}
99+
100+
this.map.set(key,newNode);
101+
};

‎222. Count Complete Tree Nodes.js

Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,38 @@
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+
varcountNodes=function(root){
13+
returntreeNodes(root);
14+
15+
functiontreeNodes(node){
16+
if(!node){
17+
return0;
18+
}else{
19+
varleftDepth=0;
20+
varrightDepth=0;
21+
varleftChild=node.left;
22+
while(leftChild){
23+
leftDepth++;
24+
leftChild=leftChild.left;
25+
}
26+
varrightChild=node.right;
27+
while(rightChild){
28+
rightDepth++;
29+
rightChild=rightChild.right;
30+
}
31+
if(leftDepth===rightDepth){
32+
returnMath.pow(2,leftDepth+1)-1;
33+
}else{
34+
returntreeNodes(node.left)+treeNodes(node.right)+1;
35+
}
36+
}
37+
}
38+
};
Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
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+
*@param {TreeNode} p
11+
*@param {TreeNode} q
12+
*@return {TreeNode}
13+
*/
14+
15+
// http://www.cnblogs.com/anne-vista/p/4815076.html
16+
varlowestCommonAncestor=function(root,p,q){
17+
if(root===null||root===p||root===q){
18+
returnroot;
19+
}
20+
21+
varl=lowestCommonAncestor(root.left,p,q);
22+
varr=lowestCommonAncestor(root.right,p,q);
23+
24+
if(l!==null&&r!==null){
25+
// p and q are on two different side of root node.
26+
returnroot;
27+
}
28+
29+
return(l!==null) ?l :r;// either one of p, q is on one side OR p, q is not in l&r subtrees
30+
};

‎257 Binary Tree Paths.js

Lines changed: 53 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,53 @@
1+
// Given a binary tree, return all root-to-leaf paths.
2+
3+
// For example, given the following binary tree:
4+
5+
// 1
6+
// / \
7+
// 2 3
8+
// \
9+
// 5
10+
// All root-to-leaf paths are:
11+
12+
// ["1->2->5", "1->3"]
13+
14+
15+
/**
16+
* Definition for a binary tree node.
17+
* function TreeNode(val) {
18+
* this.val = val;
19+
* this.left = this.right = null;
20+
* }
21+
*/
22+
/**
23+
*@param {TreeNode} root
24+
*@return {string[]}
25+
*/
26+
varbinaryTreePaths=function(root){
27+
varresult=[];
28+
29+
if(root!==null){
30+
traverse(root,[],result);
31+
}
32+
33+
returnresult;
34+
};
35+
36+
vartraverse=function(node,path,result){
37+
path.push(node.val);
38+
39+
if(node.left||node.right){
40+
if(node.left){
41+
traverse(node.left,path,result);
42+
path.pop();
43+
}
44+
45+
if(node.right){
46+
traverse(node.right,path,result);
47+
path.pop();
48+
}
49+
// path.pop()
50+
}else{
51+
result.push(path.join("->"));
52+
}
53+
}

‎263 Ugly Number.js

Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,27 @@
1+
// 263. Ugly Number
2+
3+
// Write a program to check whether a given number is an ugly number.
4+
5+
// Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 6, 8 are ugly while 14 is not ugly since it includes another prime factor 7.
6+
7+
// Note that 1 is typically treated as an ugly number.
8+
9+
/**
10+
*@param {number} num
11+
*@return {boolean}
12+
*/
13+
varisUgly=function(num){
14+
while(num>=2){
15+
if(num%2===0){
16+
num/=2;
17+
}elseif(num%3===0){
18+
num/=3;
19+
}elseif(num%5===0){
20+
num/=5;
21+
}else{
22+
returnfalse;
23+
}
24+
}
25+
26+
returnnum===1;
27+
};

‎264 Ugly Number II.js

Lines changed: 41 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,41 @@
1+
// 264. Ugly Number II
2+
3+
// Write a program to find the n-th ugly number.
4+
5+
// Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.
6+
7+
// Note that 1 is typically treated as an ugly number.
8+
9+
/**
10+
*@param {number} n
11+
*@return {number}
12+
*/
13+
varnthUglyNumber=function(n){
14+
varuglys=[1];
15+
varp2=0;
16+
varp3=0;
17+
varp5=0;
18+
19+
while(uglys.length<n){
20+
varugly2=uglys[p2]*2;
21+
varugly3=uglys[p3]*3;
22+
varugly5=uglys[p5]*5;
23+
24+
varminV=Math.min(ugly2,ugly3,ugly5);
25+
26+
if(minV===ugly2){
27+
p2++;
28+
}
29+
if(minV===ugly3){
30+
p3++;
31+
}
32+
if(minV===ugly5){
33+
p5++;
34+
}
35+
if(minV!==uglys[uglys.length-1]){
36+
uglys.push(minV);
37+
}
38+
}
39+
40+
returnuglys[n-1];
41+
};

0 commit comments

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