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

Commit48e15de

Browse files
committed
revist backtracking add 61, 78, 216
1 parent1c1e217 commit48e15de

File tree

10 files changed

+120
-83
lines changed

10 files changed

+120
-83
lines changed

‎Medium/216-combinationSumIII.js‎

Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
/**
2+
* Key: backtracking, similar to subsets
3+
* Only save combinations with length k
4+
*
5+
*@param {number} k
6+
*@param {number} n
7+
*@return {number[][]}
8+
*/
9+
varcombinationSum3=function(k,n){
10+
varnums=[];
11+
for(vari=1;i<=9;i++)nums[i]=i;
12+
varresult=[];
13+
varresults=[];
14+
helper(0,k,n,nums,result,results);
15+
returnresults;
16+
};
17+
18+
varhelper=function(start,k,n,nums,result,results){
19+
if(n===0&&k===0){
20+
results.push(result.slice());
21+
returnresults;
22+
}
23+
24+
for(vari=start;i<nums.length;i++){
25+
if(n<0)break;
26+
result.push(nums[i]);
27+
helper(i+1,k-1,n-nums[i],nums,result,results);
28+
result.pop(nums[i])
29+
}
30+
};

‎Medium/39-combinationSum.js‎

Lines changed: 4 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -17,22 +17,14 @@ var combinationSum = function(candidates, target) {
1717

1818
varcombinationSumHelper=function(candidates,target,results,result,start){
1919
if(target===0){
20-
results.push(deepCopyArray(result));
21-
return;
20+
results.push(result.slice());
21+
returnresults;
2222
}
2323

2424
for(vari=start;i<candidates.length;i++){
25-
if(target<0)break;
25+
if(candidates[i]>target)break;
2626
result.push(candidates[i]);
2727
combinationSumHelper(candidates,target-candidates[i],results,result,i);
28-
result.pop();
28+
result.pop(candidates[i]);
2929
}
3030
};
31-
32-
vardeepCopyArray=function(nums){
33-
varnewNums=[];
34-
for(vari=0;i<nums.length;i++){
35-
newNums[i]=nums[i];
36-
}
37-
returnnewNums;
38-
};

‎Medium/40-combinationSumII.js‎

Lines changed: 1 addition & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -15,7 +15,7 @@ var combinationSum2 = function(candidates, target) {
1515

1616
varcombinationSum2Helper=function(candidates,result,results,target,start){
1717
if(target===0){
18-
results.push(deepCopy(result));
18+
results.push(deepCopy(result.slice()));
1919
return;
2020
}
2121

@@ -30,9 +30,3 @@ var combinationSum2Helper = function(candidates, result, results, target, start)
3030
}
3131
}
3232
};
33-
34-
vardeepCopy=function(nums){
35-
varnewNums=[];
36-
for(vari=0;i<nums.length;i++)newNums.push(nums[i]);
37-
returnnewNums;
38-
};

‎Medium/46-permutations.js‎

Lines changed: 3 additions & 19 deletions
Original file line numberDiff line numberDiff line change
@@ -19,8 +19,8 @@ var permute = function(nums) {
1919
};
2020

