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

Commit283291c

Browse files
author
luzhipeng
committed
1 parent7fa9cc8 commit283291c

18 files changed

+1090
-6
lines changed

‎39.combination-sum.js

Lines changed: 70 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,70 @@
1+
/*
2+
*@lc app=leetcode id=39 lang=javascript
3+
*
4+
* [39] Combination Sum
5+
*
6+
* https://leetcode.com/problems/combination-sum/description/
7+
*
8+
* algorithms
9+
* Medium (46.89%)
10+
* Total Accepted: 326.7K
11+
* Total Submissions: 684.2K
12+
* Testcase Example: '[2,3,6,7]\n7'
13+
*
14+
* Given a set of candidate numbers (candidates) (without duplicates) and a
15+
* target number (target), find all unique combinations in candidates where the
16+
* candidate numbers sums to target.
17+
*
18+
* The same repeated number may be chosen from candidates unlimited number of
19+
* times.
20+
*
21+
* Note:
22+
*
23+
*
24+
* All numbers (including target) will be positive integers.
25+
* The solution set must not contain duplicate combinations.
26+
*
27+
*
28+
* Example 1:
29+
*
30+
*
31+
* Input: candidates = [2,3,6,7], target = 7,
32+
* A solution set is:
33+
* [
34+
* ⁠ [7],
35+
* ⁠ [2,2,3]
36+
* ]
37+
*
38+
*
39+
* Example 2:
40+
*
41+
*
42+
* Input: candidates = [2,3,5], target = 8,
43+
* A solution set is:
44+
* [
45+
* [2,2,2,2],
46+
* [2,3,3],
47+
* [3,5]
48+
* ]
49+
*
50+
*/
51+
52+
functionbacktrack(list,tempList,nums,remain,start){
53+
if(remain<0)return;
54+
elseif(remain===0)returnlist.push([...tempList]);
55+
for(leti=start;i<nums.length;i++){
56+
tempList.push(nums[i]);
57+
backtrack(list,tempList,nums,remain-nums[i],i);// 数字可以重复使用， i + 1代表不可以重复利用
58+
tempList.pop();
59+
}
60+
}
61+
/**
62+
*@param {number[]} candidates
63+
*@param {number} target
64+
*@return {number[][]}
65+
*/
66+
varcombinationSum=function(candidates,target){
67+
constlist=[];
68+
backtrack(list,[],candidates.sort((a,b)=>a-b),target,0);
69+
returnlist;
70+
};

‎40.combination-sum-ii.js

Lines changed: 71 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,71 @@
1+
/*
2+
*@lc app=leetcode id=40 lang=javascript
3+
*
4+
* [40] Combination Sum II
5+
*
6+
* https://leetcode.com/problems/combination-sum-ii/description/
7+
*
8+
* algorithms
9+
* Medium (40.31%)
10+
* Total Accepted: 212.8K
11+
* Total Submissions: 519K
12+
* Testcase Example: '[10,1,2,7,6,1,5]\n8'
13+
*
14+
* Given a collection of candidate numbers (candidates) and a target number
15+
* (target), find all unique combinations in candidates where the candidate
16+
* numbers sums to target.
17+
*
18+
* Each number in candidates may only be used once in the combination.
19+
*
20+
* Note:
21+
*
22+
*
23+
* All numbers (including target) will be positive integers.
24+
* The solution set must not contain duplicate combinations.
25+
*
26+
*
27+
* Example 1:
28+
*
29+
*
30+
* Input: candidates = [10,1,2,7,6,1,5], target = 8,
31+
* A solution set is:
32+
* [
33+
* ⁠ [1, 7],
34+
* ⁠ [1, 2, 5],
35+
* ⁠ [2, 6],
36+
* ⁠ [1, 1, 6]
37+
* ]
38+
*
39+
*
40+
* Example 2:
41+
*
42+
*
43+
* Input: candidates = [2,5,2,1,2], target = 5,
44+
* A solution set is:
45+
* [
46+
* [1,2,2],
47+
* [5]
48+
* ]
49+
*
50+
*
51+
*/
52+
functionbacktrack(list,tempList,nums,remain,start){
53+
if(remain<0)return;
54+
elseif(remain===0)returnlist.push([...tempList]);
55+
for(leti=start;i<nums.length;i++){
56+
if(i>start&&nums[i]==nums[i-1])continue;// skip duplicates
57+
tempList.push(nums[i]);
58+
backtrack(list,tempList,nums,remain-nums[i],i+1);// i + 1代表不可以重复利用， i 代表数字可以重复使用
59+
tempList.pop();
60+
}
61+
}
62+
/**
63+
*@param {number[]} candidates
64+
*@param {number} target
65+
*@return {number[][]}
66+
*/
67+
varcombinationSum2=function(candidates,target){
68+
constlist=[];
69+
backtrack(list,[],candidates.sort((a,b)=>a-b),target,0);
70+
returnlist;
71+
};

