Leetcode Part 3

Mar 1, 2019

https://leetcode.com/explore/featured/card/top-interview-questions-easy/92/array/646/

Strings

Implement strStr()

忘记用 Python 的 [x:y] 来一段段匹配了:

if haystack == needle or not needle:
  return 0
for i, j in enumerate(haystack):
  if i > len(haystack) - len(needle) + 1:
    break
  if needle and haystack[i] == needle[0]:
    if i + len(needle) <= len(haystack):
      notMatch = False
      for l, m in enumerate(needle):
        if haystack[i + l] != needle[l]:
          notMatch = True
          break
      if not notMatch:
        return i
return -1

Runtime: 44 ms, faster than 55.70% of Python3 online submissions for Implement strStr().

Memory Usage: 13.4 MB, less than 5.13% of Python3 online submissions for Implement strStr().

Two Sum

https://leetcode.com/problems/two-sum/

for i in range(len(nums)):
  for j in range(i + 1, len(nums)):
    if nums[i] + nums[j] == target:
      return [i, j]

Runtime: 5424 ms, faster than 12.11% of Python3 online submissions for Two Sum.

Memory Usage: 13.6 MB, less than 42.31% of Python3 online submissions for Two Sum.

Add Two Numbers

https://leetcode.com/problems/add-two-numbers/

class Solution:
  def addTwoNumbers(self, l1, l2):
    head = None
    last = None
    while l1 is not None or l2 is not None:
      i = (0 if l1 is None else l1.val) + (0 if l2 is None else l2.val)
      if l1 is not None:
        l1 = l1.next
      if l2 is not None:
        l2 = l2.next
      if last is None:
        head = ListNode(i)
        last = head
      else:
        if last.next is None:
          last.next = ListNode(i)
        else:
          last.next.val += i
        last = last.next
      if last.val >= 10:
        last.val -= 10
        last.next = ListNode(1)
    return head

Runtime: 112 ms, faster than 61.12% of Python3 online submissions for Add Two Numbers.

Memory Usage: 13.4 MB, less than 5.21% of Python3 online submissions for Add Two Numbers.

Longest Substring Without Repeating Characters

https://leetcode.com/problems/longest-substring-without-repeating-characters/

class Solution:
  def lengthOfLongestSubstring(self, s: str) -> int:
    count_max = 0
    for i in range(len(s)):
      k = []
      count = 0
      for j in range(i, len(s)):
        if s[j] in k:
          break
        else:
          k.append(s[j])
          count += 1
      if count > count_max:
        count_max = count
    return count_max

Runtime: 1796 ms, faster than 5.02% of Python3 online submissions for Longest Substring Without Repeating Characters.

Memory Usage: 13.4 MB, less than 5.05% of Python3 online submissions for Longest Substring Without Repeating Characters.


[back]