2121
varpermuteHelper=function(start,nums,results){
22-
if(start>=nums.length){
23-
results.push(deepCopyArray(nums));
22+
if(start===nums.length){
23+
results.push(nums.slice());
2424
return;
2525
}
2626

@@ -38,14 +38,6 @@ var swap = function(nums, i, j) {
3838
nums[j]=tmp;
3939
};
4040

41-
vardeepCopyArray=function(nums){
42-
varnewNums=[];
43-
for(vari=0;i<nums.length;i++){
44-
newNums[i]=nums[i];
45-
}
46-
returnnewNums;
47-
};
48-
4941
// A iterative version
5042
// for example: nums=[1,2,3]
5143
// step1: [1]
@@ -61,7 +53,7 @@ var permute = function(nums) {
6153
for(varj=0;j<=i;j++){
6254
// still need a deep copy of results[m],
6355
// otherwise, a change to list will affect results array.
64-
varlist=deepCopyArray(results[m]);
56+
varlist=results[m].slice();
6557
list.splice(j,0,nums[i]);
6658
newResults.push(list);
6759
}
@@ -71,11 +63,3 @@ var permute = function(nums) {
7163

7264
returnresults;
7365
};
74-
75-
vardeepCopyArray=function(nums){
76-
varnewNums=[];
77-
for(vari=0;i<nums.length;i++){
78-
newNums[i]=nums[i];
79-
}
80-
returnnewNums;
81-
};

‎Medium/47-permutationsII.js‎

Lines changed: 2 additions & 18 deletions
Original file line numberDiff line numberDiff line change
@@ -15,7 +15,7 @@ var permuteUnique = function(nums) {
1515

1616
varpermutation=function(results,nums,start){
1717
if(start>=nums.length){
18-
results.push(deepCopyArray(nums));
18+
results.push(nums.slice());
1919
return;
2020
}
2121

@@ -35,14 +35,6 @@ var swap = function(nums, i, j) {
3535
};
3636

3737

38-
vardeepCopyArray=function(nums){
39-
varnewNums=[];
40-
for(vari=0;i<nums.length;i++){
41-
newNums[i]=nums[i];
42-
}
43-
returnnewNums;
44-
};
45-
4638
// A iterative version, accepted, 140ms, beats 100%
4739
// same idea as permutation,
4840
// but, sort first, then if there is number is same as the previous one, skip
@@ -60,7 +52,7 @@ var permuteUnique = function(nums) {
6052
varnewResults=[];
6153
for(varm=0;m<results.length;m++){
6254
for(varj=0;j<=i;j++){
63-
varlist=deepCopyArray(results[m]);
55+
varlist=results[m].slice();
6456
list.splice(j,0,nums[i]);
6557
newResults.push(list);
6658
if(results[m][j]===nums[i])break;
@@ -71,11 +63,3 @@ var permuteUnique = function(nums) {
7163

7264
returnresults;
7365
};
74-
75-
vardeepCopyArray=function(nums){
76-
varnewNums=[];
77-
for(vari=0;i<nums.length;i++){
78-
newNums[i]=nums[i];
79-
}
80-
returnnewNums;
81-
};

‎Medium/61-rotateList.js‎

Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
// Q: Given a list, rotate the list to the right by k places, where k is non-negative.
2+
// k places means k steps ?? So, if k is bigger than the length, rotate at length - k % length
3+
4+
/**
5+
*@param {ListNode} head
6+
*@param {number} k
7+
*@return {ListNode}
8+
*/
9+
varrotateRight=function(head,k){
10+
if(!head||!head.next)returnhead;
11+
varheadCopy=head;
12+
varfirst=head;
13+
varsecond=head;
14+
vari=1;
15+
while(first.next){
16+
first=first.next;
17+
i++;
18+
}
19+
varj=i-k%i;
20+
// if the steps eqauls to i (the length) return original list.
21+
if(j===i)returnhead;
22+
23+
while(j>1){
24+
second=second.next;
25+
j--;
26+
}
27+
head=second.next;
28+
second.next=first.next;
29+
first.next=headCopy;
30+
31+
returnhead;
32+
};

‎Medium/77-combinations.js‎

Lines changed: 17 additions & 26 deletions
Original file line numberDiff line numberDiff line change
@@ -5,31 +5,22 @@
55
*@param {number} k
66
*@return {number[][]}
77
*/
8-
varcombine=function(n,k){
9-
varresult=[];
10-
varresults=[];
11-
combineHelper(n,k,1,result,results);
12-
returnresults;
13-
};
8+
varcombine=function(n,k){
9+
varresult=[];
10+
varresults=[];
11+
combineHelper(n,k,1,result,results);
12+
returnresults;
13+
};
1414

15-
varcombineHelper=function(n,k,start,result,results){
16-
if(k===0){
17-
results.push(deepCopyArray(result));
18-
return;
19-
}
15+
varcombineHelper=function(n,k,start,result,results){
16+
if(k===0){
17+
results.push(result.slice());
18+
returnresults;
19+
}
2020

21-
for(vari=start;i<=n;i++){
22-
result.push(i);
23-
// increase i here
24-
combineHelper(n,k-1,i+1,result,results);
25-
result.pop();
26-
}
27-
};
28-
29-
vardeepCopyArray=function(nums){
30-
varnewNums=[];
31-
for(vari=0;i<nums.length;i++){
32-
newNums[i]=nums[i];
33-
}
34-
returnnewNums;
35-
};
21+
for(vari=start;i<=n;i++){
22+
result.push(i);
23+
combineHelper(n,k-1,i+1,result,results);
24+
result.pop(i);
25+
}
26+
};

‎Medium/78-subsets.js‎

Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,27 @@
1+
/**
2+
*@param {number[]} nums
3+
*@return {number[][]}
4+
*/
5+
varsubsets=function(nums){
6+
nums.sort(function(a,b){
7+
returna-b;
8+
});
9+
varresult=[];
10+
varresults=[result];
11+
subsetsHelper(0,nums,result,results);
12+
returnresults;
13+
};
14+
15+
varsubsetsHelper=function(start,nums,result,results){
16+
if(start===nums.length){
17+
return;
18+
}
19+
20+
for(vari=start;i<nums.length;i++){
21+
result.push(nums[i]);
22+
results.push(result.slice());
23+
// start from next element i, not the next element of 'start'
24+
subsetsHelper(i+1,nums,result,results);
25+
result.pop(nums[i]);
26+
}
27+
};

‎Medium/89-grayCode.js‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -3,7 +3,7 @@
33
* n = 0, return [0]
44
* n = 1, return [0, 1]
55
* n = 2, return [00, 01, 11, 10]
6-
* we can see that first n elements (first half) is from n - 1 results,
6+
* we can see that first n elements (first half) is fromthe results (n - 1),
77
* in the second half of results array, first thing is to flip the highest bit to 1
88
* the rest numbers of part two is symmetric of first half part after first bit.
99
*

‎README.md‎

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -93,12 +93,14 @@
9393
*[54. Spiral Matrix](https://leetcode.com/problems/spiral-matrix/) -[Solution](./Medium/54-spiralMatrix.js)
9494
*[55. Jump Game](https://leetcode.com/problems/jump-game/) -[Solution](./Medium/55-jumpGame.js)
9595
*[59. Spiral Matrix II](https://leetcode.com/problems/spiral-matrix-ii/) -[Solution](./Medium/59-spiralMatrixII.js)
96+
*[61. Rotate List](https://leetcode.com/problems/rotate-list/) -[Solution](./Medium/61-rotateList.js)
9697
*[62.Unique Paths](https://leetcode.com/problems/unique-paths/) -[Solution](./Medium/62-uniquePaths.js)
9798
*[64.Minimum Path Sum](https://leetcode.com/problems/minimum-path-sum/) -[Solution](./Medium/64-minimumPathSum.js)
9899
*[73. Set Matrix Zeroes](https://leetcode.com/problems/set-matrix-zeroes/) -[Solution](./Medium/73-setMatrixZeroes.js)
99100
*[74. Search a 2D Matrix](https://leetcode.com/problems/search-a-2d-matrix/) -[Solution](./Medium/74-search2DMatrix.js)
100101
*[75. Sort Colors](https://leetcode.com/problems/sort-colors/) -[Solution](./Medium/75-sortColors.js)
101102
*[77.Combinations](https://leetcode.com/problems/combinations/) -[Solution](./Medium/77-combinations.js)
103+
*[78. Subsets](https://leetcode.com/problems/subsets/) -[Solution](./Medium/78-subsets.js)
102104
*[80. Remove Duplicates from Sorted Array II](https://leetcode.com/problems/remove-duplicates-from-sorted-array-ii/) -[Solution](./Medium/80-removeDuplicatesII.js)
103105
*[89. Gray Code](https://leetcode.com/problems/gray-code/) -[Solution](./Medium/89-grayCode.js)
104106
*[92. Reverse Linked List II](https://leetcode.com/problems/reverse-linked-list-ii/) -[Solution](./Medium/92-reverseLinkedListII.js)
@@ -118,6 +120,7 @@
118120
*[199. Binary Tree Right Side View](https://leetcode.com/problems/binary-tree-right-side-view/) -[Solution](./Medium/199-binaryTreeRightSideView.js)
119121
*[213. House Robber II](https://leetcode.com/problems/house-robber-ii/) -[Solution](./Medium/213-houseRobberII.js)
120122
*[215. Kth Largest Element in an Array](https://leetcode.com/problems/kth-largest-element-in-an-array/) -[Solution](./Medium/215-KthLargestElementInArray.js)
123+
*[216. Combination Sum III](https://leetcode.com/problems/combination-sum-iii/) -[Solution](./Medium/216-CombinationSumIII.js)
121124
*[229. Majority Element II](https://leetcode.com/problems/majority-element-ii/) -[Solution](./Medium/229-majorityElementII.js)
122125
*[230. Kth Smallest Element in a BST](https://leetcode.com/problems/kth-smallest-element-in-a-bst/) -[Solution](./Medium/230-kthSmallestElementinBST.js)
123126
*[238. Product of Array Except Self](https://leetcode.com/problems/product-of-array-except-self/) -[Solution](./Medium/238-productExceptSelf.js)

0 commit comments

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