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

Commit6a694ae

Browse files
Merge pull requestchihungyu1116#4 from ignacio-chiazzo/master
Added another solution to Permutation ||
2 parentsf6903cc +13b5dbd commit6a694ae

File tree

5 files changed

+149
-26
lines changed

5 files changed

+149
-26
lines changed

‎114 Flatten Binary Tree to Linked List.js

Lines changed: 26 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -16,21 +16,44 @@
1616
varflatten=function(root){
1717
varstack=[];
1818
varp=root;
19-
19+
2020
while(p!==null||stack.length!==0){
2121
if(p.right!==null){
2222
stack.push(p.right);
2323
}
24-
24+
2525
if(p.left!==null){// [!!!]point of confusing, if null then pop stack
2626
p.right=p.left;
2727
p.left=null;
2828
}elseif(stack.length!==0){
2929
varnode=stack.pop();
3030
p.right=node;
3131
}
32-
32+
3333
p=p.right;
3434
}
3535
};
3636

37+
// Recursive solution
38+
39+
varflatten=function(root){
40+
if(root===null||(root.left===null&&root.right===null)){
41+
return;
42+
}
43+
44+
varrootLeft=root.left;
45+
varrootRight=root.right;
46+
root.left=null;
47+
root.right=null;
48+
49+
flatten(rootLeft);
50+
flatten(rootRight);
51+
52+
root.right=rootLeft;
53+
54+
varaux=root;
55+
while(aux!==null&&aux.right!==null){
56+
aux=aux.right;
57+
}
58+
aux.right=rootRight;
59+
};

‎39 Combination Sum.js

Lines changed: 35 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -5,8 +5,8 @@
55
// Note:
66
// All numbers (including target) will be positive integers.
77
// The solution set must not contain duplicate combinations.
8-
// For example, given candidate set [2, 3, 6, 7] and target 7,
9-
// A solution set is:
8+
// For example, given candidate set [2, 3, 6, 7] and target 7,
9+
// A solution set is:
1010
// [
1111
// [7],
1212
// [2, 2, 3]
@@ -24,37 +24,61 @@
2424
*/
2525
varcombinationSum=function(candidates,target){
2626
varresult=[];
27-
27+
2828
if(candidates===null||candidates.length===0){
2929
returnresult;
3030
}
31-
31+
3232
candidates.sort(function(a,b){returna>b ?1 :-1});
33-
33+
3434
varoutput=[];
35-
35+
3636
generate(candidates,result,output,target,0);
37-
37+
3838
returnresult;
3939
};
4040

4141
vargenerate=function(candidates,result,output,sum,index){
4242
if(sum===0){
43-
result.push(output.slice());
43+
result.push(output.slice());
4444
}
4545
if(sum<0){
4646
return;
4747
}
48-
48+
4949
for(vari=index;i<candidates.length;i++){
5050
if(i>index&&candidates[i]===candidates[i-1]){
5151
continue;
5252
}
53-
53+
5454
if(candidates[i]<=sum){
5555
output.push(candidates[i]);
5656
generate(candidates,result,output,sum-candidates[i],i);
5757
output.pop();
5858
}
5959
}
60-
}
60+
}
61+
62+
63+
// Another solution
64+
varcombinationSum=function(candidates,target){
65+
varresults=[];
66+
comb(candidates.sort(),0,[],0,target,results);
67+
returnresults;
68+
};
69+
70+
varcomb=function(cand,index,partial,partialSum,target,results){
71+
if(target===partialSum){
72+
results.push(partial);
73+
return;
74+
}
75+
if(cand.length===index||partialSum>target){
76+
return;
77+
}
78+
79+
comb(cand,index+1,partial,partialSum,target,results);
80+
comb(cand,index,partial.concat([cand[index]].concat([cand[index]])),
81+
partialSum+2*cand[index],target,results);
82+
comb(cand,index+1,partial.concat([cand[index]]),
83+
partialSum+cand[index],target,results);
84+
};

‎47 Permutations II.js

