LeetCode 02: Add Two Numbers

Question:

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

My Resolution:

# 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
"""
ret = l1
while True:
l1.val = l1.val + l2.val

if l1.next and l2.next:
l1 = l1.next
l2 = l2.next
continue
if l1.next and (not l2.next):
l1 = l1.next
l2 = ListNode(0)
if not l1.next and l2.next:
l1.next = l2.next
l2 = ListNode(0)
if (not l1.next) and (not l2.next):
carry_bit = False
orig_ret = ret
while True:
if carry_bit:
ret.val += 1

if ret.val >= 10:
ret.val = ret.val % 10
carry_bit = True
else:
carry_bit = False

if not ret.next:
if carry_bit:
ret.next = ListNode(0)
ret = ret.next
else:
return orig_ret
else:
ret = ret.next

Discussion

这次好像是一个中等难度的题,依然是暴力解法,首先把所有的链表都加起来。然后再处理
一次需要进位的问题。这个地方有个坑就是,它没有说明哪里链表是否相等,我开始只用简
单的相等长的链表的相加,后来提交时才发现错了。

LeetCode 01: Two Sum

Question:

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

Resolution:

我开始用到的暴力破解法:

class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
for i, num1 in enumerate(nums):
for j, num2 in enumerate(nums[i + 1:]):
if num1 + num2 == target:
return [i, i + j + 1]

return None

时间复杂度:O(N^2),空间复杂度为:O(1)

Discuss

看了方案,有一个更好的利用额外的一个字典存储已经遍历的值,做到一次遍历就可以求到解,这里使用的技巧是字典的查询操作是O(1)的,用来代替我上面为了找到第二个值的O(N)遍历,很巧妙,想法很好。不过这套方案,空间复杂度是O(N),用空间优化了时间,很棒。

class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
number_dict = dict()
for index, value in enumerate(nums):
if target - value in number_dict:
return [number_dict[target-value] , index]
number_dict[value] = index
return [-1, -1]

Interview: Find the longest substring without repeating characters

原文: http://blog.gainlo.co/index.php/2016/10/07/facebook-interview-longest-substring-without-repeating-characters/

分析

暴力破解

最直接的方案,就是先把字符串拆解为所有可能的子字符串,时间复杂度为O(N^2),然后再去检查子字符串是否有重复字符,这个时间复杂度依然为O(N^2),所以最后的时间复杂度为O(N^4),同时空间复杂度在这里是O(1)

提速

我们上面的解决方案可以找到最终答案,但是高大O(N^4)的时间复杂度实在太慢,我们可以通过提高空间复杂度(更多内存)来提速。

我们在发现重复字符时,需要O(N^2)的时间复杂度,但是我们可以通过hashset去探测重复,只有O(N)的时间复杂度。

进一步优化

下面是解决拆解字符串的时间复杂度问题,原初是O(N^2)

去除不必要的操作:比如我们在检查到某个子字符串有重复的字符的时候,我们可以立即跳过所有包含该子字符串的部分。基于此,我们可以看到一个新方案:

  1. 指定2个指针(start,end)用来标定当前的子字串,初始值都设为0。
  2. 然后每次移动end指针一位,然后hashset去探测是否有重复的字符串。
    1.如果没有重复,继续向前移动。
    1.如果有重复,那把当前的字符串弹出,并把start指针移过重复的字串。
    3.重复上面的步骤,直到end指针到达字符串的末端。

最终的解决方案是O(N)的时间复杂度和O(N)的空间复杂度。