[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 ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 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