‎46.permutations.js

Lines changed: 50 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,50 @@
1+
/*
2+
*@lc app=leetcode id=46 lang=javascript
3+
*
4+
* [46] Permutations
5+
*
6+
* https://leetcode.com/problems/permutations/description/
7+
*
8+
* algorithms
9+
* Medium (53.60%)
10+
* Total Accepted: 344.6K
11+
* Total Submissions: 642.9K
12+
* Testcase Example: '[1,2,3]'
13+
*
14+
* Given a collection of distinct integers, return all possible permutations.
15+
*
16+
* Example:
17+
*
18+
*
19+
* Input: [1,2,3]
20+
* Output:
21+
* [
22+
* ⁠ [1,2,3],
23+
* ⁠ [1,3,2],
24+
* ⁠ [2,1,3],
25+
* ⁠ [2,3,1],
26+
* ⁠ [3,1,2],
27+
* ⁠ [3,2,1]
28+
* ]
29+
*
30+
*
31+
*/
32+
functionbacktrack(list,tempList,nums){
33+
if(tempList.length===nums.length)returnlist.push([...tempList]);
34+
for(leti=0;i<nums.length;i++){
35+
if(tempList.includes(nums[i]))continue;
36+
tempList.push(nums[i]);
37+
backtrack(list,tempList,nums);
38+
tempList.pop();
39+
}
40+
}
41+
/**
42+
*@param {number[]} nums
43+
*@return {number[][]}
44+
*/
45+
varpermute=function(nums){
46+
constlist=[];
47+
backtrack(list,[],nums)
48+
returnlist
49+
};
50+

‎47.permutations-ii.js

Lines changed: 52 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,52 @@
1+
/*
2+
*@lc app=leetcode id=47 lang=javascript
3+
*
4+
* [47] Permutations II
5+
*
6+
* https://leetcode.com/problems/permutations-ii/description/
7+
*
8+
* algorithms
9+
* Medium (39.29%)
10+
* Total Accepted: 234.1K
11+
* Total Submissions: 586.2K
12+
* Testcase Example: '[1,1,2]'
13+
*
14+
* Given a collection of numbers that might contain duplicates, return all
15+
* possible unique permutations.
16+
*
17+
* Example:
18+
*
19+
*
20+
* Input: [1,1,2]
21+
* Output:
22+
* [
23+
* ⁠ [1,1,2],
24+
* ⁠ [1,2,1],
25+
* ⁠ [2,1,1]
26+
* ]
27+
*
28+
*
29+
*/
30+
functionbacktrack(list,nums,tempList,visited){
31+
if(tempList.length===nums.length)returnlist.push([...tempList]);
32+
for(leti=0;i<nums.length;i++){
33+
if(visited[i])continue;
34+
// visited[i - 1] 容易忽略
35+
if(i>0&&nums[i]===nums[i-1]&&visited[i-1])continue;
36+
37+
visited[i]=true;
38+
tempList.push(nums[i]);
39+
backtrack(list,nums,tempList,visited);
40+
visited[i]=false;
41+
tempList.pop();
42+
}
43+
}
44+
/**
45+
*@param {number[]} nums
46+
*@return {number[][]}
47+
*/
48+
varpermuteUnique=function(nums){
49+
constlist=[];
50+
backtrack(list,nums.sort((a,b)=>a-b),[],[]);
51+
returnlist;
52+
};

