Skip to content

Commit 6ac9019

Browse files
Chris WuChris Wu
Chris Wu
authored and
Chris Wu
committed
no message
1 parent 69e8953 commit 6ac9019

2 files changed

Lines changed: 87 additions & 40 deletions

File tree

‎problems/3sum.py‎

Lines changed: 37 additions & 40 deletions
Original file line numberDiff line numberDiff line change
@@ -1,43 +1,40 @@
1-
class Solution(object):
2-
#this is the answer from caikehe and all the comments below
3-
4-
"""
5-
This is the answer from caikehe and all the comments below
1+
"""
2+
This is the answer from @caikehe and all the comments below
63
7-
The main idea is to iterate every number in nums.
8-
We use the number as a target to find two other numbers which make total zero.
9-
For those two other numbers, we move pointers, l and r, to try them.
4+
The main idea is to iterate every number in nums.
5+
We use the number as a target to find two other numbers which make total zero.
6+
For those two other numbers, we move pointers, `l` and `r`, to try them.
107
11-
l start from left to right
12-
r start from right to left
8+
`l` start from left to right.
9+
`r` start from right to left.
1310
14-
First, we sort the array, so we can easily move i around and know how to adjust l and r.
15-
If the number is the same as the number before, we have used it as target already, continue. [1]
16-
We always start the left pointer from i+1 because the combination of 0~i has already been tried. [2]
11+
First, we sort the array, so we can easily move i around and know how to adjust l and r.
12+
If the number is the same as the number before, we have used it as target already, continue. [1]
13+
We always start the left pointer from `i+1` because the combination of 0~`i` has already been tried. [2]
1714
18-
Now we calculate the total:
19-
If the total is less than zero, we need it to be larger, so we move the left pointer. [3]
20-
If the total is greater than zero, we need it to be smaller, so we move the right pointer. [4]
21-
If the total is zero, bingo! [5]
22-
We need to move the left and right pointers to the next different numbers, so we do not get repeating result. [6]
15+
Now we calculate the total:
16+
If the total is less than zero, we need it to be larger, so we move the left pointer. [3]
17+
If the total is greater than zero, we need it to be smaller, so we move the right pointer. [4]
18+
If the total is zero, bingo! [5]
19+
We need to move the left and right pointers to the next different numbers, so we do not get repeating result. [6]
2320
24-
We do not need to consider i after nums[i]>0, since sum of 3 positive will be always greater than zero. [7]
25-
We do not need to try the last two, since there are no rooms for l and r pointers.
26-
You can think of it as The last two have been tried by all others. [8]
21+
We do not need to consider `i` after `nums[i]>0`, since sum of 3 positive will be always greater than zero. [7]
22+
We do not need to try the last two, since there are no rooms for `l` and `r` pointers.
23+
You can think of it as The last two have been tried by all others. [8]
2724
28-
For time complexity
29-
Sorting takes O(NlogN)
30-
Now, we need to think as if the 'nums' is really really big
31-
We iterate through the 'nums' once, and each time we iterate the whole array again by a while loop
32-
So it is O(NlogN+N^2)~=O(N^2)
33-
34-
For space complexity
35-
We didn't use extra space except the 'res'
36-
Since we may store the whole 'nums' in it
37-
So it is O(N)
38-
N is the length of 'nums'
39-
"""
25+
For time complexity
26+
Sorting takes `O(NlogN)`
27+
Now, we need to think as if the `nums` is really really big
28+
We iterate through the `nums` once, and each time we iterate the whole array again by a while loop
29+
So it is `O(NlogN+N^2)~=O(N^2)`
4030
31+
For space complexity
32+
We didn't use extra space except the `res`
33+
Since we may store the whole 'nums' in it
34+
So it is `O(N)`
35+
`N` is the length of `nums`
36+
"""
37+
class Solution(object):
4138
def threeSum(self, nums):
4239
res = []
4340
nums.sort()
@@ -63,7 +60,7 @@ def threeSum(self, nums):
6360
l+=1
6461
r-=1
6562
return res
66-
63+
6764
"""
6865
def threeSum(self, nums):
6966
def twoSum(target, nums):
@@ -77,31 +74,31 @@ def twoSum(target, nums):
7774
seen[n2]+=1
7875
res.append([target*-1, n1, n2])
7976
return res
80-
77+
8178
res = []
8279
zero = 0
8380
positive = collections.Counter()
8481
negative = collections.Counter()
85-
82+
8683
for n in nums:
8784
if n>0:
8885
positive[n]+=1
8986
elif n==0:
9087
zero+=1
9188
else:
9289
negative[n]+=1
93-
90+
9491
if zero>=3:
9592
res.append([0, 0, 0])
9693
if zero>=1:
9794
for p in positive:
9895
if p*-1 in negative:
9996
res.append([0, p, p*-1])
100-
97+
10198
for p in positive:
10299
res+=twoSum(p*-1, negative)
103100
for n in negative:
104101
res+=twoSum(n*-1, positive)
105-
102+
106103
return res
107-
"""
104+
"""

‎problems/shortest-bridge.py‎

Lines changed: 50 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,50 @@
1+
import collections
2+
class Solution(object):
3+
def shortestBridge(self, A):
4+
def findFirst():
5+
for i in xrange(M):
6+
for j in xrange(N):
7+
if A[i][j]==1: return (i, j)
8+
9+
M, N = len(A), len(A[0])
10+
opt = float('inf')
11+
12+
q1 = collections.deque([findFirst()])
13+
while q1:
14+
i, j = q1.popleft()
15+
if i<0 or i>=M: continue
16+
if j<0 or j>=N: continue
17+
if A[i][j]==2 or A[i][j]==0: continue
18+
if A[i][j]==1: A[i][j] = 2
19+
q1.extend([(i+1, j), (i-1, j), (i, j+1), (i, j-1)])
20+
21+
i0, j0 = findFirst()
22+
q2 = collections.deque([(i0, j0, 0)])
23+
while q2:
24+
i, j, dis = q2.popleft()
25+
if A[i][j]==3 or A[i][j]==4:
26+
continue
27+
if A[i][j]==2:
28+
opt = min(opt, dis)
29+
continue
30+
31+
if A[i][j]==1: A[i][j] = 3
32+
if A[i][j]==0: A[i][j] = 4
33+
for ni, nj in [(i+1, j), (i-1, j), (i, j+1), (i, j-1)]:
34+
if ni<0 or ni>=M: continue
35+
if nj<0 or nj>=N: continue
36+
if A[ni][nj]==1:
37+
q2.append((ni, nj, 0))
38+
elif A[ni][nj]==0:
39+
q2.append((ni, nj, dis+1))
40+
elif A[ni][nj]==2:
41+
q2.append((ni, nj, dis))
42+
43+
return opt
44+
45+
A = [[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,0,1,1,0,1,1,0,0,0,0],[0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,0,1,1,0],[0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,0,0,0],[0,0,0,0,0,0,0,0,0,1,0,1,1,0,0,1,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,0,1,0,1,1,0,1,0,0,0],[0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,0,1,0,0,0],[0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,1,1,1,1,0],[0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,0],[0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,0],[0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,0],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,0]]
46+
print Solution().shortestBridge(A)
47+
48+
49+
50+

0 commit comments

Comments
 (0)