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

Commitc99a218

Browse files
committed
resume, add maximal squares, verify binary tree
1 parentcfd4c0e commitc99a218

File tree

6 files changed

+127
-0
lines changed

6 files changed

+127
-0
lines changed

‎Easy/101-symmetricTree.js‎

Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -21,6 +21,18 @@ var isSymmetricHelper = function(left, right) {
2121
returnisSymmetricHelper(left.left,right.right)&&isSymmetricHelper(left.right,right.left);
2222
};
2323

24+
// second try, not good.
25+
varhelper=function(left,right){
26+
if(!left||!right){
27+
if(!left&&!right)returntrue;
28+
returnfalse;
29+
}
30+
if((left.val===right.val)&&helper(left.left,right.right)&&helper(left.right,right.left)){
31+
returntrue;
32+
}
33+
returnfalse;
34+
}
35+
2436
// iterative
2537
varisSymmetric=function(root){
2638
if(!root)returntrue;

‎Medium/17-LetterCombinationsPhoneNumber.js‎

Lines changed: 15 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -36,3 +36,18 @@ var combinationHelper = function(digits, results, result) {
3636
result.pop();
3737
}
3838
};
39+
40+
// second try
41+
varcombinationHelper=function(digits,results,result){
42+
if(!digits){
43+
results.push(result.join(''));
44+
result=[];
45+
return;
46+
}
47+
varletters=map[digits[0]];
48+
for(varj=0;j<letters.length;j++){
49+
result.push(letters[j]);
50+
combinationHelper(digits.substring(1),results,result);
51+
result.pop();
52+
}
53+
};

‎Medium/221-maximalSquare.js‎

Lines changed: 37 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,37 @@
1+
/**
2+
* Solution: only current element's top left element is 1, the square numbers is possible to increase 1.
3+
* If the element's left, top is 1, yes, then the square numbers adds 1. Otherwise, set the square number of
4+
* current element to Min(topleft, left, top) + 1.
5+
* If current element's top left element is 0, just simply set current element's square number to be 0;
6+
* The formular is dp[i][j] = Math.min(dp[i-1][j], dp[i-1][j-1], dp[i][j-1]) + 1;
7+
* or dp[i][j] = 0, if matrix[i-1][j-1] == 0
8+
*
9+
*@param {character[][]} matrix
10+
*@return {number}
11+
*/
12+
varmaximalSquare=function(matrix){
13+
varrows=matrix.length;
14+
if(rows===0)return0;
15+
varcols=matrix[0].length;
16+
varsquares=[[0]];// the two dimensional array is not fully initialized yet.
17+
varresult=0;
18+
19+
for(vari=1;i<=rows;i++){
20+
squares.push([0]);
21+
for(varj=1;j<=cols;j++){
22+
squares[0][j]=0;
23+
if(matrix[i-1][j-1]==='1'){
24+
squares[i][j]=Math.min(squares[i-1][j],squares[i-1][j-1],squares[i][j-1])+1;
25+
result=Math.max(result,squares[i][j]);
26+
}else{
27+
// In JavaScript, assign 0 to an undefined element in the array.
28+
squares[i][j]=0;
29+
}
30+
}
31+
}
32+
returnresult*result;
33+
};
34+
35+
// test cases
36+
// ["1"]
37+
// ["1010","1011","1111","1001"]

‎Medium/331-verifyBinaryTree.js‎

Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
/**
2+
* Solution: use stack
3+
* Note, stack[stack.length - 3] !== '#' is important. for the case "9, #, #,#,# "
4+
*@param {string} preorder
5+
*@return {boolean}
6+
*/
7+
varisValidSerialization=function(preorder){
8+
varstack=[];
9+
vari=0;
10+
varnewStr=preorder.split(',');
11+
varlength=newStr.length;
12+
13+
while(i<length){
14+
stack.push(newStr[i]);
15+
while(stack.length>2&&stack[stack.length-1]==='#'&&
16+
stack[stack.length-2]==='#'&&stack[stack.length-3]!=='#'){
17+
stack.pop();
18+
stack.pop();
19+
stack.pop();
20+
stack.push('#');
21+
}
22+
i++;
23+
}
24+
25+
if(stack.length===1&&stack[0]==='#'){
26+
returntrue;
27+
}
28+
returnfalse;
29+
};
30+
31+
32+
// Testing cases
33+
// "9,3,4,#,#,1,#,#,2,#,6,#,#"
34+
// "1, #, #, #, #"

