8000 add 011-015 · fancymax/leetcode@d3d97d5 · GitHub
[go: up one dir, main page]
Skip to content

Commit d3d97d5

Browse files
bonfybonfy
authored
add 011-015
1 parent e25e90c commit d3d97d5

File tree

5 files changed

+244
-0
lines changed

5 files changed

+244
-0
lines changed

‎011-Container-With-Most-Water.py

Lines changed: 47 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,47 @@
1+
# -*-coding:utf-8-*-
2+
3+
# Given n non-negative integers a1, a2, ..., an,
4+
# where each represents a point at coordinate (i, ai).
5+
# n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0).
6+
# Find two lines, which together with x-axis forms a container,
7+
# such that the container contains the most water.
8+
9+
# Note: You may not slant the container.
10+
11+
# python version: Python 3
12+
13+
__Auther__ = 'BONFY'
14+
15+
16+
class Solution:
17+
def maxArea(self, height):
18+
"""
19+
:type height: List[int]
20+
:rtype: int
21+
"""
22+
max_area, i, j = 0, 0, len(height) - 1
23+
while i < j:
24+
max_area = max(max_area, min(height[i], height[j]) * (j - i))
25+
if height[i] < height[j]:
26+
i += 1
27+
else:
28+
j -= 1
29+
return max_area
30+
31+
32+
# Time Limit Exceeded
33+
class Solution2:
34+
def maxArea(self, height):
35+
"""
36+
:type height: List[int]
37+
:rtype: int
38+
"""
39+
m, l = 0, len(height)
40+
for i in range(0, l//2):
41+
for j in range(i+1, l):
42+
m = max(m, min(height[i], height[j]) * (j-i))
43+
return m
44+
45+
46+
if __name__ == '__main__':
47+
print(Solution().maxArea([28, 342, 418, 485, 719]))

‎012-Integer-to-Roman.py

Lines changed: 52 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,52 @@
1+
# -*-coding:utf-8-*-
2+
3+
# Given n non-negative integers a1, a2, ..., an,
4+
# where each represents a point at coordinate (i, ai).
5+
# n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0).
6+
# Find two lines, which together with x-axis forms a container,
7+
# such that the container contains the most water.
8+
9+
# Note: You may not slant the container.
10+
11+
# python version: Python 3
12+
13+
__Auther__ = 'BONFY'
14+
15+
16+
class Solution:
17+
def intToRoman(self, num):
18+
"""
19+
:type num: int
20+
:rtype: str
21+
"""
22+
int2roman = {
23+
1: "I",
24+
4: "IV",
25+
5: "V",
26+
9: "IX",
27+
28+
10: "X",
29+
40: "XL",
30+
50: "L",
31+
90: "XC",
32+
33+
100: "C&quo 57AE t;,
34+
400: "CD",
35+
500: "D",
36+
900: "CM",
37+
38+
1000: "M"
39+
}
40+
41+
builder = []
42+
components = list(sorted(int2roman.keys()))[::-1]
43+
for item in components:
44+
while num >= item:
45+
builder.append(int2roman[item])
46+
num -= item
47+
return "".join(builder)
48+
49+
50+
if __name__ == '__main__':
51+
print(Solution().intToRoman(1))
52+
print(Solution().intToRoman(3999))

‎013-Roman-to-Integer.py

Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
1+
# -*-coding:utf-8-*-
2+
3+
# Given a roman numeral, convert it to an integer.
4+
5+
# Input is guaranteed to be within the range from 1 to 3999.
6+
7+
# python version: Python 3
8+
9+
10+
__Auther__ = 'BONFY'
11+
12+
13+
class Solution:
14+
def romanToInt(self, s):
15+
"""
16+
:type s: str
17+
:rtype: int
18+
"""
19+
roman = {"I": 1, "V": 5, "X": 10, "L": 50, "C": 100, "D": 500, "M": 1000}
20+
total = 0
21+
for index in range(len(s)-1):
22+
type = 1 if roman[s[index]] >= roman[s[index+1]] else -1
23+
total += type*roman[s[index]]
24+
return total + roman[s[len(s)-1]]
25+
26+
27+
if __name__ == '__main__':
28+
print(Solution().romanToInt('DCXXI'))

‎014-longest-common-prefix.py

Lines changed: 63 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,63 @@
1+
# -*-coding:utf-8-*-
2+
3+
# Write a function to find the longest common prefix string amongst an array of strings.
4+
5+
# python version: Python 3
6+
7+
8+
__Auther__ = 'BONFY'
9+
10+
11+
class Solution:
12+
def longestCommonPrefix(self, strs):
13+
"""
14+
:type strs: List[str]
15+
:rtype: str
16+
"""
17+
if not strs:
18+
return ""
19+
strs = sorted(strs, key=lambda str: len(str))
20+
idx, p, rest = 0, strs[0], strs[1:]
21+
while len(p) > 0:
22+
while idx < len(rest) and p == rest[idx][:len(p)]:
23+
idx += 1
24+
if idx == len(rest):
25+
return p
26+
p = p[:-1]
27+
return ""
28+
29+
30+
# 少一步排序，更优
31+
class Solution2:
32+
def longestCommonPrefix(self, strs):
33+
"""
34+
:type strs: List[str]
35+
:rtype: str
36+
"""
37+
if not strs:
38+
return ""
39+
if len(strs) == 1:
40+
return strs[0]
41+
idx, p, rest = 0, strs[0], strs[1:]
42+
while len(p) > 0:
43+
while idx < len(rest) and len(p) <= len(rest[idx]) and p == rest[idx][:len(p)]:
44+
idx += 1
45+
if idx == len(rest):
46+
return p
47+
p = p[:-1]
48+
return ""
49+
50+
51+
if __name__ == '__main__':
52+
strs = ['abd', 'abc', 'abcd', 'abdcdss', 'aaaadss']
53+
import time
54+
start = time.clock()
55+
print(Solution().longestCommonPrefix(strs))
56+
end = time.clock()
57+
print(end-start)
58+
59+
start = time.clock()
60+
print(Solution2().longestCommonPrefix(strs))
61+
end = time.clock()
62+
print(end-start)
63+

‎015-3Sum.py

Lines changed: 54 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,54 @@
1+
# -*-coding:utf-8-*-
2+
3+
# Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0?
4+
# Find all unique triplets in the array which gives the sum of zero.
5+
6+
# Note: The solution set must not contain duplicate triplets.
7+
8+
# For example, given array S = [-1, 0, 1, 2, -1, -4],
9+
10+
# A solution set is:
11+
# [
12+
# [-1, 0, 1],
13+
# [-1, -1, 2]
14+
# ]
15+
16+
# python version: Python 3
17+
18+
19+
__Auther__ = 'BONFY'
20+
21+
22+
class Solution:
23+
def threeSum(self, nums):
24+
"""
25+
:type nums: List[int]
26+
:rtype: List[List[int]]
27+
"""
28+
nums.sort()
29+
res = []
30+
31+
for i in range(len(nums)-1): # because sums of 3 numbers
32+
if i == 0 or i > 0 and nums[i-1] != nums[i]:
33+
# avoid duplicate triplets [1 ,1, 1, -2]
34+
left = i + 1
35+
right = len(nums) - 1
36+
while left < right: # two-way pointer
37+
s = nums[i] + nums[left] + nums[right]
38+
if s == 0:
39+
res.append([nums[i], nums[left], nums[right]])
40+
left += 1
41+
right -= 1
42+
while left < right and nums[left] == nums[left - 1]:
43+
left += 1
44+
while right > left and nums[right] == nums[right + 1]:
45+
right -= 1
46+
elif s < 0:
47+
left += 1
48+
else:
49+
right -= 1
50+
return res
< 2851 /td>
51+
52+
53+
if __name__ == '__main__':
54+
print(Solution().threeSum([-1, 0, 1, 2, -1, -4]))

0 commit comments

Comments
 (0)
0