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

Commit99b3960

Browse files
committed
refactor: js | array + hash
1 parent4253d53 commit99b3960

10 files changed

+728
-331
lines changed

‎javascript/1-Two-Sum.js

Lines changed: 72 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -1,15 +1,79 @@
11
/**
2+
* Brute Force - Linear Search
3+
* Time O(N^2) | Space O(1)
4+
* https://leetcode.com/problems/two-sum/
25
*@param {number[]} nums
36
*@param {number} target
47
*@return {number[]}
58
*/
6-
vartwoSum=function(nums,target){
7-
letmap={};
8-
for(leti=0;i<nums.length;i++){
9-
if(target-nums[i]inmap){
10-
return[map[target-nums[i]],i];
11-
}else{
12-
map[nums[i]]=i;
9+
vartwoSum=(nums,target)=>{
10+
for(letcurr=0;curr<nums.length;curr++){/* Time O(N) */
11+
constcomplement=target-nums[curr];
12+
13+
for(letnext=(curr+1);next<nums.length;next++){/* Time O(N) */
14+
constnum=nums[next];
15+
16+
constisTarget=num===complement
17+
if(isTarget)return[curr,next];
1318
}
1419
}
15-
};
20+
21+
return[-1,-1];
22+
}
23+
24+
/**
25+
* Hash Map - 2 Pass
26+
* Time O(N) | Space O(N)
27+
* https://leetcode.com/problems/two-sum/
28+
*@param {number[]} nums
29+
*@param {number} target
30+
*@return {number[]}
31+
*/
32+
vartwoSum=(nums,target)=>{
33+
constmap=getMap(nums);/* Time O(N) | Space O(N) */
34+
35+
returngetSum(nums,target,map)/* Time O(N) */
36+
}
37+
38+
constgetMap=(nums,map=newMap())=>{
39+
for(letindex=0;index<nums.length;index++){/* Time O(N) */
40+
map.set(nums[index],index);/* Space O(N) */
41+
}
42+
43+
returnmap
44+
}
45+
46+
constgetSum=(nums,target,map)=>{
47+
for(letindex=0;index<nums.length;index++){/* Time O(N) */
48+
constcomplement=target-nums[index];
49+
constsumIndex=map.get(complement);
50+
51+
constisTarget=map.has(complement)&&(map.get(complement)!==index)
52+
if(isTarget)return[index,sumIndex]
53+
}
54+
55+
return[-1,-1];
56+
}
57+
58+
/**
59+
* Hash Map - 1 Pass
60+
* Time O(N) | Space O(N)
61+
* https://leetcode.com/problems/two-sum/
62+
*@param {number[]} nums
63+
*@param {number} target
64+
*@return {number[]}
65+
*/
66+
vartwoSum=(nums,target,map=newMap())=>{
67+
for(letindex=0;index<nums.length;index++){/* Time O(N) */
68+
constnum=nums[index];
69+
constcomplement=(target-num);
70+
constsumIndex=map.get(complement);
71+
72+
constisTarget=map.has(complement)
73+
if(isTarget)return[index,sumIndex];
74+
75+
map.set(num,index);/* Space O(N) */
76+
}
77+
78+
return[-1,-1];
79+
}
Lines changed: 70 additions & 70 deletions
Original file line numberDiff line numberDiff line change
@@ -1,94 +1,94 @@
1-
//////////////////////////////////////////////////////////////////////////////
2-
// Linear Search With A Hash Map
3-
// Time: O(n)
4-
// Space: O(n)
5-
// This solution only makes one pass over the `nums` array and is the highest
6-
// performing solution.
7-
//////////////////////////////////////////////////////////////////////////////
8-
91
/**
2+
* Brute Force
3+
* Greedy - Max Score
4+
* Time O (N^3) | Space O(1)
5+
* https://leetcode.com/problems/longest-consecutive-sequence/
106
*@param {number[]} nums
117
*@return {number}
128
*/
13-
functionlongestConsecutive(nums){
14-
if(!nums.length){
15-
return0;
16-
}
9+
varlongestConsecutive=(nums,maxScore=0)=>{
10+
for(constnumofnums){/* Time O(N) */
11+
let[currNum,score]=[num,1];
1712

18-
constmap=Object.create(null);
19-
letmax=0;
20-
21-
for(constnumofnums){
22-
if(numinmap){
23-
continue;
13+
while(isStreak(nums,(currNum+1))){/* Time O(N * N) */
14+
currNum++;
15+
score++;
2416
}
2517

26-
constprev=num-1;
27-
constnext=num+1;
28-
letlen=1;
29-
30-
if(previnmap){
31-
if(nextinmap){
32-
len+=map[prev]+map[next];
33-
map[prev-map[prev]+1]=len;
34-
map[next+map[next]-1]=len;
35-
}else{
36-
len+=map[prev];
37-
++map[prev-map[prev]+1];
38-
}
39-
}elseif(nextinmap){
40-
len+=map[next];
41-
++map[next+map[next]-1];
42-
}
43-
map[num]=len;
44-
max=Math.max(max,len);
18+
maxScore=Math.max(maxScore,score);
4519
}
4620

47-
returnmax;
21+
returnmaxScore;
4822
}
4923

50-
//////////////////////////////////////////////////////////////////////////////
51-
// Linear Search With A Hash Set
52-
// Time: O(n)
53-
// Space: O(n)
54-
// This solution does three passes over the `nums` array. A first pass to
55-
// setup the hash set. A second pass to find the numbers that mark the
56-
// beginning of a sequence. A third pass to calculate the length of each
57-
// sequence. The nested `while` loop does not cause quadratic calculations as
58-
// it is only initiated on the first number of each sequence.
59-
//////////////////////////////////////////////////////////////////////////////
24+
constisStreak=(nums,num)=>{
25+
for(leti=0;i<nums.length;i++){/* Time O(N) */
26+
constisEqual=nums[i]===num
27+
if(isEqual)returntrue;
28+
}
29+
30+
returnfalse;
31+
}
6032

6133
/**
34+
* Sort - HeapSort Space O(1) | QuickSort Space O(log(K))
35+
* Greedy - Max Score
36+
* Time O (N * log(N)) | Space O(1)
37+
* https://leetcode.com/problems/longest-consecutive-sequence/
6238
*@param {number[]} nums
6339
*@return {number}
6440
*/
65-
functionlongestConsecutive(nums){
66-
letlen=nums.length;
67-
if(!len){
68-
return0;
41+
varlongestConsecutive=(nums)=>{
42+
if(!nums.length)return0;
43+
44+
nums.sort((a,b)=>a-b);/* Time O(N * log(N)) | Space O(1 || log(N)) */
45+
46+
returnsearch(nums);/* Time O(N) */
47+
}
48+
49+
constsearch=(nums)=>{
50+
let[maxScore,score]=[1,1];
51+
52+
for(leti=1;i<nums.length;i++){/* Time O(N) */
53+
constisPrevDuplicate=nums[i-1]===nums[i]
54+
if(isPrevDuplicate)continue
55+
56+
constisStreak=nums[i]===((nums[i-1])+1)
57+
if(isStreak){score++;continue;}
58+
59+
maxScore=Math.max(maxScore,score);
60+
score=1;
6961
}
70-
constset=newSet(nums);
71-
letmax=0;
7262

73-
for(leti=0;i<nums.length;i++){
74-
constnum=nums[i];
63+
returnMath.max(maxScore,score);
64+
}
7565

76-
if(set.has(num-1)){
77-
continue;
78-
}
66+
/**
67+
* Hash Set - Sequence
68+
* Greedy - Max Score
69+
* Time O (N) | Space O(N)
70+
* https://leetcode.com/problems/longest-consecutive-sequence/
71+
*@param {number[]} nums
72+
*@return {number}
73+
*/
74+
varlongestConsecutive=(nums,maxScore=0)=>{
75+
constnumSet=newSet(nums);/* Time O(N) | Space O(N) */
7976

80-
letcurrentMax=1;
81-
while(set.has(num+currentMax)){
82-
currentMax++;
83-
}
77+
for(constnumof[ ...numSet]){/* Time O(N) */
78+
constprevNum=num-1;
8479

85-
if(currentMax>max){
86-
max=currentMax;
87-
}
88-
if(max>len/2){
89-
break;
80+
if(numSet.has(prevNum))continue;/* Time O(N) */
81+
82+
let[currNum,score]=[num,1];
83+
84+
constisStreak=()=>numSet.has(currNum+1)
85+
while(isStreak()){/* Time O(N) */
86+
currNum++;
87+
score++;
9088
}
89+
90+
maxScore=Math.max(maxScore,score);
9191
}
9292

93-
returnmax;
94-
}
93+
returnmaxScore;
94+
}

‎javascript/217-Contains-Duplicate.js

Lines changed: 61 additions & 20 deletions
Original file line numberDiff line numberDiff line change
@@ -1,31 +1,72 @@
11
/**
2+
* Brute Force - Linear Search
3+
* Time O(N^2) | Space O(1)
4+
* https://leetcode.com/problems/contains-duplicate/
25
*@param {number[]} nums
36
*@return {boolean}
47
*/
5-
6-
//First method using Set() (exit early if true)
7-
varcontainsDuplicate=function(nums){
8-
constnumsSet=newSet();
9-
for(constiofnums){
10-
if(numsSet.has(i)){
11-
returntrue;
8+
varcontainsDuplicate=(nums)=>{
9+
for(letright=0;right<nums.length;right++){/* Time O(N) */
10+
for(letleft=0;left<right;left++){/* Time O(N) */
11+
constisDuplicate=nums[left]===nums[right];
12+
if(isDuplicate)returntrue;
1213
}
13-
numsSet.add(i);
1414
}
15+
1516
returnfalse;
16-
};
17+
}
18+
19+
/**
20+
* Sort - HeapSort Space O(1) | QuickSort Space O(log(N))
21+
* Time O(N * log(N)) | Space O(1)
22+
* https://leetcode.com/problems/contains-duplicate/
23+
*@param {number[]} nums
24+
*@return {boolean}
25+
*/
26+
varcontainsDuplicate=(nums)=>{
27+
nums.sort((a,b)=>a-b);/* Time O(N * log(N)) | Space O(1 || log(N)) */
1728

18-
//Second method using Map() (Has to map entire array but code is more readable)
19-
varcontainsDuplicate=function(nums){
20-
//create a new hashmap with all the items in the array. Any duplicates will be removed.
21-
consttotalWithoutDuplicates=newMap(nums.map((i)=>[i]));
29+
returnhasDuplicate(nums);
30+
}
2231

23-
//check if the size of the initial array is larger than the new hashmap.
24-
returntotalWithoutDuplicates.size!==nums.length;
25-
};
32+
consthasDuplicate=(nums)=>{
33+
for(letcurr=0;curr<(nums.length-1);curr++){/* Time O(N) */
34+
constnext=(curr+1);
35+
36+
constisNextDuplicate=nums[curr]===nums[next];
37+
if(isNextDuplicate)returntrue;
38+
}
2639

27-
//Third method using Set() (Fastest runtime at 91.95% and very readable code)
28-
varcontainsDuplicate=function(nums){
29-
//Pass the array into a Set() (which removes duplicates) and then compare its size to the original array.
30-
returnnewSet(nums).size!==nums.length;
40+
returnfalse;
41+
}
42+
43+
/**
44+
* Hash Set
45+
* Time O(N) | Space O(N)
46+
* https://leetcode.com/problems/contains-duplicate/
47+
*@param {number[]} nums
48+
*@return {boolean}
49+
*/
50+
varcontainsDuplicate=(nums)=>{
51+
constnumsSet=newSet(nums);/* Time O(N) | Space O(N) */
52+
constisEqual=numsSet.size===nums.length;
53+
54+
return!isEqual;
3155
};
56+
57+
/**
58+
* Hash Set - Early Exit
59+
* Time O(N) | Space O(N)
60+
* https://leetcode.com/problems/contains-duplicate/
61+
*@param {number[]} nums
62+
*@return {boolean}
63+
*/
64+
varcontainsDuplicate=(nums,numsSet=newSet())=>{
65+
for(constnumofnums){/* Time O(N) */
66+
if(numsSet.has(num))returntrue;
67+
68+
numsSet.add(num);/* Space O(N) */
69+
}
70+
71+
returnfalse;
72+
};

0 commit comments

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