开始刷 leetcode, 简单笔记下自己的答案, 目标十一结束之前搞定所有题目.
提高一个要求, 所有的答案执行效率必须要超过 90% 的 python 答题者.
1. Two Sum.
class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
tmp = []
for i, j in enumerate(nums):
tmp.append((i, j)) for k, item in enumerate(tmp):
l, m = item
for o, p in tmp[k+1:]:
if m + p == target:
return sorted((l, o))
runtime beats: 21.30%
优化1
class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
for i, j in enumerate(nums):
for k, l in enumerate(nums[i+1:]):
if j + l == target:
return (i, k + i + 1)
runtime beats: 21.97%
还是不行, 肯定还有别的办法.
2. Add Two Numbers
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None class Solution(object):
def addTwoNumbers(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
def gen(listnode):
yield listnode.val
while listnode.next:
listnode = listnode.next
yield listnode.val def izip_longest(gen1, gen2):
flag1, flag2 = True, True
try:
i = gen1.next()
except:
i = 0
flag1 = False try:
j = gen2.next()
except:
j = 0
flag2 = False
yield i, j while flag1 or flag2:
try:
i = gen1.next()
except:
i = 0
flag1 = False try:
j = gen2.next()
except:
j = 0
flag2 = False if flag1 or flag2:
yield i, j result = []
tmp = 0
for i, j in izip_longest(gen(l1), gen(l2)):
sum = i + j + tmp
if sum < 10:
tmp = 0
result.append(sum)
else:
tmp = 1
result.append(sum - 10)
if tmp:
result.append(tmp)
return result
runtime beats: 95.07%
用 python 刷题是有点不要脸了, 本题的关键是 itertools.izip_longest, 但是平台说不认识, 于是就自己攒了一个极端丑陋的版本. 有时间回头再优化.
3. Longest Substring Without Repeating Characters
class Solution(object):
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
if not s:
return 0 tmp = set(s)
length_tmp = len(tmp)
length = len(s) while length_tmp > 0:
for i in xrange(length - length_tmp + 1):
t = s[i:length_tmp + i]
if len(set(t)) < len(t):
continue if set(t) <= tmp:
return length_tmp
length_tmp -= 1
4. Median of Two Sorted Arrays
class Solution(object):
def findMedianSortedArrays(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: float
"""
tmp = sorted(nums1 + nums2)
length = len(tmp)
half = length / 2.0
if int(round(half)) == int(half):
return (tmp[int(half) - 1] + tmp[int(half)]) / 2.0
else:
return tmp[int(half)]
...需要看看 sorted 的源码, 这样刷题有什么意思, 完全是在作弊.
5. Longest Palindromic Substring
class Solution(object):
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
if not s:
return None def reverse1(string):
return string[::-1] def reverse2(string):
tmp = list(string)
tmp.reverse()
return "".join(tmp) length = len(s)
for i in xrange(length, 0, -1):
for j in xrange(length - i + 1):
tmp = s[j:i+j]
if tmp == reverse1(tmp):
return tmp
Time Limit Exceeded
python 判定回文很简单 string == string[::-1], 但是时间超时了, 暂时想不到更好的方法, 继续下一题.
6. ZigZag Conversion
class Solution(object):
def convert(self, s, numRows):
"""
:type s: str
:type numRows: int
:rtype: str
"""
tmp = []
if numRows == 1:
return s if len(s) <= numRows:
return s def attempt(gen):
tag = True
try:
rslt = gen.next()
except:
rslt = ""
tag = False
return tag, rslt def izip_longest(gen1, gen2):
gen1 = iter(gen1)
gen2 = iter(gen2) tag1, rslt1 = attempt(gen1)
tag2, rslt2 = attempt(gen2) yield rslt1, rslt2 while tag1 or tag2:
tag1, rslt1 = attempt(gen1)
tag2, rslt2 = attempt(gen2) if rslt1 or rslt2:
yield rslt1, rslt2 step = (numRows - 1) * 2
for i in xrange(numRows):
if(i == 0 or i == numRows - 1):
tmp.extend(s[i::step])
else:
j = (numRows - 1 - i) * 2
for _ in izip_longest(s[i::step], s[i+j::step]):
tmp.extend(_) return "".join(tmp)
7. Reverse Integer
class Solution(object):
def reverse(self, x):
"""
:type x: int
:rtype: int
"""
# what's the hell?
if x > 2**31 - 1:
return 0 if x < -2**31:
return 0 if x >= 0:
tmp = list(str(x))
tmp.reverse()
rslt = int("".join(tmp))
return rslt if -2**31 <= rslt <= 2**31 -1 else 0
else:
tmp = list(str(0 - x))
tmp.reverse()
rslt = 0 - int("".join(tmp))
return rslt if -2**31 <= rslt <= 2**31 -1 else 0
8. String to Integer (atoi)
class Solution(object):
def myAtoi(self, str):
"""
:type str: str
:rtype: int
"""
def search(lst, s):
i = 0
for j in lst:
if j == s:
i += 1
return i def parse(s):
if not s:
return 0
if s == "+" or s == "-":
return 0
if search(s, "+") + search(s, "-") > 1:
return 0
else:
rslt = int(s)
if rslt > 2**31 -1:
return 2**31 -1
if rslt < -2**31:
return -2**31
return rslt str = str.strip()
if not str:
return 0 tmp = []
for i in str:
if i in ("+", "-") or i.isdigit():
tmp.append(i)
else:
break
string = "".join(tmp)
return parse(string)
9. Palindrome Number
class Solution(object):
def isPalindrome(self, x):
"""
:type x: int
:rtype: bool
"""
if x < 0 or x > 2**31 - 1:
return False tmp = list(str(x))
if tmp == tmp[::-1]:
if int("".join(tmp[::-1])) > 2**31 -1 :
return False
else:
return True
else:
return False
12. Integer to Roman
class Solution(object):
def intToRoman(self, num):
"""
:type num: int
:rtype: str
"""
def convert(value, ten, five, one):
rslt = []
if not value:
return ""
if value == 9:
rslt.append(one + ten)
elif value >= 5:
rslt.append(five + one * (value - 5))
elif value == 4:
rslt.append(one + five)
else:
rslt.append(one * value) return "".join(rslt) thousand = num // 1000
handred = (num - thousand * 1000) // 100
decade = (num - thousand * 1000 - handred * 100) // 10
unit = (num - thousand * 1000 - handred * 100 - decade * 10) result = []
if thousand:
result.append("M" * thousand) result.append(convert(handred, 'M', 'D', 'C'))
result.append(convert(decade, 'C', 'L', 'X'))
result.append(convert(unit, 'X', 'V', 'I')) return "".join(result)
13. Roman to Integer
class Solution(object):
def romanToInt(self, s):
"""
:type s: str
:rtype: int
"""
result = 0
tmp = list(s) def get(lst, num):
try:
return lst[num]
except:
return None def calculate(tmp, i, j):
if j == "M":
return 1000 if j == "D":
return 500 if j == "L":
return 50 if j == "V":
return 5 if j == "C" and get(tmp, i+1) not in ("M", "D"):
return 100
elif j == "C" and get(tmp, i+1) in ("M", "D"):
return -100 if j == "X" and get(tmp, i+1) not in ("C", "L"):
return 10
elif j == "X" and get(tmp, i+1) in ("C", "L"):
return -10 if j == "I" and get(tmp, i+1) not in ("X", "V"):
return 1
elif j == "I" and get(tmp, i+1) in ("X", "V"):
return -1 for i, j in enumerate(tmp):
result += calculate(tmp, i, j) return result
14. Longest Common Prefix
class Solution(object):
def longestCommonPrefix(self, strs):
"""
:type strs: List[str]
:rtype: str
""" # os.path.commonprefix if not strs:
return "" shortest = strs[0] for i in strs:
if len(shortest) > len(i):
shortest = i for i in xrange(len(shortest), 0, -1):
tag = True
tmp = shortest[:i]
for j in strs:
if j[:i] != tmp:
tag = False
if tag:
return tmp
return ""
15. 3Sum
class Solution(object):
def threeSum(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
if not nums:
return [] length = len(nums) rslt = []
for i in xrange(0, length):
v_i = nums[i] for j in xrange(i+1, length):
v_j = nums[j] for k in xrange(j+1, length):
v_k = nums[k] if v_i + v_j + v_k == 0:
rslt.append(tuple(sorted([v_i, v_j, v_k]))) return list(set(rslt))
Time Limit Exceeded
16. 3Sum Closest
class Solution(object):
def threeSumClosest(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
if not nums:
return [] length = len(nums) mapping = {}
rslt = set()
for i in xrange(0, length):
v_i = nums[i] for j in xrange(i+1, length):
v_j = nums[j] for k in xrange(j+1, length):
v_k = nums[k]
_abs = abs(v_i + v_j + v_k - target)
mapping[_abs] = v_i + v_j + v_k
rslt.add(_abs) return mapping[min(rslt)]
Time Limit Exceeded
17. Letter Combinations of a Phone Number
class Solution(object):
def letterCombinations(self, digits):
"""
:type digits: str
:rtype: List[str]
"""
def multi(lst1, lst2):
if not lst1:
return lst2 rslt = []
for i in lst1:
for j in lst2:
rslt.append(i + j)
return rslt def worker(lst):
rslt = []
for i in lst:
rslt = multi(rslt, i)
return rslt mapping = {
2: "abc",
3: "def",
4: "ghi",
5: "jkl",
6: "mno",
7: "pqrs",
8: "tuv",
9: "wxyz"
} if not digits:
return [] if len(digits) == 1:
return list(mapping[int(digits)]) lst = [mapping[int(_)] for _ in digits if 1 < int(_) <= 9] return worker(lst)
18. 4Sum
class Solution(object):
def fourSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[List[int]]
"""
if not nums:
return [] length = len(nums) rslt = []
for i in xrange(0, length):
v_i = nums[i] for j in xrange(i+1, length):
v_j = nums[j] for k in xrange(j+1, length):
v_k = nums[k] for l in xrange(k+1, length):
v_l = nums[l] if v_i + v_j + v_k + v_l == target:
rslt.append(tuple(sorted([v_i, v_j, v_k, v_l]))) return list(set(rslt))
Time Limit Exceeded
19. Remove Nth Node From End of List
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None class Solution(object):
def removeNthFromEnd(self, head, n):
"""
:type head: ListNode
:type n: int
:rtype: ListNode
"""
def gen(node):
yield node.val
while node.next:
node = node.next
yield node.val lst = [_ for _ in gen(head)]
del lst[-n] return lst
20. Valid Parentheses
class Solution(object):
def isValid(self, s):
"""
:type s: str
:rtype: bool
"""
left = ["(", "{", "["]
right = [")", "}", "]"]
tmp = [] for i in s:
if i in left:
tmp.append(i)
if i in right:
index = right.index(i)
try:
j = tmp.pop()
except:
return False
else:
if j != left[index]:
return False if not tmp:
return True
else:
return False
21. Merge Two Sorted Lists
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None class Solution(object):
def mergeTwoLists(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
if not l1 and not l2:
return []
if not l1 and l2:
return l2
if l1 and not l2:
return l1 def gen(node):
yield node.val
while node.next:
node = node.next
yield node.val return sorted(list(gen(l1)) + list(gen(l2)))
感受到了一些题目的模式, 需要恶补一下数据结构和算法的基础知识和套路.