开始刷 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)))
感受到了一些题目的模式, 需要恶补一下数据结构和算法的基础知识和套路.