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

Commit0336a1c

Browse files
committed
revisted remove duplicates and permutations
1 parent8d1aa99 commit0336a1c

File tree

7 files changed

+121
-1
lines changed

7 files changed

+121
-1
lines changed
Lines changed: 14 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,14 @@
1+
/**
2+
*@param {number[]} nums
3+
*@return {number}
4+
*/
5+
varremoveDuplicates=function(nums){
6+
varstart=0;
7+
for(vari=0;i<nums.length;i++){
8+
if(nums[start]!==nums[i]){
9+
start++;
10+
nums[start]=nums[i];
11+
}
12+
}
13+
returnstart+1;
14+
};

‎Easy/27-removeElement.js‎

Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,19 @@
1+
/**
2+
* Key: same solution as 26?
3+
* Two pointers
4+
*
5+
*@param {number[]} nums
6+
*@param {number} val
7+
*@return {number}
8+
*/
9+
varremoveElement=function(nums,val){
10+
varstart=0;
11+
for(vari=0;i<nums.length;i++){
12+
if(nums[i]!==val){
13+
nums[start]=nums[i];
14+
start++;
15+
}
16+
}
17+
18+
returnstart;
19+
};

‎Medium/46-permutations.js‎

Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -45,3 +45,37 @@ var deepCopyArray = function(nums) {
4545
}
4646
returnnewNums;
4747
};
48+
49+
// A iterative version
50+
// for example: nums=[1,2,3]
51+
// step1: [1]
52+
// step2: inserst 2 to [1], two possibilities: [2,1], [1,2]
53+
// step2: inserst 3 to [1,2] and [2,1],
54+
// Three possibilities for each: [3,2,1], [2,3,1], [2,1,3] & [3,1,2], [1,3,2], [1,2,3]
55+
varpermute=function(nums){
56+
if(nums.length===0)returnnums;
57+
varresults=[[nums[0]]];
58+
for(vari=1;i<nums.length;i++){
59+
varnewResults=[];
60+
for(varm=0;m<results.length;m++){
61+
for(varj=0;j<=i;j++){
62+
// still need a deep copy of results[m],
63+
// otherwise, a change to list will affect results array.
64+
varlist=deepCopyArray(results[m]);
65+
list.splice(j,0,nums[i]);
66+
newResults.push(list);
67+
}
68+
}
69+
results=newResults;
70+
}
71+
72+
returnresults;
73+
};
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: 37 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -35,6 +35,43 @@ 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+
46+
// A iterative version, accepted, 140ms, beats 100%
47+
// same idea as permutation,
48+
// but, sort first, then if there is number is same as the previous one, skip
49+
// for example: nums=[1,2,2]
50+
// step1: [1]
51+
// step2: inserst 2 to [1], two possibilities: [2,1], [1,2]
52+
// step3: inserst 2 to [1,2] and [2,1]? but there is a 2 in each array, so skip this number and return
53+
varpermuteUnique=function(nums){
54+
if(nums.length===0)returnnums;
55+
nums.sort(function(a,b){
56+
returna-b;
57+
});
58+
varresults=[[nums[0]]];
59+
for(vari=1;i<nums.length;i++){
60+
varnewResults=[];
61+
for(varm=0;m<results.length;m++){
62+
for(varj=0;j<=i;j++){
63+
varlist=deepCopyArray(results[m]);
64+
list.splice(j,0,nums[i]);
65+
newResults.push(list);
66+
if(results[m][j]===nums[i])break;
67+
}
68+
}
69+
results=newResults;
70+
}
71+
72+
returnresults;
73+
};
74+
3875
vardeepCopyArray=function(nums){
3976
varnewNums=[];
4077
for(vari=0;i<nums.length;i++){

‎Medium/50-powerxn.js‎

Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,13 @@
1+
/**
2+
*@param {number} x
3+
*@param {number} n
4+
*@return {number}
5+
*/
6+
varmyPow=function(x,n){
7+
if(n===0)return1;
8+
if(n<0){
9+
n=-1*n;
10+
x=1/x;
11+
}
12+
returnn%2===0 ?myPow(x*x,n/2) :x*myPow(x*x,Math.floor(n/2));
13+
};

‎Medium/80-removeDuplicatesII.js‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,5 @@
11
/**
2-
* Key: Use two pointers. First pointer is for the a generated array
2+
* Key: Use two pointers. First pointer is for the anewly(modified)generated array
33
* as long as it doesn't have more than two more Duplicates, the original point
44
* keeps moving...
55
*

‎README.md‎

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -14,6 +14,8 @@
1414
*[21. Merge Two Sorted Lists](https://leetcode.com/problems/merge-two-sorted-lists/) -[Solution](./Easy/21-mergeSortedLists.js)
1515
*[24. Swap Nodes in Pairs](https://leetcode.com/problems/swap-nodes-in-pairs/) -[Solution](./Easy/24-swapNodesPairs.js)
1616
*[28. Implement strStr()](https://leetcode.com/problems/implement-strstr/) -[Solution](./Easy/28-implementstrStr.js)
17+
*[26. Remove Duplicates from Sorted Array](https://leetcode.com/problems/remove-duplicates-from-sorted-array/) -[Solution](./Easy/26-removeDuplicatesSortedArray.js)
18+
*[27. Remove Element](https://leetcode.com/problems/remove-element/) -[Solution](./Easy/27-removeElement.js)
1719
*[36. Valid Sudoku](https://leetcode.com/problems/valid-sudoku/) -[Solution](./Easy/36-validSudoku.js)
1820
*[38. Count and Say](https://leetcode.com/problems/count-and-say/) -[Solution](./Easy/38-countandSay.js)
1921
*[66. Plus One](https://leetcode.com/problems/plus-one/) -[Solution](./Easy/66-plusOne.js)
@@ -85,6 +87,7 @@
8587
*[46. Permutations](https://leetcode.com/problems/permutations/) -[Solution](./Medium/46-permutations.js)
8688
*[47. Permutations II](https://leetcode.com/problems/permutations-ii/) -[Solution](./Medium/47-permutationsII.js)
8789
*[48. Rotate Image](https://leetcode.com/problems/rotate-image/) -[Solution](./Medium/48-rotateImage.js)
90+
*[50. Pow(x, n)](https://leetcode.com/problems/powx-n/) -[Solution](./Medium/50-powerxn.js)
8891
*[53. Maximum Subarray](https://leetcode.com/problems/maximum-subarray/) -[Solution](./Medium/53-maximumSubarray.js)
8992
*[54. Spiral Matrix](https://leetcode.com/problems/spiral-matrix/) -[Solution](./Medium/54-spiralMatrix.js)
9093
*[59. Spiral Matrix II](https://leetcode.com/problems/spiral-matrix-ii/) -[Solution](./Medium/59-spiralMatrixII.js)

0 commit comments

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