从今天起开始做每日LeetCode这个系列，从array, string, tree, linkedlist, math标签里选题做。
189. Rotate Array
tag. array
Solution来源 ：https://leetcode.com/problems/rotate-array/discuss/54426/Summary-of-solutions-in-Python
3-step array rotation: O(n) in time, O(1) in space
1
2
3
4
5
6
7
8
9
10
11
12
13
|
class Solution(object):
def rotate(self, nums, k):
if k is None or k <= 0:
return
k, end = k % len(nums), len(nums) - 1
self.reverse(nums, 0, end - k)
self.reverse(nums, end - k + 1, end)
self.reverse(nums, 0, end)
def reverse(self, nums, start, end):
while start < end:
nums[start], nums[end] = nums[end], nums[start]
start, end = start + 1, end - 1
|
Algorithm
This approach is based on the fact that when we rotate the array k times, k%nk elements from the back end of the array come to the front and the rest of the elements from the front shift backwards.
In this approach, we firstly reverse all the elements of the array. Then, reversing the first k elements followed by reversing the rest n-kn−k elements gives us the required result.
Let n=7n=7 and k=3k=3.
Original List : 1 2 3 4 5 6 7
After reversing all numbers : 7 6 5 4 3 2 1
After reversing first k numbers : 5 6 7 4 3 2 1
After revering last n-k numbers : 5 6 7 1 2 3 4 –> Result
67. Add Binary
tag. math, string
实现二进制的加法
Solution来源 ：https://leetcode.com/problems/add-binary/discuss/359628/python3-solutioneasy-to-understand
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 addBinary(self, a: str, b: str) -> str:
"""二进制加法运算"""
# 承接最后要返回的答案
ans = ""
a_index = len(a) - 1
b_index = len(b) - 1
# 进位标志
carry = 0
while a_index >= 0 or b_index >= 0:
# p、q是从右到左依次取得的各位数，如果不存在，则用0代替
p = int(a[a_index]) if a_index >= 0 else 0
q = int(b[b_index]) if b_index >= 0 else 0
a_index -= 1
b_index -= 1
# 计算对应位的和
sum = p + q + carry
# 保存加和后得到的字符串
ans = str(sum % 2) + ans
# 保存进位值
carry = sum // 2
# 如果到最后，进位值为1，则总位数加一位，首位为1
return "1" + ans if carry == 1 else ans
|
58. Length of Last Word
tag. string
算最后一个word的长度，这道题好评率略低。
我的Solution
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
class Solution:
def lengthOfLastWord(self, s: str) -> int:
last_space = True
len_without_space = len(s)
for i in range(len(s),0,-1):
# 需要考虑s最后有空格的情况，即"ab "长度是2.
if last_space:
if s[i-1] == ' ':
len_without_space -= 1
continue
else:
last_space = False
if s[i-1] == ' ':
return len_without_space - i
return len_without_space
|
Runtime: 32 ms, faster than 90.14% of Python3 online submissions for Length of Last Word.
Memory Usage: 14 MB, less than 5.26% of Python3 online submissions for Length of Last Word.
Discussion里面python的solution大部分使用split函数, 但有说明这种属于cheat的方法，真正interview的时候不要用这种方法。
Solution来源：https://leetcode.com/problems/length-of-last-word/discuss/21901/One-line-Python-solution
1
2
|
def lengthOfLastWord(self, s):
return len(s.rstrip(' ').split(' ')[-1])
|
21. Merge Two Sorted Lists
tag. linkedlist
合并两个有序链表，需要注意的是有一个额外的要求就是希望改变输入的两个链表(The new list should be made by splicing together the nodes of the first two lists)
Solution来源: https://leetcode.com/problems/merge-two-sorted-lists/discuss/9735/Python-solutions-(iteratively-recursively-iteratively-in-place).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
# iteratively
def mergeTwoLists1(self, l1, l2):
# cur总是指向我们最终想要建立的list的tail
dummy = cur = ListNode(0)
while l1 and l2:
if l1.val < l2.val:
cur.next = l1
l1 = l1.next
else:
cur.next = l2
l2 = l2.next
cur = cur.next
cur.next = l1 or l2
return dummy.next
|
Linkedlist问题小结
在Linkedlist的问题上，经常会利用到dumyhead，因为这样做能有效地处理empty list。(如果不使用dumyhead，那cur需要指向None，那又需要小心地处理cur->next)
100. Same Tree
tag. tree
判断两个树是否相同
Solution来源: https://leetcode.com/problems/same-tree/discuss/32729/Shortest%2Bsimplest-Python
1
2
3
4
|
def isSameTree(self, p, q):
if p and q:
return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
return p is q
|
递归来实现是非常直接简单的思路，值得学习的是上面有一个trick就是and和is的用法。
p is q等价于True if p==None and q==None else False, 即只有两个同时为None返回True。
另一个递归解法：
- Time complexity : O(N), where N is a number of nodes in the tree, since one visits each node exactly once.
- Space complexity :O(log(N)) in the best case of completely balanced tree and O(N) in the worst case of completely unbalanced tree, to keep a recursion stack.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
class Solution:
def isSameTree(self, p, q):
"""
:type p: TreeNode
:type q: TreeNode
:rtype: bool
"""
# p and q are both None
if not p and not q:
return True
# one of p and q is None
if not q or not p:
return False
if p.val != q.val:
return False
return self.isSameTree(p.right, q.right) and \
self.isSameTree(p.left, q.left)
|
Solution来源: https://leetcode.com/problems/same-tree/solution/
Iteration方法
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
|
from collections import deque
class Solution:
def isSameTree(self, p, q):
"""
:type p: TreeNode
:type q: TreeNode
:rtype: bool
"""
def check(p, q):
# if both are None
if not p and not q:
return True
# one of p and q is None
if not q or not p:
return False
if p.val != q.val:
return False
return True
deq = deque([(p, q),])
while deq:
p, q = deq.popleft()
if not check(p, q):
return False
if p:
deq.append((p.left, q.left))
deq.append((p.right, q.right))
return True
|
deque是double-end queue双向队列。
相比于list实现的队列，deque实现拥有更低的时间和空间复杂度。list实现在出队（pop）和插入（insert）时的空间复杂度大约为O(n)，deque在出队（pop）和入队（append）时的时间复杂度是O(1)。
https://zhuanlan.zhihu.com/p/37093602