‎62.unique-paths.js

Lines changed: 71 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,71 @@
1+
/*
2+
*@lc app=leetcode id=62 lang=javascript
3+
*
4+
* [62] Unique Paths
5+
*
6+
* https://leetcode.com/problems/unique-paths/description/
7+
*
8+
* algorithms
9+
* Medium (46.53%)
10+
* Total Accepted: 277K
11+
* Total Submissions: 587.7K
12+
* Testcase Example: '3\n2'
13+
*
14+
* A robot is located at the top-left corner of a m x n grid (marked 'Start' in
15+
* the diagram below).
16+
*
17+
* The robot can only move either down or right at any point in time. The robot
18+
* is trying to reach the bottom-right corner of the grid (marked 'Finish' in
19+
* the diagram below).
20+
*
21+
* How many possible unique paths are there?
22+
*
23+
*
24+
* Above is a 7 x 3 grid. How many possible unique paths are there?
25+
*
26+
* Note: m and n will be at most 100.
27+
*
28+
* Example 1:
29+
*
30+
*
31+
* Input: m = 3, n = 2
32+
* Output: 3
33+
* Explanation:
34+
* From the top-left corner, there are a total of 3 ways to reach the
35+
* bottom-right corner:
36+
* 1. Right -> Right -> Down
37+
* 2. Right -> Down -> Right
38+
* 3. Down -> Right -> Right
39+
*
40+
*
41+
* Example 2:
42+
*
43+
*
44+
* Input: m = 7, n = 3
45+
* Output: 28
46+
*
47+
* START
48+
*/
49+
/**
50+
*@param {number} m
51+
*@param {number} n
52+
*@return {number}
53+
*/
54+
varuniquePaths=function(m,n){
55+
// backtracking
56+
constdp=[];
57+
for(leti=0;i<m+1;i++){
58+
dp[i]=[];
59+
dp[i][0]=0;
60+
}
61+
for(leti=0;i<n+1;i++){
62+
dp[0][i]=0;
63+
}
64+
for(leti=1;i<m+1;i++){
65+
for(letj=1;j<n+1;j++){
66+
dp[i][j]=j===1 ?1 :dp[i-1][j]+dp[i][j-1];
67+
}
68+
}
69+
70+
returndp[m][n];
71+
};

‎78.subsets.js

Lines changed: 53 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,53 @@
1+
/*
2+
*@lc app=leetcode id=78 lang=javascript
3+
*
4+
* [78] Subsets
5+
*
6+
* https://leetcode.com/problems/subsets/description/
7+
*
8+
* algorithms
9+
* Medium (51.19%)
10+
* Total Accepted: 351.6K
11+
* Total Submissions: 674.8K
12+
* Testcase Example: '[1,2,3]'
13+
*
14+
* Given a set of distinct integers, nums, return all possible subsets (the
15+
* power set).
16+
*
17+
* Note: The solution set must not contain duplicate subsets.
18+
*
19+
* Example:
20+
*
21+
*
22+
* Input: nums = [1,2,3]
23+
* Output:
24+
* [
25+
* ⁠ [3],
26+
* [1],
27+
* [2],
28+
* [1,2,3],
29+
* [1,3],
30+
* [2,3],
31+
* [1,2],
32+
* []
33+
* ]
34+
*
35+
*/
36+
functionbacktrack(list,tempList,nums,start){
37+
list.push([...tempList]);
38+
for(leti=start;i<nums.length;i++){
39+
tempList.push(nums[i]);
40+
backtrack(list,tempList,nums,i+1);
41+
tempList.pop();
42+
}
43+
}
44+
/**
45+
*@param {number[]} nums
46+
*@return {number[][]}
47+
*/
48+
varsubsets=function(nums){
49+
constlist=[];
50+
backtrack(list,[],nums,0);
51+
returnlist;
52+
};
53+

0 commit comments

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