‎Medium/74-search2DMatrix.js‎

Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -25,3 +25,30 @@ var findElementByIndex = function(matrix, index, m, n) {
2525
varcol=index-n*row;
2626
returnmatrix[row][col];
2727
};
28+
29+
// second try
30+
varsearchMatrix=function(matrix,target){
31+
varlow=0;
32+
varrows=matrix.length;
33+
varcols=matrix[0].length;
34+
varhigh=rows*cols-1;
35+
while(low<=high){
36+
varmid=low+Math.floor((high-low)/2);
37+
varmidElement=findElementByIndex(matrix,mid,cols);
38+
if(midElement===target){
39+
returntrue;
40+
}elseif(midElement>target){
41+
high=mid-1;
42+
}else{
43+
low=mid+1;
44+
}
45+
}
46+
returnfalse;
47+
};
48+
49+
// only need n (columns).
50+
varfindElementByIndex=function(matrix,index,n){
51+
varrow=Math.floor(index/n);
52+
varcol=Math.floor(index%n);
53+
returnmatrix[row][col];
54+
};

‎README.md‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -154,6 +154,7 @@
154154
*[213. House Robber II](https://leetcode.com/problems/house-robber-ii/) -[Solution](./Medium/213-houseRobberII.js)
155155
*[215. Kth Largest Element in an Array](https://leetcode.com/problems/kth-largest-element-in-an-array/) -[Solution](./Medium/215-KthLargestElementInArray.js)
156156
*[216. Combination Sum III](https://leetcode.com/problems/combination-sum-iii/) -[Solution](./Medium/216-CombinationSumIII.js)
157+
*[221. Maximal Square](https://leetcode.com/problems/maximal-square/) -[Solution](./Medium/221-maximalSquare.js)
157158
*[229. Majority Element II](https://leetcode.com/problems/majority-element-ii/) -[Solution](./Medium/229-majorityElementII.js)
158159
*[230. Kth Smallest Element in a BST](https://leetcode.com/problems/kth-smallest-element-in-a-bst/) -[Solution](./Medium/230-kthSmallestElementinBST.js)
159160
*[238. Product of Array Except Self](https://leetcode.com/problems/product-of-array-except-self/) -[Solution](./Medium/238-productExceptSelf.js)
@@ -166,6 +167,7 @@
166167
*[309. Best Time to Buy and Sell Stock with Cooldown](https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/) -[Solution](./Medium/309-bestTimeStockCooldown.js)
167168
*[318. Maximum Product of Word Lengths](https://leetcode.com/problems/maximum-product-of-word-lengths/) -[Solution](./Medium/318-maximumProductWordLengths.js)
168169
*[319. Bulb Switcher](https://leetcode.com/problems/bulb-switcher/) -[Solution](./Medium/319-bulbSwitcher.js)
170+
*[331. Verify Preorder Serialization of a Binary Tree](https://leetcode.com/problems/verify-preorder-serialization-of-a-binary-tree/) -[Solution](./Medium/331-verifyBinaryTree.js)
169171
*[337. House Robber III](https://leetcode.com/problems/house-robber-iii/) -[Solution](./Medium/337-houseRobberIII.js)
170172
*[347. Top K Frequent Elements](https://leetcode.com/problems/top-k-frequent-elements/) -[Solution](./Medium/247-topKFrequentElements.js)
171173

0 commit comments

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