leetcode notes

今天开始做一下LeetCode的算法题,做一下记录。

Two Sum

我最初的实现是暴利遍历,看了答案学习到这个O(n)的实现。

关键在于这里对于number 元素 index的字典索引是一个hash table,它的查询是时间复杂度O(1)的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
# number-index map, also as the iteration record
numIndex_map = dict()
for index, element in enumerate(nums):
co_element = target - element
if co_element in numIndex_map:
return numIndex_map[co_element], index
# append numIndex_map
numIndex_map[element] = index
return None

Add two numbers

第二题是单链表逆序表示十进制正整数实现加法。

我的实现考虑了下面的情况:

  • 在相加一方位数大于另一方时候,在没有进位tenFlag的时候,加和的ListNodenext指针直接指向大位数的那些高位node,而非继续遍历大位数的所有位。

另外,这是我第一次学习链表已经它的python实现,觉得很开心。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None

class Solution:
def addTwoNumbers(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
tenFlag, lowestDigi = divmod(l1.val + l2.val, 10)
result = ListNode(lowestDigi)
cursor_1, cursor_2, cursor_result = l1, l2, result

while (cursor_1.next is not None) and (cursor_2.next is not None):
tenFlag, added_Val = divmod(cursor_1.next.val + cursor_2.next.val + tenFlag, 10)
cursor_result.next = ListNode(added_Val)
cursor_1, cursor_2, cursor_result = cursor_1.next, cursor_2.next, cursor_result.next

cursor_result.next = (cursor_1.next or cursor_2.next)
while tenFlag == 1:
if cursor_result.next is None:
cursor_result.next = ListNode(0)
tenFlag, added_Val = divmod(cursor_result.next.val + tenFlag, 10)
cursor_result.next.val = added_Val
cursor_result = cursor_result.next
return result

Longest substring without repeating characters

第三题是找出字符串里最长的无重复字母子字符串。

我的最初实现是从两侧移动指针,两边的字母如果属于被指针包裹的子字符串,则向内移动。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
start, end = (0, len(s) - 1)
while (len(set(s[start:end+1])) < (end + 1 - start)) and start < end:
if s[start] in s[start + 1:end + 1]:
start = start + 1
continue
else:
end = end - 1
return end - start + 1

这是很傻的,因为它粗暴地假设先触及重复字母一定不包含于最终的最长子字符串。
反例: "pwwkew" 作为输入之后,选择的最长子字符串是 "pw", 而非 "wke"

修改之后的初步算法如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
def lengthOfLongestSubstring(s):
def duplicated_char_exists(s):
for i, c in enumerate(s):
if c in s[i + 1:]:
return True
return False
subStrLenMax = len(set(s))
#print("Possibly max substr length by len(set(s)) is %s" % subStrLenMax)
lenOfStr = len(s)
for delta in range(subStrLenMax + 1):
lenOfSubstr = subStrLenMax - delta
start = 0
end = start + lenOfSubstr
while end < lenOfStr + 1:
#if len(set(s[start:end])) < lenOfSubstr:
if duplicated_char_exists(s[start:end]):
start += 1
end += 1
else:
#print("first result sub-string is %s" % s[start:end])
return lenOfSubstr
return lenOfSubstr
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
def lengthOfLongestSubstring(self, s):
list_ = []
max_ = 0
for i in s:
if i in list_:
del list_[0:list_.index(i)+1]
list_.append(i)
else:
list_.append(i)
if len(list_) > max_:
max_ = len(list_)
return max_

to be continued…