Lines changed: 29 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -50,4 +50,32 @@ var generatePermute = function(nums, step, currentResult, visited, finalResult)
5050
visited[i]=false;
5151
}
5252
}
53-
}
53+
}
54+
55+
//Another Solution, similar approach that Permutation.js
56+
varpermuteUnique=function(nums){
57+
returnpermut(nums.sort(),[]);
58+
};
59+
60+
varpermut=function(nums,partial){
61+
if(nums.length===0){
62+
return[partial];
63+
}
64+
varlistSol=[];
65+
for(vari=0;i<nums.length;i++){
66+
varendRepeated=i;
67+
while(endRepeated<nums.length&&nums[i]===nums[endRepeated]){
68+
endRepeated++;
69+
}
70+
71+
vararrayWithoutI=nums.slice(0,i).concat(nums.slice(i+1,nums.length));
72+
varpartialSol=partial.concat([nums[i]]);
73+
varsol=permut(arrayWithoutI,partialSol);
74+
if(sol.length>0){
75+
listSol=listSol.concat(sol);
76+
}
77+
i=endRepeated-1;
78+
}
79+
returnlistSol;
80+
};
81+

‎48 Rotate Image.js

Lines changed: 38 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -11,20 +11,20 @@
1111
*/
1212
varrotate=function(matrix){
1313
varrow=matrix.length;
14-
14+
1515
if(row===0){
1616
return;
1717
}
18-
18+
1919
varcol=matrix[0].length;
20-
20+
2121
// swap them in diagonal
2222
for(vari=0;i<row;i++){
2323
for(varj=0;j<col-i;j++){
2424
swap(matrix,i,j,row-1-j,col-1-i);
2525
}
2626
}
27-
27+
2828
// swap in middle
2929
for(i=0;i<Math.floor(row/2);i++){
3030
for(j=0;j<col;j++){
@@ -37,4 +37,37 @@ function swap(matrix, x1, y1, x2, y2) {
3737
vartmp=matrix[x1][y1];
3838
matrix[x1][y1]=matrix[x2][y2];
3939
matrix[x2][y2]=tmp;
40-
}
40+
}
41+
42+
//Clearer Solution
43+
varrotate=function(matrix){
44+
rotateColumns(matrix);
45+
rotateEachDiagonal(matrix);
46+
};
47+
48+
varrotateColumns=function(matrix){
49+
for(varj=0;j<matrix.length;j++){
50+
varlow=0;
51+
varceil=matrix.length-1;
52+
while(low<ceil){
53+
swap(matrix,low,j,ceil,j);
54+
low++;
55+
ceil--;
56+
}
57+
}
58+
};
59+
60+
varrotateEachDiagonal=function(matrix){
61+
for(vari=0;i<matrix.length;i++){
62+
for(varj=i;j<matrix.length;j++){
63+
swap(matrix,i,j,j,i);
64+
}
65+
}
66+
};
67+
68+
varswap=function(matrix,i1,j1,i2,j2){
69+
varaux=matrix[i1][j1];
70+
matrix[i1][j1]=matrix[i2][j2];
71+
matrix[i2][j2]=aux;
72+
};
73+

‎78 Subsets.js

Lines changed: 21 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -32,7 +32,7 @@ var generate = function(nums, index, cur, result) {
3232
result.push(cur.slice());
3333
return
3434
}
35-
35+
3636
generate(nums,index+1,cur,result);
3737
cur.push(nums[index]);
3838
generate(nums,index+1,cur,result);
@@ -42,11 +42,9 @@ var generate = function(nums, index, cur, result) {
4242

4343

4444
// second try
45-
46-
4745
varsubsets=function(nums){
4846
varres=[[]];
49-
47+
5048
functiongenerate(nums,i,cur,res){
5149
for(;i<nums.length;i++){
5250
cur.push(nums[i]);
@@ -55,7 +53,24 @@ var subsets = function(nums) {
5553
cur.pop();
5654
}
5755
}
58-
56+
5957
generate(nums,0,[],res);
6058
returnres;
61-
};
59+
};
60+
61+
// Third solution
62+
varsubsets=function(nums){
63+
varresults=[];
64+
combine(nums,0,[],results);
65+
returnresults;
66+
}
67+
68+
varcombine=function(nums,index,partial,results){
69+
if(index===nums.length){
70+
results.push(partial);
71+
return;
72+
}
73+
74+
combine(nums,index+1,partial,results);
75+
combine(nums,index+1,partial.concat([nums[index]]),results);
76+
}

0 commit comments

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