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

Commit893650b

Browse files
committed
add more solution
1 parentd02932f commit893650b

File tree

41 files changed

+1854
-111
lines changed

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

41 files changed

+1854
-111
lines changed
Lines changed: 55 additions & 33 deletions
Original file line numberDiff line numberDiff line change
@@ -1,3 +1,22 @@
1+
// Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).
2+
3+
// For example:
4+
// Given binary tree [3,9,20,null,null,15,7],
5+
// 3
6+
// / \
7+
// 9 20
8+
// / \
9+
// 15 7
10+
// return its zigzag level order traversal as:
11+
// [
12+
// [3],
13+
// [20,9],
14+
// [15,7]
15+
// ]
16+
// Hide Company Tags LinkedIn Bloomberg Microsoft
17+
// Hide Tags Tree Breadth-first Search Stack
18+
// Hide Similar Problems (E) Binary Tree Level Order Traversal
19+
120
/**
221
* Definition for a binary tree node.
322
* function TreeNode(val) {
@@ -10,47 +29,50 @@
1029
*@return {number[][]}
1130
*/
1231
varzigzagLevelOrder=function(root){
13-
varresult=[]
32+
// bfs
1433

1534
if(!root){
16-
returnresult;
35+
return[];
1736
}
1837

19-
varfromLeft=false;
20-
varcurLvl=[];
21-
curLvl.push(root);
22-
23-
varnextLvl=[];
24-
vartemp=[];
25-
26-
while(curLvl.length!==0){
27-
varp=curLvl.pop();
28-
temp.push(p.val);
38+
varcurLevel=[];
39+
curLevel.push(root);
40+
41+
varfromLeft=true;
42+
varresult=[];
43+
vartmpResult=[];
44+
varnextLevel=[];
45+
46+
while(curLevel.length>0){
47+
varlen=curLevel.length;
2948

30-
if(fromLeft){
31-
if(p.left){
32-
nextLvl.push(p.left);
33-
}
34-
if(p.right){
35-
nextLvl.push(p.right);
36-
}
37-
}else{
38-
if(p.right){
39-
nextLvl.push(p.right);
40-
}
41-
if(p.left){
42-
nextLvl.push(p.left);
49+
for(vari=0;i<len;i++){
50+
varnode=curLevel.pop();
51+
tmpResult.push(node.val);
52+
53+
if(fromLeft){
54+
if(node.left){
55+
nextLevel.push(node.left);
56+
}
57+
if(node.right){
58+
nextLevel.push(node.right);
59+
}
60+
}else{
61+
if(node.right){
62+
nextLevel.push(node.right);
63+
}
64+
if(node.left){
65+
nextLevel.push(node.left);
66+
}
4367
}
4468
}
4569

46-
if(curLvl.length===0){
47-
fromLeft=!fromLeft;
48-
result.push(temp);
49-
temp=[];
50-
curLvl=nextLvl;
51-
nextLvl=[];
52-
}
70+
fromLeft=!fromLeft;
71+
curLevel=nextLevel;
72+
nextLevel=[];
73+
result.push(tmpResult);
74+
tmpResult=[];
5375
}
5476

55-
returnresult
77+
returnresult;
5678
};

‎117 Populating Next Right Pointer.js

Lines changed: 69 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,69 @@
1+
// Follow up for problem "Populating Next Right Pointers in Each Node".
2+
3+
// What if the given tree could be any binary tree? Would your previous solution still work?
4+
5+
// Note:
6+
7+
// You may only use constant extra space.
8+
// For example,
9+
// Given the following binary tree,
10+
// 1
11+
// / \
12+
// 2 3
13+
// / \ \
14+
// 4 5 7
15+
// After calling your function, the tree should look like:
16+
// 1 -> NULL
17+
// / \
18+
// 2 -> 3 -> NULL
19+
// / \ \
20+
// 4-> 5 -> 7 -> NULL
21+
// Hide Company Tags Microsoft Bloomberg Facebook
22+
// Hide Tags Tree Depth-first Search
23+
// Hide Similar Problems (M) Populating Next Right Pointers in Each Node
24+
25+
26+
27+
/**
28+
* Definition for binary tree with next pointer.
29+
* function TreeLinkNode(val) {
30+
* this.val = val;
31+
* this.left = this.right = this.next = null;
32+
* }
33+
*/
34+
35+
/**
36+
*@param {TreeLinkNode} root
37+
*@return {void} Do not return anything, modify tree in-place instead.
38+
*/
39+
varconnect=function(root){
40+
if(!root){
41+
return;
42+
}
43+
44+
// leftEnd is used to track the current left most node
45+
varleftEnd=root;
46+
47+
while(leftEnd!==null){
48+
varcur=leftEnd;
49+
// dummy is used to point to the next level's leftEnd
50+
vardummy=newTreeLinkNode(0);
51+
varpre=dummy;
52+
// for each level we use leftEnd and leftEnd next to achieve level traversal
53+
while(cur!==null){
54+
if(cur.left!==null){
55+
pre.next=cur.left;
56+
pre=cur.left;
57+
}
58+
59+
if(cur.right!==null){
60+
pre.next=cur.right;
61+
pre=cur.right;
62+
}
63+
64+
cur=cur.next;
65+
}
66+
67+
leftEnd=dummy.next;
68+
}
69+
};

‎117 Populating Next Right Pointers in Each Node II.js

Whitespace-only changes.

‎125 Valid Palindrome.js

Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
// Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.
2+
3+
// For example,
4+
// "A man, a plan, a canal: Panama" is a palindrome.
5+
// "race a car" is not a palindrome.
6+
7+
// Note:
8+
// Have you consider that the string might be empty? This is a good question to ask during an interview.
9+
10+
// For the purpose of this problem, we define empty string as valid palindrome.
11+
12+
// Hide Company Tags Microsoft Uber Facebook Zenefits
13+
// Hide Tags Two Pointers String
14+
// Hide Similar Problems (E) Palindrome Linked List
15+
16+
17+
/**
18+
*@param {string} s
19+
*@return {boolean}
20+
*/
21+
varisPalindrome=function(s){
22+
s=s.toLowerCase();
23+
varbeg=0;
24+
varend=s.length-1;
25+
26+
while(beg<end){
27+
if(!s[beg].match(/[a-z0-9]/)){
28+
beg++;
29+
}elseif(!s[end].match(/[a-z0-9]/)){
30+
end--;
31+
}elseif(s[beg]!==s[end]){
32+
returnfalse;
33+
}else{
34+
end--;
35+
beg++;
36+
}
37+
}
38+
39+
returntrue;
40+
};

‎149 Max Points on a Line.js

Lines changed: 69 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,69 @@
1+
解这个平面几何题有3个要点：
2+
3+
1.如何判断共线?
4+
两点成一直线，所以两点没有共线不共线之说。对于点p1(x1,y1)，p2(x2,y2)，p3(x3,y3)来说，共线的条件是p1-p2连线的斜率与p1-p3连线的斜率相同，即
5+
(y2-y1)/(x2-x1)=(y3-y1)/(x3-x1)
6+
所以对共线的n点，其中任意两点连线的斜率相同。
7+
8+
2.如何判断最多的共线点?
9+
对于每个点p出发，计算该点到所有其他点qi的斜率，对每个斜率统计有多少个点符合。其中最多的个数加1（出发点本身）即为最多的共线点。
10+
11+
3.特殊情况
12+
当x1=x2，y1!=y2时，为垂直连线。计算斜率时分母为0会出错。
13+
当x1=x2，y1=y2时，两点重合。则(x2,y2)和所有(x1,y1)的连线共线。
14+
15+
16+
1
17+
2
18+
3
19+
4
20+
5
21+
6
22+
7
23+
8
24+
9
25+
10
26+
11
27+
12
28+
13
29+
14
30+
15
31+
16
32+
17
33+
18
34+
19
35+
20
36+
21
37+
22
38+
23
39+
24
40+
25
41+
26
42+
27
43+
classSolution{
44+
public:
45+
intmaxPoints(vector<Point>&points){
46+
intmaxPts=0;
47+
for(inti=0;i<points.size();i++){
48+
intnMax=0,nSame=0,nInf=0;
49+
unordered_map<float,int>comSlopes;
50+
51+
for(intj=i+1;j<points.size();j++){
52+
if(points[j].x==points[i].x){
53+
if(points[j].y==points[i].y)
54+
nSame++;
55+
else
56+
nInf++;
57+
continue;
58+
}
59+
floatslope=(float)(points[j].y-points[i].y)/(float)(points[j].x-points[i].x);
60+
comSlopes[slope]++;
61+
nMax=max(nMax,comSlopes[slope]);
62+
}
63+
64+
nMax=max(nMax,nInf)+nSame+1;
65+
maxPts=max(maxPts,nMax);
66+
}
67+
returnmaxPts;
68+
}
69+
};

‎161 One Edit Distance.js

Lines changed: 45 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,45 @@
1+
// Given two strings S and T, determine if they are both one edit distance apart.
2+
3+
// Hide Company Tags Snapchat Uber Facebook Twitter
4+
// Hide Tags String
5+
// Hide Similar Problems (H) Edit Distance
6+
7+
8+
/**
9+
*@param {string} s
10+
*@param {string} t
11+
*@return {boolean}
12+
*/
13+
14+
// tricky question!
15+
16+
varisOneEditDistance=function(s,t){
17+
if(s.length>t.length){
18+
vartmp=s;
19+
s=t;
20+
t=tmp;
21+
}
22+
23+
if((t.length-s.length)>1){
24+
returnfalse;
25+
}
26+
27+
varfound=false;
28+
29+
for(vari=0,j=0;i<s.length;i++,j++){
30+
if(s[i]!==t[j]){
31+
32+
if(found){
33+
returnfalse;
34+
}
35+
36+
found=true;
37+
38+
if(s.length<t.length){
39+
i--;
40+
}
41+
}
42+
}
43+
44+
returnfound||s.length<t.length;
45+
};

‎191 Number of 1 Bits.js

Lines changed: 14 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -2,6 +2,20 @@
22
// Language: Javascript
33
// Problem: https://leetcode.com/problems/number-of-1-bits/
44
// Author: Chihung Yu
5+
6+
// Write a function that takes an unsigned integer and returns the number of ’1' bits it has (also known as the Hamming weight).
7+
8+
// For example, the 32-bit integer ’11' has binary representation 00000000000000000000000000001011, so the function should return 3.
9+
10+
// Credits:
11+
// Special thanks to@ts for adding this problem and creating all test cases.
12+
13+
// Hide Company Tags Microsoft Apple
14+
// Hide Tags Bit Manipulation
15+
// Hide Similar Problems (E) Reverse Bits (E) Power of Two (M) Counting Bits
16+
17+
18+
519
/**
620
*@param {number} n - a positive integer
721
*@return {number}

0 commit comments

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