Skip to content

Commit b443fd3

Browse files
author
chris
committed
no message
1 parent fb73ea0 commit b443fd3

File tree

6 files changed

+296
-0
lines changed

6 files changed

+296
-0
lines changed

‎3sum.py‎

Lines changed: 93 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,93 @@
1+
class Solution(object):
2+
#this is the answer from caikehe and all the comments below
3+
4+
"""
5+
the main idea is to iterate every number in nums.
6+
we use the number as a target to find two other numbers which make total zero.
7+
for those two other numbers, we move pointers, l and r, to try them.
8+
9+
l start from left to right
10+
r start from right to left
11+
12+
first, we sort the array, so we can easily move i around and know how to adjust l and r.
13+
if the number is the same as the number before, we have used it as target already, continue. [1]
14+
we always start the left pointer from i+1 because the combination has already tried. [2]
15+
16+
now we calculate the total
17+
if the total is less than zero, we need it to be larger, so we move the left pointer. [3]
18+
if the total is greater than zero, we need it to be smaller, so we move the right pointer. [4]
19+
if the total is zero, bingo! [5]
20+
we need to move the left and right pointers to the next different numbers, so we do not get repeating result. [6]
21+
22+
we do not need to consider i after nums[i]>0, since sum of positive will be always greater than zero. [7]
23+
we do not need to try the last two, since there are no rooms for l and r pointers.
24+
You can think of it as The last two have been tried by all others. [8]
25+
"""
26+
27+
def threeSum(self, nums):
28+
res = []
29+
nums.sort()
30+
length = len(nums)
31+
for i in xrange(length-2): #[8]
32+
if nums[i]>0: break #[7]
33+
if i>0 and nums[i]==nums[i-1]: continue #[1]
34+
35+
l, r = i+1, length-1 #[2]
36+
while l<r:
37+
total = nums[i]+nums[l]+nums[r]
38+
39+
if total<0: #[3]
40+
l+=1
41+
elif total>0: #[4]
42+
r-=1
43+
else: #[5]
44+
res.append([nums[i], nums[l], nums[r]])
45+
while l<r and nums[l]==nums[l+1]: #[6]
46+
l+=1
47+
while l<r and nums[r]==nums[r-1]: #[6]
48+
r-=1
49+
l+=1
50+
r-=1
51+
return res
52+
53+
"""
54+
def threeSum(self, nums):
55+
def twoSum(target, nums):
56+
res = []
57+
seen = collections.Counter()
58+
for n1 in nums:
59+
n2 = target-n1
60+
if n1 in seen or n2 in seen or n2 not in nums: continue
61+
if n1==n2 and nums[n1]<2: continue
62+
seen[n1]+=1
63+
seen[n2]+=1
64+
res.append([target*-1, n1, n2])
65+
return res
66+
67+
res = []
68+
zero = 0
69+
positive = collections.Counter()
70+
negative = collections.Counter()
71+
72+
for n in nums:
73+
if n>0:
74+
positive[n]+=1
75+
elif n==0:
76+
zero+=1
77+
else:
78+
negative[n]+=1
79+
80+
if zero>=3:
81+
res.append([0, 0, 0])
82+
if zero>=1:
83+
for p in positive:
84+
if p*-1 in negative:
85+
res.append([0, p, p*-1])
86+
87+
for p in positive:
88+
res+=twoSum(p*-1, negative)
89+
for n in negative:
90+
res+=twoSum(n*-1, positive)
91+
92+
return res
93+
"""

‎copy-list-with-random-pointer.py‎

Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
# Definition for singly-linked list with a random pointer.
2+
# class RandomListNode(object):
3+
# def __init__(self, x):
4+
# self.label = x
5+
# self.next = None
6+
# self.random = None
7+
class Solution(object):
8+
def copyRandomList(self, head):
9+
if head==None: return head
10+
11+
curr = head
12+
while curr:
13+
temp = curr.next
14+
new_node = RandomListNode(curr.label)
15+
new_node.next = temp
16+
curr.next = new_node
17+
curr = curr.next.next
18+
19+
curr = head
20+
while curr:
21+
curr.next.random = curr.random.next if curr.random else None
22+
curr = curr.next.next
23+
24+
curr = head
25+
curr_copy = head.next
26+
head_copy = head.next
27+
28+
while curr:
29+
curr.next = curr.next.next
30+
curr_copy.next = curr_copy.next.next if curr_copy.next else None
31+
curr = curr.next
32+
curr_copy = curr_copy.next
33+
34+
return head_copy

‎longest-palindromic-substring.py‎

