[TOC]

72.编辑距离

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
def minDistance(self, word1, word2):
"""
:type word1: str
:type word2: str
:rtype: int"""
if word1 == '' or word2 == '':
return len(word1) if word1 != '' else len(word2)
dp = [[0]*(len(word1)+1) for _ in range(len(word2) + 1)]
for i in range(1,len(word1) + 1):
dp[0][i] += i
for i in range(1,len(word2) + 1):
dp[i][0] += i
for i in range(1, len(word2) + 1):
for j in range(1, len(word1) + 1):
if word2[i-1] == word1[j - 1]:
dp[i][j] = min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1]-1) + 1
else:
dp[i][j] = min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1]) + 1
return dp[-1][-1]

岛屿数量

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 numIslands(self, grid):
"""
:type grid: List[List[str]]
:rtype: int"""
if grid == []:
return 0
res = 0
def dfs(grid,pox,poy):
xh = [1,0,-1,0]
yh = [0,1,0,-1]
for k in range(4):
x = xh[k] + pox
y = yh[k] + poy
if 0 <= x < len(grid) and 0 <= y < len(grid[0]) and grid[x][y] == '1':
grid[x][y] = '-1'
dfs(grid,x,y)
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == '1':
res += 1
grid[i][j] = '-1'
dfs(grid,i,j)
return res

数组中第k个最大元素

