Skip to content

Commit 9c99683

Browse files
author
Chris Wu
committed
no message
1 parent 7cba347 commit 9c99683

File tree

7 files changed

+318
-2
lines changed

7 files changed

+318
-2
lines changed

‎problems/3sum-closest.py‎

Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
class Solution(object):
2+
def threeSumClosest(self, nums, target):
3+
ans = float('inf')
4+
N = len(nums)
5+
6+
nums.sort()
7+
8+
for i in xrange(N):
9+
l = i+1
10+
r = N-1
11+
12+
while l<r:
13+
s = nums[i]+nums[l]+nums[r]
14+
15+
if abs(target-s)<abs(target-ans): ans = s
16+
17+
if s>target:
18+
r -= 1
19+
elif s<target:
20+
l += 1
21+
else:
22+
return s
23+
24+
return ans

‎problems/3sum.py‎

Lines changed: 101 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -102,3 +102,104 @@ def twoSum(target, nums):
102102
103103
return res
104104
"""
105+
106+
107+
108+
#2021/7/5
109+
"""
110+
Hash Table
111+
Time: O(N^2)
112+
Space: O(N)
113+
114+
memo := {num:[index1, index2,...]}
115+
Iterate through every i and j, see if the required number exist in memo.
116+
"""
117+
import collections
118+
class Solution(object):
119+
def threeSum(self, nums):
120+
memo = collections.defaultdict(list)
121+
N = len(nums)
122+
ans = set()
123+
124+
for k in xrange(N):
125+
memo[nums[k]].append(k)
126+
127+
for i in xrange(N):
128+
for j in xrange(i+1, N):
129+
t = (nums[i]+nums[j])*-1
130+
131+
for k in memo[t]:
132+
if k!=i and k!=j:
133+
ans.add(tuple(sorted([nums[i], nums[j], nums[k]])))
134+
break
135+
return ans
136+
137+
"""
138+
Two Pointers
139+
Time: O(N^2)
140+
Space: O(1)
141+
142+
Sort the nums.
143+
Iterate through i.
144+
j = i+1 and k = N-1, see if the sum s equals to 0.
145+
if s>0, means that we need to reduce the s and it can only be done by decreasing k.
146+
if s<0, means that we need to increase the s and it can only be done by increasing j.
147+
"""
148+
class Solution(object):
149+
def threeSum(self, nums):
150+
nums.sort()
151+
ans = set()
152+
N = len(nums)
153+
154+
for i in xrange(N):
155+
j = i+1
156+
k = N-1
157+
158+
while j<k:
159+
s = nums[i]+nums[j]+nums[k]
160+
if s>0:
161+
k -= 1
162+
elif s<0:
163+
j += 1
164+
else:
165+
ans.add(tuple(sorted([nums[i], nums[j], nums[k]])))
166+
k -= 1
167+
j += 1
168+
169+
return ans
170+
171+
"""
172+
Two Pointers
173+
Time: O(N^2)
174+
Space: O(1)
175+
176+
Same as above. Move pointers to avoid repeation. Faster.
177+
"""
178+
class Solution(object):
179+
def threeSum(self, nums):
180+
nums.sort()
181+
ans = []
182+
N = len(nums)
183+
184+
for i in xrange(N):
185+
j = i+1
186+
k = N-1
187+
188+
if i>0 and nums[i]==nums[i-1]: continue #[1]
189+
190+
while j<k:
191+
s = nums[i]+nums[j]+nums[k]
192+
193+
if s>0:
194+
k -= 1
195+
elif s<0:
196+
j += 1
197+
else:
198+
ans.append([nums[i], nums[j], nums[k]])
199+
200+
while j<k and nums[k]==nums[k-1]: k -= 1 #[2]
201+
while j<k and nums[j]==nums[j+1]: j += 1 #[3]
202+
k -= 1
203+
j += 1
204+
205+
return ans

‎problems/4sum.py‎

Lines changed: 64 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,64 @@
1+
"""
2+
Time: O(N^3)
3+
Space: O(1)
4+
5+
Using tuple to remove redundant, each `ans.add(tuple(sorted([nums[a], nums[b], nums[c], nums[d]])))` is using constant time and space.
6+
So no increase to the time and space complexity.
7+
"""
8+
class Solution(object):
9+
def fourSum(self, nums, target):
10+
nums.sort()
11+
N = len(nums)
12+
ans = set()
13+
14+
for a in xrange(N):
15+
for b in xrange(a+1, N):
16+
c = b+1
17+
d = N-1
18+
19+
while c<d:
20+
s = nums[a]+nums[b]+nums[c]+nums[d]
21+
22+
if s>target:
23+
d -= 1
24+
elif s<target:
25+
c += 1
26+
else:
27+
ans.add(tuple(sorted([nums[a], nums[b], nums[c], nums[d]])))
28+
d -= 1
29+
c += 1
30+
return ans
31+
32+
"""
33+
Remove tuple by skipping the same value for each a, b, c and d.
34+
I find that doing this does not improve overall run time.
35+
"""
36+
class Solution(object):
37+
def fourSum(self, nums, target):
38+
nums.sort()
39+
N = len(nums)
40+
ans = []
41+
42+
for a in xrange(N):
43+
if a>0 and nums[a]==nums[a-1]: continue
44+
for b in xrange(a+1, N):
45+
if b>0 and nums[b]==nums[b-1] and a!=b-1: continue
46+
c = b+1
47+
d = N-1
48+
49+
while c<d:
50+
s = nums[a]+nums[b]+nums[c]+nums[d]
51+
52+
if s>target:
53+
d -= 1
54+
elif s<target:
55+
c += 1
56+
else:
57+
ans.append([nums[a], nums[b], nums[c], nums[d]])
58+
59+
while c<d and nums[c]==nums[c+1]: c+=1
60+
while c<d and nums[d]==nums[d-1]: d-=1
61+
62+
d -= 1
63+
c += 1
64+
return ans

‎problems/intersection-of-two-arrays-ii.py‎

Lines changed: 43 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,43 @@
1+
"""
2+
Time: O(NLogN)
3+
Space: O(1)
4+
"""
5+
class Solution(object):
6+
def intersect(self, nums1, nums2):
7+
nums1.sort()
8+
nums2.sort()
9+
10+
i = j = 0
11+
ans = []
12+
13+
while i<len(nums1) and j<len(nums2):
14+
if nums1[i]==nums2[j]:
15+
ans.append(nums1[i])
16+
i += 1
17+
j +=1
18+
elif nums1[i]>nums2[j]:
19+
j += 1
20+
else:
21+
i += 1
22+
return ans
23+
24+
"""
25+
Time: O(N)
26+
Space: O(N)
27+
"""
28+
class Solution(object):
29+
def intersect(self, nums1, nums2):
30+
c = {} #nums1 counter
31+
ans = []
32+
33+
for n in nums1:
34+
if n in c:
35+
c[n] += 1
36+
else:
37+
c[n] = 1
38+
39+
for n in nums2:
40+
if n in c and c[n]>0:
41+
ans.append(n)
42+
c[n] -= 1
43+
return ans

‎problems/intersection-of-two-arrays.py‎

Lines changed: 9 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -19,4 +19,12 @@ def intersection(self, nums1, nums2):
1919
#element in set is not repeated
2020
#set has some convenient build-in operator
2121
def intersection(self, nums1, nums2):
22-
return list(set(nums1) & set(nums2))
22+
return list(set(nums1) & set(nums2))
23+
24+
25+
class Solution(object):
26+
def intersection(self, nums1, nums2):
27+
nums1 = set(nums1)
28+
nums2 = set(nums2)
29+
30+
return nums1.intersection(nums2)

‎problems/two-sum.py‎

Lines changed: 13 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -30,4 +30,16 @@ def twoSum(self, nums, target):
3030
if num in M: return (M[num], i)
3131
M[target-num] = i
3232

33-
return False
33+
return False
34+
35+
#2021/7/4
36+
class Solution(object):
37+
def twoSum(self, nums, target):
38+
memo = {} #{key : value} := {"counter part needed for n" : "index of n"}
39+
40+
for i, n in enumerate(nums):
41+
if n in memo:
42+
return [memo[n], i]
43+
else:
44+
memo[target-n] = i
45+
return []

‎problems/wiggle-subsequence.py‎

Lines changed: 64 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,64 @@
1+
"""
2+
dp[0][0 or 1] is considering no num in nums.
3+
dp[1][0 or 1] is considering the first num in nums.
4+
dp[2][0 or 1] is considering the second num in nums.
5+
dp[3][0 or 1] is considering the third num in nums.
6+
...
7+
8+
dp[i][0] := longest length of wiggle seq that ends at nums[i-1] and diff ends in positive number.
9+
dp[i][1] := longest length of wiggle seq that ends at nums[i-1] and diff ends in negative number.
10+
11+
Time: O(N)
12+
Space: O(N)
13+
"""
14+
class Solution(object):
15+
def wiggleMaxLength(self, nums):
16+
ans = 1
17+
N = len(nums)
18+
19+
dp = [[0, 0] for _ in xrange(N+1)]
20+
dp[1][0] = 1
21+
dp[1][1] = 1
22+
23+
for i in xrange(2, N+1):
24+
if nums[i-1]-nums[i-2]>0:
25+
dp[i][0] = dp[i-1][1]+1
26+
dp[i][1] = dp[i-1][1]
27+
elif nums[i-1]-nums[i-2]<0:
28+
dp[i][1] = dp[i-1][0]+1
29+
dp[i][0] = dp[i-1][0]
30+
else:
31+
dp[i][1] = dp[i-1][1]
32+
dp[i][0] = dp[i-1][0]
33+
34+
ans = max(ans, dp[i][0], dp[i][1])
35+
36+
return ans
37+
38+
"""
39+
From the above solution, we notice that we do not need whole array to keep track.
40+
Just need two variables.
41+
Use `up` and `down` to replace dp[i-1][0] and dp[i-1][1]
42+
43+
Time: O(N)
44+
Space: O(1)
45+
"""
46+
class Solution(object):
47+
def wiggleMaxLength(self, nums):
48+
N = len(nums)
49+
50+
ans = 1
51+
up = 1
52+
down = 1
53+
54+
for i in xrange(2, N+1):
55+
if nums[i-1]-nums[i-2]>0:
56+
up, down = down+1, down
57+
elif nums[i-1]-nums[i-2]<0:
58+
down = up+1
59+
60+
ans = max(ans, up, down)
61+
62+
return ans
63+
64+

0 commit comments

Comments
 (0)