Lines changed: 46 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,46 @@
1+
class Solution(object):
2+
def longestPalindrome(self, s):
3+
4+
"""
5+
findPalindorome() find the palindrone string from the center "mid"
6+
The center could be one char (case 1) or two the same char (case 2)
7+
We iterate through every char in string and assume it is the center
8+
And put it in findPalindorome() to find the longest
9+
10+
Time Efficiency: O(N^2)
11+
Space Efficiency: O(N)
12+
"""
13+
def findPalindorome(mid, mid2=None):
14+
r = 0
15+
l = len(s)
16+
max_pal = ''
17+
18+
if mid2:
19+
#case 2
20+
if mid<0 or mid>=l: return ''
21+
if mid2<0 or mid2>=l: return ''
22+
while mid-r>=0 and mid2+r<l and s[mid-r]==s[mid2+r]:
23+
max_pal = s[mid-r:mid2+r+1]
24+
r+=1
25+
else:
26+
#case 1
27+
if mid<0 or mid>=l: return ''
28+
while mid-r>=0 and mid+r<l and s[mid-r]==s[mid+r]:
29+
max_pal = s[mid-r:mid+r+1]
30+
r+=1
31+
return max_pal
32+
33+
max_pal = ''
34+
l = len(s)
35+
for i in range(len(s)):
36+
#case 1
37+
p = findPalindorome(i)
38+
max_pal = p if len(p)>len(max_pal) else max_pal
39+
40+
#case 2
41+
p2 = findPalindorome(i, i+1)
42+
max_pal = p2 if len(p2)>len(max_pal) else max_pal
43+
44+
return max_pal
45+
46+

‎meeting-rooms-ii.py‎

Lines changed: 60 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,60 @@
1+
# Definition for an interval.
2+
# class Interval(object):
3+
# def __init__(self, s=0, e=0):
4+
# self.start = s
5+
# self.end = e
6+
7+
class Solution(object):
8+
def minMeetingRooms(self, intervals):
9+
if len(intervals)==0: return 0
10+
11+
timeline = {}
12+
room_open = 0
13+
result = 0
14+
15+
for inter in intervals:
16+
if inter.start not in timeline:
17+
timeline[inter.start] = [1, 0]
18+
else:
19+
timeline[inter.start][0]+=1
20+
if inter.end not in timeline:
21+
timeline[inter.end] = [0, 1]
22+
else:
23+
timeline[inter.end][1]+=1
24+
25+
for time in timeline.keys().sort():
26+
room_open-=timeline[time][1]
27+
room_open+=timeline[time][0]
28+
result = max(result, room_open)
29+
30+
return result
31+
32+
# Definition for an interval.
33+
# class Interval(object):
34+
# def __init__(self, s=0, e=0):
35+
# self.start = s
36+
# self.end = e
37+
38+
class Solution(object):
39+
def minMeetingRooms(self, intervals):
40+
if not intervals: return 0
41+
42+
free_rooms = []
43+
intervals.sort(key= lambda x: x.start)
44+
45+
heapq.heappush(free_rooms, intervals[0].end)
46+
for i in intervals[1:]:
47+
if free_rooms[0]<=i.start:
48+
heapq.heappop(free_rooms)
49+
heapq.heappush(free_rooms, i.end)
50+
51+
return len(free_rooms)
52+
53+
54+
55+
56+
57+
58+
59+
60+

‎merge-intervals.py‎

Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
"""
2+
imagine a number line, we put all the numbers on it and draw a line between two numbers for each interval.
3+
for all the overlap lines we just want the start and the end
4+
5+
we need to sort the array of intervals, so we won't miss any overlaps by iterate through the array once. [1]
6+
7+
first we check if there is overlaps
8+
if we the end of the last interval is greater or equal than the start of this inteval, we found the overlaps. [2]
9+
so we need to update the last interval's end [3]
10+
11+
if there is no overlaps [4]
12+
we don't need to do anything, just put it in the array
13+
"""
14+
class Solution(object):
15+
def merge(self, intervals):
16+
result = []
17+
intervals.sort(key=lambda x: x.start) #[1]
18+
19+
for inter in intervals:
20+
if len(result)>0 and result[-1].end>=inter.start: #[2]
21+
result[-1].end = max(result[-1].end, inter.end) #[3]
22+
else: #[4]
23+
result.append(inter)
24+
return result

‎product-of-array-except-self.py‎

Lines changed: 39 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,39 @@
1+
"""
2+
I learn the solution from hqpdash and c040120's answer
3+
4+
the main idea is for each element of the array
5+
to get the product from all its left and the product from all its right
6+
then we product those two
7+
8+
note that the first element of nums don't have any left element
9+
so for the output[0], it is 1*(the product of all its right)
10+
the last element of nums don't have any right element
11+
so for the output[last], it is 1*(the product of all its left)
12+
13+
first, we iterate through every element [1]
14+
the main gaol here is to produce an array that
15+
output[i] is the product of all nums[i]'s left
16+
by incrementally product every number we gone through and store it in 't' [2]
17+
18+
second, we iterate backward [3]
19+
the main gaol here is to get the product from all nums[i] right and store it in 't' [4]
20+
and product it with the output from first step
21+
so output[i] now is (the product of all nums[i]'s left) * (the product of all nums[i]'s right) [5]
22+
"""
23+
24+
class Solution(object):
25+
def productExceptSelf(self, nums):
26+
l = len(nums)
27+
output = []
28+
29+
t = 1
30+
for i in xrange(l): #[1]
31+
output.append(t)
32+
t = t*nums[i] #[2]
33+
34+
t = 1 #reset the temporary variable
35+
for i in reversed(xrange(l)): #[3]
36+
output[i] = output[i]*t #[5]
37+
t = t*nums[i] #[4]
38+
39+
return output

0 commit comments

Comments
 (0)