快排

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 findKthLargest(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int"""
def quick_sort(nums,left,right):
if left >= right:
return
pivot = nums[left]
l = left
r = right
while l < r:
while l < r and nums[r] > pivot:
r -= 1
while l < r and nums[l] <= pivot:
l += 1
nums[l],nums[r] = nums[r],nums[l]
nums[left],nums[l] = nums[l],nums[left]
quick_sort(nums,left,l-1)
quick_sort(nums,l+1,right)
quick_sort(nums,0,len(nums)-1)
return nums[-k]

堆排

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(object):
def findKthLargest(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int"""
# 堆
# 构造大根树
def create_heap(nums,root_index,n):
left = root_index*2 + 1
right = root_index*2 + 2
max_index = root_index
if left <= n and nums[root_index] < nums[left]:
max_index = left
if right <= n and nums[max_index] < nums[right]:
max_index = right
if max_index != root_index:
nums[max_index],nums[root_index] = nums[root_index],nums[max_index]
create_heap(nums,max_index,n)

def sort_heap(nums):
n = len(nums) - 1
last_index = (n-1)//2 # 2i+1,2i+2
for i in range(last_index+1)[::-1]:
create_heap(nums,i,n)
sort_heap(nums)
n = len(nums) - 1
for i in range(k):
nums[0],nums[n-i] = nums[n-i],nums[0]
create_heap(nums,0,n-i-1)
return nums[-k]

搜索旋转排序数组

思路:先找到target在上面,还是在下面。然后通过组合条件and,确定是left,还是right移动。

image-20220429165935649

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 search(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int"""
if nums == []:
return -1
left = 0
right = len(nums) - 1
while left <= right:
mid = (left + right) >> 1
if nums[mid] == target:
return mid
if target <= nums[right]:
if target < nums[mid] and nums[mid] <= nums[right]:
right = mid - 1
else:
left = mid + 1
else:
if target > nums[mid] and nums[mid] >= nums[left]:
left = mid + 1
else:
right = mid - 1
return -1

Ps1:当数组有重复元素,可能出现nums[left] == nums[mid] == nums[right],无法区分,因此出现这种情况时,left += 1,right +=1跳过。

寻找旋转数组中的最小值

最小值一定在右侧,因此用mid与nums[right]比,left = mid + 1,right = mid

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

ps:当允许有重复数字的时候,会出现nums[mid] ==nums[right]的时候,并不意味着已经找到最小值了。因此当nums[mid] ==nums[right]相等的时候,选择right -= 1往里逼近。

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

无重复字符串的最长子串

list,维护最长子串,复杂度较高

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
if s == '':
return 0
res = []
ans = 0
for val in s:
while val in res:
res.pop(0)
res.append(val)
ans = max(ans,len(res))
return ans

使用set代替list,加快查找和删除的效率,用一个循环模拟set中元素的位置:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
occ = set()
ans = 0
right = -1
n = len(s)
for left in range(len(s)):
if left != 0:
occ.remove(s[left-1])
while right + 1 < n and s[right + 1] not in occ:
occ.add(s[right + 1])
right += 1
ans = max(ans, right - left + 1)
return ans

map,用map记录字母下标,left,right滑动窗口,当遇到相同的,用map给left赋值,跳过循环:

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 lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
mapper = {}
left,right = 0,0
n = len(s)
ans = 0
while right < n:
if s[right] not in mapper:
mapper[s[right]] = right
else:
ans = max(ans, right - 1 - left + 1)
if mapper[s[right]] >= left:
left = mapper[s[right]] + 1
mapper[s[right]] = right
right += 1
ans = max(ans,right -1 - left + 1)
return ans

二叉树中最大路径和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
def maxPathSum(self, root):
"""
:type root: TreeNode
:rtype: int"""
import sys
self.ans = -sys.maxsize
def dfs(root):
if root == None:
return 0
left = max(dfs(root.left),0)
right = max(dfs(root.right),0)
self.ans = max(self.ans, root.val + left + right)
return max(left,right) + root.val
dfs(root)
return self.ans

最长上升子序列

300题,带输出序列路径的版本,n2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution(object):
def lengthOfLIS(self, nums):
"""
:type nums: List[int]
:rtype: int"""
if nums == []:
return 0
dp = [1]* len(nums)
index = [-1]*len(nums)
for i in range(1,len(nums)):
for j in range(i):
if nums[i] > nums[j]:
dp[i] = max(dp[i],dp[j] + 1)
if dp[i] == dp[j] + 1:
index[i] = j
index_max = dp.index(max(dp))
res = [nums[index_max]]
while index[index_max]!= -1:
index_max = index[index_max]
res.append(nums[index_max])
print(res[::-1])
return max(dp)

维护一个最长最小递增序列的方法,nlog(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
class Solution(object):
def lengthOfLIS(self, nums):
"""
:type nums: List[int]
:rtype: int"""
if nums == []:
return 0
dp = [nums[0]]
for i in range(1,len(nums)):
val = nums[i]
if val > dp[-1]:
dp.append(val)
else:
left = 0
right = len(dp) - 1
pos = right
while left <= right:
mid = (left + right) >> 1
if dp[mid] >= val:
pos = mid
right = mid - 1
else:
left = mid + 1
dp[pos] = val
return len(dp)

平方根

69题,二分法

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 mySqrt(self, x):
"""
:type x: int
:rtype: int
"""
if x < 2:
return x
left = 0
right = x//2
while left <= right:
mid = (left + right) >> 1
if mid*mid == x:
return mid
if mid*mid > x:
right = mid - 1
elif (mid+1)**2 >x:
return mid
else:
left = mid + 1
return left

ps:上述是精确到1位,精确到小数点后3位,即mid - 1e-3。

二叉树锯齿层次遍历

103题,队列queue来完成。

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
# 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 zigzagLevelOrder(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
if root == None:
return []
ans = []
res = []
queue = [root]
flag = 0
level = 1
while queue:
node = queue.pop(0)
level -= 1
res.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
if level == 0:
if flag == 1:
res = res[::-1]
flag ^= 1
level = len(queue)
ans.append(res)
res = []
return ans

合并k个升序链表

23题,使用小根树(最小堆)来解决。

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
class Solution(object):
def mergeKLists(self, lists):
"""
:type lists: List[ListNode]
:rtype: ListNode
"""
if lists == []:
return None
lists = [val for val in lists if val != None ]
def create_heap(lists,root_index,n):
left = 2 * root_index + 1
right = 2 * root_index + 2
min_index = root_index
if left <= n and lists[left].val < lists[min_index].val:
min_index = left
if right <= n and lists[right].val < lists[min_index].val:
min_index = right
if min_index != root_index:
lists[min_index],lists[root_index] = lists[root_index],lists[min_index]
create_heap(lists,min_index,n)
def sort_heap(lists):
n = len(lists) - 1
last_index = (n-1)//2
for i in range(last_index + 1)[::-1]:
create_heap(lists,i,n)
sort_heap(lists)
dummy = ListNode(-1)
cur = dummy
while lists:
n = len(lists) - 1
if n == 0:
cur.next = lists[0]
break
cur.next = ListNode(lists[0].val)
cur = cur.next
lists[0] = lists[0].next
if lists[0] == None:
lists[0] = lists[-1]
lists.pop()
create_heap(lists,0,len(lists) - 1)
return dummy.next

二叉树最近公共祖先

236,后序遍历,一旦遇到选定子阶段就返回,不需要往下再遍历了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
def lowestCommonAncestor(self, root, p, q):
"""
:type root: TreeNode
:type p: TreeNode
:type q: TreeNode
:rtype: TreeNode"""
if root == q or root == p or root == None:
return root
left = self.lowestCommonAncestor(root.left,p,q)
right = self.lowestCommonAncestor(root.right,p,q)
if left and right:
return root
elif left == None:
return right
else:
return left

岛屿最大面积

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
31
class Solution(object):
def maxAreaOfIsland(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
if grid == []:
return 0
visits = [[0]*len(grid[0]) for _ in range(len(grid))]
def dfs(grid,visits,pox,poy,res):
xh = [1,0,-1,0]
yh = [0,1,0,-1]
for i in range(4):
x = xh[i] + pox
y = yh[i] + poy
if 0 <= x < len(grid) and 0 <= y < len(grid[0]) and visits[x][y] == 0 and grid[x][y] == 1:
visits[x][y] = 1
res[0] += 1
dfs(grid,visits,x,y,res)

ans = 0
res = [0]
for i in range(len(grid)):
for j in range(len(grid[0])):
if visits[i][j] == 0 and grid[i][j] == 1:
res[0] += 1
visits[i][j] = 1
dfs(grid,visits,i,j,res)
ans = max(res[0],ans)
res[0] = 0
return ans

最大正方形

dp的方法,dp[i][j] = min(dp[i-1][j-1],min(dp[i][j-1],dp[i-1][j])) + 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
def maximalSquare(self, matrix):
"""
:type matrix: List[List[str]]
:rtype: int
"""
if matrix == []:
return 0
side = 0
dp = [[0]*len(matrix[0]) for _ in range(len(matrix))]
for i in range(len(matrix)):
for j in range(len(matrix[0])):
if matrix[i][j] == '1':
if i == 0 or j == 0:
dp[i][j] = 1
else:
dp[i][j] = min(dp[i-1][j-1],min(dp[i][j-1],dp[i-1][j])) + 1
side = max(side,dp[i][j])
return side ** 2

滑动窗口

239题,用单调栈来做,用stack记录下标,保证stack[0]下标合法,删掉stack中比最新加入stack的元素要小的数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
def maxSlidingWindow(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: List[int]"""
if nums == []:
return []
ans = []
stack = []
# 单调栈
for i in range(len(nums)):
while stack and stack[0] < i - k + 1:
stack.pop(0)
while stack and nums[stack[-1]] <= nums[i]:
stack.pop()
stack.append(i)
if i >= k - 1:
ans.append(nums[stack[0]])
return ans

三数之和

15题,先排序,确定一个target,然后左右指针逼近。注意去重,第一遍记录之后,后续的要去重。

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 Solution(object):
def threeSum(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
if len(nums) < 3:
return []
nums = sorted(nums)
res = []
for i in range(len(nums)):
if i > 0 and nums[i] == nums[i-1]:
continue
target = - nums[i]
left = i + 1
right = len(nums) - 1
while left < right:
if left > i+1 and nums[left] == nums[left - 1]:
left += 1
continue
if right < len(nums) - 1 and nums[right] == nums[right + 1]:
right -= 1
continue
if target == nums[left] + nums[right]:
res.append([-target,nums[left],nums[right]])
left += 1
right -= 1
elif target < nums[left] + nums[right]:
right -= 1
else:
left += 1
return res

k个一组翻转链表

25题,翻转题很直观,但是容易乱,最好的方法就是拆解功能,将长度为k的子链表翻转单独作为一个函数,记住首尾元素,进行连接。

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 Solution(object):
def reverseKGroup(self, head, k):
"""
:type head: ListNode
:type k: int
:rtype: ListNode"""
if head == None or k == 1:
return head
dummy = ListNode(-1)
dummy.next = head
cur = dummy
def convert(begin,end):
dummy = ListNode(-1)
dummy.next = begin
pre = dummy
cur = begin
while cur != end:
tmp = cur.next
cur.next = pre
pre = cur
cur = tmp
cur.next = pre
return end,begin
while cur:
end = cur
for i in range(k):
if end.next == None:
return dummy.next
end = end.next
# print(end)
last = end.next
sub_begin,sub_end = convert(cur.next,end)
cur.next = sub_begin
sub_end.next = last
cur = sub_end
return dummy.next

全排列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
def permute(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]"""
if nums == []:
return []
visit = [0]*len(nums)
def dfs(nums,ans,visit,res):
if len(res) == len(nums):
ans.append(res)
return
for i in range(len(nums)):
if visit[i] == 0:
visit[i] = 1
dfs(nums,ans,visit,res+[nums[i]])
visit[i] = 0
ans = []
dfs(nums,ans,visit,[])
return ans

寻找正序数的中位数

4题,用二分法来解,每次判断两个数组k//2位置的大小,从而删掉k//2个数。直到k == 1 得到结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution(object):
def findMedianSortedArrays(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: float
"""
k1 = (len(nums1) + len(nums2) + 1) // 2
k2 = (len(nums1) + len(nums2) + 2) // 2
def helper(nums1,nums2,k):
if len(nums1) < len(nums2):
nums1,nums2 = nums2,nums1
if nums2 == []:
return nums1[k-1]
if k == 1:
return min(nums1[0],nums2[0])
t = min(k//2, len(nums2))
if nums1[t-1] >= nums2[t-1]:
return helper(nums1,nums2[t:],k-t)
else:
return helper(nums1[t:],nums2,k-t)
return (helper(nums1,nums2,k1) + helper(nums1,nums2,k2)) / 2.0

152 乘积最大子数组

注意正负号,因此同时维护imax,imin。每一个位置选择乘上历史乘积,和不乘历史乘积的最大值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
def maxProduct(self, nums):
"""
:type nums: List[int]
:rtype: int"""
import sys
ans = -sys.maxsize
if nums == []:
return 0
imax,imin = 1,1
for val in nums:
if val < 0:
imax,imin = imin,imax
imax = max(val,val*imax)
imin = min(val,val*imin)
ans = max(ans,imax)
return ans

64 最小路径和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
def minPathSum(self, grid):
"""
:type grid: List[List[int]]
:rtype: int"""
if grid == [] or grid[0] == []:
return 0
for i in range(1,len(grid[0])):
grid[0][i] += grid[0][i-1]
for j in range(1,len(grid)):
grid[j][0] += grid[j-1][0]
for i in range(1,len(grid)):
for j in range(1,len(grid[0])):
grid[i][j] = min(grid[i-1][j],grid[i][j-1]) + grid[i][j]
return grid[-1][-1]

92. 翻转链表

记住pre,next,last等这些节点信息。

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(object):
def reverseBetween(self, head, left, right):
"""
:type head: ListNode
:type left: int
:type right: int
:rtype: ListNode
"""
dummy = ListNode(-1)
dummy.next = head
pre = dummy
cur = pre
begin = dummy
while left:
cur = cur.next
left -= 1
if left == 1:
begin = cur
end = cur
cur = dummy
while right:
cur = cur.next
right -= 1
last = cur.next
cur = begin.next
pre = begin
while cur != last:
tmp = cur.next
cur.next = pre
pre = cur
cur = tmp
begin.next = pre
end.next = last
return dummy.next

400. 第N位数字

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
def findNthDigit(self, n):
"""
:type n: int
:rtype: int
"""
count = 1
lens = 1
while n > 9 *count * lens:
n -= 9 *count * lens
count *= 10
lens += 1
cur_num = (n-1) / lens + count
return int(str(cur_num)[(n-1)%lens])

139. 单词拆分

判断字符串能否由一个单词列表组成,思路是使用动态规划,s每个位置判断if dp[j] and s[j:i] in dicts,如果为真,则可以由单词表组成。

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 wordBreak(self, s, wordDict):
"""
:type s: str
:type wordDict: List[str]
:rtype: bool
"""
if s == '':
return False
n = len(s)
dp = [False]*(n+1)
dp[0] = True
dicts = {}
for val in wordDict:
dicts[val] = 1
for i in range(1,n+1):
for j in range(i):
if dp[j] and s[j:i] in dicts:
dp[i] = True
break
return dp[-1]

121 买卖股票的最佳时期

股票类型题1,仅能买卖一次,计算最大收益,没有约束条件,维护一个历史最小值,用每天的价格减去最小值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
if prices == []:
return 0
mins = prices[0]
res = 0
for i in range(1,len(prices)):
res = max(res,prices[i] - mins)
mins = min(mins,prices[i])
return res

122 买卖股票的最佳时期2

可以无限次买卖,计算最大收益,用dp模拟股票交易的全过程,有点像是遍历某个东西,由于股票交易过程要抽象成dp数组,因此有点难度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
# 用dp模拟股票交易的全过程,有点像是遍历某个东西
# 由于股票交易过程要抽象成dp数组,因此有点难度。
if prices == []:
return 0
dp = [[0]*2 for _ in range(len(prices))]
dp[0][1] = -prices[0]
for i in range(1,len(prices)):
dp[i][0] = max(dp[i-1][0],dp[i-1][1] + prices[i])
dp[i][1] = max(dp[i-1][1],dp[i-1][0] - prices[i])
return dp[-1][0]

297. 二叉树的序列化和反序列化

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 Codec:
def serialize(self, root):
"""Encodes a tree to a single string.

:type root: TreeNode
:rtype: str
"""
if root == None:
return ''
ans = ''
res = []
queue = [root]
while queue:
node = queue.pop(0)
if node:
res.append(str(node.val))
else:
res.append('null')
continue
queue.append(node.left)
queue.append(node.right)
ans = ','.join(res)
return ans

def deserialize(self, data):
"""Decodes your encoded data to tree.

:type data: str
:rtype: TreeNode
"""
if data == '':
return []
res = data.split(',')
root = TreeNode(int(res[0]))
res.pop(0)
queue = [root]
while queue:
node = queue.pop(0)
if res[0] == 'null':
node.left = None
else:
node.left = TreeNode(int(res[0]))
queue.append(node.left)
res.pop(0)
if res[0] == 'null':
node.right = None
else:
node.right = TreeNode(int(res[0]))
queue.append(node.right)
res.pop(0)
return root

接雨水

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
def trap(self, height):
"""
:type height: List[int]
:rtype: int"""
if height == []:
return 0
left = [0] * len(height)
left[0] = height[0]
right = [0] * len(height)
right[-1] = height[-1]
for i in range(1,len(height)):
left[i] = (max(left[i-1],height[i]))
for i in range(len(height)-1)[::-1]:
right[i] = (max(right[i+1],height[i]))
ans = 0
for i in range(len(height)):
ans += min(right[i],left[i]) - height[i]
return ans

209. 长度最小的子数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
def minSubArrayLen(self, s, nums):
"""
:type s: int
:type nums: List[int]
:rtype: int
"""
if nums == []:
return []
res = []
ans = 0
for i in range(len(nums)):
res.append(nums[i])
while sum(res) >= s:
if len(res) < ans or ans == 0:
ans = len(res)
res.pop(0)
# print(res)
return ans

19. 删除倒数第N个节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
def removeNthFromEnd(self, head, n):
"""
:type head: ListNode
:type n: int
:rtype: ListNode
"""
if head == None:
return None
dummy = ListNode(-1)
dummy.next = head
first = dummy
for _ in range(n):
first = first.next
cur = dummy
while first.next:
cur = cur.next
first = first.next
cur.next =cur.next.next
return dummy.next

394. 字符串解码

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(object):
def decodeString(self, s):
"""
:type s: str
:rtype: str
"""
if s == '':
return ''
stack = []
i = 0
while i < len(s):
if '0' <= s[i] <= '9':
res = 0
while i < len(s) and '0' <= s[i] <= '9':
res = res * 10 + int(s[i])
i += 1
stack.append(res)
elif s[i] == ']':
word = ''
while stack[-1] != '[':
word += stack.pop()
stack.pop()
num = stack.pop()
# word = word[::-1]
stack.append(num*word)
i += 1
else:
stack.append(s[i])
i += 1
# print(stack)
return ''.join([val[::-1] for val in stack])

206. 翻转链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
def reverseList(self, head):
"""
:type head: ListNode
:rtype: ListNode"""
if head == None:
return head
pre = head
cur = pre.next
head.next = None
while cur:
tmp = cur.next
cur.next = pre
pre = cur
cur = tmp
return pre

673. 最长递增子序列

同时维护一个dp最长序列长度,以及一个cnt,记录子序列的长度。

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 findNumberOfLIS(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if nums == []:
return 0
max_len = 0
cnt = [1] * len(nums)
dp = [1] * len(nums)
ans = 0
for i in range(len(nums)):
for j in range(i):
if nums[j] < nums[i]:
if dp[i] < dp[j] + 1:
dp[i] = dp[j] + 1
cnt[i] = cnt[j]
elif dp[i] == dp[j] + 1:
cnt[i] += cnt[j]
if dp[i] > max_len:
max_len = dp[i]
ans = cnt[i]
elif dp[i] == max_len:
ans += cnt[i]
return ans

96. 不同的二叉搜索树

左子树和右子树的笛卡尔积。

1
2
3
4
5
6
7
8
9
10
11
class Solution(object):
def numTrees(self, n):
"""
:type n: int
:rtype: int"""
G = [0]*(n+1)
G[0],G[1] = 1,1
for i in range(2,n+1):
for j in range(1,i+1):
G[i] += G[j-1]*G[i-j]
return G[-1]

148. 排序链表

使用归并排序,sort_func部分每次进行对半拆分,当只有一个node或者没有node的时候返回,merge部分对list进行拼接。

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 Solution(object):
def sortList(self, head):
"""
:type head: ListNode
:rtype: ListNode"""
def sort_func(head,tail):
if not head:
return head
if head.next == tail:
head.next = None
return head
fast = head
slow = head
while fast != tail:
slow = slow.next
fast = fast.next
if fast != tail:
fast = fast.next
mid = slow
return merge(sort_func(head,mid),sort_func(mid,tail))
def merge(temp1,temp2):
dummy = ListNode(-1)
cur = dummy
while temp1 and temp2:
if temp1.val <= temp2.val:
cur.next = temp1
temp1 = temp1.next
else:
cur.next = temp2
temp2 = temp2.next
cur = cur.next
if temp1:
cur.next = temp1
else:
cur.next = temp2
return dummy.next
return sort_func(head,None)

41. 缺失的第一个正数

申请一个辅助数组,遍历数组填充到dp的不同位置上,找到第一个未出现的正数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
def firstMissingPositive(self, nums):
"""
:type nums: List[int]
:rtype: int"""
if nums == []:
return 1
dp = [0]*(len(nums) + 1)
for val in nums:
if val <= 0 or val > len(nums):
continue
else:
dp[val] = 1
for i in range(1,len(nums) + 1):
if dp[i] == 0:
return i
return len(nums) + 1

53. 最大子数组和

1
2
3
4
5
6
7
8
9
10
11
class Solution(object):
def maxSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int"""
ans = 0
dp = ans = -sys.maxsize
for val in nums:
dp = max(dp,0) + val
ans = max(ans,dp)
return ans

1143. 最长公共子序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
def longestCommonSubsequence(self, text1, text2):
"""
:type text1: str
:type text2: str
:rtype: int
"""
if text1 == '' or text2 == '':
return 0
dp = [[0]*(len(text1)+1) for _ in range(len(text2)+1)]
dp[0][0] = 0
for i in range(1,len(text2)+1):
for j in range(1,len(text1)+1):
if text1[j-1] == text2[i-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j],dp[i][j-1])
return dp[-1][-1]

509. 斐波那契数

1
2
3
4
5
6
7
8
9
10
11
class Solution(object):
def fib(self, N):
"""
:type N: int
:rtype: int"""
if N <= 1:
return N
a,b = 0,1
for i in range(2,N+1):
a,b = b, a + b
return b

470. 用rand7实现rand10

1
2
3
4
5
6
7
8
9
10
11
12
class Solution(object):
def rand10(self):
"""
:rtype: int
"""
col,row,idx = 0,0,0
while True:
col = rand7()
row = rand7()
idx = col + (row - 1)*7
if idx <= 40:
return 1 + (idx - 1)%10

143. 重排链表

先找到中间位置的节点,然后分成左右两边进行操作。

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
class Solution(object):
def reorderList(self, head):
"""
:type head: ListNode
:rtype: None Do not return anything, modify head in-place instead.
"""
if head == None or head.next == None:
return head
fast = head.next
slow = head
while fast != None:
fast = fast.next
slow = slow.next
if fast!=None:
fast = fast.next
mid = slow
pre = mid
cur = mid.next
mid.next = None
while cur != None:
tmp = cur.next
cur.next = pre
pre = cur
cur = tmp
dummy = ListNode(-1)
p1 = head
p2 = pre

flag = 1
cur = dummy
while p1 != p2:
if flag == 1:
cur.next = p1
p1 = p1.next
else:
cur.next = p2
p2 = p2.next
flag ^= 1
cur = cur.next
cur.next = p2
return dummy.next

240. 搜索二维矩阵 II

从左下角作为开始节点,进行搜索。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
def searchMatrix(self, matrix, target):
"""
:type matrix: List[List[int]]
:type target: int
:rtype: bool"""
if matrix == [] or matrix[0] == []:
return False
pox,poy = len(matrix) - 1,0
while pox >= 0 and poy < len(matrix[0]):
if matrix[pox][poy] > target:
pox -= 1
elif matrix[pox][poy] < target:
poy += 1
else:
return True
return False

70. 爬楼梯

斐波那契数列的解法。

1
2
3
4
5
6
7
8
9
10
11
class Solution(object):
def climbStairs(self, n):
"""
:type n: int
:rtype: int"""
if n == 0:
return 0
a,b = 0,1
for i in range(1,n+1):
a,b = b, b+a
return b

31. 下一个排列

一个正序的数组是最小的排列,是一个开口向右的直角三角形,最大的排列是开口向左的直角三角形,因此,下一个排列,就是从后往前,找到第一个降序的数pos,然后从pos之后的数中找一个更小的替换它,随后将pos后的数,做一个最小的排列。因为替换后依然有序,所以用双指针,翻转区间即可。

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 nextPermutation(self, nums):
"""
:type nums: List[int]
:rtype: None Do not return anything, modify nums in-place instead.
"""
if len(nums) == 0:
return
pos = len(nums) - 2
while pos >= 0 and nums[pos] >= nums[pos+1]:
pos -= 1
if pos < 0:
nums.sort()
return
left = pos+1
right = len(nums) - 1
for i in range(left,right+1)[::-1]:
if nums[i] > nums[pos]:
nums[pos],nums[i]= nums[i],nums[pos]
break
left = pos + 1
right = len(nums) - 1
while left < right:
nums[left],nums[right] = nums[right],nums[left]
left += 1
right -= 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
33
34
35
class Solution(object):
def isValidBST(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
if root == None:
return True
ans = []
queue = []
cur = root

while cur or queue:
while cur:
queue.append(cur)
cur = cur.left
cur = queue.pop()
ans.append(cur.val)
if len(ans) >= 2:
if ans[-1] <= ans[-2]:
return False
cur = cur.right
return True

def dfs(root,low,high):
if root == None:
return True
if not low < root.val < high:
return False
if not dfs(root.left,low,root.val):
return False
if not dfs(root.right,root.val, high):
return False
return True
return dfs(root,-sys.maxsize,sys.maxsize)

二叉树层次遍历

非递归BFS以及递归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
31
32
33
34
35
36
37
38
39
40
41
class Solution(object):
def levelOrder(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]"""
# BFS
if root == None:
return []
res = []
queue = [root]
level = 1
ans = []
while queue:
node = queue.pop(0)
level -= 1
res.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
if level == 0:
ans.append(res[::])
res = []
level = len(queue)
return ans

# DFS
if root == None:
return []
res = []
def dfs(root,depth):
if root == None:
return
if len(res) - 1 < depth:
res.append([root.val])
else:
res[depth].append(root.val)
dfs(root.left,depth+1)
dfs(root.right,depth+1)
dfs(root,0)
return 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
26
27
28
29
30
31
class Solution(object):
def spiralOrder(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: List[int]"""
if matrix == [] or matrix[0] == []:
return []
startx,starty = 0,0
endx,endy = len(matrix)-1,len(matrix[0])-1
res = []
while startx <= endx and starty <= endy:
for i in range(starty,endy+1):
res.append(matrix[startx][i])
startx += 1
if startx > endx:
break
for i in range(startx,endx+1):
res.append(matrix[i][endy])
endy -= 1
if starty > endy:
break
for i in range(starty,endy+1)[::-1]:
res.append(matrix[endx][i])
endx -= 1
if startx > endx:
break
for i in range(startx,endx+1)[::-1]:
res.append(matrix[i][starty])
starty += 1
# print(startx,starty,endx,endy)
return res

334. 递增的三元子序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
def increasingTriplet(self, nums):
"""
:type nums: List[int]
:rtype: bool"""
if len(nums) < 3:
return False
sub = [nums[0]]
for val in nums[1:]:
if val > sub[-1]:
sub.append(val)
else:
for j in range(len(sub)):
if sub[j] >= val:
sub[j] = val
break
if len(sub) == 3:
return True
return False

84. 柱状图中最大的矩阵

使用单调栈来求解。栈用来记录元素的下标。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
def largestRectangleArea(self, heights):
"""
:type heights: List[int]
:rtype: int"""
if heights == []:
return 0
stack = [-1]
res = 0
for i in range(len(heights)):
while len(stack) > 1 and heights[i] <= heights[stack[-1]]:
res = max(res,heights[stack.pop()]*(i-stack[-1]-1))
stack.append(i)
while len(stack) > 1:
res = max(res,heights[stack.pop()] * (len(heights) - stack[-1] - 1))
return res

1. 两数之和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
if nums == []:
return []
dicts = {}
for i in range(len(nums)):
if nums[i] in dicts:
return [dicts[nums[i]],i]
else:
dicts[target - nums[i]] = i

279. 完全平方数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
def numSquares(self, n):
"""
:type n: int
:rtype: int
"""
if n == 0:
return 0
dp = [0]*(n+1)
for i in range(n+1):
dp[i] = i
y = 0
while i - y*y >= 0:
dp[i] = min(dp[i],dp[i-y*y] + 1)
y += 1
return dp[-1]

50. Pow(x,n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
def myPow(self, x, n):
"""
:type x: float
:type n: int
:rtype: float"""
def dfs(x,n):
if n == 0:
return 1.0
half = dfs(x,n//2)
if n % 2 == 0:
return half*half
else:
return half*half*x
if n < 0:
x = 1/x
n = -n
return dfs(x,n)

560. 和为k的子数组

前缀和 + map求解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
def subarraySum(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int
"""
pre = 0
count = 0
mp = {0:1}
for val in nums:
pre += val
if pre - k in mp:
count += mp[pre-k]
if pre in mp:
mp[pre] += 1
else:
mp[pre] = 1
return count

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
class Solution(object):
def solveNQueens(self, n):
"""
:type n: int
:rtype: List[List[str]]
"""
res = []
arr = [['.']*n for _ in range(n)]

def is_vaild(arr,x,y):
if 'Q' in arr[x]:
return False
for i in range(len(arr)):
if arr[i][y] == 'Q':
return False
pox,poy = x,y
while 0 <= pox and 0 <= poy:
if arr[pox][poy] == 'Q':
return False
pox -= 1
poy -= 1
pox,poy = x,y
while pox < len(arr) and poy < len(arr[0]):
if arr[pox][poy] == 'Q':
return False
pox += 1
poy += 1
pox,poy = x,y
while 0 <= pox and poy < len(arr[0]):
if arr[pox][poy] == 'Q':
return False
pox -= 1
poy += 1
pox,poy = x,y
while pox < len(arr) and 0 <= poy:
if arr[pox][poy] == 'Q':
return False
pox += 1
poy -= 1
return True

def dfs(arr,row,res):
if row == len(arr):
tmp = []
for i in range(len(arr)):
tmp.append(''.join(arr[i]))
res.append(tmp[::])
return
for i in range(n):
if is_vaild(arr,row,i):
arr[row][i] = 'Q'
dfs(arr,row+1,res)
arr[row][i] = '.'
dfs(arr,0,res)
return res

盛最多水的容器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
def maxArea(self, height):
"""
:type height: List[int]
:rtype: int"""
if height == []:
return 0
left,right = 0,len(height) - 1
res = 0
while left < right:
res = max(res,(right-left)*min(height[right],height[left]))
if height[right] > height[left]:
left += 1
else:
right -= 1
return res

36. 二叉搜索树与双向链表

记录前驱节点,记录首节点

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 treeToDoublyList(self, root):
"""
:type root: Node
:rtype: Node
"""
self.pre = None
def dfs(cur):
if cur == None:
return
dfs(cur.left)
if self.pre:
self.pre.right = cur
cur.left = self.pre
else:
self.head = cur
self.pre = cur
dfs(cur.right)
if not root:
return None
dfs(root)
self.pre.right = self.head
self.head.left = self.pre
return self.head

51. 数组中的逆序对

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 reversePairs(self, nums):
"""
:type nums: List[int]
:rtype: int"""
self.ans = 0
def dfs(nums,left,right):
if right - left < 1:
return
mid = (left + right) // 2
dfs(nums,left,mid)
dfs(nums,mid + 1, right)
tmp = []
l = left
r = mid + 1
while l <= mid and r <= right:
if nums[l] > nums[r]:
self.ans += mid - l + 1
tmp.append(nums[r])
r += 1
else:
tmp.append(nums[l])
l += 1
if l <= mid:
tmp.extend(nums[l:mid+1])
elif r <= right:
tmp.extend(nums[r:right+1])
nums[left:right+1] = tmp
dfs(nums,0,len(nums)-1)
return self.ans

141.环形链表

使用快慢指针来求解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
def hasCycle(self, head):
"""
:type head: ListNode
:rtype: bool"""
if head == None:
return False
slow = head
fast = head.next
while slow and fast:
if slow == fast:
return True
slow = slow.next
fast = fast.next
if fast:
fast = fast.next
return False

142. 环形链表II

找到环形节点。

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 detectCycle(self, head):
"""
:type head: ListNode
:rtype: ListNode"""
if head == None:
return None
dummy = ListNode(-1)
dummy.next = head
slow = head
fast = head.next
while slow and fast:
if slow == fast:
break
slow = slow.next
fast = fast.next
if fast:
fast = fast.next
if slow == None or fast == None:
return None
# print(slow.val,fast.val)
fast = dummy
while slow != fast:
slow = slow.next
fast = fast.next
return slow

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
25
26
27
28
29
class Solution(object):
def isValid(self, s):
"""
:type s: str
:rtype: bool
"""
if s == '':
return True
stack = []
for val in s:
if val in '{[(':
stack.append(val)
else:
if stack == []:
return False
elif val == '}':
if stack.pop() != '{':
return False
elif val == ']':
if stack.pop() != '[':
return False
elif val == ')':
if stack.pop() != '(':
return False
else:
return False
if stack:
return False
return True

94. 中序遍历

递归,以及用队列模拟非递归。

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 inorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
cur = root
queue = []
ans = []
while cur or queue:
while cur:
queue.append(cur)
cur = cur.left
node = queue.pop()
ans.append(node.val)
cur = node.right
return ans

def dfs(root,res):
if root == None:
return
dfs(root.left,res)
res.append(root.val)
dfs(root.right,res)
res = []
dfs(root,res)
return res

123. 买股票的最佳时机III

仔细分析每一次状态转移。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
buy1,buy2 = -prices[0],-prices[0]
sell1,sell2 = 0,0
for i in range(1,len(prices)):
buy1 = max(buy1,-prices[i])
sell1 = max(sell1,buy1 + prices[i])
buy2 = max(buy2, sell1 - prices[i])
sell2 = max(sell2,buy2 + prices[i])
return sell2

88.合并两个有序数组

从后往前合并。

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 merge(self, nums1, m, nums2, n):
"""
:type nums1: List[int]
:type m: int
:type nums2: List[int]
:type n: int
:rtype: None Do not return anything, modify nums1 in-place instead.
"""
cur = m + n - 1
l1 = m - 1
l2 = n - 1
while l1 >=0 and l2 >= 0:
if nums1[l1] > nums2[l2]:
nums1[cur] = nums1[l1]
l1 -= 1
cur -= 1
else:
nums1[cur] = nums2[l2]
l2 -= 1
cur -= 1
if l2 >=0:
nums1[:cur+1] = nums2[:l2+1]

49. 字母异位词分解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
def groupAnagrams(self, strs):
"""
:type strs: List[str]
:rtype: List[List[str]]
"""
ans = []
dicts = {}
count = 0
for val in strs:
v_sort = ''.join(sorted(val))
if v_sort not in dicts:
dicts[v_sort] = count
count += 1
ans.append([val])
else:
ans[dicts[v_sort]].append(val)
return ans

29.顺时针打印

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(object):
def spiralOrder(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: List[int]
"""
if matrix == [] or matrix[0] == []:
return []
startx,starty = 0,0
endx,endy = len(matrix),len(matrix[0])
ans = []
while startx < endx and starty <endy:
for i in range(starty,endy):
ans.append(matrix[startx][i])
startx += 1
if startx >= endx:
break
for i in range(startx,endx):
ans.append(matrix[i][endy-1])
endy -= 1
if starty >= endy:
break
for i in range(starty,endy)[::-1]:
ans.append(matrix[endx-1][i])
endx -= 1
if startx >= endx:
break
for i in range(startx,endx)[::-1]:
ans.append(matrix[i][starty])
starty += 1
return ans

85. 最大矩阵

84题的升级版,在二维矩阵上计算最大面积。

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 maximalRectangle(self, matrix):
"""
:type matrix: List[List[str]]
:rtype: int
"""
def cal_area(heights):
stack = [-1]
res = 0
for i in range(len(heights)):
while len(stack) > 1 and heights[i] <= heights[stack[-1]]:
res = max(res,heights[stack.pop()] * (i - stack[-1] - 1))
stack.append(i)
while len(stack) > 1:
res = max(res, heights[stack.pop()]*(len(heights) - stack[-1] - 1))
return res

if matrix == [] or matrix[0] == []:
return 0
nums = [0] * len(matrix[0])
ans = 0
for val in matrix:
for i in range(len(val)):
if int(val[i]) == 0:
nums[i] = 0
else:
nums[i] += int(val[i])
ans = max(ans,cal_area(nums))
return ans

有效三角形的个数

三指针,先确定最大值,然后判断两边之和大于第三边的个数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
def triangleNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if nums == 0:
return 0
res = 0
nums = sorted(nums)
for right in range(2,len(nums)):
left = 0
cur = right - 1
while left < cur:
if nums[left] + nums[cur] > nums[right]:
res += cur - left
cur -= 1
else:
left += 1
return res

62.不同路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
def uniquePaths(self, m, n):
"""
:type m: int
:type n: int
:rtype: int
"""
dp = [[0]*n for _ in range(m)]
dp[0] = [1]*n
for i in range(m):
dp[i][0] = 1
for i in range(1,m):
for j in range(1,n):
dp[i][j] = dp[i-1][j] + dp[i][j-1]
return dp[-1][-1]

337. 打家劫舍

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
def rob(self, root):
"""
:type root: TreeNode
:rtype: int
"""
def dfs(root):
if root == None:
return 0,0
left = dfs(root.left)
right = dfs(root.right)
result = [0,0] # 不抢或抢
result[0] = max(left) + max(right)
result[1] = left[0] + right[0] + root.val
return result
return max(dfs(root))

1031. 两个非重叠子数组的最大和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
def maxSumTwoNoOverlap(self, nums, firstLen, secondLen):
"""
:type nums: List[int]
:type firstLen: int
:type secondLen: int
:rtype: int
"""
if nums == []:
return 0
for i in range(1,len(nums)):
nums[i] += nums[i-1]
res,lmax,mmax = nums[firstLen+secondLen-1],nums[firstLen-1],nums[secondLen-1]
for i in range(firstLen+secondLen,len(nums)):
lmax = max(lmax,nums[i-secondLen] - nums[i-firstLen-secondLen])
mmax = max(mmax, nums[i-firstLen] - nums[i-firstLen-secondLen])
res = max(res, max(lmax + nums[i] - nums[i-secondLen],mmax + nums[i] - nums[i-firstLen]))
return res

22. 括号生成

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
def generateParenthesis(self, n):
"""
:type n: int
:rtype: List[str]
"""
self.ans = []
def dfs(n,res,right):
if len(res) == n*2:
if right == 0:
self.ans.append(res[::])
return
if right > n or right < 0:
return
dfs(n,res + '(',right + 1)
dfs(n,res + ')',right - 1)
dfs(n,'',0)
return self.ans

224. 基本计算器

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 Solution(object):
def calculate(self, s):
"""
:type s: str
:rtype: int
"""
res = 0
flag = 1
stack = []
num = 0
for c in s:
if c.isdigit():
num = num*10 + int(c)
elif c == '+':
res += num*flag
num = 0
flag = 1
elif c == '-':
res += num*flag
num = 0
flag = -1
elif c == '(':
stack.append(res)
stack.append(flag)
flag = 1
res = 0
elif c == ')':
res += num*flag
num = 0
res = stack.pop()*res + stack.pop()
res += flag*num
return res

43. 字符串相乘

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 multiply(self, num1, num2):
"""
:type num1: str
:type num2: str
:rtype: str
"""
m = len(num1)
n = len(num2)
if num1 == '0' or num2 == '0':
return '0'
res = [0]*(n+m)
for i in range(m)[::-1]:
for j in range(n)[::-1]:
val = int(num1[i])*int(num2[j])
res[i+j+1] += val
for i in range(1,len(res))[::-1]:
res[i-1] += res[i] // 10
res[i] = res[i] % 10
res = ''.join([str(c) for c in res])
if res[0] == '0':
res = res[1:]
return res

662. 二叉树最大宽度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
def widthOfBinaryTree(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if root == None:
return 0
queue = [(root,0,0)]
cur_depth,left = 0,0
ans = 0
for node,depth,pos in queue:
if node:
queue.append((node.left,depth+1,2*pos+1))
queue.append((node.right,depth + 1,2*pos + 2))
if cur_depth != depth:
cur_depth = depth
left = pos
ans= max(ans,pos - left + 1)
return ans

73. 矩阵置零

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 setZeroes(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: None Do not return anything, modify matrix in-place instead.
"""
col = set()
row = set()
for i in range(len(matrix)):
for j in range(len(matrix[0])):
if matrix[i][j] == 0:
if i not in col:
col.add(i)
if j not in row:
row.add(j)
for cc in col:
for i in range(len(matrix[0])):
matrix[cc][i] = 0
for cc in row:
for i in range(len(matrix)):
matrix[i][cc] = 0

2. 两数相加

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(object):
def addTwoNumbers(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
if l1 == None or l2 == None:
return l1 if l1 else l2
step = 0
dummy = ListNode(-1)
cur = dummy
while l1 and l2:
val = l1.val + l2.val + step
step = val // 10
val = val % 10
node = ListNode(val)
cur.next = node
cur = cur.next
l1 = l1.next
l2 = l2.next
ll = l1 if l1 else l2
while ll:
val = step + ll.val
step = val // 10
val = val % 10
node = ListNode(val)
cur.next = node
cur = cur.next
ll = ll.next
if step != 0:
node = ListNode(step)
cur.next = node
return dummy.next

199. 二叉树右视图

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 rightSideView(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
if root == None:
return []
queue = [root]
# res = []
ans = []
level = 1
while queue:
node = queue.pop(0)
level -= 1
# res.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
if level == 0:
level = len(queue)
ans.append(node.val)
res = []
return ans

07. 重建二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def buildTree(self, preorder, inorder):
"""
:type preorder: List[int]
:type inorder: List[int]
:rtype: TreeNode"""
def dfs(preorder,inorder):
if preorder == [] or inorder == []:
return None
val = preorder[0]
index = inorder.index(val)
root = TreeNode(val)
root.left = dfs(preorder[1:index+1],inorder[:index])
root.right = dfs(preorder[index+1:],inorder[index+1:])
return root
return dfs(preorder,inorder)

04. 二维矩阵数组查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
def findNumberIn2DArray(self, matrix, target):
"""
:type matrix: List[List[int]]
:type target: int
:rtype: bool
"""
if matrix == [] or matrix[0] == []:
return False
x = len(matrix) - 1
y = 0
while x >= 0 and y < len(matrix[0]):
if matrix[x][y] == target:
return True
elif matrix[x][y] < target:
y += 1
else:
x -= 1
return False

445 II 两数相加

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
class Solution(object):
def addTwoNumbers(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
def convert(head):
if head == None or head.next == None:
return head
pre = head
cur = head.next
pre.next = None
while cur:
tmp = cur.next
cur.next = pre
pre = cur
cur = tmp
return pre
if l1 == None or l2 == None:
return None
l1 = convert(l1)
l2 = convert(l2)
step = 0
dummy = ListNode(-1)
cur = dummy
while l1 and l2:
val = l1.val + l2.val + step
step = val // 10
val = val % 10
node = ListNode(val)
cur.next =node
cur = cur.next
l1 = l1.next
l2 = l2.next
ll = l1 if l1 else l2
while ll:
val = ll.val + step
step = val // 10
val = val % 10
node = ListNode(val)
cur.next = node
cur = cur.next
ll = ll.next
if step != 0:
node = ListNode(step)
cur.next = node
return convert(dummy.next)

704. 二分法

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

146. LRU缓存

请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache 类:
LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中,则返回关键字的值,否则返回 -1 。
void put(int key, int value) 如果关键字 key 已经存在,则变更其数据值 value ;如果不存在,则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ,则应该 逐出 最久未使用的关键字。
函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
class LRUCache(object):

def __init__(self, capacity):
"""
:type capacity: int
"""
self.capacity = capacity
self.stack = {}
self.order = []


def get(self, key):
"""
:type key: int
:rtype: int
"""
if key not in self.stack:
return -1
else:
self.order.remove(key)
self.order.append(key)
return self.stack[key]


def put(self, key, value):
"""
:type key: int
:type value: int
:rtype: None
"""
if key in self.stack:
self.stack[key] = value
self.order.remove(key)
self.order.append(key)
else:
if len(self.order) == self.capacity:
val = self.order.pop(0)
del self.stack[val]
self.stack[key] = value
self.order.append(key)

class DLinkedNode:
def __init__(self, key=0, value=0):
self.key = key
self.value = value
self.prev = None
self.next = None

class LRUCache:

def __init__(self, capacity: int):
self.cache = dict()
# 使用伪头部和伪尾部节点
self.head = DLinkedNode()
self.tail = DLinkedNode()
self.head.next = self.tail
self.tail.prev = self.head
self.capacity = capacity
self.size = 0

def get(self, key: int) -> int:
if key not in self.cache:
return -1
# 如果 key 存在,先通过哈希表定位,再移到头部
node = self.cache[key]
self.moveToHead(node)
return node.value

def put(self, key: int, value: int) -> None:
if key not in self.cache:
# 如果 key 不存在,创建一个新的节点
node = DLinkedNode(key, value)
# 添加进哈希表
self.cache[key] = node
# 添加至双向链表的头部
self.addToHead(node)
self.size += 1
if self.size > self.capacity:
# 如果超出容量,删除双向链表的尾部节点
removed = self.removeTail()
# 删除哈希表中对应的项
self.cache.pop(removed.key)
self.size -= 1
else:
# 如果 key 存在,先通过哈希表定位,再修改 value,并移到头部
node = self.cache[key]
node.value = value
self.moveToHead(node)

def addToHead(self, node):
node.prev = self.head
node.next = self.head.next
self.head.next.prev = node
self.head.next = node

def removeNode(self, node):
node.prev.next = node.next
node.next.prev = node.prev

def moveToHead(self, node):
self.removeNode(node)
self.addToHead(node)

def removeTail(self):
node = self.tail.prev
self.removeNode(node)
return node

153. 寻找数组最小值

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(object):
def findMin(self, nums):
"""
:type nums: List[int]
:rtype: int"""
if nums == []:
return -1
left = 0
right = len(nums) - 1
while left < right:
mid = (left + right) >> 1
if nums[mid] > nums[right]:
left = mid + 1
else:
right = mid
return nums[left]
# 寻找最大值
class Solution(object):
def findMin(self, nums):
"""
:type nums: List[int]
:rtype: int"""
left = 0
right = len(nums) - 1
while left < right:
mid = (left + right) >> 1
if nums[mid] > nums[left]:
left = mid
else:
right = mid - 1
return nums[left]

122. 买卖股票最佳时期

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
if prices == []:
return 0
res = 0
top = prices[0]
for val in prices[1:]:
if val - top > 0:
res += val - top
top = val
return res

129. 根节点到叶子节点之和

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 sumNumbers(self, root):
"""
:type root: TreeNode
:rtype: int
"""
res = []
ans = []
def dfs(root,res):
if root == None:
return
elif root.left == None and root.right == None:
res.append(root.val)
ans.append(int(''.join([str(i) for i in res])))
res.pop()
return
dfs(root.left,res + [root.val])
dfs(root.right,res + [root.val])
dfs(root,res)
# print(ans)
return sum(ans)

179. 最大数

1
2
3
4
5
6
7
8
9
10
11
class Solution(object):
def largestNumber(self, nums):
"""
:type nums: List[int]
:rtype: str
"""
class compare(str):
def __lt__(x,y):
return x + y > y + x
res = ''.join(sorted(map(str,nums),key = compare))
return '0' if res[0] == '0' else res

48. 旋转数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
def rotate(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: None Do not return anything, modify matrix in-place instead.
"""
if matrix == [] or matrix[0] == []:
return matrix
begin = 0
end = len(matrix) - 1
while begin < end:
matrix[begin],matrix[end] = matrix[end],matrix[begin]
begin += 1
end -= 1
for i in range(len(matrix)):
for j in range(i+1,len(matrix[0])):
matrix[i][j],matrix[j][i] = matrix[j][i],matrix[i][j]
return matrix

415. 字符串相加

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 Solution(object):
def addStrings(self, num1, num2):
"""
:type num1: str
:type num2: str
:rtype: str
"""
if len(num2) > len(num1):
num1,num2 = num2,num1
cur = 0
res = ''
step = 0
num1 = num1[::-1]
num2 = num2[::-1]
while cur < len(num2):
val = int(num1[cur]) + int(num2[cur]) + step
step = val // 10
val = val % 10
res += str(val)
cur += 1
if step == 0:
res += num1[cur:]
else:
while cur < len(num1):
val = int(num1[cur]) + step
step = val // 10
val = val % 10
cur += 1
res += str(val)
if step == 1:
res += '1'
return res[::-1]

912. 排序数组

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
class Solution(object):
def sortArray(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
# 快排
def quick_sort(nums,left,right):
if left >= right:
return
index = random.randint(left, right)
nums[left],nums[index] = nums[index],nums[left]
pivot = nums[left]
l = left
r = right
while left < right:
while left < right and nums[right] >= pivot:
right -= 1
while left < right and nums[left] <= pivot:
left += 1
nums[left],nums[right] = nums[right],nums[left]
nums[l],nums[left] = nums[left],nums[l]
quick_sort(nums,l,left-1)
quick_sort(nums,left+1,r)
quick_sort(nums,0,len(nums)-1)
return nums
# 堆排序
def create_heap(nums,root_index,total_index):
c1 = root_index * 2 + 1
c2 = root_index * 2 + 2
max_index = root_index
if c1 <= total_index and nums[c1] > nums[max_index]:
max_index = c1
if c2 <= total_index and nums[c2] > nums[max_index]:
max_index = c2
if max_index != root_index:
nums[max_index],nums[root_index] = nums[root_index],nums[max_index]
create_heap(nums,max_index,total_index)

def sort_heap(nums):
n = len(nums) - 1
last_index = (n-1) // 2
for i in range(last_index + 1)[::-1]:
create_heap(nums,i,n)
sort_heap(nums)
for i in range(len(nums))[::-1]:
nums[0],nums[i] = nums[i],nums[0]
create_heap(nums,0,i-1)
return nums

110.平衡二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution(object):
def isBalanced(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
if root ==None:
return True
self.ans = True
def dfs(root):
if self.ans == False:
return 0
if root == None:
return 0
left = dfs(root.left)
right = dfs(root.right)
if abs(left - right) > 1:
self.ans = False
return 0
return max(left,right) + 1
dfs(root)
return self.ans

739. 每日温度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
def dailyTemperatures(self, T):
"""
:type T: List[int]
:rtype: List[int]
"""
if T == []:
return []
ans = [0]*len(T)
stack = []
for i in range(len(T)):
t = T[i]
while stack and t > T[stack[-1]]:
day = stack.pop()
ans[day] = i - day
stack.append(i)
return ans

207. 课程表

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
class Solution(object):
def canFinish(self, numCourses, prerequisites):
"""
:type numCourses: int
:type prerequisites: List[List[int]]
:rtype: bool
"""
if numCourses == 0:
return True
preccourse = {}
for course in prerequisites:
if course[1] not in preccourse:
preccourse[course[1]] = [course[0]]
else:
preccourse[course[1]].append(course[0])
visit = [0]*numCourses
self.vaild = True
def dfs(u):
visit[u] = 1
if u in preccourse:
for v in preccourse[u]:
if visit[v] == 0:
dfs(v)
if not self.vaild:
return
elif visit[v] == 1:
self.vaild = False
return
visit[u] = 2
for i in range(numCourses):
if self.vaild and visit[i] == 0:
dfs(i)
return self.vaild

45. 跳跃游戏II

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 jump(self, nums):
"""
:type nums: List[int]
:rtype: int"""
if len(nums) <= 1:
return 0
right = nums[0]
left = 0
new_right = right
res = 1
while left < len(nums):
if left < right:
left += 1
if left == len(nums)-1:
return res
new_right = max(new_right, left + nums[left])
else:
if right > new_right:
return -1
right = new_right
res += 1
return res

76. 最小覆盖子串

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 minWindow(self, s, t):
"""
:type s: str
:type t: str
:rtype: str
"""
if s == '' or t == '':
return ''
if len(t) > len(s):
return ''
window = {}
res = ''
for c in t:
window[c] = 0
upper = {}
for c in t:
if c not in upper:
upper[c] = 1
else:
upper[c] += 1
left = right = 0
count = 0
while right < len(s):
if s[right] in window:
window[s[right]] += 1
if window[s[right]] == upper[s[right]] or (upper[s[right]] > 1 and window[s[right]] < upper[s[right]]):
count += 1
while count >= len(t):
if res =='' or len(res) > right - left + 1:
res = s[left:right+1]
if s[left] in window:
window[s[left]] -= 1
if window[s[left]] < upper[s[left]]:
count -= 1
left += 1
right += 1

return res

169. 多数元素

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 Solution(object):
def majorityElement(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if nums == []:
return -1
count = 1
candidate = nums[0]
for val in nums[1:]:
if count == 0:
candidate = val
count +=1
else:
if val == candidate:
count += 1
else:
count -= 1
return candidate
## 随机生成上述数组
import random
res = []
val = random.randint(0,10)
res.extend([val] * (len(nums)//2+1))
rr = 0
for i in range(len(nums)//2):
rr = random.randint(0,10)
while rr == val:
rr = random.randint(0,10)
res.append(rr)
random.shuffle(res)

python中随机数的用法

1
2
3
4
5
6
7
import random
val = random.random() # 0.654567822
val = random.randint(0,10) # 8
random.choice('tomorrow') # r,随机取一个
random.uniform(1.1,5.4) # 2.2332123
random.randrange(1,100,2) # 55, 随机选一个,间隔为2,全是奇数
random.shuffle(a)

名词解释

1
优先队列:可以插入,快速查询或删除最大值(最小值),用堆来实现。

优先队列heapq方法

1
2
3
4
5
# heapq 支持最小堆,堆顶最小
heap = [5,1,7,3,9]
heapq.heapify(heap) # 将list构建成堆
heapq.heappush(heap,item) # 将item插入堆中
heapq.heappop(heap) # 删除堆顶元素

253. 会议室II

给你一个会议时间安排的数组 intervals ,每个会议时间都会包括开始和结束的时间 intervals[i] = [starti, endi] ,为避免会议冲突,同时要考虑充分利用会议室资源,请你计算至少需要多少间会议室,才能满足这些会议安排。

输入:intervals = [[0,30],[5,10],[15,20]]

输出:2

1
2
3
4
5
6
7
8
9
10
11
class Solution
def minMeetingRooms(self,intervals):
intervals.sort() # 开始时间排序
heap = []
ans = 0
for begin,end in intervals:
while heap and heap[-1] <= left:
heapq.heappop(heap)
heapq.heappush(heap,end)
ans = min(ans,len(heap))
return ans

56. 合并区间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
def merge(self, intervals):
"""
:type intervals: List[List[int]]
:rtype: List[List[int]]
"""
if intervals == []:
return []
ans = []
intervals.sort()
for left,right in intervals:
if ans != [] and ans[-1][-1] < left:
ans.append([left,max(ans[-1][-1],right)])
elif ans == []:
ans.append([left,right])
else:
ans[-1][-1] = max(ans[-1][-1],right)
return ans

零钱兑换

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
def coinChange(self, coins, amount):
"""
:type coins: List[int]
:type amount: int
:rtype: int
"""
if coins == []:
return 0
dp = [sys.maxsize]*(amount + 1)
dp[0] = 0
for coin in coins:
for i in range(coin,amount + 1):
dp[i] = min(dp[i],dp[i-coin] + 1)
return dp[-1] if dp[-1] != sys.maxsize else -1

523. 连续子数组和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
def checkSubarraySum(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: bool
"""
if len(nums) < 2:
return False
res = 0
m = {0:-1}
for i in range(len(nums)):
res = (res + nums[i]) % k
if res in m:
if i - m[res] >= 2:
return True
else:
m[res] = i
return False

151. 颠倒字符串中的单词

1
2
3
4
5
6
7
class Solution(object):
def reverseWords(self, s):
"""
:type s: str
:rtype: str
"""
return' '.join([val for val in s.strip().split(' ') if val != ''][::-1])

413. 等差数列划分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
def numberOfArithmeticSlices(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
n = len(nums)
if n < 2:
return 0
d,t = nums[1] - nums[0],0
ans = 0
for i in range(2,len(nums)):
if nums[i] - nums[i-1] == d:
t += 1
else:
d = nums[i] - nums[i-1]
t = 0
ans += t
return ans

32. 最长有效括号

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution(object):
def longestValidParentheses(self, s):
"""
:type s: str
:rtype: int
"""
if s == '':
return 0
dp = [0]*len(s)
for i in range(1,len(s)):
if s[i] == '(':
dp[i] = 0
else:
if s[i-1] == '(':
dp[i] = 2
if i-2 >= 0:
dp[i] += dp[i-2]
elif i - dp[i-1] - 1 >= 0 and s[i - dp[i-1] - 1] == '(':
dp[i] = dp[i-1] + 2
if i - dp[i-1] - 2 >= 0:
dp[i] += dp[i-dp[i-1]-2]
return max(dp)

5. 最长回文串

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 Solution(object):
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
if s == '':
return ''
ans = ''
res = ''
for i in range(len(s)):
# jishu
left = i
right = i
res = ''
while left >= 0 and right < len(s) and s[left] == s[right]:
left -= 1
right += 1
res = s[left+1:right]
if len(ans) < len(res):
ans = res
res = ''
# oushu
left = i-1
right = i
while left >= 0 and right < len(s) and s[left] == s[right]:
left -= 1
right += 1
res = s[left+1:right]
if len(ans) < len(res):
ans = res
return ans

786. 第k个最小素数分数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
def kthSmallestPrimeFraction(self, arr: List[int], k: int) -> List[int]:
n = len(arr)
left,right = 0.0,1.0
while True:
mid = (left + right) / 2
i, count = -1, 0
x,y = 0,1
for j in range(1,n):
while arr[i+1] / arr[j] < mid:
i += 1
if arr[i] * y > arr[j] * x:
x,y = arr[i],arr[j]
count += i + 1
if count == k:
return [x,y]
if count < k:
left = mid
else:
right = mid

42. 接雨水

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 trap(self, height):
"""
:type height: List[int]
:rtype: int"""
if height == []:
return 0
left = [0] * len(height)
right = [0] * len(height)
left[0] =height[0]
for i in range(1,len(height)):
left[i] = max(left[i-1],height[i])
right[-1] = height[-1]
for i in range(len(height)-1)[::-1]:
right[i] = max(right[i+1],height[i])
ans = 0
# print(left)
# print(right)
for i in range(len(height)):
ans += min(left[i],right[i]) - height[i]
return ans

440. 字典序的第k小数字

按照字典树的方式去遍历。

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 findKthNumber(self, n, k):
"""
:type n: int
:type k: int
:rtype: int
"""
def get_step(cur,n):
step,first,last = 0,cur,cur
while first <= n:
step += min(last,n) - first + 1
first *= 10
last = last * 10 + 9
return step
cur = 1
k -= 1
while k:
steps = get_step(cur,n)
if steps <= k:
k -= steps
cur += 1
else:
k -= 1
cur *= 10
return cur

632. 最小区间

使用优先队列来解,保持队列长度为n。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
def smallestRange(self, nums: List[List[int]]) -> List[int]:
from queue import PriorityQueue
q = PriorityQueue()
n = len(nums)
maxx = -sys.maxsize
for i in range(n):
q.put((nums[i][0],i,0))
maxx = max(maxx, nums[i][0])
begin,end = -sys.maxsize,sys.maxsize
while q.qsize() == n:
val,i,j = q.get()
if maxx - val < end - begin:
begin,end = val,maxx
if j+1 < len(nums[i]):
nv = nums[i][j+1]
q.put((nv,i,j+1))
maxx = max(nv,maxx)
return [begin,end]

优先队列

1
2
3
4
5
6
from queue import PriorityQueue
q = PriorityQueue()
q.put((val,i,j))
q.put()
q.empty()
q.qsize()

329. 矩阵中最长递增路径

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 longestIncreasingPath(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: int
"""
if matrix == [] or matrix[0] == []:
return 0
res = [[0]*len(matrix[0]) for _ in range(len(matrix))]
def dfs(res,matrix,pox,poy):
if res[pox][poy] != 0:
return res[pox][poy]
xh = [0,1,0,-1]
yh = [1,0,-1,0]
for i in range(4):
px = pox + xh[i]
py = poy + yh[i]
if 0 <= px < len(matrix) and 0 <= py < len(matrix[0]) and matrix[px][py] > matrix[pox][poy]:
res[pox][poy] = max(res[pox][poy], dfs(res,matrix,px,py))
res[pox][poy] += 1
return res[pox][poy]
ans = 0
for i in range(len(matrix)):
for j in range(len(matrix[0])):
ans = max(ans,dfs(res,matrix,i,j))
return ans

34. 在排序数组中查找元素的第一个和最后一个位置

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 searchRange(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
left = 0
right = len(nums) - 1
if nums == []:
return [-1,-1]
while left <= right:
mid = (left + right) >> 1
if nums[mid] == target:
break
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
if left > right:
return [-1,-1]
left = mid
right = mid
while left >= 0 and nums[left] == target:
left -= 1
while right < len(nums) and nums[right] == target:
right += 1
return [left+1,right-1]

42. 连续子数组最大和

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(object):
def maxSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
import sys
if nums == []:
return 0
dp = [-sys.maxsize] *len(nums)
cur = 0
for i in range(len(nums)):
if cur + nums[i] > 0:
cur = cur + nums[i]
dp[i] = cur
else:
cur = max(0,nums[i])
dp[i] = nums[i]
val = max(dp)
return val
#返回最大和所在数组
right = dp.index(val)
left = right
if val <= 0:
print(nums[left:right+1])
return max_val
while left >= 0:
if val > 0:
val -= nums[left]
left -= 1
else:
break
print(nums[left+1:right+1])
return max_val

135. 分发糖果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
def candy(self, ratings):
"""
:type ratings: List[int]
:rtype: int
"""
left = [1]*len(ratings)
right = [1]*len(ratings)
for i in range(1,len(ratings)):
if ratings[i] > ratings[i-1]:
left[i] = left[i-1] + 1
for i in range(len(ratings) - 1)[::-1]:
if ratings[i] > ratings[i+1]:
right[i] = right[i+1] + 1
ans = 0
for i in range(len(ratings)):
ans += max(left[i],right[i])
return ans
# 如果题目是连成一个环,那么找到最小的元素,一次向左和向右遍历,随后取max

113. 路径总和II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
def pathSum(self, root, targetSum):
"""
:type root: TreeNode
:type targetSum: int
:rtype: List[List[int]]
"""
if root == None:
return []
self.ans = []
def dfs(root,res,targetSum):
if root == None:
return
if targetSum == root.val and root.left == root.right == None:
self.ans.append(res + [root.val])
return
dfs(root.left,res + [root.val], targetSum - root.val)
dfs(root.right,res + [root.val], targetSum - root.val)
dfs(root,[],targetSum)
return self.ans

233. 数字1的个数

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
def countDigitOne(self, n):
"""
:type n: int
:rtype: int
"""
k, mulk = 0, 1
ans = 0
while n >= mulk:
ans += (n // (mulk * 10)) * mulk + min(max(n % (mulk * 10) - mulk + 1, 0), mulk)
k += 1
mulk *= 10
return ans

删掉字符串中所有相邻的重复项

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
def removeDuplicates(self, s):
"""
:type s: str
:rtype: str
"""
stack = []
for val in s:
if stack == []:
stack.append(val)
elif stack[-1] != val:
stack.append(val)
else:
stack.pop()
return ''.join(stack)

82. 删除排序链表中的重复元素

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 deleteDuplicates(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if head == None:
return head
dummy = ListNode(-1)
dummy.next = head
pre = dummy
cur = head
right = cur.next
while cur:
if right and cur.val == right.val:
while right and cur.val == right.val:
right = right.next
pre.next = right
cur = right
if right:
right = right.next
elif right and cur.val != right.val:
right = right.next
cur = cur.next
pre = pre.next
else:
break
return dummy.next

138. 复制带随机指针的链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
def copyRandomList(self, head):
"""
:type head: Node
:rtype: Node
"""
self.dicts = {}
def dfs(head):
if head == None:
return None
if head not in self.dicts:
newHead = Node(head.val,None,None)
self.dicts[head] = newHead
newHead.next = dfs(head.next)
newHead.random = dfs(head.random)
return self.dicts[head]
return dfs(head)

拼接最大数

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 maxNumber(self, nums1, nums2, k):
"""
:type nums1: List[int]
:type nums2: List[int]
:type k: int
:rtype: List[int]
"""
def pick(num,pick_k):
pop_n = len(num) - pick_k
res = []
for val in num:
while pop_n and res and val > res[-1]:
pop_n -= 1
res.pop()
res.append(val)
return res[:pick_k]
def merge(nums1,nums2):
res = []
while nums1 and nums2:
res.append(nums1.pop(0) if nums1 > nums2 else nums2.pop(0))
res.extend(nums1 or nums2)
return res
ans = 0
for i in range(k+1):
if i <= len(nums1) and k-i <= len(nums2):
ans = max(ans, merge(pick(nums1,i),pick(nums2,k-i)))
return ans

93. 复原ip地址

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 restoreIpAddresses(self, s):
"""
:type s: str
:rtype: List[str]
"""
ans = []
n = len(s)
def dfs(start,depth,res,s):
# print(start,depth,res)
if depth == 4:
res = res[:-1]
ans.append(res)
return
# minend表示剩下的数字段长度全为3,当前数字段最小开始的位置
minend = max(start + 1, n - (3 - depth) * 3)
# maxend表示剩下数字段长度为1,当前数字段最大结束的位置
maxend = min(start + 3, n - (3 - depth) * 1)
# print(minend,maxend)
for end in range(minend, maxend + 1):
split = s[start:end]
# print(split)
if len(split) > 1 and split[0] == '0':
break
if int(split) <= 255:
dfs(end, depth +1 ,res + split + '.', s)
dfs(0,0,'',s)
return ans

198. 打家劫舍

先确定前两个数,然后判断是否抢当前的家,如果要求计算路径的话,加上path。

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 rob(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if nums == []:
return 0
if len(nums) <= 2:
return max(nums)
dp = [0] *len(nums)
dp[0] = nums[0]
dp[1] = max(nums[0],nums[1])
for i in range(2,len(nums)):
dp[i] = max(nums[i] + dp[i-2], dp[i-1])
return dp[-1]

# 计算路径
if nums == []:
return 0
if len(nums) <= 2:
return max(nums)
path = ['']*len(nums)
dp = [0] *len(nums)
dp[0] = nums[0]
path[0] = '0'
dp[1] = max(nums[0],nums[1])
if dp[1] == nums[1]:
path[1] += str(1)
else:
path[1] += str(0)
for i in range(2,len(nums)):
dp[i] = max(nums[i] + dp[i-2], dp[i-1])
if dp[i] == dp[i-1]:
path[i] = path[i-1]
else:
path[i] = path[i-2] + str(i)
print(path[-1])
return dp[-1]

55. 跳跃游戏

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

78. 子集

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
def subsets(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
self.ans = []
def dfs(nums,pos,res):
self.ans.append(res)
for i in range(pos,len(nums)):
dfs(nums,i+1,res + [nums[i]])
dfs(nums,0,[])
return self.ans

18. 四数之和

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
class Solution(object):
def fourSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[List[int]]
"""
if len(nums) < 4:
return []
ans = []
n = len(nums)
nums = sorted(nums)
for i in range(n-3):
if i > 0 and nums[i] == nums[i-1]:
continue
if nums[i] + nums[i+1] + nums[i+2] + nums[i+3] > target:
break
if nums[i] + nums[n-3] + nums[n-2] + nums[n-1] < target:
continue
for j in range(i + 1,n - 2):
if j > i + 1 and nums[j] == nums[j-1]:
continue
if nums[i] + nums[j] + nums[j+1] + nums[j+2] > target:
break
if nums[i] + nums[j] + nums[n-1] + nums[n-2] < target:
continue
left,right = j + 1, n - 1
while left < right:
total = nums[i] + nums[j] + nums[left] + nums[right]
if total == target:
ans.append([nums[i], nums[j], nums[left], nums[right]])
while left < right and nums[left] == nums[left + 1]:
left += 1
left += 1
while left < right and nums[right] == nums[right - 1]:
right -= 1
right -= 1
elif total < target:
left += 1
else:
right -= 1
return ans

47. 全排列 II

给定一个可包含重复数字的序列 nums按任意顺序 返回所有不重复的全排列。

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 permuteUnique(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
if nums == []:
return []

self.ans = []
nums = sorted(nums)
def dfs(nums,res,visits):
if len(res) == len(nums):
self.ans.append(res)
return
for i in range(len(nums)):
if i > 0 and nums[i] == nums[i-1] and visits[i-1] == 0:
continue
if visits[i] == 0:
visits[i] = 1
dfs(nums,res + [nums[i]],visits)
visits[i] = 0
visits = [0] * len(nums)
dfs(nums,[],visits)
return self.ans

347. 前k高频元素

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
class Solution(object):
def topKFrequent(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: List[int]
"""
def create_heap(nums,root_index,n):
c1 = root_index * 2 + 1
c2 = root_index * 2 + 2
max_index = root_index
if c1 <= n and nums[max_index][1] < nums[c1][1]:
max_index = c1
if c2 <= n and nums[max_index][1] < nums[c2][1]:
max_index = c2
if max_index != root_index:
nums[max_index],nums[root_index] = nums[root_index],nums[max_index]
create_heap(nums,max_index,n)
def sort_heap(nums):
n = len(nums) - 1
last_index = (n-1) // 2
for i in range(last_index + 1)[::-1]:
create_heap(nums,i,n)
dicts = {}
for val in nums:
if val not in dicts:
dicts[val] = 1
else:
dicts[val] += 1
num_k = []
for key,val in dicts.items():
num_k.append([key,val])
sort_heap(num_k)
res = []
last = len(num_k) - 1
for i in range(k):
num_k[0],num_k[last] = num_k[last],num_k[0]
res.append(num_k[last][0])
create_heap(num_k,0,last - 1)
last -= 1
return res

145. 二叉树的后序遍历

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
class Solution(object):
def postorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
# 递归
self.res = []
def dfs(root):
if root == None:
return
dfs(root.left)
dfs(root.right)
self.res.append(root.val)
dfs(root)
return self.res
# 用栈,根右左,左右根
if root == None:
return []
res = []
stack = [root]
while stack:
node = stack.pop()
res.append(node.val)
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
return res[::-1]
# 遍历完左边,然后遍历右边
class Solution(object):
def postorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
if root == None:
return []
res = []
stack = []
prev = None
while root or stack != []:
while root:
stack.append(root)
root = root.left
root = stack[-1]
if root.right and root.right != prev:
root = root.right
else:
prev = stack.pop()
res.append(root.val)
root = None
return res

22. 链表中第k个节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
def getKthFromEnd(self, head, k):
"""
:type head: ListNode
:type k: int
:rtype: ListNode
"""
first = head
for _ in range(k):
first = first.next
second = head
while first != None:
second = second.next
first = first.next
return second

62. 圆圈中最后剩下的数字

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 lastRemaining(self, n, m):
"""
:type n: int
:type m: int
:rtype: int"""
# 模拟法,超时了
stack = [i for i in range(n)]
cur = 0
while len(stack) > 1:
lens = len(stack)
cur = (cur + m - 1) % lens
stack.pop(cur)
return stack[0]
# 数学规律反推法,从最后剩下的两个数字开始,规律为
# (当前位置 + m) % 上一轮长度
# 最后一轮是1,所以上一轮从2开始
ans = 0
for i in range(2, n+1):
ans = (ans + m) % i
return ans

227. 基本计算器

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 calculate(self, s):
"""
:type s: str
:rtype: int
"""
res = []
num = 0
presign = '+'
for idx,val in enumerate(s):
if val in '0123456789':
num = num * 10 + int(val)
if idx == len(s) - 1 or val in '+-*/':
if presign == '+':
res.append(num)
elif presign == '-':
res.append(-num)
elif presign == '*':
res.append(res.pop() * num)
else:
res.append(int(res.pop()*1.0 / num))
presign = val
num = 0
return sum(res)

718. 最长重复子数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
def findLength(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: int
"""
if nums1 == [] or nums2 == []:
return 0
ans = 0
dp = [[0]*(len(nums1) + 1) for _ in range(len(nums2) + 1)]
dp[0][0] = 0
for i in range(1, len(nums2) + 1):
for j in range(1, len(nums1) + 1):
if nums2[i-1] == nums1[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
ans = max(dp[i][j], ans)
return ans

518. 零钱兑换

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
def change(self, amount, coins):
"""
:type amount: int
:type coins: List[int]
:rtype: int
"""
if coins == []:
return 0
dp = [0] * (amount + 1)
dp[0] = 1
for coin in coins:
for i in range(coin,amount + 1):
dp[i] += dp[i - coin]
return dp[-1]

54. 二叉搜索树第k大节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def kthLargest(self, root, k):
"""
:type root: TreeNode
:type k: int
:rtype: int5"""
self.k = k
self.ans = root.val
def dfs(root):
if root == None:
return
dfs(root.right)
if self.k == 0:
return
self.k -= 1
if self.k == 0:
self.ans = root.val
dfs(root.left)
dfs(root)
return self.ans

160. 相交链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution(object):
def getIntersectionNode(self, headA, headB):
"""
:type head1, head1: ListNode
:rtype: ListNode
"""
p1 = headA
p2 = headB
count = 0
while True:
if p1 == p2:
return p1
p1 = p1.next
p2 = p2.next
if p1 == None:
p1 = headB
count += 1
if p2 == None:
p2 = headA
count += 1
if count >= 3:
return None

128. 最长连续序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
def longestConsecutive(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if len(nums) == 0:
return 0
nums_s = set(nums)
ans = 1
for val in nums_s:
if val + 1 not in nums_s:
lens = 1
while val - 1 in nums_s:
lens += 1
val -= 1
ans = max(ans, lens)
return ans

104. 二叉树最大深度

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
def maxDepth(self, root):
"""
:type root: TreeNode
:rtype: int
"""
def dfs(root):
if root == None:
return 0
left = dfs(root.left)
right = dfs(root.right)
return max(left,right) + 1
return dfs(root)

887. 鸡蛋掉落

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution(object):
def superEggDrop(self, K, N):
"""
:type K: int
:type N: int
:rtype: int
"""
if N == 1:
return 1
if K == 1:
return N
dp = [[0] * (K + 1) for _ in range(N + 1)] # K个蛋,最多扔N次
for i in range(1, K+1): # 只有一次机会,不论K(蛋)有几个,只要扔一次
dp[1][i] = 1
ans = -1
for i in range(2,N+1): # 机会次数
for j in range(1, K+1): # 蛋的个数
dp[i][j] = 1 + dp[i-1][j-1] + dp[i-1][j] # 蛋碎 + 蛋没碎
if dp[i][K] >= N:
ans = i
break
return ans

1008. 给定任意数组构造搜索二叉树

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 bstFromPreorder(self, preorder):
"""
:type preorder: List[int]
:rtype: TreeNode
"""
if preorder == []:
return None
root = TreeNode(preorder[0])

def insert(root,val):
if root.val > val:
if root.left == None:
root.left = TreeNode(val)
else:
insert(root.left,val)
else:
if root.right == None:
root.right = TreeNode(val)
else:
insert(root.right,val)
for i in range(1,len(preorder)):
insert(root,preorder[i])
return root

105. 从前序与中序遍历序列构造二叉树

同时也可以得到后续遍历的结果。

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 buildTree(self, preorder, inorder):
"""
:type preorder: List[int]
:type inorder: List[int]
:rtype: TreeNode
"""
if preorder == []:
return None
self.post = []
self.inorder = []
self.pre = []
def dfs(preorder,inorder):
if preorder == []:
return None
root = TreeNode(preorder[0])
index = inorder.index(preorder[0])
self.pre.append(root.val)
root.left = dfs(preorder[1:index+1],inorder[:index])
self.inorder.append(root.val)
root.right = dfs(preorder[index+1:],inorder[index+1:])
self.post.append(root.val) # 构造树的过程中,得到后续遍历
return root
res = dfs(preorder,inorder)
print(self.pre)
print(self.inorder)
print(self.post)
return res

101 .对称二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
def isSymmetric(self, root):
"""
:type root: TreeNode
:rtype: bool"""
if root == None:
return True
def dfs(A,B):
if A == None and B == None:
return True
if A == None or B == None:
return False
return (A.val == B.val) and dfs(A.left,B.right) and dfs(A.right,B.left)
return dfs(root.left,root.right)

234.回文链表

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
class Solution(object):
def isPalindrome(self, pHead):
# write code here
if pHead == None:
return True
first = pHead
second = pHead.next
if second == None:
return True
flag = 0
while second.next != None:
first = first.next
second = second.next
if second.next == None:
flag = 1
break
second = second.next
mid = first
left = mid
right = mid.next
cur = pHead
nex = cur.next
while cur != mid:
tmp = nex.next
nex.next = cur
cur = nex
nex = tmp
if flag == 1:
left = mid.next
while left and right:
if left.val != right.val:
return False
left = left.next
right = right.next
return True

tensorflow实现基本的类

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
import tensorflow as tf
def dense_layer(inputs):
dense1 = tf.keras.layers.Dense(256,activation = None,use_bias=False)(inputs)
ln1 = tf.keras.layers.LayerNormalization(axis=1)(dense1)
relu1 = tf.keras.PRelu()(ln1)
dense2 = tf.keras.layers.Dense(14,activation=None, use_bias=False)(relu1)
ln2 = tf.keras.layers.LayerNormalizaton(axis=1)(dense2)
return ln2

# 定义变量
import tensorflow as tf # tf2
import tensorflow.compat.v1 as tf1
w_init = tf.keras.initializers.TruncatedNormal(mean = 0.0, stddev = 0.1)
with tf1.variable_scope(name, reuse=tfv.AUTO_REUSE):
common_weight = tfv.get_variable('common_weight', [num], initializer=w_init, trainable=True, dtype=tf.float32)
# 调换channel
tensors= tf.transpose(X_0,perm=[0,2,1])

# reshape 操作
tf.reshape(tensors, shape = (-1, feature_dim, num_field, 1))
# 矩阵乘
Z_k_1 = tf.matmul(X_0,X_k)
# concat
all_input = tf.concat([ln1, cin_ln1], axis=-1)
# split
fm_feature_weights = tf.split(fm_feature_weight,[16, 16, 16], 2)
tf.reduce_sum(self.masked_loss, axis=1)
self.multitask_loss = tf.nn.sigmoid_cross_entropy_with_logits(labels=self.labels, logits=self.score)
tf.cast(self.inputs.labels, tf.float32)
self.masked_loss = tf.multiply(self.multitask_loss, self.labels_mask)

# 创建mlp layer
class MLP(tf.keras.layers.Layer):

def __init__(self,
num_units: int = None,
activation_func = None,
use_bias: bool = False,
name="mlp"):
super(MLP, self).__init__(name=name)
self.num_units = num_units
self.activation_func = activation_func
self.dense_layers = []
for i in range(0, len(self.num_units)):
self.dense_layers.append(tf.keras.layers.Dense(units=self.num_units[i], use_bias=use_bias, name="{}_dense_{}".format(name, i)))

def call(self, inputs):
transform_layers = [inputs]
for i, layer in enumerate(self.dense_layers):
next_layer = layer(transform_layers[-1])
if i != len(self.dense_layers) - 1:
if self.activation_func is not None:
next_layer = self.activation_func(next_layer)
transform_layers.append(next_layer)
return transform_layers[-1]

tf.tensordot

计算两个tensor,按照选中的aixs 进行相乘后相加。

tensordot(a, b,axes)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
a = np.arange(60.).reshape(3,4,5)
>>> b = np.arange(24.).reshape(4,3,2)
>>> c = np.tensordot(a,b, axes=([1,0],[0,1]))
>>> c.shape
(5, 2)
>>> c
array([[4400., 4730.],
[4532., 4874.],
[4664., 5018.],
[4796., 5162.],
[4928., 5306.]])
>>> # A slower but equivalent way of computing the same...
>>> d = np.zeros((5,2))
>>> for i in range(5):
... for j in range(2):
... for k in range(3):
... for n in range(4):
... d[i,j] += a[k,n,i] * b[n,k,j]
>>> c == d
array([[ True, True],
[ True, True],
[ True, True],
[ True, True],
[ True, True]])

115. 不同的子序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
def numDistinct(self, s, t):
"""
:type s: str
:type t: str
:rtype: int
"""
if len(s) < len(t):
return 0
dp = [[0] * (len(s)+1) for _ in range(len(t) + 1)]
for i in range(len(s)+1):
dp[-1][i] = 1
for i in range(len(t))[::-1]:
for j in range(len(s))[::-1]:
if t[i] == s[j]:
dp[i][j] = dp[i+1][j+1] + dp[i][j+1]
else:
dp[i][j] = dp[i][j+1]
# print(dp)
return dp[0][0]

112.路径总和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
def hasPathSum(self, root, sum):
"""
:type root: TreeNode
:type sum: int
:rtype: bool
"""
def dfs(root,sum):
if root == None:
return False
if sum - root.val == 0 and root.left == None and root.right==None:
return True
return dfs(root.left,sum - root.val) or dfs(root.right, sum - root.val)
if root == None:
return False
return dfs(root,sum)

109. 链表构建二叉搜索树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution(object):
def sortedListToBST(self, head):
"""
:type head: Optional[ListNode]
:rtype: Optional[TreeNode]
"""
if head == None:
return None
listnode = []
tmp = head
while tmp:
listnode.append(tmp.val)
tmp = tmp.next
def dfs(left,right,listnode):
if left > right:
return None
mid = (left + right) >> 1
root = TreeNode(listnode[mid])
root.left = dfs(left,mid - 1,listnode)
root.right = dfs(mid + 1,right,listnode)
return root
return dfs(0,len(listnode)- 1, listnode)

165.比较版本号

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution(object):
def compareVersion(self, version1, version2):
"""
:type version1: str
:type version2: str
:rtype: int
"""
list1 = [int(val) for val in version1.split('.')]
list2 = [int(val) for val in version2.split('.')]
flag = 1
if len(list1) > len(list2):
list1,list2 = list2,list1
flag = -1
for i in range(len(list1)):
if list1[i] > list2[i]:
return flag
elif list1[i] < list2[i]:
return flag * -1
for i in range(len(list1),len(list2)):
if list2[i] > 0:
return flag * -1
return 0

162. 寻找峰值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
def findPeakElement(self, nums):
"""
:type nums: List[int]
:rtype: int
二分,往高处走
"""
import sys
nums = [-sys.maxsize] + nums + [-sys.maxsize]
left = 0
right = len(nums)
while left < right:
mid = (left + right) >> 1
if nums[mid-1] < nums[mid] and nums[mid] > nums[mid+1]:
return mid - 1
if nums[mid-1] > nums[mid]:
right = mid
else:
left = mid

39.组合总数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution(object):
def combinationSum(self, candidates, target):
"""
:type candidates: List[int]
:type target: int
:rtype: List[List[int]]
"""
if candidates == []:
return []
candidates = sorted(candidates)
def dfs(candidates,target,res,pos,ans):
if target == 0:
if ans not in ans:
ans.append(res)
return
if target < candidates[0]:
return
for i in range(pos,len(candidates)):
dfs(candidates, target - candidates[i], res + [candidates[i]],i,ans)
ans = []
dfs(candidates,target,[],0,ans)
return ans

大数相加

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
def addStrings(self, num1, num2):
"""
:type num1: str
:type num2: str
:rtype: str
"""
max_len = max(len(num1),len(num2))
num1 = num1.zfill(max_len)
num2 = num2.zfill(max_len)
result = [0]* (max_len + 1)
for i in range(max_len)[::-1]:
tmp = int(num1[i]) + int(num2[i]) + result[i+1]
result[i+1] = tmp % 10
result[i] = tmp // 10
if result[0] == 0:
result = result[1:]
return ''.join(str(val) for val in result)

大数相乘

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution(object):
def multiply(self, num1, num2):
"""
:type num1: str
:type num2: str
:rtype: str
"""
if num1 == '0' or num2 == '0':
return '0'
n = len(num1)
m = len(num2)
res = [0]*(n+m)
for i in range(n):
for j in range(m):
res[i+j+1] += int(num1[i]) * int(num2[j])
for i in range(n+m)[::-1]:
res[i-1] += res[i] // 10
res[i] = res[i] % 10
index = 0
while res[index] == 0:
index += 1
return ''.join(str(val) for val in res[index:])

115. 最小栈

常数时间得到栈的最小值,用一个辅助单调栈来做。

543. 二叉树的直径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
def diameterOfBinaryTree(self, root):
"""
:type root: TreeNode
:rtype: int
"""
self.ans = 0
def dfs(root):
if root == None:
return 0
left = dfs(root.left)
right = dfs(root.right)
self.ans = max(self.ans,left + right + 1)
return max(left,right) + 1
dfs(root)
return self.ans - 1 if self.ans >= 0 else 0

圆环回到原点

圆环上有m个点,每次可以顺时针,逆时针走,走n步回到了0有多少种情况。

1
2
3
4
5
6
7
8
9
class Solution:
def backToOrigin(self,m,n):
dp = [[0] * m for _ n range(n + 1)]
dp[0][0] = 1
for i in range(1,n+1):
for j in range(m):
dp[i][j] = dp[i-1][(j-1+m)%m] + dp[i-1][(j+1+m)%m]
return dp[n][0]
# dp[i][j] 表示第i步,走到j点所需的步数。

958. 二叉树的完全性检验

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
def isCompleteTree(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
if root == None:
return True
nodes = [(root,1)]
i = 0
while i < len(nodes):
node,v = nodes[i]
i += 1
if node:
nodes.append((node.left,2*v))
nodes.append((node.right,2*v+1))
return nodes[-1][1] == len(nodes)

拓扑排序,课程表

课程有先后学习的问题,先导课必须先学,但是由于可能存在环,相互依赖。因此需要用拓扑排序进行判断。

  1. 选择图中入度为0的点
  2. 删掉该点,以及该点的边,对应节点的入度减1
  3. 重复上述,记录中间结果
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 findOrder(self, numC, pre):
"""
:type numCourses: int
:type prerequisites: List[List[int]]
:rtype: List[int]
"""
graph = [[] for _ in range(numC)] # 先修课:后修课
inedge = [0]*numC # 存储节点的入度
for C,preC in pre:
graph[preC].append(C)
inedge[C] += 1
queue = []
res = []
for idx, course in enumerate(inedge):
if course == 0:
queue.append(idx)
while queue:
t = queue.pop(0)
res.append(t)
for C in graph[t]:
inedge[C] -= 1
if inedge[C] == 0:
queue.append(C)
if len(res) == numC:
return res
else:
return []

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
28
29
30
31
32
33
34
class Solution(object):
def exist(self, board, word):
"""
:type board: List[List[str]]
:type word: str
:rtype: bool
"""
if word == '':
return True
if board == [] or board[0] == []:
return False
def dfs(board,visit,word,pox,poy):
if word == '':
return True
xh = [0,1,0,-1]
yh = [1,0,-1,0]
for k in range(4):
x = pox + xh[k]
y = poy + yh[k]
if 0<= x < len(board) and 0<=y<len(board[0]) and visit[x][y] == 0 and board[x][y] == word[0]:
visit[x][y] = 1
if dfs(board,visit,word[1:],x,y):
return True
visit[x][y] = 0
return False
visit = [[0] * len(board[0]) for _ in range(len(board))]
for i in range(len(board)):
for j in range(len(board[0])):
if board[i][j] == word[0]:
visit[i][j] = 1
if dfs(board,visit,word[1:],i,j):
return True
visit[i][j] = 0
return False

402. 移掉k位数字

单调栈,维持栈递增。

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 removeKdigits(self, num, k):
"""
:type num: str
:type k: int
:rtype: str
"""
if len(num) <= k:
return '0'
stack = []
for val in num:
if stack == []:
stack.append(val)
else:
while stack and val < stack[-1] and k > 0:
stack.pop()
k -= 1
stack.append(val)
while k > 0:
stack.pop()
k -= 1
while stack and stack[0] == '0':
stack.pop(0)
return '0' if stack == [] else ''.join(stack)

321. 戳气球

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
def maxCoins(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
nums = [1] + nums + [1]
dp = [[0] * len(nums) for _ in range(len(nums))]
for i in range(len(nums))[::-1]:
for j in range(i+1,len(nums)):
for k in range(i+1,j):
dp[i][j] = max(dp[i][j],dp[i][k] + dp[k][j] + nums[i]*nums[k]*nums[j])
return dp[0][-1]

8. 字符串转整数

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 myAtoi(self, str):
"""
:type str: str
:rtype: int
"""
str = str.strip()
res = ''
for idx,ch in enumerate(str):
if ch in '-+' and idx == 0:
res += ch
elif '0' <= ch <= '9':
res += ch
else:
break
if res == '':
return 0
if len(res) == 1 and res in '-+':
return 0
import sys
if int(res) < -2**31:
return -2**31
if int(res) > 2**31 - 1:
return 2**31 - 1
return int(res)

226.翻转二叉树

1
2
3
4
5
6
7
8
9
10
11
12
class Solution(object):
def invertTree(self, root):
"""
:type root: TreeNode
:rtype: TreeNode
"""
if root == None:
return root
node = TreeNode(root.val)
node.left = self.invertTree(root.right)
node.right = self.invertTree(root.left)
return node

83. 删除重复元素

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

114. 二叉树展开为链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
def flatten(self, root):
"""
:type root: TreeNode
:rtype: None Do not return anything, modify root in-place instead.
"""
while root:
if root.left == None:
root = root.right
else:
pre = root.left
while pre.right != None:
pre = pre.right
pre.right = root.right
root.right = root.left
root.left = None
root = root.right

230. 二叉搜索树中第k小的元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
def kthSmallest(self, root, k):
"""
:type root: TreeNode
:type k: int
:rtype: int
"""
res = []
def dfs(root,res):
if root==None:
return
dfs(root.left,res)
res.append(root.val)
dfs(root.right,res)
dfs(root,res)
return res[k-1]

24. 两两交换链表的节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution(object):
def swapPairs(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if head == None:
return head
dummy = ListNode(-1)
dummy.next = head
first = dummy
second = head
while second != None:
last = second.next
if last == None:
break
first.next = last
second.next = last.next
last.next = second
first = second
second = second.next
return dummy.next

283. 移动零

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
def moveZeroes(self, nums):
"""
:type nums: List[int]
:rtype: None Do not return anything, modify nums in-place instead.
"""
if nums == []:
return
cur = 0
right = 0
while right < len(nums):
if nums[right] != 0:
nums[cur] = nums[right]
cur += 1
right += 1
else:
right += 1
while cur < len(nums):
nums[cur] = 0
cur += 1

468. 验证IP地址

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 Solution(object):
def validIPAddress(self, queryIP):
"""
:type queryIP: str
:rtype: str
"""
def isIPV4(queryIP):
IPList = queryIP.split('.')
if len(IPList) != 4:
return False
for val in IPList:
try:
if str(int(val)) != val:
return False
except:
return False
if not(0 <= int(val) <= 255):
return False
return True

if isIPV4(queryIP):
return 'IPv4'

def isIPV6(queryIP):
IPList = queryIP.split(':')
if len(IPList) != 8:
return False
for val in IPList:
if not( 1<=len(val)<=4):
return False
for c in val:
if c not in '1234567890abcdefABCDEF':
return False
return True
if isIPV6(queryIP):
return 'IPv6'
return 'Neither'

498.对角线遍历

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(object):
def findDiagonalOrder(self, mat):
"""
:type mat: List[List[int]]
:rtype: List[int]
"""
if mat == []:
return []
res = []
lenx = len(mat)
leny = len(mat[0])
total = 0
while total < lenx + leny:
# 1,3,5,7...
x = total if total < lenx else lenx - 1
y = total - x
while 0 <= x < lenx and 0 <= y < leny:
res.append(mat[x][y])
x -= 1
y += 1
total += 1
if total >= lenx + leny:
return res
y = total if total < leny else leny - 1
x = total - y
while 0 <= x < lenx and 0 <= y < leny:
res.append(mat[x][y])
x += 1
y -= 1
total += 1
return res

144. 二叉树前序遍历

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 preorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
self.res = []
def dfs(root):
if root == None:
return
self.res.append(root.val)
dfs(root.left)
dfs(root.right)
dfs(root)
return self.res
# 迭代法
if root == None:
return []
res = []
queue = []
cur = root
while queue or cur:
while cur:
queue.append(cur)
res.append(cur.val)
cur = cur.left
cur = queue.pop()
cur = cur.right
return res

14. 最长公共前缀

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
def longestCommonPrefix(self, strs):
"""
:type strs: List[str]
:rtype: str
"""
if strs == []:
return ''
common = strs[0]
for val in strs[1:]:
common = common[:len(val)]
for i in range(len(val)):
if i >= len(common):
break
if common[i] != val[i]:
common = common[:i]
break
return common

16. 最接近的三数之和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution(object):
def threeSumClosest(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
nums.sort()
import sys
ans = sys.maxsize
for idx,val in enumerate(nums):
left = idx + 1
right = len(nums) - 1
while left < right:
tmp = nums[left] + nums[right] + val
if abs(tmp - target) < abs(ans - target):
ans = tmp
if tmp - target > 0:
right -= 1
else:
left += 1
return ans

74. 搜索二维矩阵

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
class Solution(object):
def searchMatrix(self, matrix, target):
"""
:type matrix: List[List[int]]
:type target: int
:rtype: bool
"""
if matrix == []:
return False

left = 0
right = len(matrix) - 1
while left < right:
mid = (left + right) >> 1
if matrix[mid][0] > target:
right = mid - 1
else:
left = mid
if left + 1 == right:
if matrix[right][0] > target:
right -= 1
else:
left += 1
row = left
left = 0
right = len(matrix[0]) - 1
while left <= right:
mid = (left + right) >> 1
if matrix[row][mid] == target:
return True
if matrix[row][mid] > target:
right = mid - 1
else:
left = mid + 1
return False

862. 和至少为k的最短子数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
def shortestSubarray(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int
"""
queue = [0]
for val in nums:
queue.append(queue[-1] + val)
indexs = []
ans = len(nums) + 1
for idx, sums in enumerate(queue):
while indexs != [] and sums <= queue[indexs[-1]]:
indexs.pop()
while indexs != [] and sums - queue[indexs[0]]>=k:
ans = min(ans,idx - indexs[0])
indexs.pop(0)
indexs.append(idx)
return ans if ans <= len(nums) else -1

40. 组合总数 II

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 combinationSum2(self, candidates, target):
"""
:type candidates: List[int]
:type target: int
:rtype: List[List[int]]
"""
if candidates == []:
return []
candidates.sort()
def dfs(candidates,target,pos,res,ans):
if target == 0:
if res not in ans:
ans.append(res)
return
for i in range(pos,len(candidates)):
if i > pos and candidates[i] == candidates[i-1]:
continue
if target >= candidates[i]:
dfs(candidates,target-candidates[i],i+1,res + [candidates[i]],ans)
else:
break
ans = []
dfs(candidates,target,0,[],ans)
return ans

26. 树的子结构

子结构,可以只是树的一部分,子树要求到叶子。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
def isSubStructure(self, A, B):
"""
:type A: TreeNode
:type B: TreeNode
:rtype: bool
"""
if A == None or B == None:
return False
def dfs(A,B):
if B == None:
return True
if A == None:
return False
return A.val == B.val and dfs(A.left,B.left) and dfs(A.right,B.right)
return dfs(A,B) or self.isSubStructure(A.left,B) or self.isSubStructure(A.right,B)

61. 旋转链表

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 rotateRight(self, head, k):
"""
:type head: ListNode
:type k: int
:rtype: ListNode
"""
if head == None:
return head
n = 0
tmp = head
while tmp:
if tmp.next == None:
tail = tmp
tmp = tmp.next
n += 1
k %= n
if k == 0:
return head
k = n - k
tmp = head
tail.next = head
for _ in range(k-1):
tmp = tmp.next
new_head = tmp.next
tmp.next = None
return new_head

27.二叉树镜像

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
def mirrorTree(self, root):
"""
:type root: TreeNode
:rtype: TreeNode
"""
if root == None:
return None
def dfs(root):
if root== None:
return None
dfs(root.left)
dfs(root.right)
root.left,root.right = root.right,root.left
dfs(root)
return root

59. 旋转矩阵II

给你一个正整数 n ,生成一个包含 1n2 所有元素,且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix

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 Solution(object):
def generateMatrix(self, n):
"""
:type n: int
:rtype: List[List[int]]
"""
if n == 0:
return []
matrix = [[0] * n for _ in range(n)]
pox,poy = 0,0
lenx,leny = n-1,n-1
value = 1
while pox <= lenx and poy <= leny:
for i in range(poy,leny+1):
matrix[pox][i] = value
value += 1
pox += 1
if pox > lenx:
return matrix
for i in range(pox,lenx+1):
matrix[i][leny] = value
value += 1
leny -= 1
if poy > leny:
return matrix
for i in range(poy,leny+1)[::-1]:
matrix[lenx][i] = value
value += 1
lenx -= 1
if pox > lenx:
return matrix
for i in range(pox,lenx+1)[::-1]:
matrix[i][poy] = value
value += 1
poy += 1
return matrix

21. 调整数组顺序使奇数在偶数前

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

71. 简化路径

化简linux路径。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
def simplifyPath(self, path):
"""
:type path: str
:rtype: str
"""
if path == '':
return ''
res = path.split('/')
ans = []
for val in res:
if val == '.' or len(val) == 0:
continue
elif val =='..':
if ans != []:
ans.pop()
else:
ans.append(val)
return '/' + '/'.join(ans)

556.下一个更大的元素

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 nextGreaterElement(self, n):
"""
:type n: int
:rtype: int
"""
if 0 <= n < 10:
return -1
strs = str(n)
nums = [c for c in strs]
pos = len(nums) - 2
while pos >= 0 and nums[pos] >= nums[pos + 1]:
pos -= 1
if pos < 0:
return -1
left = pos + 1
right = len(nums) - 1
for i in range(left,right + 1)[::-1]:
if nums[pos] < nums[i]:
nums[pos],nums[i] = nums[i],nums[pos]
break
left = pos + 1
right = len(nums) - 1
while left < right:
nums[left],nums[right] = nums[right],nums[left]
left += 1
right -= 1
res = int(''.join(nums))
return res if res <= 2**31-1 else -1

670. 最大交换

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution(object):
def maximumSwap(self, num):
"""
:type num: int
:rtype: int
"""
str_num = [val for val in str(num)]
sort_num = sorted(str_num)[::-1]
small = ''
big = ''
for i in range(len(str_num)):
if str_num[i] != sort_num[i]:
small = str_num[i]
big = sort_num[i]
str_num[i] = big
break
if small != '':
for i in range(len(str_num))[::-1]:
if str_num[i] == big:
str_num[i] = small
break
return int(''.join(str_num))

38. 字符串全排列

输入一个字符串,打印出该字符串中字符的所有排列。你可以以任意顺序返回这个字符串数组,但里面不能有重复元素

输入:s = “abc”
输出:[“abc”,”acb”,”bac”,”bca”,”cab”,”cba”]

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 permutation(self, s):
"""
:type s: str
:rtype: List[str]
"""
if s == []:
return []

def dfs(s,ans,res,visit):
if len(res) == len(s):
if res not in ans:
ans.append(res)
return
for i in range(len(s)):
if visit[i] == 0:
visit[i] = 1
dfs(s,ans,res+s[i],visit)
visit[i] = 0
ans = []
visit = [0]*len(s)
dfs(s,ans,'',visit)
return ans

股票问题

核心思想是最大化手上的钱,当前的买卖行为至于前一次买卖行为有关。

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
class Solution:
# 只考虑手中的钱最多,买相当于减,卖相当于加,这一次是买还是卖只与上一次是买还是卖有关
# 整体属于dp思想,对于第i价格,利润与之前价格都有关系,所以需要buy = max(buy, ?),sell = max(sell, ?)
# 即dp滚动数组思想,这意味着,我们每天(第i天为结尾)都在买卖(dp就是循环推导)
def maxProfit(self, prices: List[int]) -> int:
# def maxProfit(self, k: int, prices: List[int]) -> int:
# def maxProfit(self, prices: List[int], fee: int) -> int:

# 买卖一次
buy, sell = -float('inf'), 0 # buy一定初始化为无穷小,因为第一次买看成手中钱减少(是个负数),sell初始化小于等于0
for p in prices:
buy = max(buy, 0-p) # 由于只能买一次,买之前手里只有0元,买之后手里有max(buy, 0-p)
sell = max(sell, buy+p) # 卖之前一定是买buy,卖完手里有max(sell, buy+p)
return sell

# 不限制买卖次数
buy, sell = -float('inf'), 0
for p in prices:
buy = max(buy, sell-p) # 由于不限制交易次数,买之前可能是卖过手里的钱sell,买之后max(buy, sell-p)
sell = max(sell, buy+p) # 卖之前一定是买buy,卖完手里有max(sell, buy+p)
return sell

# 买卖两次
buy1, sell1, buy2, sell2 = -float('inf'), 0, -float('inf'), 0
for p in prices:
buy1 = max(buy1, 0-p)
sell1 = max(sell1, buy1+p)
buy2 = max(buy2, sell1-p)
sell2 = max(sell2, buy2+p) # 整体而言,这次操作只与上一次有关
return sell2

# 买卖k次
buy = [-float('inf')] * (k+1)
sell = [0] * (k+1) # 初始化为k+1,是因为第一次买,是0-p,这里我们sell[0]=0,就可以了
for p in prices:
for k in range(1, k+1):
buy[k] = max(buy[k], sell[k-1]-p) # 第一次sell[i-1]=sell[0]=0
sell[k] = max(sell[k], buy[k]+p)
return sell[-1]

# 不限制买卖次数,冻结期为1天
buy, sell_pre, sell_now = -float('inf'), 0, 0
# # 冻结期为1天,意味着,我们买的上一个状态不能是上一次卖的,而是上上次卖的
# # 至此,要理解,这是dp滚动数组思想,这意味着,我们每天都在买卖
for p in prices:
buy = max(buy, sell_pre-p) # 这次买的是接着上上次卖的,可以理解为buy[i]与sell[j-1]有关,而不是sell[j]
sell_pre = sell_now # 因为后面要更新sell_now,这里要先保存,buy[i-1]的记录
sell_now = max(sell_now, buy+p)
return sell_now

# 不限制买卖次数,但是有手续费
buy, sell = -float('inf'), 0
for p in prices:
buy = max(buy, sell-fee-p) # 多减去手续费即可
sell = max(sell, buy+p)
return sell

572. 另一棵树的子树

给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在,返回 true ;否则,返回 false 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
def isSubtree(self, root, subRoot):
"""
:type root: TreeNode
:type subRoot: TreeNode
:rtype: bool
"""
if subRoot == None and root == None:
return True
elif subRoot == None or root == None:
return False
def dfs(root,subRoot):
if root == subRoot == None:
return True
if root == None or subRoot == None:
return False
return root.val == subRoot.val and dfs(root.left,subRoot.left) and dfs(root.right,subRoot.right)

return dfs(root,subRoot) or self.isSubtree(root.left,subRoot) or self.isSubtree(root.right,subRoot)

34.二叉树中和为某一值的路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
def pathSum(self, root, s):
"""
:type root: TreeNode
:type sum: int
:rtype: List[List[int]]
"""
if root == None:
return []
def dfs(root,s,res,ans):
if root == None:
return
if s == root.val and root.left == None and root.right == None:
ans.append(res + [root.val])
return
dfs(root.left,s-root.val,res + [root.val],ans)
dfs(root.right,s-root.val,res + [root.val],ans)
ans = []
dfs(root,s,[],ans)
return ans

75. 颜色分类

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。

我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

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 sortColors(self, nums):
"""
:type nums: List[int]
:rtype: None Do not return anything, modify nums in-place instead.
"""
if nums == []:
return nums
left = 0
right = len(nums) - 1
i = 0
while i <= right:
if nums[i] == 0:
nums[i],nums[left] = nums[left],nums[i]
i += 1
left += 1
elif nums[i] == 1:
i += 1
continue
else:
nums[i],nums[right] = nums[right],nums[i]
right -= 1
return nums

10. 匹配正则表达式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution(object):
def isMatch(self, s, p):
"""
:type s: str
:type p: str
:rtype: bool
"""
dp = [[0]*(len(s)+1) for _ in range(len(p) + 1)]
dp[0][0] = 1
for i in range(2,len(p)+1):
if p[i-1] == '*':
dp[i][0] = dp[i-2][0]
for i in range(1,len(p) + 1):
for j in range(1,len(s) + 1):
if p[i-1] == s[j-1] or p[i-1] == '.':
dp[i][j] = dp[i-1][j-1]
elif i>1 and p[i-1] == '*':
if p[i-2] == s[j-1] or p[i-2] == '.':
dp[i][j] = dp[i][j-1]
if dp[i-2][j]:
dp[i][j] = dp[i-2][j]
return False if dp[-1][-1] == 0 else True

503. 下一个更大的元素

给定一个循环数组 nums ( nums[nums.length - 1] 的下一个元素是 nums[0] ),返回 nums 中每个元素的 下一个更大元素 。

数字 x下一个更大的元素 是按数组遍历顺序,这个数字之后的第一个比它更大的数,这意味着你应该循环地搜索它的下一个更大的数。如果不存在,则输出 -1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
def nextGreaterElements(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
stack = []
N = len(nums)
res = [-1]*N
for i in range(2*N):
while stack and nums[stack[-1]] < nums[i % N]:
res[stack.pop()] = nums[i%N]
stack.append(i%N)
return res

91.解码方法

将数字转成字母,有几种转法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
def numDecodings(self, s):
"""
:type s: str
:rtype: int
"""
if s == '':
return 0
if s[0] == '0':
return 0
dp = [0] * (len(s) + 1)
dp[0] = 1
dp[1] = 1
for i in range(2,len(s) + 1):
if s[i-1] !='0':
dp[i] += dp[i-1]
if s[i-2] != '0' and int(s[i-2:i]) <= 26:
dp[i] += dp[i-2]
return dp[-1]

136. 只出现过一次的数字

1
2
3
4
5
6
7
8
9
10
class Solution(object):
def singleNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
res = 0
for val in nums:
res ^= val
return res

冒泡排序

主要思想是一个二层循环将大的气泡升到右边。外循环选中一个值,将这个值与其右边的元素依次进行比较,交换,最终找到合适的位置,对所有的外围元素均比较一遍,得到结果。

$O(n^2)$ 的复杂度,稳定的排序(相同元素保持顺序)。

1
2
3
4
5
6
def maopao(nums):
for i in range(len(nums)):
for j in range(i+1,len(nums)):
if nums[i] > nums[j]:
nums[i],nums[j] = nums[j],nums[i]
return nums

快速排序

主要思想是,先选中一个pivot,右左逼近的方式找到这个元素所属的位置,该位置左的元素都比它小,右边的元素都比它大,然后将左右两个子数组进行递归排序,直到完成数组的排序。

不稳定的排序,时间复杂度为$O(nlogn)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def paixu(nums,left,right):
if left > right:
return
low = left
high = right
pivot = nums[low]
while left <right:
while left < right and nums[right] > pivot:
right -= 1
while left < right and nums[left] <= pivot:
left -= 1
nums[left],nums[right] = nums[right],nums[left]
nums[low] = nums[left]
nums[left] = pivot
paixu(nums,0,left - 1)
paixu(nums,left+1,high)

选择排序

每次选择剩余数组中最小的,放到左边。

不稳定的排序,时间复杂度为$O(n^2)$

1
2
3
4
5
6
def xuanzhepaixu(nums):
for i in range(len(nums)):
for j in range(i+1,len(nums)):
if nums[i] > nums[j]:
nums[i],nums[j] = nums[j],nums[i]
return nums

插入排序

以外循环为核心,对于i -> i-1的元素,对i依次进行比较后交换。

稳定排序,内排序,时间复杂度:$O(n^2)$

1
2
3
4
5
6
7
def charu(nums):
for i in range(1,len(nums)):
while i > 0 and nums[i] < nums[i-1]:
nums[i],nums[i-1] = nums[i-1],nums[i]
i -= 1
return nums
return charu(nums)

归并排序

将数组平均拆分,然后对左、右数组分别进行排序,然后融合。递归的出口是,当数组长度为1的时候,不需要排序了,可以直接返回。

稳定的排序,时间复杂度为$O(nlogn)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def merge_sort(nums):
if len(nums) == 1:
return nums
mid = len(nums) // 2
left = merge_sort(nums[:mid])
right = merge_sort(nums[mid:])
return merge(left,right)
def merge(left,right):
res = []
i = 0
j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
res.append(left[i])
i += 1
else:
res.append(right[j])
j += 1
res += left[i:]
res += right[j:]
return res
return merge_sort(nums)

堆排序

将数组按照堆的方式进行存储,根据二叉树特有的,i节点,左孩子2i+1,右孩子2i+2这种方式,构建完全二叉树。然后从最后一个元素开始,构造大顶堆,堆顶在第0个元素位置。然后将堆顶和数组最后一个元素,交换之后,从堆顶开始,重新构造。

  1. 构造大根堆,即根节点大于左右节点
    1. 完全二叉树节点i(从0开始),左节点2i+1,右节点2i+2
    2. 从叶子节点向上遍历,从节点n开始,根节点为(n-1)// 2到0,调换位置形成大根,将调换位置的节点,重新传入,再次与其子树形成大根
    3. 构造完之后,nums[0]为最大原始,找出topk,即将nums[0]与数组最后一个元素交换,对nums[0]重新构造大根,得到去掉最大值子树的大根,即第二大值,与nums[-2]交换,知道topk位置。

不稳定排序,复杂度:$O(nlogn)$.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def create_heap(nums,n,root):
left = 2*root + 1
right = 2*root + 2
max_index = root
if left <= n and nums[left] > nums[root]:
max_index = left
if right <= n and nums[right] > nums[max_index]:
max_index = right
if max_index != root:
nums[max_index],nums[root] = nums[root],nums[max_index]
create_heap(nums,n,max_index)

def heap_sort(nums):
if nums==[]:
return nums
n = len(nums) - 1
last_index = (n-1)//2
for i in range(last_index+1)[::-1]:
create_heap(nums,n,i)
heap_sort(nums)
for i in range(1,len(nums))[::-1]:
nums[0],nums[i] = nums[i],nums[0]
create_heap(nums,i-1,0)
return nums

AUC计算

AUC在概率上的解释是任取一对正负样本,正样本的预测值大于负样本的预测值的概率。

因此计算过程就是将从label中分别取出正负样本,然后对正负样本两两组合,计算正样本概率大于负样本概率的个数,然后除以总的组合数,即得到AUC的值。

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
def calculate(label,predict):
# label = [0, 0, 0, 0, 1, 1, 1, 1, 1, 1]
# pred = [0.1, 0.4, 0.5 ,0.6, 0.35, 0.8, 0.9, 0.4, 0.25, 0.5]
pos = sum(label)
neg = len(label) - pos
pos_pro = []
neg_pro = []
for idx, val in enumerate(label):
if val == 1:
pos_pro.append(predict[idx])
else:
neg_pro.append(predict[idx])
num = 0
for pos_ in pos_pro:
for neg_ in neg_pro:
if pos_ > neg_:
num += 1
elif pos_ == neg_:
num += 0.5
return num / (pos*neg*1.0)

label = [0, 0, 0, 0, 1, 1, 1, 1, 1, 1]
pred = [0.1, 0.4, 0.5 ,0.6, 0.35, 0.8, 0.9, 0.4, 0.25, 0.5]
result = calculate(label,pred)
print(result)

7.整数翻转

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
def reverse(self, x: int) -> int:
INT_MIN, INT_MAX = -2**31, 2**31 - 1

rev = 0
while x != 0:
# INT_MIN 也是一个负数,不能写成 rev < INT_MIN // 10
if rev < INT_MIN // 10 + 1 or rev > INT_MAX // 10:
return 0
digit = x % 10
# Python3 的取模运算在 x 为负数时也会返回 [0, 9) 以内的结果,因此这里需要进行特殊判断
if x < 0 and digit > 0:
digit -= 10

# 同理,Python3 的整数除法在 x 为负数时会向下(更小的负数)取整,因此不能写成 x //= 10
x = (x - digit) // 10
rev = rev * 10 + digit

return rev

26. 删除有序数组中的重复项

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
def removeDuplicates(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if nums == []:
return 0
slow = 0
fast = 1
while fast < len(nums):
if nums[slow] != nums[fast]:
slow += 1
nums[slow] = nums[fast]
fast += 1
return slow + 1

450. 删除二叉搜索树中的节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution(object):
def deleteNode(self, root, key):
"""
:type root: TreeNode
:type key: int
:rtype: TreeNode
"""
if root == None:
return None
if root.val > key:
root.left = self.deleteNode(root.left,key)
elif root.val < key:
root.right = self.deleteNode(root.right,key)
elif root.left == None or root.right == None:
root = root.left if root.left else root.right
else:
cur = root.right
while cur.left:
cur = cur.left
cur.left = root.left
root = root.right
return root