坚持每天刷Leetcode,每日至少一题。

  • 20180628更新:开始刷Leetcode题,争取至少每日一道。
  • 20180728更新:已经在Leetcode上刷题200道,目前总数680道,还差480道。已经完成了29.4%。7月份刷题52道。
  • 20180802更新:已经在Leetcode上刷题221道,目前总数688道,还差467道。已经完成了32.1%。距上次统计平均每天刷题4.2道。

2018-08-09

414. 第三大的数

为啥代码差不多一样,排名差了这么多,,,仅仅击败4%的提交

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
def thirdMax(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if not nums:
return
nums = sorted(set(nums), reverse=True)
if len(nums) < 3:
return nums[0]
else:
return nums[2]

14. 最长公共前缀

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
def longestCommonPrefix(self, strs):
"""
:type strs: List[str]
:rtype: str
"""
if not strs:
return ''
min_str = min(strs)
max_str = max(strs)
length = min(len(min_str), len(max_str))
for i in range(length):
if min_str[i] == max_str[i]:
i += 1
else:
return min_str[:i]
return min_str

击败74%的提交

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(object):
def same_prefix(self, a, b):
length = min(len(a), len(b))
for i in range(length):
if a[i] == b[i]:
i += 1
else:
return a[:i]
return a[:length]
def longestCommonPrefix(self, strs):
"""
:type strs: List[str]
:rtype: str
"""
if not strs:
return ''
res = strs[0]
for i in range(1, len(strs)):
res = self.same_prefix(res, strs[i])
if not res:
return res
return res

190. 颠倒二进制位

击败90.38%的提交

1
2
3
4
5
6
7
class Solution:
# @param n, an integer
# @return an integer
def reverseBits(self, n):
bits = bin(n)[2:]
bits = '0' * (32 - len(bits)) + bits
return int(bits[::-1], 2)

击败15.9%的提交

1
2
3
4
5
6
7
8
9
10
11
class Solution:
# @param n, an integer
# @return an integer
def reverseBits(self, n):
bits = []
while n != 0:
n, bit = divmod(n, 2)
bits.append(bit)
bits = [0] * (32 - len(bits)) + bits[::-1]
target_bits = ''.join(str(bit) for bit in bits[::-1])
return int(target_bits, 2)

2018-08-08

645. 错误的集合

击败96.49%的提交

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
def findErrorNums(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
# set一下,可以得到n为set的长度加一,这样就知道总和
# 减去set的和,就知道少了什么元素,拿未set的数据和减set的和,就知道多了什么
num_set = set(nums)
set_sum = sum(num_set)
n = len(num_set) + 1
return [sum(nums) - set_sum, int(n * (n+1) / 2 - set_sum)]

卧槽,现在写代码效率越来越低了,只击败了13%的提交

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
def findErrorNums(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
min_num = min(nums)
max_num = max(nums)
num_map = {num: 0 for num in range(min_num, max_num+1)}
res = [None, None]
for num in nums:
if num_map[num] == 1:
res[0] = num
else:
num_map[num] = 1
for num, value in num_map.items():
if value == 0:
res[1] = num
break
else:
res[1] = 1 if min_num != 1 else max_num + 1
return res

2018-08-07

687. 最长同值路径

已经遍历的元素不再进行查找,击败了50%的提交

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class Solution1(object):
def _dfs(self, node, value, seen):
if not node:
return 0
if node.val == value:
seen.add(node)
count = 1
left_count = self._dfs(node.left, value, seen)
right_count = self._dfs(node.right, value, seen)
count += max(left_count, right_count)
return count
return 0
def longestUnivaluePath(self, root):
"""
:type root: TreeNode
:rtype: int
"""
"""
5
/ \
4 5
/ \ \
1 1 5
2
1
/ \
4 5
/ \ \
4 4 5
2
"""
# 从根节点开始找,只要找到与根节点元素相等的值,就加一即可
if not root:
return 0
max_count = 0
stack = [root]
seen = set()
while stack:
node = stack.pop()
if node not in seen:
count = self._dfs(node.left, node.val, seen)
count += self._dfs(node.right, node.val, seen)
max_count = max(max_count, count)
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
return max_count

这个题没说明白,就是最大路径上一个节点只能连两条线。下面这个提交只击败了2.81%的提交,肯定复杂度是比较高的。这只是确定能解出这个题目的第一种方法,后面会作出优化。

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
class Solution(object):
def _dfs(self, node, value):
if not node:
return 0
if node.val == value:
count = 1
left_count = self._dfs(node.left, value)
right_count = self._dfs(node.right, value)
count += max(left_count, right_count)
return count
return 0
def longestUnivaluePath(self, root):
# 从根节点开始找,只要找到与根节点元素相等的值,就加一即可
if not root:
return 0
max_count = 0
stack = [root]
while stack:
node = stack.pop()
count = self._dfs(node.left, node.val)
count += self._dfs(node.right, node.val)
max_count = max(max_count, count)
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
return max_count

2018-08-06

160. 相交链表

实锤了,Leetcode服务器运行的太慢了,233333

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
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def getIntersectionNode(self, headA, headB):
"""
:type head1, head1: ListNode
:rtype: ListNode
"""
# 双指针,同时开始遍历
if not headA or not headB:
return
node_a, node_b = headA, headB
while node_a and node_b and node_a != node_b:
node_a = node_a.next
node_b = node_b.next
# 如果相等退出,包含None的情况
if node_a == node_b:
return node_a
# 如果node_a完了,跳到b链表,
# 两个链表如果相交的化,第二次遍历的时候肯定会重合
if not node_a:
node_a = headB
if not node_b:
node_b = headA
return node_a

给链表上加标记,然后如果重复的话,说明有相交节点,感觉已经很高效了,但只是击败了25%的提交 = =!

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
class Solution(object):
def getIntersectionNode(self, headA, headB):
"""
:type head1, head1: ListNode
:rtype: ListNode
"""
"""
A: a1 → a2
c1 → c2 → c3
B: b1 → b2 → b3
c1相交
"""
# 1. 给节点上加标记
node_a = headA
node_b = headB
while node_a or node_b:
if node_a:
if not hasattr(node_a, 'visited'):
node_a.visited = True
else:
return node_a
node_a = node_a.next
if node_b:
if not hasattr(node_b, 'visited'):
node_b.visited = True
else:
return node_b
node_b = node_b.next

643. 子数组最大平均数 I

数组题把我做懵逼了都。不过遇到这种循环中要用sum函数的,还是慎重,如果能推出来,最好推导出来,这样极大提高效率。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
def findMaxAverage(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: float
"""
i = k
start_sum = sum(nums[:k])
max_average = start_sum / k
while i < len(nums):
i = i + 1
start_sum = start_sum - nums[i - k - 1] + nums[i - 1]
max_average = max(start_sum / k, max_average)
return max_average

2018-08-05

849. 到最近的人的最大距离

优化了下,击败了40%的提交

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
def maxDistToClosest(self, seats):
"""
:type seats: List[int]
:rtype: int
"""
seated = [idx for idx in range(len(seats)) if seats[idx] == 1]
max_dis = 0
for idx in range(len(seated) - 1):
dis = (seated[idx + 1] - seated[idx]) // 2
max_dis = max(dis, max_dis)
if seats[0] != 1:
max_dis = max(max_dis, seated[0])
if seats[-1] != 1:
max_dis = max(max_dis, len(seats) - seated[-1] - 1)
return max_dis

脑子感觉锈住了,找不到好的算法,击败10%的提交。。

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
class Solution:
def maxDistToClosest(self, seats):
"""
:type seats: List[int]
:rtype: int
"""
i = 0
max_dis = 0
while i < len(seats):
if seats[i] == 1:
i += 1
continue
left = i
while left >= 0 and seats[left] != 1:
left -= 1
right = i
while right < len(seats) and seats[right] != 1:
right += 1
if left == -1:
max_dis = max(max_dis, right-i)
elif right == len(seats):
max_dis = max(max_dis, i-left)
else:
max_dis = max(max_dis, min(i - left, right-i))
i += 1
return max_dis

724. 寻找数组的中心索引

击败73%的提交

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
def pivotIndex(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
total = sum(nums)
left = 0
for i in range(len(nums)):
if (left << 1) + nums[i] == total:
return i
else:
left += nums[i]
return -1

另一种方法,就是记录下左边和右边目前的和,然后下一次就只需要在左边加上,和在右边减去对应的值就可以了,然后进行判断,击败30%的提交,还是有很大的改进余地。

其实这个加和减也可以优化掉,因为要使得题目成立,那么nums[i] + left + right = total, 并且 left = right,也就是nums[i] + 2 left = total,就只有一个未知数了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
def pivotIndex(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
left_sum_cache = 0
right_sum_cache = sum(nums)
for i in range(len(nums)):
left_sum_cache = left_sum_cache + (nums[i-1] if i != 0 else 0)
right_sum_cache = right_sum_cache - nums[i]
if left_sum_cache == right_sum_cache:
return i
return -1

第一种方法超时 = =!

1
2
3
4
5
6
7
8
9
10
class Solution:
def pivotIndex(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
for i in range(len(nums)):
if sum(nums[:i]) == sum(nums[i + 1:]):
return i
return -1

2018-08-04

189. 旋转数组

这种题,唉,一言难尽

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
31
32
33
34
35
36
37
38
class Solution(object):
def rotate(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: void Do not return anything, modify nums in-place instead.
"""
if k == 0:
return
nums_len = len(nums)
nums[:nums_len-k] = nums[:nums_len-k][::-1]
nums[nums_len-k:] = nums[nums_len-k:][::-1]
nums[:] = nums[::-1]
class Solution1(object):
def rotate(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: void Do not return anything, modify nums in-place instead.
"""
nums_len = len(nums)
nums[:] = nums[nums_len-k:] + nums[:nums_len-k]
class Solution3:
def rotate(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: void Do not return anything, modify nums in-place instead.
"""
nums_len = len(nums)
new_nums = nums.copy()
for i in range(len(nums)):
new_nums[(i+k) % nums_len] = nums[i]
nums[:] = new_nums

2018-08-03

700. 二叉搜索树中的搜索

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
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def searchBST(self, root, val):
"""
:type root: TreeNode
:type val: int
:rtype: TreeNode
"""
if not root:
return
queue = [root]
while queue:
node = queue.pop(0)
if node.val == val:
return node
elif val < node.val and node.left:
queue.append(node.left)
elif val > node.val and node.right:
queue.append(node.right)

2018-08-02

482. 密钥格式化

不优雅就不优雅了吧,脑子已经是一锅粥了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution(object):
def licenseKeyFormatting(self, S, K):
"""
:type S: str
:type K: int
:rtype: str
"""
S = ''.join(S.split('-')).upper()
# 从后面往前遍历,每到一组就将结果放入结果集
i = len(S) - 1
j = len(S)
count = 1
res = []
while i >= 0:
if count % K == 0:
res.append(S[i:j])
j = i
count = 1
else:
count += 1
if i == 0 and S[i:j]:
res.append(S[i:j])
i -= 1
return '-'.join(res[::-1])

234. 回文链表

O(n)时间复杂度和O(1)的空间复杂度,击败98%的吃瓜群众

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
31
32
class Solution1(object):
def isPalindrome(self, head):
"""
:type head: ListNode
:rtype: bool
"""
"""
1->2->2->1->1
输出: true
"""
slow = head
fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
# slow 在中间位置(奇数) 或者 中间靠右(偶数)
# 将slow右边的链表反转
node = slow
left = None
while node:
right = node.next
node.next = left
left = node
node = right
while left and head:
if head.val != left.val:
return False
left = left.next
head = head.next
return True

O(n)时间复杂度和空间复杂度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
def isPalindrome(self, head):
"""
:type head: ListNode
:rtype: bool
"""
"""
1->2->2->1
输出: true
"""
res = []
node = head
while node:
res.append(node.val)
node = node.next
return res == res[::-1]

2018-08-01

20. 有效的括号

感觉脑子注意力无法集中了。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution(object):
def isValid(self, s):
"""
:type s: str
:rtype: bool
"""
if not s:
return True
s_map = {
']': '[',
')': '(',
"}": '{'
}
# 栈 依次入栈 出栈
stack = [s[0]]
i = 1
while i < len(s):
if s[i] not in s_map:
stack.append(s[i])
else:
if not stack or s_map[s[i]] != stack.pop(-1):
return False
i += 1
return True if len(stack) == 0 else False

674. 最长连续递增序列

注意细节啊

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution(object):
def findLengthOfLCIS(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if not nums:
return 0
i = 1
count = 1
res = 0
while i < len(nums):
if nums[i] > nums[i-1]:
count += 1
else:
res = max(res, count)
count = 1
i += 1
else:
res = max(res, count)
return res

594. 最长和谐子序列

这道题换一种思路会非常简单,直接统计各个元素的数量,然后去找和该元素相差1的元素数量,两者之和就是结果。另外规定只按照向右找,即2找3,3找4.

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
def findLHS(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
from collections import Counter
counter = Counter(nums)
max_len = 0
for key, value in counter.items():
if key + 1 in counter:
max_len = max(max_len, value + counter[key+1])
return max_len

836. 矩形重叠

击败98.25%的提交

1
2
3
4
5
6
7
8
9
10
11
12
class Solution(object):
def isRectangleOverlap(self, rec1, rec2):
"""
:type rec1: List[int]
:type rec2: List[int]
:rtype: bool
"""
# 重叠的可能有多种多样,不重叠的可能只有4种
# 以第二个矩形为中心,进行判断
if rec1[2] <= rec2[0] or rec1[1] >= rec2[3] or rec1[0] >= rec2[2] or rec1[3] <= rec2[1]:
return False
return True

111. 二叉树的最小深度

击败95.72%的提交

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def minDepth(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if not root:
return 0
queue = [(root, 1)]
while queue:
node, level = queue.pop(0)
if not node.left and not node.right:
return level
if node.left:
queue.append((node.left, level+1))
if node.right:
queue.append((node.right, level+1))

125. 验证回文串

1
2
3
4
5
6
7
8
9
10
11
class Solution(object):
def isPalindrome(self, s):
"""
:type s: str
:rtype: bool
"""
res = []
for ele in s:
if ele.isalnum():
res.append(ele.lower())
return res == res[::-1]

不知道为啥,很慌,做错了好几次

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(object):
def isPalindrome(self, s):
"""
:type s: str
:rtype: bool
"""
if not s:
return True
s = s.lower()
i = 0
j = len(s) - 1
while i < j:
while i < len(s) and not s[i].isalnum():
i += 1
while j > 0 and not s[j].isalnum():
j -= 1
if i > j:
return True
if s[i] != s[j]:
return False
i += 1
j -= 1
return True

290. 单词模式

双向,完全匹配 233333

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
def wordPattern(self, pattern, str):
"""
:type pattern: str
:type str: str
:rtype: bool
"""
strings = str.split(' ')
if len(strings) != len(pattern):
return False
word_map = {}
used = set()
for idx, ele in enumerate(pattern):
if ele not in word_map and strings[idx] not in used:
word_map[ele] = strings[idx]
used.add(strings[idx])
if word_map.get(ele) != strings[idx]:
return False
return True

2018-07-31

28. 实现strStr()

需要注意一些细节问题

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
class Solution(object):
def strStr(self, haystack, needle):
"""
:type haystack: str
:type needle: str
:rtype: int
"""
if not needle:
return 0
if len(needle) > len(haystack):
return -1
i = j = 0
while i < len(haystack) and len(needle) <= len(haystack) - i:
if haystack[i] != needle[0]:
i += 1
else:
inner_i = i
while j < len(needle):
if haystack[inner_i] == needle[j]:
inner_i += 1
j += 1
else:
j = 0
i += 1
break
else:
return i
return -1

746. 使用最小花费爬楼梯

明显一看就是动态规划,那么动态规划要求解最后一个问题,就要找出前面问题之间的关系。这道题可以上一个台阶,也可以上两个台阶,那么dp[stop] = min(dp[stop-1]+cost[stop-1], dp[stop-2]+cost[stop-2])就是说,到达stop的时候可以通过前一个台阶上来,也可以通过前两个台阶上来,所以问题就转换成两个子问题的求解了,以此类推,那么一开始的时候只要知道第一个和第二个台阶的cost值就可以完成求解。

明显可以看出来dp[0]=0, dp[1]=0,因为一开始上台阶是没有cost的,所以开始动态规划的迭代,每个子问题都是最优解,那么最后的stop也是最优解了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
def minCostClimbingStairs(self, cost):
"""
:type cost: List[int]
:rtype: int
"""
stop = len(cost)
dp = {
0: 0,
1: 0
}
for i in range(2, stop+1):
dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])
return dp[stop]

2018-07-30

876. 链表的中间结点

双指针法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def middleNode(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
# 双指针
i = j = head
while i and j:
if j.next and j.next.next:
j = j.next.next
i = i.next
elif j.next:
return i.next
else:
return i

2018-07-29

720. 词典中最长的单词

纳尼 ["yo","ew","fc","zrc","yodn","fcm","qm","qmo","fcmz","z","ewq","yod","ewqz","y"] 输出 ewqz 居然是错的,答案是yodn,什么鬼?原来是里面每个字不断的组成都得有

实现了个单词查找树,不过效率上只击败了15%的提交

另一种方法就是对每个单词进行迭代,然后对每个单词的前缀分别都进行遍历查找,看有没有在单词列表中

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
class Node:
ENDOF = '#'
def __init__(self, depth, parent, val=None):
self.depth = depth
self.val = val
self.parent = parent
self.children = {}
class Trie:
def __init__(self):
self.root = Node(depth=0, parent=None, val="root")
self.size = 0
self.count = None
def add(self, key):
self.size += 1
node = self.root
# 将单词key中的每一个字添加到树中
for ele in key:
if ele not in node.children:
node.children[ele] = Node(node.depth + 1, node, ele)
node = node.children[ele]
else:
node.children[Node.ENDOF] = Node(node.depth + 1, node, Node.ENDOF)
return self.root
def has_prefix(self, word):
node = self.root
for ele in word:
node = node.children[ele]
if Node.ENDOF not in node.children:
return False
else:
return True
class Solution(object):
def longestWord(self, words):
"""
:type words: List[str]
:rtype: str
"""
trie = Trie()
for word in words:
trie.add(word)
def _sort_func(x, y):
if len(y) - len(x) == 0:
if x < y:
return -1
elif x > y:
return 1
else:
return 0
else:
return len(y) - len(x)
from functools import cmp_to_key
words = sorted(words, key=cmp_to_key(_sort_func))
for word in words:
if trie.has_prefix(word):
return word

2018-07-28

427. 建立四叉树

核心在于如何分割矩形以及递归截止条件

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
"""
# Definition for a QuadTree node.
class Node(object):
def __init__(self, val, isLeaf, topLeft, topRight, bottomLeft, bottomRight):
self.val = val
self.isLeaf = isLeaf
self.topLeft = topLeft
self.topRight = topRight
self.bottomLeft = bottomLeft
self.bottomRight = bottomRight
"""
class Solution(object):
def build_tree(self, rect):
dup = set()
row_len, col_len = len(rect), len(rect[0])
row_mid, col_mid = row_len // 2, col_len // 2
top_left_rect = []
top_right_rect = []
bottom_right_rect = []
bottom_left_rect = []
for row in range(row_mid):
dup |= set(ele for ele in rect[row])
top_left_rect.append(rect[row][0:col_mid])
top_right_rect.append(rect[row][col_mid:])
for row in range(row_mid, row_len):
dup |= set(ele for ele in rect[row])
bottom_left_rect.append(rect[row][0:col_mid])
bottom_right_rect.append(rect[row][col_mid:])
if len(dup) == 1:
return Node(
val=bool(dup.pop()), isLeaf=True, topLeft=None,
topRight=None, bottomLeft=None, bottomRight=None
)
top_left = self.build_tree(top_left_rect)
top_right = self.build_tree(top_right_rect)
bottom_left = self.build_tree(bottom_left_rect)
bottom_right = self.build_tree(bottom_right_rect)
node = Node(
val=True, isLeaf=False, topLeft=top_left,
topRight=top_right, bottomLeft=bottom_left,
bottomRight=bottom_right
)
return node
def construct(self, grid):
"""
:type grid: List[List[int]]
:rtype: Node
"""
if not grid:
return
return self.build_tree(grid)

2018-07-27

205. 同构字符串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
def isIsomorphic(self, s, t):
"""
:type s: str
:type t: str
:rtype: bool
"""
alphabet_map = {}
used = set()
for s_ele, t_ele in zip(s, t):
if s_ele not in alphabet_map and t_ele not in used:
alphabet_map[s_ele] = t_ele
used.add(t_ele)
if alphabet_map.get(s_ele) != t_ele:
return False
return True

830. 较大分组的位置

击败21.98%的提交,68ms,但是感觉效率应该挺高的啊,O(n)?看第一名也是O(n)算法啊,44ms

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
def largeGroupPositions(self, S):
"""
:type S: str
:rtype: List[List[int]]
"""
i = 0
res = []
while i < len(S):
j = i + 1
while j < len(S) and S[j] == S[i]:
j += 1
if j - i >= 3:
res.append([i, j-1])
i = j
return res

203. 删除链表中的节点

一个优化后的迭代法,击败60%的提交

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
def removeElements(self, head, val):
"""
:type head: ListNode
:type val: int
:rtype: ListNode
"""
while head and head.val == val:
head = head.next
if not head:
return
node = head
while node:
if node.next and node.next.val == val:
node.next = node.next.next
else:
node = node.next
return head

迭代法击败40%的提交

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
def removeElements(self, head, val):
"""
:type head: ListNode
:type val: int
:rtype: ListNode
"""
while head and head.val == val:
head = head.next
if not head:
return
prev = head
node = head.next
while node:
if node.val == val:
prev.next = node.next
else:
prev = prev.next
node = node.next
return head

递归解法只击败了7%的提交。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
def removeElements(self, head, val):
"""
:type head: ListNode
:type val: int
:rtype: ListNode
"""
if not head:
return
if head.val == val:
return self.removeElements(head.next, val)
elif head.next and head.next.val == val:
head.next = self.removeElements(head.next.next, val)
else:
head.next = self.removeElements(head.next, val)
return head

796. 旋转字符串

感觉自己的算法功底提高了呢

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
def rotateString(self, A, B):
"""
:type A: str
:type B: str
:rtype: bool
"""
if len(A) != len(B):
return False
if A == B:
return True
i = 0
while i < len(B):
if B[i] == A[0] and B[i:] + B[:i] == A:
return True
i += 1
return False

697. 数组的度

另外一个版本,左右指针法,在遇到更大型数组的时候同样超出时间限制。。。那就是相同频次的数太多了。。。后来加了个判断,如果res == freq的话,直接返回结果即可,这样accepted了,而且击败了79%的提交。

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
class Solution(object):
def findShortestSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if not nums:
return 0
from collections import Counter, defaultdict
freqs = defaultdict(list)
counter = Counter(nums)
for value, c in counter.items():
freqs[c].append(value)
freq = max(freqs)
res = len(nums)
for num in freqs[freq]:
i, j = 0, len(nums) - 1
while i < j:
while nums[i] != num:
i += 1
while nums[j] != num:
j -= 1
res = min(res, j - i + 1)
if res == freq:
return res
break
return res

这个版本的答案超出时间限制,n2算法是有很大优化余地的,2333333

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
class Solution(object):
def findShortestSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if not nums:
return 0
from collections import Counter
counter = Counter(nums)
freq = counter.most_common(1)[0][1]
i = 0
res = len(nums)
while i < len(nums):
j = i + 1
inner_counter = Counter([nums[i]])
while max(inner_counter.values()) != freq and j < len(nums):
inner_counter.update([nums[j]])
if max(inner_counter.values()) == freq:
res = min(res, j - i + 1)
if res == freq:
return res
break
j += 1
i += 1
return res

872. 叶子相似的树

深度优先搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution(object):
def dfs(self, node):
res = []
leaf = True
if node.left:
leaf = False
res.extend(self.dfs(node.left))
if node.right:
leaf = False
res.extend(self.dfs(node.right))
if leaf:
res.append(node.val)
return res
def leafSimilar(self, root1, root2):
"""
:type root1: TreeNode
:type root2: TreeNode
:rtype: bool
"""
leaf_nodes_1 = self.dfs(root1)
leaf_nodes_2 = self.dfs(root2)
return leaf_nodes_1 == leaf_nodes_2

2018-07-26

747. 至少是其他数字两倍的最大数

时间复杂度为O(n),看了其他答案,比如先max, 再index的,最后再遍历一遍nums,虽然总体是一个量级,但是常数项太大,所以我超过了98%的用户,233333333

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
class Solution(object):
def dominantIndex(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if len(nums) == 1:
return 0
max_num = second_max_num = None
i = 0
while i < len(nums):
if max_num is None:
max_num = nums[i], i
elif nums[i] > max_num[0]:
second_max_num = max_num
max_num = nums[i], i
elif second_max_num is None:
second_max_num = nums[i], i
elif nums[i] > second_max_num[0]:
second_max_num = nums[i], i
i += 1
if second_max_num[0] == 0 or max_num[0] / second_max_num[0] >= 2:
return max_num[1]
else:
return -1

589. N叉树的前序遍历

递归版,只击败了5%的用户,尴尬

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
def preorder(self, root):
"""
:type root: Node
:rtype: List[int]
"""
# 前序遍历 递归版
if not root:
return []
res = [root.val]
for child in root.children:
res.extend(self.preorder(child))
return res

迭代版击败70%的用户

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
def preorder(self, root):
"""
:type root: Node
:rtype: List[int]
"""
# 迭代版
if not root:
return []
stack = [root]
res = []
while stack:
node = stack.pop()
res.append(node.val)
for child in node.children[::-1]:
stack.append(child)
return res

2018-07-25

784. 字母大小写全排列

回溯,然后到结束的时候把结果记录下来,然后再返回上一层,这样就可以把所有可能的结果拿出来了。

回溯是一种穷举,但与brute force有一些区别,回溯带了两点脑子的,并不多,brute force一点也没带。

第一点脑子是回溯知道回头;相反如果是brute force,发现走不通立刻跳下山摔死,换第二条命从头换一条路走。

第二点脑子是回溯知道剪枝;如果有一条岔路上放了一坨屎,那这条路我们不走,就可以少走很多不必要走的路。

回溯是一种找路方法,搜索的时候走不通就回头换路接着走,直到走通了或者发现此山根本不通。

DFS是一种开路策略,就是一条道先走到头,再往回走一步换一条路走到头,这也是回溯用到的策略。在树和图上回溯时人们叫它DFS。

递归是一种行为,回溯和递归如出一辙,都是一言不合就回到来时的路,所以一般回溯用递归实现;当然也可以不用,用栈。

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
class Solution(object):
def back_tracking(self, s, index, res):
if index >= len(s):
res.append(''.join(s))
return
if s[index].isalpha():
s[index] = s[index].lower()
self.back_tracking(s, index+1, res)
s[index] = s[index].upper()
self.back_tracking(s, index+1, res)
else:
self.back_tracking(s, index + 1, res)
def letterCasePermutation(self, S):
"""
:type S: str
:rtype: List[str]
"""
# 回溯
"""
root
a A
1 1
b B b B
2 2 2 2
"""
res = []
self.back_tracking(list(S), 0, res)
return res

2018-07-24

819. 最常见的单词

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from collections import Counter
class Solution(object):
def mostCommonWord(self, paragraph, banned):
"""
:type paragraph: str
:type banned: List[str]
:rtype: str
"""
symbol = "!?',;."
counter = Counter()
for word in paragraph.split(' '):
word = word.strip(symbol).lower()
if word not in banned:
counter[word] += 1
return counter.most_common(1)[0][0]

429. N叉树的层序遍历

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
31
32
33
"""
# Definition for a Node.
class Node(object):
def __init__(self, val, children):
self.val = val
self.children = children
"""
from collections import defaultdict
class Solution(object):
def levelOrder(self, root):
"""
:type root: Node
:rtype: List[List[int]]
"""
"""
[
[1],
[3,2,4],
[5,6]
]
"""
if not root:
return []
queue = [(root, 0)]
res = defaultdict(list)
while queue:
node, level = queue.pop(0)
res[level].append(node.val)
for child in node.children:
queue.append((child, level+1))
return [res[key] for key in sorted(res.keys())]

2018-07-23

717. 1比特与2比特字符

找到每一个比特字符的开始位置,然后往后加,毕竟1开始的就2位,0开始的就1位

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
def isOneBitCharacter(self, bits):
"""
:type bits: List[int]
:rtype: bool
"""
start = 0
if len(bits) == 1:
return True
while start < len(bits):
if bits[start] == 1:
start += 2
else:
start += 1
if start == len(bits) - 1:
return True
return False

458. 可怜的小猪

参考: https://www.zhihu.com/question/60227816

1
2
3
4
5
6
7
8
9
10
class Solution(object):
def poorPigs(self, buckets, minutesToDie, minutesToTest):
"""
:type buckets: int
:type minutesToDie: int
:type minutesToTest: int
:rtype: int
"""
import math
return int(math.ceil(math.log(buckets, 1+minutesToTest / minutesToDie)))

2018-07-22

661. 图片平滑器

反正这道题不是什么好题。。。

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
31
32
33
34
35
36
37
import math
import copy
class Solution:
def gen_inner_result(self, row, col, col_len, count, value):
count += 1
value += self.M[row][col]
if col - 1 >= 0:
count += 1
value += self.M[row][col - 1]
if col + 1 < col_len:
count += 1
value += self.M[row][col + 1]
return count, value
def gen_result(self, row, col, row_len, col_len):
count = value = 0
if row - 1 >= 0:
count, value = self.gen_inner_result(row-1, col, col_len, count, value)
if row + 1 < row_len:
count, value = self.gen_inner_result(row+1, col, col_len, count, value)
count, value = self.gen_inner_result(row, col, col_len, count, value)
return int(math.floor(value / count))
def imageSmoother(self, M):
"""
:type M: List[List[int]]
:rtype: List[List[int]]
"""
if not M:
return M
self.M = M
res_M = copy.deepcopy(M)
for row in range(len(M)):
for col in range(len(M[0])):
res_M[row][col] = self.gen_result(row, col, len(M), len(M[0]))
return res_M

2018-07-21

67. 二进制求和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
def addBinary(self, a, b):
"""
:type a: str
:type b: str
:rtype: str
"""
a_stack = [int(ele) for ele in a]
b_stack = [int(ele) for ele in b]
res = []
carry = 0
while a_stack or b_stack or carry != 0:
a_ele = a_stack.pop(-1) if a_stack else 0
b_ele = b_stack.pop(-1) if b_stack else 0
ele_sum = a_ele + b_ele + carry
carry, res_ele = divmod(ele_sum, 2)
res.append(str(res_ele))
return ''.join(res[::-1])

2018-07-20

671. 二叉树中第二小的节点

传统方法,先把节点值都拿出来,然后判断,肯定比较慢,没有用到这个树的特性

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
class Solution:
def traverse(self, node):
if not node:
return []
res = [node.val]
res += self.traverse(node.left)
res += self.traverse(node.right)
return res
def findSecondMinimumValue(self, root):
"""
:type root: TreeNode
:rtype: int
"""
"""
2
/ \
2 5
/ \
5 7
5
"""
values = set(self.traverse(root))
if len(values) <= 1:
return -1
else:
return sorted(values)[1]

另外一种方法,使用迭代法更加直观和简洁,通过记录first, second小的变量,不断迭代树中的节点并且进行更新即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
def findSecondMinimumValue(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if not root:
return -1
stack = [root]
first, second = root.val, -1
while stack:
node = stack.pop()
if node.val < first:
first = node.val
elif first < node.val and (node.val < second or second == -1):
second = node.val
if node.left:
stack.append(node.left)
stack.append(node.right)
return second

590. N叉树的后序遍历

递归解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
def postorder(self, root):
"""
:type root: Node
:rtype: List[int]
"""
# 左->右->中间
if not root:
return []
res = []
for child in root.children:
res += self.postorder(child)
res.append(root.val)
return res

迭代法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
def postorder(self, root):
"""
:type root: Node
:rtype: List[int]
"""
if not root:
return []
# 迭代法就是自己模拟栈
stack = [root]
res = []
while stack:
node = stack.pop()
for child in node.children:
stack.append(child)
# res添加的顺序正好和后序遍历相反
# 即先进入节点值,再进入的是右边子节点,所以后面直接逆序即可
res.append(node.val)
return res[::-1]

70. 爬楼梯

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
31
32
33
34
35
36
37
38
39
class Solution(object):
def climbStairs(self, n):
"""
:type n: int
:rtype: int
"""
"""
1
1
2
1 1
2
3
2
1 2
1
1 1 1
2 1
4
1
1 1 1 1
1 2 1
2 1 1
2
1 1 2
2 2
"""
dp = {
1: 1,
2: 2
}
for i in range(3, n+1):
# 其实就是上第i-1个台阶的不同方法加上 上第i-2个台阶的方法次数只和
# 因为如果上到i-2,差两个台阶上到i的可能次数
# 如果上到i-1,就是差一个台阶上到i的可能次数
# 比如n=4,差一个台阶上来的可能性为,也就是说末尾数字是1,则可能有 1111 121 211 即n=3的可能性
# 差两个台阶上来的可能性为,就是末尾数字是2,可能有 22 112 即为n=2的可能性
dp[i] = dp[i-1] + dp[i-2]
return dp[n]

559. N叉树的最大深度

传统的dfs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
def dfs(self, node, depth):
max_depth = depth
for child in node.children:
max_depth = max(max_depth, self.dfs(child, depth+1))
return max_depth
def maxDepth(self, root):
"""
:type root: Node
:rtype: int
"""
if not root:
return 0
depth = self.dfs(root, 1)
return depth

另一种方法,和上面原理一样,只是更简洁

1
2
3
4
5
6
7
8
9
10
11
class Solution(object):
def maxDepth(self, root):
"""
:type root: Node
:rtype: int
"""
if root is None:
return 0
if not root.children:
return 1
return max(map(self.maxDepth, root.children)) + 1

844. 比较含退格的字符串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
def build_string(self, string):
stack = []
for s in string:
if s != '#':
stack.append(s)
elif s == '#' and stack:
stack.pop()
return ''.join(stack)
def backspaceCompare(self, S, T):
"""
:type S: str
:type T: str
:rtype: bool
"""
# 两个栈,入栈,并且遇到#出栈,最后比较字符串是否相等
s = self.build_string(S)
t = self.build_string(T)
return s == t

733. 图像渲染

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
31
32
33
34
35
36
37
38
39
class Solution:
def dfs(self, x, y, color, seen):
# top
if x - 1 >= 0 and not seen[x-1][y] and self.image[x-1][y] == self.image[x][y]:
seen[x-1][y] = True
self.dfs(x-1, y, color, seen)
self.image[x - 1][y] = color
if y + 1 < len(self.image[0]) and not seen[x][y+1] and self.image[x][y+1] == self.image[x][y]:
seen[x][y+1] = True
self.dfs(x, y+1, color, seen)
self.image[x][y+1] = color
if x + 1 < len(self.image) and not seen[x+1][y] and self.image[x+1][y] == self.image[x][y]:
seen[x + 1][y] = True
self.dfs(x+1, y, color, seen)
self.image[x+1][y] = color
if y - 1 >= 0 and not seen[x][y-1] and self.image[x][y-1] == self.image[x][y]:
seen[x][y-1] = True
self.dfs(x, y-1, color, seen)
self.image[x][y-1] = color
def floodFill(self, image, sr, sc, newColor):
"""
:type image: List[List[int]]
:type sr: int
:type sc: int
:type newColor: int
:rtype: List[List[int]]
"""
self.image = image
seen = []
for i in range(len(image)):
inner = []
for j in range(len(image[0])):
inner.append(False)
seen.append(inner)
self.dfs(sr, sc, newColor, seen)
self.image[sr][sc] = newColor
return self.image

2018-07-19

155. 最小栈

使用最小堆

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
31
32
33
34
35
36
37
38
39
40
41
import heapq
class MinStack:
def __init__(self):
"""
initialize your data structure here.
"""
self.stack = []
self.min_heap = []
def push(self, x):
"""
:type x: int
:rtype: void
"""
heapq.heappush(self.min_heap, x)
self.stack.append(x)
def pop(self):
"""
:rtype: void
"""
if self.stack:
value = self.stack.pop(len(self.stack)-1)
if value is not None:
self.min_heap.remove(value)
def top(self):
"""
:rtype: int
"""
if self.stack:
return self.stack[len(self.stack)-1]
def getMin(self):
"""
:rtype: int
"""
if self.min_heap:
return heapq.nsmallest(1, self.min_heap)[0]

最小值判断

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
31
32
33
34
35
36
37
38
39
40
41
42
import sys
class MinStack1:
def __init__(self):
"""
initialize your data structure here.
"""
self.min = sys.maxsize
self.stack = []
def push(self, x):
"""
:type x: int
:rtype: void
"""
if x <= self.min:
# 在小于x的最小的值
self.stack.append(self.min)
self.min = x
self.stack.append(x)
def pop(self):
"""
:rtype: void
"""
peak = self.stack.pop()
if peak == self.min:
self.min = self.stack.pop()
def top(self):
"""
:rtype: int
"""
return self.stack[-1]
def getMin(self):
"""
:rtype: int
"""
return self.min

2018-07-18

783. 二叉搜索树结点最小距离

常规方法,用到bst的特效

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
class Solution:
def find_max(self, node):
while node.right:
node = node.right
return node.val
def find_min(self, node):
while node.left:
node = node.left
return node.val
def minDiffInBST(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if not root:
return
left_max = abs(root.val - self.find_max(root.left)) if root.left else None
right_min = abs(root.val - self.find_min(root.right)) if root.right else None
left = self.minDiffInBST(root.left)
right = self.minDiffInBST(root.right)
seq = [ele for ele in [left_max, right_min, left, right] if ele is not None]
if seq:
return min(seq)

先把数都拿出来,然后排序,然后逐一求差,找最小的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
def get_values(self, node):
if not node:
return []
values = [node.val]
values += self.get_values(node.left)
values += self.get_values(node.right)
return values
def minDiffInBST(self, root):
"""
:type root: TreeNode
:rtype: int
"""
tree_vals = self.get_values(root)
dp = []
tree_vals.sort()
for i in range(1, len(tree_vals)):
dp.append(abs(tree_vals[i] - tree_vals[i-1]))
return min(dp)

38. 报数

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
class Solution:
def build(self, string):
current = '#'
count = 0
res = ''
for i in string:
# 如果遍历字符和current记录中的不一样,则有可能是刚开始,也可能是一串相等数字的结束,
# 如果是结束,则current就不等于#,这样将上一串数字结果加入到res
# 然后将current置为当前数字,并且count置为1
if i != current:
if current != '#':
res += str(count) + current
current = i
count = 1
else:
count += 1
res += str(count) + current
return res
def countAndSay(self, n):
"""
:type n: int
:rtype: str
"""
string = '1'
for i in range(2, n+1):
string = self.build(string)
return string

225. 用队列实现栈

这种题感觉比较无聊

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
31
32
33
34
35
36
37
38
39
from collections import deque
class MyStack:
def __init__(self):
"""
Initialize your data structure here.
"""
self.queue = deque([])
def push(self, x):
"""
Push element x onto stack.
:type x: int
:rtype: void
"""
self.queue.appendleft(x)
def pop(self):
"""
Removes the element on top of the stack and returns that element.
:rtype: int
"""
return self.queue.popleft()
def top(self):
"""
Get the top element.
:rtype: int
"""
return self.queue[0]
def empty(self):
"""
Returns whether the stack is empty.
:rtype: bool
"""
return len(self.queue) == 0

706. Design HashMap

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
31
32
33
34
35
36
class MyHashMap:
def __init__(self):
"""
Initialize your data structure here.
"""
self.map = [None] * 1000000
def put(self, key, value):
"""
value will always be positive.
:type key: int
:type value: int
:rtype: void
"""
self.map[key] = value
def get(self, key):
"""
Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key
:type key: int
:rtype: int
"""
value = self.map[key]
if value is None:
return -1
else:
return value
def remove(self, key):
"""
Removes the mapping of the specified value key if this map contains a mapping for the key
:type key: int
:rtype: void
"""
self.map[key] = None

2018-07-17

653. 两数之和 IV - 输入 BST

哎,累了的时候就容易出小错误

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
31
32
33
34
class Solution:
def traverse(self, node):
if not node:
return []
res = [node]
res += self.traverse(node.left)
res += self.traverse(node.right)
return res
def search(self, node, target):
if not node:
return
if node.val == target:
return node
elif node.val < target:
return self.search(node.right, target)
else:
return self.search(node.left, target)
def findTarget(self, root, k):
"""
:type root: TreeNode
:type k: int
:rtype: bool
"""
# 遍历tree,随便拿一个元素,然后在bst中找另一个元素
for ele in self.traverse(root):
another = k - ele.val
node = self.search(root, another)
if node is None or node == ele:
continue
else:
return True
return False

二进制间距

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
def binaryGap(self, N):
"""
:type N: int
:rtype: int
"""
i = 0
binary = bin(N)[2:]
res = 0
while i < len(binary):
step = 1
j = i + 1
while j < len(binary) and binary[j] != '1':
j += 1
step += 1
if j == len(binary):
break
i = j
res = max(step, res)
return res

Design HashSet

哈希表?

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
31
32
33
34
35
36
37
class MyHashSet:
def __init__(self):
"""
Initialize your data structure here.
"""
self.table = [None] * 1000000
def add(self, key):
"""
:type key: int
:rtype: void
"""
self.table[key] = key
def remove(self, key):
"""
:type key: int
:rtype: void
"""
self.table[key] = None
def contains(self, key):
"""
Returns true if this set did not already contain the specified element
:type key: int
:rtype: bool
"""
return self.table[key] is not None
# Your MyHashSet object will be instantiated and called as such:
# obj = MyHashSet()
# obj.add(key)
# obj.remove(key)
# param_3 = obj.contains(key)

690. 员工的重要性

递归处理

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
"""
# Employee info
class Employee:
def __init__(self, id, importance, subordinates):
# It's the unique id of each node.
# unique id of this employee
self.id = id
# the importance value of this employee
self.importance = importance
# the id of direct subordinates
self.subordinates = subordinates
"""
class Solution:
def traverse(self, employee_id):
employee = self.employees_dict[employee_id]
importance = employee.importance
for subordinate in employee.subordinates:
importance += self.traverse(subordinate)
return importance
def getImportance(self, employees, id):
"""
:type employees: Employee
:type id: int
:rtype: int
"""
self.employees_dict = {e.id: e for e in employees}
return self.traverse(id)

2018-07-16

确定边界条件的要点是,保证定义的区间规则和循环内部迭代的区间规则一致。比如下面的是左闭右闭区间,那么迭代的时候就可以使用right=mid-1,如果是左闭右开区间,那么right=mid,因为mid-1可能就是解,如果将right=mid-1那么就可能错过这个正解。循环结束条件也应该符合相同的区间规则。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
def search(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
left, right = 0, len(nums) - 1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1

2018-07-15

709. 转换成小写字母

直接调用python的方法

1
2
3
4
5
6
7
class Solution:
def toLowerCase(self, str):
"""
:type str: str
:rtype: str
"""
return str.lower()

或者通过ASC码来转换

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
def toLowerCase(self, str):
"""
:type str: str
:rtype: str
"""
res = []
for s in str:
ord_s = ord(s)
if 65 <= ord_s <= 90:
res.append(chr(ord_s + 32))
else:
res.append(s)
return ''.join(res)

2018-07-14

860.柠檬水找零

贪心算法,优先拿大钞找零

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
class Solution:
def lemonadeChange(self, bills):
"""
:type bills: List[int]
:rtype: bool
"""
five, ten, twenty = 0, 0, 0
for bill in bills:
if bill == 5:
five += 1
elif bill == 10:
if five == 0:
return False
five -= 1
ten += 1
else:
if ten != 0 and five != 0:
ten -= 1
five -= 1
twenty += 1
elif five >= 3:
five -= 3
twenty += 1
else:
return False
return True

2018-07-13

旋转数字

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
class Solution:
def rotatedDigits(self, N):
"""
:type N: int
:rtype: int
"""
rotate_map = {
'0': '0',
'1': '1',
'8': '8',
'5': '2',
'2': '5',
'6': '9',
'9': '6'
}
count = 0
for n in range(N+1):
n_list = []
for d in str(n):
if d not in rotate_map:
break
n_list.append(rotate_map[d])
else:
if n != int(''.join(n_list)):
count += 1
return count

2018-07-12

计数二进制子串

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
class Solution:
def countBinarySubstrings(self, s):
"""
:type s: str
:rtype: int
"""
# 当前重复的数字种类的个数
cur = 1
# 上一种数字重复的次数
pre = 0
res = 0
idx = 1
# 遍历的时候如果和前一个数相等,则cur+1
# 如果出现不等,则将cur赋值给pre
# 只要pre大于等于cur的时候,count就自增1
# 因为0011中的结果为2-> 01 和 0011
while idx < len(s):
if s[idx-1] == s[idx]:
cur += 1
else:
pre = cur
cur = 1
if pre >= cur:
res += 1
idx += 1
return res

2018-07-11

区域和检索 - 数组不可变

一道简单的题,却没想到动态规划可以如此高的效率

  • 普通方法(1416 ms)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class NumArray:
def __init__(self, nums):
"""
:type nums: List[int]
"""
self.nums = nums
def sumRange(self, i, j):
"""
:type i: int
:type j: int
:rtype: int
"""
return sum(self.nums[i:j+1])
  • 动态规划(88 ms)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class NumArray:
def __init__(self, nums):
"""
:type nums: List[int]
"""
self._dp = {}
sums = 0
for idx, num in enumerate(nums):
sums += num
self._dp[idx] = sums
def sumRange(self, i, j):
"""
:type i: int
:type j: int
:rtype: int
"""
if i == 0:
return self._dp[j]
return self._dp[j] - self._dp[i-1]

2018-07-10

山羊拉丁文

这是一道多么无聊的题啊!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
def toGoatLatin(self, S):
"""
:type S: str
:rtype: str
"""
res = []
d = {'A', 'E', 'I', 'O', 'U'}
for idx, word in enumerate(S.split(' '), 1):
if word[0].upper() in d:
word += 'ma'
else:
first_alphabet = word[0]
word = word[1:] + first_alphabet + 'ma'
word += 'a' * idx
res.append(word)
return ' '.join(res)

2018-07-09

最大三角形面积

海伦公式:A = sqrt(s*(s-a)*(s-b)*(s-c)) 其中 s 为周长的一半 s = (a+b+c)/2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
def largestTriangleArea(self, points):
"""
:type points: List[List[int]]
:rtype: float
"""
import math
max_area = 0
for i in range(len(points)):
for j in range(i+1, len(points)):
for k in range(j+1, len(points)):
point_i, point_j, point_k = points[i], points[j], points[k]
distance_i_j = math.sqrt((point_i[0] - point_j[0]) ** 2 + (point_i[1] - point_j[1]) ** 2)
distance_i_k = math.sqrt((point_i[0] - point_k[0]) ** 2 + (point_i[1] - point_k[1]) ** 2)
distance_j_k = math.sqrt((point_k[0] - point_j[0]) ** 2 + (point_k[1] - point_j[1]) ** 2)
s = (distance_i_j + distance_i_k + distance_j_k) / 2
max_area = max(s * (s-distance_i_k) * (s-distance_i_j) * (s-distance_j_k), max_area)
return math.sqrt(max_area)

2018-07-08

岛屿的最大面积

深度优先遍历,注意递归的结束条件

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class Solution:
def go_right(self, row, col):
if col + 1 < self.cols:
return row, col + 1
return None, None
def go_up(self, row, col):
if row - 1 >= 0:
return row - 1, col
return None, None
def go_down(self, row, col):
if row + 1 < self.rows:
return row + 1, col
return None, None
def go_left(self, row, col):
if col - 1 >= 0:
return row, col - 1
return None, None
def traverse_island(self, row, col):
if row is None or col is None:
return 0
if self.grid[row][col] != 1:
return 0
self.grid[row][col] = 0
result = 1
result += self.traverse_island(*self.go_right(row, col))
result += self.traverse_island(*self.go_down(row, col))
result += self.traverse_island(*self.go_left(row, col))
result += self.traverse_island(*self.go_up(row, col))
return result
def maxAreaOfIsland(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
if not grid:
return 0
self.grid = grid
self.rows, self.cols = len(grid), len(grid[0])
max_count = 0
for row in range(self.rows):
for col in range(self.cols):
if grid[row][col] == 0:
continue
else:
max_count = max(max_count, self.traverse_island(row, col))
return max_count

2018-07-07

转置矩阵

对于方阵的话更简单,只需要考虑上半角矩阵,然后使用Python中的数字交换即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
def transpose(self, A):
"""
:type A: List[List[int]]
:rtype: List[List[int]]
"""
if not A:
return []
rows, cols = len(A), len(A[0])
B = [[0 for _ in range(rows)] for _ in range(cols)]
for row in range(rows):
for col in range(cols):
if row != col:
B[col][row] = A[row][col]
else:
B[row][col] = A[row][col]
return B

2018-07-06

托普利茨矩阵

感觉不能再刷简单题了,要不废了。。。233333

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
def isToeplitzMatrix(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: bool
"""
if not matrix:
return True
rows, cols = len(matrix), len(matrix[0])
for row in range(rows):
for col in range(cols):
if row + 1 < rows and col + 1 < cols:
if matrix[row][col] != matrix[row+1][col+1]:
return False
return True

2018-07-05

二进制表示中质数个计算置位

最大的数不超过100万,直接把二进制中小于100万的位数弄出来,这样二进制中最多的1,就是这个最大值了。所以直接遍历下,然后判断其中1的个数是不是在质数列表中即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
def countPrimeSetBits(self, L, R):
"""
:type L: int
:type R: int
:rtype: int
"""
# 2^19 == 524288
primes = {2, 3, 5, 7, 11, 13, 17, 19}
res = 0
for number in range(L, R+1):
count = bin(number).count('1')
if count in primes:
res += 1
return res

2018-07-04

棒球比赛

题目复杂,说了一大堆,解法简单

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
def calPoints(self, ops):
"""
:type ops: List[str]
:rtype: int
"""
res = []
for op in ops:
if op == '+':
res.append(sum(res[-2:]))
elif op == 'D':
res.append(res[-1] * 2)
elif op == 'C':
res.pop(-1)
else:
res.append(int(op))
return sum(res)

修剪二叉搜索树

递归递归递归

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
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def trimBST(self, root, L, R):
"""
:type root: TreeNode
:type L: int
:type R: int
:rtype: TreeNode
"""
if not root:
return
if L <= root.val <= R:
root.left = self.trimBST(root.left, L, R)
root.right = self.trimBST(root.right, L, R)
elif root.val < L:
root = self.trimBST(root.right, L, R)
elif root.val > R:
root = self.trimBST(root.left, L, R)
return root

2018-07-03

罗马数字转整数

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
class Solution:
def romanToInt(self, s):
"""
:type s: str
:rtype: int
"""
converter = {
'I': 1,
"V": 5,
"X": 10,
"L": 50,
"C": 100,
"D": 500,
"M": 1000
}
s_list = list(s.upper())
res = idx = 0
s_list_len = len(s_list)
while idx < s_list_len:
ele = s_list[idx]
if idx < s_list_len - 1:
next_ele = s_list[idx+1]
if converter[ele] < converter[next_ele]:
res += converter[next_ele] - converter[ele]
idx += 2
continue
res += converter[ele]
idx += 1
return res

2018-07-02

写字符串需要的行数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
def numberOfLines(self, widths, S):
"""
:type widths: List[int]
:type S: str
:rtype: List[int]
"""
pos = {alphabet: idx for idx, alphabet in enumerate("abcdefghijklmnopqrstuvwxyz")}
idx = row = col = 0
while idx < len(S):
expected = col + widths[pos[S[idx]]]
if expected > 100:
row += 1
col = 0
else:
col += widths[pos[S[idx]]]
idx += 1
return [row+1, col]

2018-07-01

子域名访问计数

这道题没太多算法需要考虑,就是细节问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
def subdomainVisits(self, cpdomains):
"""
:type cpdomains: List[str]
:rtype: List[str]
"""
from collections import defaultdict
counter = defaultdict(int)
for cpdomain in cpdomains:
times, domain = cpdomain.split(' ')
elements = domain.split('.')
idx = 0
while idx < len(elements):
subdomain = '.'.join(elements[idx:])
counter[subdomain] += int(times)
idx += 1
return ["{} {}".format(value, key) for key, value in counter.items()]

2018-06-30

交替位二进制数

这道题比较简单,不过注意结束条件应该是n!=0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
def hasAlternatingBits(self, n):
"""
:type n: int
:rtype: bool
"""
last = None
while n != 0:
n, remain = divmod(n, 2)
if last is not None:
if remain == last:
return False
last = remain
return True

2018-06-29

字符的最短距离

采用了左右边界指针法,pos为当前遍历指针,c_lft_posc_rgt_pos分别为在S中的c值左右指针,当pos遍历的时候,在lft指针左边,就是lft指针位置减去当前位置,在lft和rgt中间,则取最小值,等于rgt的时候需要调整左右指针位置,大于rgt则为pos减去rgt指针的位置。即可得解。

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
31
class Solution:
def shortestToChar(self, S, C):
"""
:type S: str
:type C: str
:rtype: List[int]
"""
c_pos_in_S = []
for idx, s in enumerate(S):
if s == C:
c_pos_in_S.append(idx)
if not c_pos_in_S:
return []
c_lft_pos = c_pos_in_S.pop(0)
c_rgt_pos = c_pos_in_S.pop(0) if c_pos_in_S else c_lft_pos
pos = 0
res = []
while pos < len(S):
if pos <= c_lft_pos:
res.append(c_lft_pos - pos)
elif c_lft_pos < pos < c_rgt_pos:
res.append(min([c_rgt_pos - pos, pos - c_lft_pos]))
elif pos == c_rgt_pos:
# 在等于右边界的时候调整边界位置
res.append(c_rgt_pos - pos)
c_lft_pos = c_rgt_pos
c_rgt_pos = c_pos_in_S.pop(0) if c_pos_in_S else c_lft_pos
else:
res.append(pos - c_rgt_pos)
pos += 1
return res

2018-06-28

唯一摩尔斯密码词

最朴素的解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
def uniqueMorseRepresentations(self, words):
"""
:type words: List[str]
:rtype: int
"""
alphabet_morse = [".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....", "..", ".---", "-.-", ".-..", "--",
"-.", "---", ".--.", "--.-", ".-.", "...", "-", "..-", "...-", ".--", "-..-", "-.--", "--.."]
alphabets = 'abcdefghijklmnopqrstuvwxyz'
alphabet_morse_dict = {alphabet: morse for alphabet, morse in zip(alphabets, alphabet_morse)}
res = set()
for word in words:
res.add(''.join(alphabet_morse_dict[w] for w in word))
return len(res)

当然也可以这样,a的ascii码为97

1
2
3
4
5
6
7
8
9
class Solution:
def uniqueMorseRepresentations(self, words):
"""
:type words: List[str]
:rtype: int
"""
t = [".-","-...","-.-.","-..",".","..-.","--.","....","..",\
".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."]
return len(set("".join(t[ord(a) - 97] for a in x) for x in words))

山脉数组的峰顶索引

二分法,主要确定循环条件,以及lo,hi值的确定

  • 慎重截止条件,根据指针移动条件来看,这里需要将数组判断到空为止,不能进入死循环。比如lo=0;hi=len(A)-1;lo<=hi,并且根据lo和hi指针的意义,比如判断数组等于key的位置,如果key存在于数组,lo==hi相等时已经得到解,所以是lo<hi
  • hi的确定一定在mid为止的左边,并且不包含当前位置
  • 一定在mid位置的右边,并且不包括当前mid位置

该题截止条件就是将数组判断为空为止,而且一般也不可能出现lo==hi这种情况,因为输入数组肯定是山峰数组,所以lo=0;hi=len(A);lo<hilo=0;hi=len(A)-1;lo<=hi都是可以的

lo的确定,一定在mid位置的右边,并且不包括当前mid位置,因为在第一个if已经判断了,所以mid不是正解

hi的确定,一定在mid为止的左边,并且不包含当前mid位置,因为在第一个if已经判断了,所以mid不是正解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
def peakIndexInMountainArray(self, A):
"""
:type A: List[int]
:rtype: int
"""
lo = 0
hi = len(A) - 1
while lo <= hi:
mid = lo + (hi - lo) // 2
if A[mid - 1] < A[mid] > A[mid + 1]:
return mid
elif A[mid] >= A[mid - 1]:
lo = mid + 1
elif A[mid] >= A[mid + 1]:
hi = mid - 1

翻转图像

比较简单,无须赘述。不过使用字典来取反,比使用异或运算ele ^ 1快点

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
def flipAndInvertImage(self, A):
"""
:type A: List[List[int]]
:rtype: List[List[int]]
"""
reverse = {1: 0, 0: 1}
res = []
for element in A:
processed_element = [reverse[ele] for ele in element[::-1]]
res.append(processed_element)
return res