leetcode

发表于 更新于 分类于

贪心算法

  • 贪心：当下做局部最优判断
  • 回溯：能够回退
  • 动态规划：最优判度 + 回退

    860. 柠檬水找零 (2021.2.20)

自己的答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def lemonadeChange(self, bills: List[int]) -> bool:
        if bills[0] > 5:
            return False
        five_count, ten_count = 0, 0
        for i in range(len(bills)):
            if bills[i] == 5:
                five_count += 1
            elif bills[i] == 10:
                if five_count < 0: return False
                else:
                    five_count -= 1
                    ten_count += 1
            elif bills[i] == 20:
                if five_count > 0 and ten_count > 0:
                    five_count -= 1
                    ten_count -= 1
                elif five_count >= 3:
                    five_count -= 3
                else: return False
        return True

优秀代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def lemonadeChange(self, bills: List[int]) -> bool:
        five = ten = 0
        for num in bills:
            if num == 5:
                five += 1
            elif num == 10 and five:
                ten += 1
                five -= 1
            elif num == 20 and five and ten:
                five -= 1
                ten -= 1
            elif num == 20 and five >= 3:
                five -= 3
            else:
                return False
        return True

122. 买卖股票的最佳时机 II (2021.2.20)

自己的答案

1
2
3
4
5
6
7
8
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        sum = 0
        for i in range(len(prices)-1):
            gain = prices[i+1] - prices[i]
            if gain > 0:
                sum += gain
        return sum

优秀代码

1
2
3
4
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        return sum(max(prices[i + 1] - prices[i], 0) for i in range(len(prices) - 1))
        return sum([b-a for a,b in zip(prices,prices[1:]) if b-a > 0])

55. 跳跃游戏 (2021.3.4)

愚蠢的我想用动态规划来做，附上失败的代码:

1
2
3
4
5
6
7
8
9
class Solution:
    def canJump(self, nums: List[int]) -> bool:
        if len(nums) == 1:
            return True
        if nums[-2] >= 1:
            nums_ = nums[:-1]
            return self.canJump(nums_)
        else:
            return False

前向递推 + 贪心

1
2
3
4
5
6
7
8
9
10
class Solution:
    def canJump(self, nums: List[int]) -> bool:
        cover = 0
        for i, r in enumerate(nums):
            if i > cover:
                return False
            cover = max(cover, i+nums[i])
            if cover >= len(nums)-1:
                break
        return True

二分查找

  • 目标函数单调性（单调递增或者递减）
  • 存在上下界
  • 能够通过索引访问

69. x 的平方根 (2021.2.22)

自己的答案

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def mySqrt(self, x: int) -> int:
        left, right = 0, x
        while left <= right:
            mid = (left + right)//2
            if mid * mid <= x < (mid+1)*(mid+1):
                return mid
            if mid *mid > x:
                right = mid - 1
            else:
                left = mid + 1

优秀代码

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def mySqrt(self, x: int) -> int:
        left, right = 0, x
        while left <= right:
            mid = left + (right - left) // 2
            mid_square = mid ** 2
            if mid_square == x:
                return mid
            elif mid_square > x:
                right = mid - 1
            else:
                left = mid + 1
        return right

取巧的方法—牛顿迭代法

牛顿迭代法的思路：利用曲线的切线不断迭代从而逼近真实解
参考链接：如何通俗易懂地讲解牛顿迭代法求开方？（知乎）

关键迭代公式：

1
2
3
4
5
6
class Solution:
    def mySqrt(self, x: int) -> int:
        result = x
        while result**2 > x:
            result = (result + x//result)//2
        return result

33. 搜索旋转排序数组 (2021.2.25)

自己的答案

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

这道题我开始做的时候真的是非常的痛苦，看了很多题解并都看懂了，可是一到自己开始写的时候就发懵，尤其是边界条件的判度完全找不到任何的头绪，最后试了几个用例并用手推几次后，渐渐发现了一些思路：

  • 核心思路：先利用边界点和中心点确定单调区间，如果target在单调区间中，只要不断二分即可；如果target不在单调区间中，那就要通过中心点的信息不断迭代来缩小搜素区间来找target
  • 边界条件的判度（等号的位置）：多试几个特殊用例，慢慢就会找到相应的规律

优秀代码

1
2
3
4
5
6
7
8
9
10
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        lo, hi = 0, len(nums) - 1
        while lo < hi:
            mid = (lo + hi) // 2
            if (nums[0] > target) ^ (nums[0] > nums[mid]) ^ (target > nums[mid]):
                lo = mid + 1
            else:
                hi = mid
        return lo if target in nums[lo:lo+1] else -1

这种异或的方法看懂都要花好长时间，更别说自己想出来了，膜拜！
核心思路：利用mid和target的大小信息来确定前向二分还是后向二分，前向二分的情况如下所示：

nums[0] <= target <= nums[i]
　　　　　 target <= nums[i] < nums[0]
　　　　 　　　　　 nums[i] < nums[0] <= target

其余情况都用后向二分，根据归纳出的情况便可整理出如下的异或条件：
(nums[0] > target) ^ (nums[0] > nums[mid]) ^ (target > nums[mid])

动态规划

  • 最优子结构: 最优子问题
  • 状态定义方式：存储中间状态
  • 递推公式：状态转移方程

剑指 Offer 10- I. 斐波那契数列 (2021.3.1)

递归法（会超时）

1
2
3
4
5
class Solution:
    def fib(self, n: int) -> int:
        if n < 2:
            return n
        return self.fib(n-1) + self.fib(n-2)

DP（LU cache）

优秀代码（两个变量相互迭代）

1
2
3
4
5
6
7
class Solution:
    def fib(self, n: int) -> int:
        a, b = 0, 1
        constant = 1000000007
        for _ in range(n):
            b, a = (a+b)%constant, b%constant
        return a

62. 不同路径 (2021.3.2)

DP(二维状态空间)

1
2
3
4
5
6
7
class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        path = [[1]*n]+[[1]+[0]*(n-1) for _ in range(m-1)]
        for i in range(1, m):
            for j in range(1, n):
                path[i][j] = path[i-1][j] + path[i][j-1]
        return path[m-1][n-1]

72. 编辑距离 (2021.3.4)

自己的答案

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    @lru_cache()
    def minDistance(self, word1: str, word2: str) -> int:
        len1, len2 = len(word1), len(word2)
        if len1 == 0: return len2
        if len2 == 0: return len1
        if word1[-1] == word2[-1]:
            word1 = word1[:len1-1]
            word2 = word2[:len2-1]
            return self.minDistance(word1, word2)
        else:
            return min(self.minDistance(word1[:len1-1],word2),
            self.minDistance(word1, word2[:len2-1]), self.minDistance(word1[:len1-1], word2[:len2-1])) + 1

因为之前做文本相关处理的时候用到过编辑距离，所以这道题能够很快的想出来。思路：两个单词都从最后一个字符开始向前递推比较，最优子问题为word1最后一个字符删除、替换和插入之后和word2之间的编辑距离取最小。

字典树(Trie)

208. 实现 Trie (前缀树) (2021.3.10)

自己的答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Trie:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.root = {}
        self.end = "#"

    def insert(self, word: str) -> None:
        """
        Inserts a word into the trie.
        """
        node = self.root
        for i in word:
            node = node.setdefault(i, {})
        node[self.end] = self.end


    def search(self, word: str) -> bool:
        """
        Returns if the word is in the trie.
        """
        node = self.root
        for i in word:
            if i not in node:
                return False
            node = node[i]
        return self.end in node


    def startsWith(self, prefix: str) -> bool:
        """
        Returns if there is any word in the trie that starts with the given prefix.
        """
        node = self.root
        for i in prefix:
            if i not in node:
                return False
            node = node[i]
        return True

212. 单词搜索 II (2021.3.11)

自己的答案

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
import collections

class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:

        self.dx = [-1, 1, 0, 0]
        self.dy = [0, 0, -1, 1]
        self.end = "#"
        self.result = set()

        if not board or not board[0]: return []
        if not words: return []

        # 构建Trie
        root = collections.defaultdict()
        for word in words:
            node = root
            for char in word:
                node = node.setdefault(char, collections.defaultdict())
            node[self.end] = self.end

        for i in range(len(board)):
            for j in range(len(board[0])):
                if board[i][j] in root:
                    self._dfs(board, i, j, '', root)
        return list(self.result)

    # 深度优先搜索
    def _dfs(self, board, i, j, curchar, curdict):
        curchar = curchar + board[i][j]
        curdict = curdict[board[i][j]]
        if self.end in curdict:
            self.result.add(curchar)
        tmp, board[i][j] = board[i][j], "@"
        for ori in range(4):
            x = i + self.dx[ori]
            y = j + self.dy[ori]
            if 0<=x<len(board) and 0<=y<len(board[0]) and board[x][y] != "@" and board[x][y] in curdict:
                self._dfs(board, x, y, curchar, curdict)
        board[i][j] = tmp

本题思路：字典树 + DFS（关键要能想到用这种思路求解，且构建Trie和DFS的代码要能非常熟练的写出来）

并查集(Disjoint Set)

547. 省份数量 (2021.3.13)

自己的答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:

        n = len(isConnected)
        p = [i for i in range(n)]

        for r in range(n):
            for c in range(n):
                if isConnected[r][c] == 1:
                    self._union(p, r, c)
        return len(set([self._parent(p, i) for i in range(n)]))

    def _union(self, p, r, c):
        p1 = self._parent(p, r)
        p2 = self._parent(p, c)
        p[p2] = p1

    def _parent(self, p, i):
        root = i
        while p[root] != root:
            root = p[root]
        while p[i] != i:
            x = i
            # i = p[x]
            i = p[i]
            p[x] = root
        return root

高级排序算法

归并排序算法 (2021.4.9)

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
def merge_sort(arr, left, right):
    if right <= left: return None
    mid = (left + right) >> 1
    merge_sort(arr, left, mid)
    merge_sort(arr, mid+1, right)
    merge(arr, left, mid, right)

def merge(arr, left, mid, right):
    temp = [0]*(right-left+1)
    i, j, k = left, mid+1, 0

    while (i<=mid) and (j<=right):
        if arr[i] <= arr[j]:
            temp[k] = arr[i]
            i += 1
        else:
            temp[k] = arr[j]
            j += 1
        k += 1
    while i<=mid:
        temp[k] = arr[i]
        k+=1; i+=1
    while j<=right:
        temp[k] = arr[j]
        k+=1; j+=1
    for p in range(k):
        arr[left+p] = temp[p]

栈、队列、双端队列、优先队列

20. 有效的括号 (2021.6.3)

1. 暴力法：遇到成对括号替换为空字符串
2. 维护一个栈的方法解决

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def isValid(self, s: str) -> bool:
        if len(s) % 2 != 0:
            return False

        # while '()' in s or '{}' in s or '[]' in s:
        #     s = s.replace('()','').replace('{}','').replace('[]','')
        # if s == '':
        #     return True
        # else:
        #     return False

        stack = []
        dic = {')':'(', '}':'{', ']':'['}
        for i in s:
            if i in dic:
                if not stack or stack.pop() != dic[i]:
                    return False
            else:
                stack.append(i)
        return not stack

155. 最小栈 (2021.6.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
class MinStack:

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.stack = []
        self.min_stack = [math.inf]


    def push(self, val: int) -> None:
        self.stack.append(val)
        self.min_stack.append(min(val, self.min_stack[-1]))


    def pop(self) -> None:
        self.stack.pop()
        self.min_stack.pop()


    def top(self) -> int:
        return self.stack[-1]


    def getMin(self) -> int:
        return self.min_stack[-1]

84. 柱状图中最大的矩形 (2021.6.3)

技巧：始终维护一个从小到大的栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:

        heights.append(-1)
        res = 0
        stack = [-1]

        for i in range(0, len(heights)):
            while heights[i] < heights[stack[-1]]:
                h = heights[stack.pop()]
                w = i - stack[-1] - 1
                res = max(res, h*w)
            stack.append(i)
        return res

239. 滑动窗口最大值 (2021.6.3)

技巧：使用双端队列（队列的第一个元素始终保持最大）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        res = []
        d = collections.deque()

        for i, num in enumerate(nums):
            while d and num > nums[d[-1]]:
                d.pop()
            d.append(i)
            if i - k == d[0]:
                d.popleft()
            if i >= k-1:
                res.append(nums[d[0]])
        return res

641. 设计循环双端队列 (2021.6.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
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
class MyCircularDeque:

    def __init__(self, k: int):
        """
        Initialize your data structure here. Set the size of the deque to be k.
        """
        self.deque = [-1]*k
        self.head, self.tail = 0, 0
        self.size = 0
        self.cap = k


    def insertFront(self, value: int) -> bool:
        """
        Adds an item at the front of Deque. Return true if the operation is successful.
        """
        if self.isFull(): return False
        if self.isEmpty():
            self.deque[self.head] = value
        else:
            self.head = (self.head - 1) % self.cap
            self.deque[self.head] = value
        self.size += 1
        return True


    def insertLast(self, value: int) -> bool:
        """
        Adds an item at the rear of Deque. Return true if the operation is successful.
        """
        if self.isFull(): return False
        if self.isEmpty():
            self.deque[self.tail] = value
        else:
            self.tail = (self.tail + 1) % self.cap
            self.deque[self.tail] = value
        self.size += 1
        return True


    def deleteFront(self) -> bool:
        """
        Deletes an item from the front of Deque. Return true if the operation is successful.
        """
        if self.isEmpty(): return False
        self.deque[self.head] = -1
        self.head = (self.head + 1) % self.cap
        self.size -= 1
        if self.isEmpty():
            self.tail = self.head
        return True


    def deleteLast(self) -> bool:
        """
        Deletes an item from the rear of Deque. Return true if the operation is successful.
        """
        if self.isEmpty(): return False
        self.deque[self.tail] = -1
        self.tail = (self.tail - 1) % self.cap
        self.size -= 1
        if self.isEmpty():
            self.head = self.tail
        return True


    def getFront(self) -> int:
        """
        Get the front item from the deque.
        """
        return self.deque[self.head]


    def getRear(self) -> int:
        """
        Get the last item from the deque.
        """
        return self.deque[self.tail]


    def isEmpty(self) -> bool:
        """
        Checks whether the circular deque is empty or not.
        """
        if self.size == 0:
            return True


    def isFull(self) -> bool:
        """
        Checks whether the circular deque is full or not.
        """
        if self.size == self.cap:
            return True

42. 接雨水 (2021.6.3)

1. 暴力法遍历
2. 维护单调栈（单调递减）
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class Solution:
    def trap(self, height: List[int]) -> int:
        1. 暴力法
        # res = 0
        # for i in range(len(height)):
        #     left, right = 0, 0
        #     for j in range(0, i):
        #         left = max(left, height[j])
        #     for k in range(i+1, len(height)):
        #         right = max(right, height[k])
        #     if min(left, right) - height[i] < 0:
        #         res += 0
        #     else:
        #         res += min(left, right) - height[i]
        # return res

        2. 单调栈
        # stack = []
        # res = 0

        # for i in range(len(height)):
        #     while stack and height[i] > height[stack[-1]]:
        #         temp = stack.pop()
        #         if not stack:
        #             break
        #         h = min(height[i], height[stack[-1]]) - height[temp]
        #         w = i - stack[-1] - 1
        #         res += h * w
        #     stack.append(i)
        # return res

        3. 双指针
        left, right = 0, len(height) - 1
        max_left, max_right, res = 0, 0, 0
        while left < right:
            if height[left] <= height[right]:
                if height[left] > max_left:
                    max_left = height[left]
                else:
                    res += max_left - height[left]
                left += 1
            else:
                if height[right] > max_right:
                    max_right = height[right]
                else:
                    res += max_right - height[right]
                right -= 1
        return res

哈希表、映射、集合

242. 有效的字母异位词 (2021.6.4)

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:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False

        # s = sorted(s)
        # t = sorted(t)
        # return s == t

        # a, b = [0]*26, [0]*26
        # for i in s:
        #     a[ord(i) - ord('a')] += 1
        # for j in t:
        #     b[ord(j) - ord('a')] += 1
        # return a == b

        hash_dict = collections.defaultdict(int)
        for i in s:
            hash_dict[i] += 1
        for j in t:
            hash_dict[j] -= 1
            if hash_dict[j] < 0:
                return False
        return True

49. 字母异位词分组 (2021.6.4)

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:

        # hash_dict = {}
        # for s in strs:
        #     key = tuple(sorted(s))
        #     hash_dict[key] = hash_dict.get(key, []) + [s]
        # return list(hash_dict.values())

        hash_dict = collections.defaultdict(list)
        for s in strs:
            hash_dict[tuple(sorted(s))].append(s)
        return list(hash_dict.values())

1. 两数之和 (2021.6.4)

1
2
3
4
5
6
7
8
9
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:

        dic = {}
        for i, j in enumerate(nums):
            if target - j in dic:
                return [i, dic[target - j]]
            dic[j] = i
        return []

树、二叉树、二叉搜索树

94. 二叉树的中序遍历 (2021.6.4)

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
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        # visited = []
        # def helper(root, visited):
        #     if root:
        #         helper(root.left, visited)
        #         visited.append(root.val)
        #         helper(root.right, visited)
        # helper(root, visited)
        # return visited

        visited, stack = [], []
        while root or stack:
            if root:
                stack.append(root)
                root = root.left
            else:
                root = stack.pop()
                visited.append(root.val)
                root = root.right
        return visited

144. 二叉树的前序遍历 (2021.6.4)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        # visited = []
        # def helper(root, visited):
        #     if root:
        #         visited.append(root.val)
        #         helper(root.left, visited)
        #         helper(root.right, visited)
        # helper(root, visited)
        # return visited

        visited, stack = [], [root]
        while stack:
            root = stack.pop()
            if root:
                visited.append(root.val)
                stack.append(root.right)
                stack.append(root.left)
        return visited

145. 二叉树的后序遍历 (2021.6.4)

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
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        # visited = []
        # def helper(root, visited):
        #     if root:
        #         helper(root.left, visited)
        #         helper(root.right, visited)
        #         visited.append(root.val)
        # helper(root, visited)
        # return visited

        visited, stack = [], []
        pre = None
        while root or stack:
            while root:
                stack.append(root)
                root = root.left
            root = stack.pop()
            if not root.right or root.right == pre:
                visited.append(root.val)
                pre = root
                root = None
            else:
                stack.append(root)
                root = root.right
        return visited

590. N 叉树的后序遍历 (2021.6.4)

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
"""
# Definition for a Node.
class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children
"""

class Solution:
    def postorder(self, root: 'Node') -> List[int]:
        visited = []
        if not root:
            return visited

        # def recursion(root, visited):
        #     for child in root.children:
        #         recursion(child, visited)
        #     visited.append(root.val)

        # recursion(root, visited)
        # return visited

        visited, stack = [], [root]
        while stack:
            root = stack.pop()
            visited.append(root.val)
            stack.extend(root.children)
        return visited[::-1]

589. N 叉树的前序遍历 (2021.6.4)

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
"""
# Definition for a Node.
class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children
"""

class Solution:
    def preorder(self, root: 'Node') -> List[int]:
        visited = []
        if not root:
            return visited

        # def recursion(root, visited):
        #     visited.append(root.val)
        #     for child in root.children:
        #         recursion(child, visited)

        # recursion(root, visited)
        # return visited

        stack = [root]
        while stack:
            root = stack.pop()
            visited.append(root.val)
            stack.extend(root.children[::-1])
        return visited

429. N 叉树的层序遍历 (2021.6.4)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
"""
# Definition for a Node.
class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children
"""

class Solution:
    def levelOrder(self, root: 'Node') -> List[List[int]]:
        result = []
        def recursion(root, level):
            if len(result) == level:
                result.append([])
            result[level].append(root.val)
            for child in root.children:
                recursion(child, level + 1)

        if root != None:
            recursion(root, 0)
        return result

泛型递归、树的递归

70. 爬楼梯 (2021.6.4)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
from functools import lru_cache
class Solution:
    @lru_cache()
    def climbStairs(self, n: int) -> int:
        if n <= 2:
            return n
        return self.climbStairs(n - 1) + self.climbStairs(n - 2)

        # if n <= 2:
        #     return n
        # f1, f2 = 0, 1
        # for i in range(n):
        #     f1, f2 = f2, f1 + f2
        # return f2

22. 括号生成 (2021.6.4)

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        left, right = 0, 0
        res = []
        def recursion(left, right, s):
            if left == n and right == n:
                res.append(s)
            if left < n:
                recursion(left + 1, right, s + "(")
            if right < left:
                recursion(left, right + 1, s + ")")
        recursion(left, right, '')
        return res

226. 翻转二叉树 (2021.6.4)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        # if not root:
        #     return None
        # root.left, root.right = root.right, root.left
        # self.invertTree(root.left)
        # self.invertTree(root.right)

        # return root

        if not root:
            return root

        left = self.invertTree(root.left)
        right = self.invertTree(root.right)
        root.left, root.right = right, left

        return root

98. 验证二叉搜索树 (2021.6.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
26
27
28
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        # def recursion(root, left, right):
        #     if not root:
        #         return True
        #     if root.val <= left or root.val >= right:
        #         return False
        #     return recursion(root.left, left, root.val) and recursion(root.right, root.val, right)
        # return recursion(root, -inf, inf)

        if not root:
            return True
        stack = [(root, -inf, inf)]
        while stack:
            root, left, right = stack.pop()
            if root.val <= left or root.val >= right:
                return False
            if root.left:
                stack.append((root.left, left, root.val))
            if root.right:
                stack.append((root.right, root.val, right))
        return True

104. 二叉树的最大深度 (2021.6.8)

1
2
3
4
5
6
7
8
9
10
11
12
13
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if not root:
            return 0
        left = self.maxDepth(root.left)
        right = self.maxDepth(root.right)
        return max(left, right) + 1

111. 二叉树的最小深度 (2021.6.8)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def minDepth(self, root: TreeNode) -> int:
        if not root:
            return 0
        left = self.minDepth(root.left)
        right = self.minDepth(root.right)
        if not root.left or not root.right:
            return left + right + 1
        else:
            return min(left, right) + 1

297. 二叉树的序列化与反序列化 (2021.6.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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Codec:

    def serialize(self, root):
        """Encodes a tree to a single string.

        :type root: TreeNode
        :rtype: str
        """
        def recursion(root):
            if root:
                res.append(str(root.val))
                recursion(root.left)
                recursion(root.right)
            else:
                res.append('#')
        res = []
        recursion(root)
        return " ".join(res)


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

        :type data: str
        :rtype: TreeNode
        """
        def recursion():
            val = next(vals)
            if val == '#':
                return None
            Node = TreeNode(int(val))
            Node.left = recursion()
            Node.right = recursion()
            return Node
        vals = iter(data.split())
        return recursion()


# Your Codec object will be instantiated and called as such:
# ser = Codec()
# deser = Codec()
# ans = deser.deserialize(ser.serialize(root))

236. 二叉树的最近公共祖先 (2021.6.8)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if not root or root == p or root == q:
            return root
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
        if not left:
            return right
        if not right:
            return left
        return root

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        if inorder:
            ind = inorder.index(preorder.pop(0))
            root = TreeNode(inorder[ind])
            root.left = self.buildTree(preorder, inorder[0:ind])
            root.right = self.buildTree(preorder, inorder[ind+1:])
            return root

77. 组合 (2021.6.8)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        res, stack = [], []
        x = 1
        while True:
            l = len(stack)
            if l == k:
                res.append(stack[:])
            if l == k or x > n - k + l + 1:
                if not stack:
                    return res
                x = stack.pop() + 1
            else:
                stack.append(x)
                x += 1

46. 全排列 (2021.6.8)

1
2
3
4
5
6
7
8
9
10
class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        res = []
        def dfs(nums, path, res):
            if not nums:
                res.append(path)
            for i in range(len(nums)):
                dfs(nums[:i]+nums[i+1:], path+[nums[i]], res)
        dfs(nums, [], res)
        return res

47. 全排列 II (2021.6.8)

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        res, visited = [], []
        def dfs(nums, path, res):
            if not nums:
                res.append(path)
            for i in range(len(nums)):
                if i > 0 and nums[i] == nums[i-1]:
                    continue
                dfs(nums[:i]+nums[i+1:], path+[nums[i]], res)
        nums.sort()
        dfs(nums, [], res)
        return res

分治、回溯

50. Pow(x, n) (2021.6.8)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def myPow(self, x: float, n: int) -> float:
        if n == 0: return 1
        if n < 0:
            x, n = 1/x, -n

        def recursion(x, n):
            if n == 1: return x
            val = recursion(x, n//2)
            if n % 2 == 0:
                return val * val
            else:
                return val * val * x

        return recursion(x, n)

78. 子集 (2021.6.9)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        # res = [[]]
        # for i in nums:
        #     res = res + [ x + [i] for x in res]
        # return res

        res = []
        def dfs(index, val, nums):
            if index == len(nums):
                res.append(val)
                return None
            dfs(index+1, val.copy(), nums)
            val.append(nums[index])
            dfs(index+1, val.copy(), nums)
        dfs(0, [], nums)
        return res

169. 多数元素 (2021.6.9)

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:
    def majorityElement(self, nums: List[int]) -> int:
        # counter = collections.Counter(nums)
        # return max(counter.keys(), key=counter.get)

        # nums.sort()
        # return nums[len(nums)//2]

        def recursion(lo, hi):
            if lo == hi:
                return nums[lo]

            mid= (lo + hi)//2
            left = recursion(lo, mid)
            right = recursion(mid+1, hi)
            if left == right:
                return left
            left_count = sum([1 for num in nums[lo:hi+1] if num == left])
            right_count = sum([1 for num in nums[lo:hi+1] if num == right])
            if left_count > right_count:
                return left
            else:
                return right

        return recursion(0, len(nums)-1)

17. 电话号码的字母组合 (2021.6.9)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if digits == '':
            return []
        hash_map = {"2": "abc", "3": "def", "4": "ghi", "5": "jkl",
                    "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"}
        res = []

        def recursion(index, digits, s):
            if index == len(digits):
                res.append(s)
                return None
            for i in hash_map[digits[index]]:
                recursion(index+1, digits, s+i)
        recursion(0, digits, '')
        return res

51. N 皇后 (2021.6.9)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        res = []
        def recursion(queens, pie, na):
            row = len(queens)
            if row == n:
                res.append(queens)
                return None
            for col in range(n):
                if col not in queens and row+col not in pie and row-col not in na:
                    recursion(queens+[col], pie+[row+col], na+[row-col])
        recursion([], [], [])
        res_form = [['.'*i + 'Q' + '.'*(n-i-1) for i in r] for r in res]
        return res_form

深度优先搜索和广度优先搜索

102. 二叉树的层序遍历 (2021.6.9)

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
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        # res = []
        # def dfs(level, root):
        #     if not root:
        #         return None
        #     if level == len(res):
        #         res.append([])
        #     res[level].append(root.val)
        #     dfs(level + 1, root.left)
        #     dfs(level + 1, root.right)
        # dfs(0, root)
        # return res

        q, res = collections.deque(), []
        if root:
            q.append(root)
        while len(q):
            level = []
            for _ in range(len(q)):
                root = q.popleft()
                level.append(root.val)
                if root.left:
                    q.append(root.left)
                if root.right:
                    q.append(root.right)
            res.append(level)
        return res

433. 最小基因变化 (2021.6.9)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def minMutation(self, start: str, end: str, bank: List[str]) -> int:
        bank = set(bank)
        q = collections.deque([(start, 0)])
        while q:
            start, res = q.popleft()
            if start == end:
                return res
            for i in range(8):
                for j in "ACGT":
                    new = start[:i] + j + start[i+1:]
                    if new in bank:
                        q.append((new, res+1))
                        bank.discard(new)
        return -1

515. 在每个树行中找最大值 (2021.6.9)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def largestValues(self, root: TreeNode) -> List[int]:
        res, q = [], deque()
        if root:
            q.append(root)
        while q:
            length, level = len(q), []
            for _ in range(length):
                root = q.popleft()
                level.append(root.val)
                if root.left:
                    q.append(root.left)
                if root.right:
                    q.append(root.right)
            res.append(max(level))
        return res

127. 单词接龙 (2021.6.9)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        wordList = set(wordList)
        if beginWord in wordList:
            wordList.remove(beginWord)
        if endWord not in wordList:
            return 0

        q = collections.deque([(beginWord, 1)])
        length = len(beginWord)
        while q:
            begin, res = q.popleft()
            if begin == endWord:
                return res
            for i in range(length):
                for j in string.ascii_lowercase:
                    tmp = begin[:i] + j + begin[i+1:]
                    if tmp in wordList:
                        q.append((tmp, res+1))
                        wordList.remove(tmp)
        return 0

126. 单词接龙 II (2021.6.9)

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:
    def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) -> List[List[str]]:
        wordList = set(wordList)
        if beginWord in wordList:
            wordList.remove(beginWord)
        if endWord not in wordList:
            return []

        layer = {}
        layer[beginWord] = [[beginWord]]
        length = len(beginWord)
        while layer:
            newLayer = collections.defaultdict(list)
            for word in layer:
                if word == endWord:
                    return layer[word]
                for i in range(length):
                    for j in string.ascii_lowercase:
                        newWord = word[:i] + j + word[i+1:]
                        if newWord in wordList:
                            newLayer[newWord] += [x+[newWord] for x in layer[word]]
            wordList -= set(newLayer.keys())
            layer = newLayer

        return []

200. 岛屿数量 (2021.6.9)

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:
    def numIslands(self, grid: List[List[str]]) -> int:
        dx = [1, -1, 0, 0]
        dy = [0, 0, 1, -1]
        l1, l2 = len(grid), len(grid[0])
        count = 0

        # def dfs(row, col):
        #     if grid[row][col] == "0":
        #         return None
        #     grid[row][col] = '0'
        #     for index in range(4):
        #         x = row + dx[index]
        #         y = col + dy[index]
        #         if 0 <= x and x <= l1-1 and y >= 0 and y <= l2-1:
        #             dfs(x, y)

        def dfs(row, col):
            if row < 0 or col < 0 or row >= l1 or col >= l2 or grid[row][col] == '0':
                return None
            grid[row][col] = '0'
            dfs(row+1, col)
            dfs(row-1, col)
            dfs(row, col+1)
            dfs(row, col-1)


        for i in range(l1):
            for j in range(l2):
                if grid[i][j] == '1':
                    dfs(i, j)
                    count += 1
        return count

529. 扫雷游戏 (2021.6.9)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:
        d = [(-1,-1), (-1,0), (-1,1), (0,-1), (0,1), (1,-1), (1,0), (1,1)]
        m, n = len(board), len(board[0])

        def dfs(board, row, col):
            if row < 0 or row >= m or col < 0 or col >= n:
                return None
            if board[row][col] == 'M':
                board[row][col] = 'X'
            elif board[row][col] == 'E':
                count = sum(board[row+i][col+j] == 'M' for i, j in d if 0 <= row+i < m and 0 <= col+j < n)
                if count:
                    board[row][col] = str(count)
                else:
                    board[row][col] = 'B'
                    for i, j in d:
                        dfs(board, row+i, col+j)

        dfs(board, *click)
        return board

贪心算法

860. 柠檬水找零 (2021.6.10)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def lemonadeChange(self, bills: List[int]) -> bool:
        five, ten = 0, 0
        for i in bills:
            if i == 5:
                five += 1
            elif i == 10 and five:
                five -= 1
                ten += 1
            elif i == 20 and five and ten:
                five -= 1
                ten -= 1
            elif i == 20 and five >= 3:
                five -= 3
            else:
                return False
        return True

122. 买卖股票的最佳时机 II (2021.6.10)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        # dp = [[0, 0] for i in range(len(prices))]
        # dp[0][0], dp[0][1] = 0, -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]

        res = 0
        for i in range(1, len(prices)):
            if prices[i] > prices[i-1]:
                res += prices[i] - prices[i-1]
        return res

455. 分发饼干 (2021.6.10)

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def findContentChildren(self, g: List[int], s: List[int]) -> int:
        res, i, j = 0, 0, 0
        g.sort()
        s.sort()
        while i < len(g) and j < len(s):
            if g[i] <= s[j]:
                res += 1
                i += 1
                j += 1
            else:
                j += 1
        return res

874. 模拟行走机器人 (2021.6.10)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:
        i = j = res = index = 0
        d = [(0, 1), (-1, 0), (0, -1), (1, 0)]
        obstacles = set(map(tuple, obstacles))
        for command in commands:
            if command == -2:
                index = (index + 1) % 4
            elif command == -1:
                index = (index - 1) % 4
            else:
                dx, dy = d[index]
                while command and (i + dx, j + dy) not in obstacles:
                    i += dx
                    j += dy
                    command -= 1
            res = max(res, i**2 + j**2)

        return res

55. 跳跃游戏 (2021.6.10)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def canJump(self, nums: List[int]) -> bool:
        # end = len(nums) - 1
        # for i in range(len(nums)-1, -1, -1):
        #     if nums[i] + i >= end:
        #         end = i
        # return end == 0

        cover = 0
        for i in range(len(nums)):
            if i > cover:
                return False
            cover = max(cover, i + nums[i])
            if cover >= len(nums):
                break
        return True

45. 跳跃游戏 II (2021.6.10)

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def jump(self, nums: List[int]) -> int:
        if len(nums) <= 1:
            return 0
        l, r = 0, nums[0]
        count = 1
        while r < len(nums) - 1:
            count += 1
            nxt = max(i + nums[i] for i in range(l, r + 1))
            l, r = r, nxt
        return count

二分查找

69. x 的平方根 (2021.6.10)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def mySqrt(self, x: int) -> int:
        # res = x
        # while res ** 2 > x:
        #     res = (res + x//res)//2
        # return res

        left, right = 0, x
        while left <= right:
            mid = left + (right - left)//2
            x_ = mid ** 2
            if x_ == x:
                return mid
            if mid ** 2 > x:
                right = mid - 1
            else:
                left = mid + 1
        return right

367. 有效的完全平方数 (2021.6.10)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        if num <= 1:
            return True
        left, right = 0, num//2
        while left <= right:
            mid = (left + right) // 2
            x = mid ** 2
            if x == num:
                return True
            if x > num:
                right = mid - 1
            else:
                left = mid + 1
        return False

33. 搜索旋转排序数组 (2021.6.10)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        # lo, hi = 0, len(nums) - 1
        # while lo < hi:
        #     mid = (lo + hi) // 2
        #     if (nums[0] > target) ^ (nums[0] > nums[mid]) ^ (target > nums[mid]):
        #         lo = mid + 1
        #     else:
        #         hi = mid
        # # return lo if target in nums[lo:lo+1] else -1
        # return lo if target == nums[lo] else -1

        left, right = 0, len(nums) - 1
        while left <= right:
            mid = (left + right) // 2
            if target == nums[mid]:
                return mid
            if nums[left] <= nums[mid]:
                if nums[left] <= target and target < nums[mid]:
                    right = mid - 1
                else:
                    left += 1
            else:
                if nums[mid] < target and target <= nums[right]:
                    left = mid + 1
                else:
                    right -= 1
        return -1

74. 搜索二维矩阵 (2021.6.10)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        if not matrix or target is None:
            return False
        # m, n = len(matrix), len(matrix[0])
        # left, right = 0, m * n - 1
        # while left <= right:
        #     mid = (left + right) // 2
        #     val = matrix[mid // n][mid % n]
        #     if val == target:
        #         return True
        #     if target < val:
        #         right = mid - 1
        #     else:
        #         left = mid + 1
        # return False

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

153. 寻找旋转排序数组中的最小值 (2021.6.10)

1
2
3
4
5
6
7
8
9
10
class Solution:
    def findMin(self, nums: List[int]) -> int:
        left, right = 0, len(nums) - 1
        while left < right:
            mid = (left + right) // 2
            if nums[mid] < nums[right]:
                right = mid
            else:
                left = mid + 1
        return nums[left]

动态规划

剑指 Offer 10- I. 斐波那契数列 (2021.6.11)

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    @lru_cache
    def fib(self, n: int) -> int:
        # if n <= 1: return n
        # return int((self.fib(n-1) + self.fib(n-2)) % (1e9+7))

        f1, f2 = 0, 1
        const = 1000000007
        for _ in range(n):
            f1, f2 = f2 % const, (f1 + f2) % const
        return f1

62. 不同路径 (2021.6.11)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        # dp = [[1]*n] + [[1] + [0]*(n-1) for _ in range(m-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]

        dp = [1] * n
        for i in range(m-1):
            for j in range(n):
                if j > 0:
                    dp[j] += dp[j-1]
        return dp[-1]

63. 不同路径 II (2021.6.11)

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        m, n = len(obstacleGrid), len(obstacleGrid[0])
        dp = [1] + [0] * (n - 1)
        for i in range(m):
            for j in range(n):
                if obstacleGrid[i][j] == 1:
                    dp[j] = 0
                elif j > 0:
                    dp[j] += dp[j - 1]
        return dp[-1]

1143. 最长公共子序列 (2021.6.11)

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        if not text1 or not text2:
            return 0
        m, n = len(text1), len(text2)
        dp = [[0]*(n+1) for _ in range(m+1)]
        for i in range(1, m+1):
            for j in range(1, n+1):
                if text1[i-1] == text2[j-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]

70. 爬楼梯 (2021.6.11)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
from functools import lru_cache
class Solution:
    # @lru_cache()
    def climbStairs(self, n: int) -> int:
        # if n <= 2:
        #     return n
        # return self.climbStairs(n - 1) + self.climbStairs(n - 2)

        # if n <= 2:
        #     return n
        f1, f2 = 0, 1
        for i in range(n):
            f1, f2 = f2, f1 + f2
        return f2

120. 三角形最小路径和 (2021.6.11)

1
2
3
4
5
6
7
class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        dp = triangle
        for i in range(len(triangle)-2, -1, -1):
            for j in range(len(triangle[i])):
                dp[i][j] += min(dp[i+1][j], dp[i+1][j+1])
        return dp[0][0]

53. 最大子序和 (2021.6.11)

1
2
3
4
5
6
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        dp = nums
        for i in range(1, len(nums)):
            dp[i] = max(0, dp[i-1]) + nums[i]
        return max(dp)

152. 乘积最大子数组 (2021.6.11)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        # maxValue = minValue = res = nums[0]
        # for i in range(1, len(nums)):
        #     x = max(nums[i], minValue*nums[i], maxValue*nums[i])
        #     y = min(nums[i], minValue*nums[i], maxValue*nums[i])
        #     maxValue, minValue = x, y
        #     res = max(res, maxValue)
        # return res

        maxValue = minValue = res = nums[0]
        for i in range(1, len(nums)):
            if nums[i] < 0:
                maxValue, minValue = minValue, maxValue
            maxValue = max(nums[i], maxValue*nums[i])
            minValue = min(nums[i], minValue*nums[i])
            res = max(res, maxValue)
        return res

322. 零钱兑换 (2021.6.11)

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:
    def coinChange(self, coins: List[int], amount: int) -> int:
        # dp = [amount + 1] * (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[amount] if dp[amount] != amount + 1 else -1

        if not amount:
            return 0
        q = collections.deque([(0, 0)])
        visited = [True] + [False]*amount
        while q:
            num, cur = q.popleft()
            num += 1
            for coin in coins:
                nex = cur + coin
                if nex == amount:
                    return num
                if nex < amount:
                    if not visited[nex]:
                        visited[nex] = True
                        q.append((num, nex))
        return -1

198. 打家劫舍 (2021.6.15)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def rob(self, nums: List[int]) -> int:
        length = len(nums)
        # dp = [[0]*2 for _ in range(length)]
        # dp[0][0], dp[0][1] = 0, nums[0]

        # for i in range(1, length):
        #     dp[i][0] = max(dp[i-1][0], dp[i-1][1])
        #     dp[i][1] = dp[i-1][0] + nums[i]
        # return max(dp[length-1][0], dp[length-1][1])

        # dp = [0] * (length + 1)
        # dp[0], dp[1] = 0, nums[0]

        # for i in range(2, length+1):
        #     dp[i] = max(dp[i-1], dp[i-2] + nums[i-1])
        # return dp[-1]

        cur, pre = nums[0], 0
        for i in range(1, length):
            cur, pre = max(cur, pre + nums[i]), cur
        return cur

字典树(Trie)

208. 实现 Trie (前缀树) (2021.6.15)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Trie:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.root = {}
        self.end = "#"


    def insert(self, word: str) -> None:
        """
        Inserts a word into the trie.
        """
        node = self.root
        for char in word:
            node = node.setdefault(char, {})
        node[self.end] = self.end


    def search(self, word: str) -> bool:
        """
        Returns if the word is in the trie.
        """
        node = self.root
        for char in word:
            if char not in node:
                return False
            node = node[char]
        return self.end in node


    def startsWith(self, prefix: str) -> bool:
        """
        Returns if there is any word in the trie that starts with the given prefix.
        """
        node = self.root
        for char in prefix:
            if char not in node:
                return False
            node = node[char]
        return True


# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.startsWith(prefix)

212. 单词搜索 II (2021.6.15)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        dx = [0, 0, 1, -1]
        dy = [1, -1, 0, 0]
        m, n = len(board), len(board[0])
        res = set()

        root = {}
        for word in words:
            node = root
            for char in word:
                node = node.setdefault(char, {})
            node["#"] = True


        def dfs(i, j, s, node, visited):
            if "#" in node:
                res.add(s)
            for d in range(4):
                x = i + dx[d]
                y = j + dy[d]
                if 0 <= x < m and 0 <= y < n and (x, y) not in visited and board[x][y] in node:
                    dfs(x, y, s + board[x][y], node[board[x][y]], visited | {(x, y)})


        for i in range(m):
            for j in range(n):
                if board[i][j] in root:
                    dfs(i, j, board[i][j], root[board[i][j]], {(i, j)})
        return list(res)

并查集(Disjoint Set)

547. 省份数量 (2021.6.15)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        # n = len(isConnected)
        # count = 0
        # visited = set()

        # def dfs(i):
        #     for j in range(n):
        #         if isConnected[i][j] == 1 and j not in visited:
        #             visited.add(j)
        #             dfs(j)

        # for i in range(n):
        #     if i not in visited:
        #         dfs(i)
        #         count += 1
        # return count

        def union(i, j):
            p1 = parent(i)
            p2 = parent(j)
            p[p2] = p1

        def parent(k):
            root = k
            while p[root] != root:
                root = p[root]
            while p[k] != k:
                tmp = k
                k = p[k]
                p[tmp] = root
            return root

        l = len(isConnected)
        p = [n for n in range(l)]
        for i in range(l):
            for j in range(l):
                if isConnected[i][j] == 1:
                    union(i, j)
        return len(set([parent(n) for n in range(l)]))

200. 岛屿数量 (2021.6.15)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if len(grid) == 0:
            return 0
        row, col = len(grid), len(grid[0])
        p = [i for i in range(row * col)]
        self.count = sum(grid[i][j] == '1' for i in range(row) for j in range(col))

        def parent(root):
            if p[root] != root:
                return parent(p[root])
            return root

        def union(x, y):
            p1, p2 = parent(x), parent(y)
            if p1 == p2:
                return
            p[p1] = p2
            self.count -= 1

        for i in range(row):
            for j in range(col):
                if grid[i][j] == '0': continue
                index = i * col + j
                if j < col - 1 and grid[i][j+1] == '1':
                    union(index, index+1)
                if i < row - 1 and grid[i+1][j] == '1':
                    union(index, index+col)
        return self.count

130. 被围绕的区域 (2021.6.15)

并查集的方法在倒数第二个测试用例会超出时间限制😂

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
class Solution:
    def solve(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        # m, n = len(board), len(board[0])

        # def dfs(i, j):
        #     if 0 <= i < m and 0 <= j < n and board[i][j] == 'O':
        #         board[i][j] = '#'
        #         dfs(i+1, j)
        #         dfs(i-1, j)
        #         dfs(i, j+1)
        #         dfs(i, j-1)

        # for i in [0, m-1]:
        #     for j in range(n):
        #         dfs(i, j)
        # for i in range(m):
        #     for j in [0, n-1]:
        #         dfs(i, j)

        # for i in range(m):
        #     for j in range(n):
        #         if board[i][j] == "O":
        #             board[i][j] = "X"
        #         if board[i][j] == "#":
        #             board[i][j] = "O"
        # return board

        row, col = len(board), len(board[0])
        dummy = row * col
        p = [i for i in range(dummy)] + [dummy]

        def parent(root):
            if p[root] != root:
                return parent(p[root])
            return root

        def union(x, y):
            p1, p2 = parent(x), parent(y)
            if p1 == p2:
                return
            p[p1] = p2

        for i in range(row):
            for j in range(col):
                if board[i][j] == 'O':
                    if i == 0 or j == 0 or i == row-1 or j == col-1:
                        union(i*col+j, dummy)
                    else:
                        for dx, dy in [(0,1), (0,-1), (1,0), (-1,0)]:
                            if board[i+dx][j+dy] == 'O':
                                union(i*col+j, (i+dx)*col+(j+dy))
        for i in range(row):
            for j in range(col):
                if parent(i*col+j) == parent(dummy):
                    board[i][j] = "O"
                else:
                    board[i][j] = "X"
        return board

高级搜索

36. 有效的数独 (2021.6.16)

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:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        # return 1 == max(list(collections.Counter(
        # x
        # for i, row in enumerate(board)
        # for j, c in enumerate(row)
        # if c != '.'
        # for x in ((c, i), (j, c), ((i//3)*3 + j//3, c, "#"))
        # ).values())+ [1])

        row = [{} for _ in range(9)]
        col = [{} for _ in range(9)]
        block = [{} for _ in range(9)]

        for i in range(9):
            for j in range(9):
                if board[i][j] != '.':
                    num = board[i][j]
                    row[i][num] = row[i].get(num, 0) + 1
                    col[j][num] = col[j].get(num, 0) + 1
                    block[(i//3)*3+j//3][num] = block[(i//3)*3+j//3].get(num, 0) + 1

                    if row[i][num] > 1 or col[j][num] > 1 or block[(i//3)*3+j//3][num] > 1:
                        return False
        return True

37. 解数独 (2021.6.16)

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:
    def solveSudoku(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        row = [set(range(1, 10)) for _ in range(9)]
        col = [set(range(1, 10)) for _ in range(9)]
        block = [set(range(1, 10)) for _ in range(9)]

        empty = []
        for i in range(9):
            for j in range(9):
                if board[i][j] == '.':
                    empty.append((i, j))
                else:
                    num = board[i][j]
                    row[i].remove(int(num))
                    col[j].remove(int(num))
                    block[(i//3)*3+j//3].remove(int(num))

        def dfs(iter=0):
            if iter == len(empty):
                return True
            i, j = empty[iter]
            for num in row[i] & col[j] & block[(i//3)*3+j//3]:
                board[i][j] = str(num)
                row[i].remove(num)
                col[j].remove(num)
                block[(i//3)*3+j//3].remove(num)
                if dfs(iter + 1):
                    return True
                row[i].add(num)
                col[j].add(num)
                block[(i//3)*3+j//3].add(num)
            return False
        return dfs()

127. 单词接龙 (2021.6.16) —-> 双向BFS

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
class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        # wordList = set(wordList)
        # if beginWord in wordList:
        #     wordList.remove(beginWord)
        # if endWord not in wordList:
        #     return 0

        # q = collections.deque([(beginWord, 1)])
        # length = len(beginWord)
        # while q:
        #     begin, res = q.popleft()
        #     if begin == endWord:
        #         return res
        #     for i in range(length):
        #         for j in string.ascii_lowercase:
        #             tmp = begin[:i] + j + begin[i+1:]
        #             if tmp in wordList:
        #                 q.append((tmp, res+1))
        #                 wordList.remove(tmp)
        # return 0

        if endWord not in wordList: return 0
        wordList = set(wordList)
        length = len(beginWord)
        res = 1

        front = {beginWord}
        back = {endWord}

        while front:
            res += 1
            next_front = set()
            for word in front:
                for i in range(length):
                    for char in string.ascii_lowercase:
                        if char != word[i]:
                            new_word = word[:i] + char + word[i+1:]
                            if new_word in back:
                                return res
                            if new_word in wordList:
                                next_front.add(new_word)
                                wordList.remove(new_word)
            front = next_front
            if len(front) > len(back):
                front, back = back, front
        return 0

433. 最小基因变化 —-> 双向BFS

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
class Solution:
    def minMutation(self, start: str, end: str, bank: List[str]) -> int:
        # bank = set(bank)
        # q = collections.deque([(start, 0)])
        # while q:
        #     start, res = q.popleft()
        #     if start == end:
        #         return res
        #     for i in range(8):
        #         for j in "ACGT":
        #             new = start[:i] + j + start[i+1:]
        #             if new in bank:
        #                 q.append((new, res+1))
        #                 bank.discard(new)
        # return -1

        if end not in bank: return -1
        bank = set(bank)
        length = len(start)
        res = 0

        front, back = {start}, {end}

        while front:
            res += 1
            next_front = set()
            for seq in front:
                for i in range(length):
                    for c in "ACGT":
                        if c != seq[i]:
                            new_seq = seq[:i] + c + seq[i+1:]
                            if new_seq in back:
                                return res
                            if new_seq in bank:
                                next_front.add(new_seq)
                                bank.remove(new_seq)
            front = next_front
            if len(front) > len(back):
                front, back = back, front
        return -1

1091. 二进制矩阵中的最短路径 —-> A*搜索

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
class Solution:
    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
        # if grid[0][0] == 1 or grid[-1][-1] == 1 or not grid:
        #     return -1
        # n = len(grid)
        # if n <= 2: return n
        # d = [(0,1), (0,-1), (-1,0), (1,0), (1,1), (1,-1), (-1,1), (-1,-1)]

        # q, visited = [(0, 0, 1)], set()
        # while q:
        #     next_q = []
        #     for i, j, r in q:
        #         visited.add((i, j))
        #         if i == j == n-1:
        #             return r
        #         for x, y in d:
        #             if 0<=i+x<n and 0<=j+y<n and grid[i+x][j+y]==0:
        #                 if (i+x, j+y) not in visited:
        #                     next_q.append((i+x, j+y, r+1))
        #     q = next_q
        # return -1

        # if grid[0][0] == 1 or grid[-1][-1] == 1 or not grid:
        #     return -1
        # n, q = len(grid), [(0,0,2)]
        # if n <= 2: return n

        # for i, j, r in q:
        #     for x, y in [(i,j+1), (i,j-1), (i-1,j), (i+1,j), (i+1,j+1), (i+1,j-1), (i-1,j+1), (i-1,j-1)]:
        #         if x == y == n-1:
        #             return r
        #         if 0 <= x < n and 0 <= y < n and not grid[x][y]:
        #             q += [(x, y, r+1)]
        #             grid[x][y] = 1
        # return -1


        n = len(grid)
        if n==0 or grid[0][0]==1:
            return -1
        target = (n-1,n-1)
        f0 = 2*n-2
        scores = {(0,0): f0}
        heap = [(f0,1,0,0)]
        while heap:
            f,g,i,j = heappop(heap)
            if (i,j) == target:
                return g
            children = [(i+1,j),(i-1,j),(i,j+1),(i,j-1),(i+1,j+1),(i-1,j-1),(i+1,j-1),(i-1,j+1)]
            for k,l in children:
                if 0 <= k < n and 0 <= l <n and grid[k][l] == 0:
                    heuristic = max(abs(k-target[0]), abs(l-target[1]))
                    new_score = heuristic + g + 1
                    if new_score < scores.get((k,l), float('inf')):
                        scores[(k,l)] = new_score
                        heappush(heap,(new_score,g+1,k,l))
        return -1

773. 滑动谜题 —-> A*搜索(写的有问题)

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
class Solution:
    def slidingPuzzle(self, board: List[List[int]]) -> int:
        # d = {0:[1,3],
        #      1:[0,2,4],
        #      2:[1,5],
        #      3:[0,4],
        #      4:[1,3,5],
        #      5:[2,4]}

        # s = ''.join([str(c) for row in board for c in row])
        # q, visited, count = [s], set(), 0
        # while q:
        #     next_q = []
        #     for s in q:
        #         visited.add(s)
        #         if s == '123450':
        #             return count
        #         loc = s.index('0')
        #         arr = list(s)
        #         for i in d[loc]:
        #             new_arr = arr[:]
        #             new_arr[loc], new_arr[i] = new_arr[i], new_arr[loc]
        #             new_s = ''.join(new_arr)
        #             if new_s not in visited:
        #                 next_q.append(new_s)
        #     q = next_q
        #     count += 1
        # return -1


        d = [[1,3], [0,2,4], [1,5], [0,4], [1,3,5], [2,4]]
        board = board[0] + board[1]
        q, visited = [(tuple(board), board.index(0), 0)], set()
        while q:
            state, loc, count = q.pop(0)
            if state == (1,2,3,4,5,0):
                return count
            visited.add(state)
            for i in d[loc]:
                new = list(state)
                new[i], new[loc] = new[loc], new[i]
                new = tuple(new)
                if new not in visited:
                    q.append((new, new.index(0), count+1))
        return -1


        # scores = [0]*6
        # trues = {0:[1,2],
        #          1:[0,0],
        #          2:[0,1],
        #          3:[0,2],
        #          4:[1,0],
        #          5:[1,1]}
        # for num in range(6):
        #     scores[num] = [[abs(trues[num][0]-i)+abs(trues[num][1]-j) for j in range(3)] for i in range(2)]

        # def calc(new):
        #     board = []
        #     new = list(new)
        #     board.append(new[:3])
        #     board.append(new[3:])
        #     return sum([scores[board[i][j]][i][j] for i in range(2) for j in range(3)])

        # d = [[1,3], [0,2,4], [1,5], [0,4], [1,3,5], [2,4]]
        # board = board[0] + board[1]
        # q, visited = [(0, tuple(board), board.index(0), 0)], set()
        # while q:
        #     score, state, loc, count = heappop(q)
        #     if state == (1,2,3,4,5,0):
        #         return count
        #     visited.add(state)
        #     for i in d[loc]:
        #         new = list(state)
        #         new[i], new[loc] = new[loc], new[i]
        #         new = tuple(new)
        #         if new not in visited:
        #             heappush(q, (calc(new)+count+1, new, new.index(0), count+1))
        # return -1

位运算

191. 位1的个数 (2021.6.17)

1
2
3
4
5
6
7
class Solution:
    def hammingWeight(self, n: int) -> int:
        count = 0
        while n != 0:
            count += 1
            n &= n-1
        return count

231. 2 的幂 (2021.6.17)

1
2
3
class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        return (n != 0) and (n & n-1 == 0)

190. 颠倒二进制位 (2021.6.17)

1
2
3
4
5
6
7
class Solution:
    def reverseBits(self, n: int) -> int:
        res = 0
        for _ in range(32):
            res = (res << 1) + (n & 1)
            n >>= 1
        return res

52. N皇后 II (2021.6.17)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def totalNQueens(self, n: int) -> int:
        if n < 1: return 0
        self.count = 0
        self.dfs(n, 0, 0, 0, 0)
        return self.count

    def dfs(self, n, row, col, pie, na):
        if row >= n:
            self.count += 1
            return

        bits = (~(col | pie | na) & ((1 << n) - 1))
        while bits:
            p = bits & (-bits)
            bits &= (bits - 1)
            self.dfs(n, row+1, col|p, (p|pie)>>1, (p|na)<<1)

338. 比特位计数 (2021.6.17)

1
2
3
4
5
6
class Solution:
    def countBits(self, n: int) -> List[int]:
        dp = [0]
        for i in range(1, n + 1):
            dp.append(dp[i & (i-1)] + 1)
        return dp

LRU Cache

146. LRU 缓存机制 (2021.6.17)

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
# class LRUCache:

#     def __init__(self, capacity: int):
#         self.dic = collections.OrderedDict()
#         self.remain = capacity


#     def get(self, key: int) -> int:
#         if key in self.dic:
#             value = self.dic.pop(key)
#             self.dic[key] = value
#             return value
#         return -1


#     def put(self, key: int, value: int) -> None:
#         if key in self.dic:
#             self.dic.pop(key)
#         else:
#             if self.remain > 0:
#                 self.remain -= 1
#             else:
#                 self.dic.popitem(last=False)
#         self.dic[key] = value


class DLinkedNode:
    def __init__(self, key=0, value=0):
        self.key = key
        self.value = value
        self.pre = None
        self.nex = None


class LRUCache:

    def __init__(self, capacity: int):
        self.dic = {}
        self.remain = capacity
        self.head = DLinkedNode()
        self.tail = DLinkedNode()
        self.head.nex = self.tail
        self.tail.pre = self.head


    def get(self, key: int) -> int:
        if key in self.dic:
            node = self.dic[key]
            self.removeToHead(node)
            return node.value
        return -1


    def put(self, key: int, value: int) -> None:
        if key in self.dic:
            node = self.dic[key]
            node.value = value
            self.removeToHead(node)
        else:
            if self.remain > 0:
                self.remain -= 1
            else:
                self.removeTail()
            node = DLinkedNode(key, value)
            self.dic[key] = node
            self.addToHead(node)


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


    def addToHead(self, node):
        node.pre = self.head
        node.nex = self.head.nex
        self.head.nex.pre = node
        self.head.nex = node

    def removeNode(self, node):
        node.pre.nex = node.nex
        node.nex.pre = node.pre


    def removeTail(self):
        node = self.tail.pre
        self.dic.pop(node.key)
        self.removeNode(node)


# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)

排序算法 (2021.6.17)

初级排序 - O(n^2)

冒泡排序

1
2
3
4
5
6
7
def bubble_sort(array):
    n = len(array)
    for i in range(n):
        for j in range(n-i-1):
            if array[j] > array[j+1]:
                array[j], array[j+1] = array[j+1], array[j]
    return array

插入排序

1
2
3
4
5
6
7
8
9
def insertion_sort(array):
    for i in range(1, len(array)):
        key = array[i]
        j = i - 1
        while j >= 0 and array[j] > key:
            array[j+1] = array[j]
            j -= 1
        array[j+1] = key
    return array

选择排序

1
2
3
4
5
6
7
8
def selection_sort(array):
    for i in range(len(array)):
        idx = i
        for j in range(i+1, len(array)):
            if array[idx] > array[j]:
                idx = j
        array[i], array[idx] = array[idx], array[i]
    return array

高级排序 - O(N*LogN)

快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from random import randint

def quick_sort(array):
    if len(array) < 2:
        return array
    pivot = array[randint(0, len(array)-1)]
    low, same, high = [], [], []
    for i in array:
        if i > pivot:
            high.append(i)
        elif i == pivot:
            same.append(i)
        else:
            low.append(i)
    return quick_sort(low) + same + quick_sort(high)

归并排序

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
def merge(left, right):
    if len(left) == 0:
        return right
    if len(right) == 0:
        return left

    res, left_index, right_index = [], 0, 0

    while len(res) < len(left) + len(right):
        if left[left_index] < right[right_index]:
            res.append(left[left_index])
            left_index += 1
        else:
            res.append(right[right_index])
            right_index += 1

        if len(left) == left_index:
            res += right[right_index:]
            break

        if len(right) == right_index:
            res += left[left_index:]
            break
    return res


def merge_sort(array):
    if len(array) < 2:
        return array

    mid = len(array) >> 1

    return merge(left = merge_sort(array[:mid]),
                  right = merge_sort(array[mid:]))

堆排序(2021.6.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
def heapify(arr, n, i):

    large = i
    left = 2 * i + 1
    right = 2 * i + 2

    if left < n and arr[large] < arr[left]:
        large = left
    if right < n and arr[large] < arr[right]:
        large = right

    if large != i:
        arr[large], arr[i] = arr[i], arr[large]

        heapify(arr, n, large)


def heap_sort(arr):

    n = len(arr)
    for i in range(n//2 -1, -1, -1):
        heapify(arr, n, i)

    for j in range(n-1, 0, -1):
        arr[j], arr[0] = arr[0], arr[j]
        heapify(arr, j, 0)

    return arr

1122. 数组的相对排序 (2021.6.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
class Solution:
    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:
        # count, index = 0, 0
        # for item in arr2:
        #     for i in range(index, len(arr1)):
        #         if arr1[i] == item:
        #             arr1[i], arr1[count] = arr1[count], arr1[i]
        #             count += 1
        #     index = count
        # return arr1[:index] + sorted(arr1[index:])


        # def compare(x):
        #     return (0, rank[x]) if x in rank else (1, x)

        # rank = {x:i for i, x in enumerate(arr2)}
        # arr1.sort(key=compare)
        # return arr1


        upper = max(arr1)
        freq = [0] * (upper + 1)
        ans = []

        for x in arr1:
            freq[x] += 1
        for i in arr2:
            ans.extend([i]*freq[i])
            freq[i] = 0
        for j in range(upper + 1):
            if freq[j] > 0:
                ans.extend([j]*freq[j])
        return ans

56. 合并区间 (2021.6.18)

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:

        intervals.sort(key=lambda x: x[0])
        ans = []

        for interval in intervals:
            if not ans or interval[0] > ans[-1][1]:
                ans.append(interval)
            else:
                ans[-1][1] = max(ans[-1][1], interval[1])
        return ans

493. 翻转对 (2021.6.18)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        if not nums:
            return 0
        return self.mergesort(nums)[1]


    def mergesort(self, nums):
        if len(nums) < 2:
            return nums, 0
        mid = len(nums) >> 1
        left, cnt1 = self.mergesort(nums[:mid])
        right, cnt2 = self.mergesort(nums[mid:])
        cnt = cnt1 + cnt2
        for r in right:
            temp = len(left) - bisect.bisect(left, 2*r)
            if temp == 0:
                break
            cnt += temp
        return sorted(left + right), cnt

剑指 Offer 51. 数组中的逆序对 (2021.6.18)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        if not nums:
            return 0
        return self.mergesort(nums)[1]


    def mergesort(self, nums):
        if len(nums) <= 1:
            return nums, 0
        m = len(nums)//2
        left, countl = self.mergesort(nums[:m])
        right, countr = self.mergesort(nums[m:])
        count = countl + countr
        for r in right:
            temp = len(left) - bisect.bisect(left, r)
            if temp == 0:
                break
            count += temp
        return sorted(left+right), count

高级动态规划

64. 最小路径和 (2021.6.19)

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        dp = grid
        for j in range(1, len(grid[0])):
            dp[0][j] += dp[0][j-1]
        for i in range(1, len(grid)):
            dp[i][0] += dp[i-1][0]
        for i in range(1, len(grid)):
            for j in range(1, len(grid[0])):
                dp[i][j] += min(dp[i-1][j], dp[i][j-1])
        return dp[-1][-1]

121. 买卖股票的最佳时机 (2021.6.19)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        # dp = [[0]*2 for _ in range(len(prices))]
        # dp[0][0], dp[0][1] = 0, -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], - prices[i])
        # return dp[-1][0]

        dp_0_0, dp_0_1 = 0, -prices[0]
        for i in range(1, len(prices)):
            dp_0_0 = max(dp_0_0, dp_0_1+prices[i])
            dp_0_1 = max(dp_0_1, -prices[i])
        return dp_0_0

122. 买卖股票的最佳时机 II (2021.6.19)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        # dp = [[0, 0] for i in range(len(prices))]
        # dp[0][0], dp[0][1] = 0, -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]

        # res = 0
        # for i in range(1, len(prices)):
        #     if prices[i] > prices[i-1]:
        #         res += prices[i] - prices[i-1]
        # return res

        dp_0_0, dp_0_1 = 0, -prices[0]
        for i in range(1, len(prices)):
            dp_0_0 = max(dp_0_0, dp_0_1 + prices[i])
            dp_0_1 = max(dp_0_1, dp_0_0 - prices[i])
        return dp_0_0

123. 买卖股票的最佳时机 III (2021.6.19)

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        dp_i_1_0 = dp_i_2_0 = 0
        dp_i_1_1 = dp_i_2_1 = -prices[0]

        for i in range(1, len(prices)):
            dp_i_1_0 = max(dp_i_1_0, dp_i_1_1 + prices[i])
            dp_i_1_1 = max(dp_i_1_1, -prices[i])
            dp_i_2_0 = max(dp_i_2_0, dp_i_2_1 + prices[i])
            dp_i_2_1 = max(dp_i_2_1, dp_i_1_0 - prices[i])
        return dp_i_2_0

188. 买卖股票的最佳时机 IV (2021.6.19)

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:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        # if not prices:
        #     return 0

        # k = min(k, len(prices)//2)
        # sell = [[0]*(k+1) for _ in range(len(prices))]
        # buy = [[0]*(k+1) for _ in range(len(prices))]

        # for j in range(0, k+1):
        #     sell[0][j] = 0
        #     buy[0][j] = -prices[0]

        # for i in range(1, len(prices)):
        #     for j in range(1, k+1):
        #         sell[i][j] = max(sell[i-1][j], buy[i-1][j] + prices[i])
        #         buy[i][j] = max(buy[i-1][j], sell[i-1][j-1] - prices[i])
        # return sell[-1][k]


        if not prices:
            return 0

        k = min(k, len(prices)//2)
        sell = [0]*(k+1)
        buy = [0]*(k+1)

        for j in range(0, k+1):
            sell[j] = 0
            buy[j] = -prices[0]

        for i in range(1, len(prices)):
            for j in range(1, k+1):
                sell[j] = max(sell[j], buy[j] + prices[i])
                buy[j] = max(buy[j], sell[j-1] - prices[i])
        return sell[k]

309. 最佳买卖股票时机含冷冻期 (2021.6.19)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        # dp = [[0]*2 for _ in range(len(prices))]
        # dp[0][0], dp[0][1], dp_pre = 0, -prices[0], 0
        # for i in range(1, len(prices)):
        #     temp = dp[i-1][0]
        #     dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
        #     dp[i][1] = max(dp[i-1][1], dp_pre - prices[i])
        #     dp_pre = temp
        # return dp[-1][0]

        dp_i_0, dp_i_1, dp_pre = 0, -prices[0], 0
        for i in range(1, len(prices)):
            temp = dp_i_0
            dp_i_0 = max(dp_i_0, dp_i_1 + prices[i])
            dp_i_1 = max(dp_i_1, dp_pre - prices[i])
            dp_pre = temp
        return dp_i_0

剑指 Offer 63. 股票的最大利润 (2021.6.19)

1
2
3
4
5
6
7
8
9
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if not prices:
            return 0
        dp_0_0, dp_0_1 = 0, -prices[0]
        for i in range(1, len(prices)):
            dp_0_0 = max(dp_0_0, dp_0_1 + prices[i])
            dp_0_1 = max(dp_0_1, - prices[i])
        return dp_0_0

714. 买卖股票的最佳时机含手续费 (2021.6.19)

1
2
3
4
5
6
7
class Solution:
    def maxProfit(self, prices: List[int], fee: int) -> int:
        dp_i_0, dp_i_1 = 0, -prices[0]-fee
        for i in range(len(prices)):
            dp_i_0 = max(dp_i_0, dp_i_1 + prices[i])
            dp_i_1 = max(dp_i_1, dp_i_0 - prices[i] - fee)
        return dp_i_0

746. 使用最小花费爬楼梯 (2021.6.19)

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        # dp = [0]*(len(cost)+1)
        # for i in range(2, len(dp)):
        #     dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2])
        # return dp[-1]

        dp_0 = dp_1 = 0
        for i in range(1, len(cost)):
            dp_1, dp_0 = min(dp_1 + cost[i], dp_0 + cost[i-1]), dp_1
        return dp_1

72. 编辑距离 (2021.6.19)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m, n = len(word1), len(word2)
        if n * m == 0:
            return n + m

        dp = [[0]*(n+1) for _ in range(m+1)]
        dp[0] = [i for i in range(n+1)]
        for i in range(m+1):
            dp[i][0] = i

        for i in range(1, m+1):
            for j in range(1, n+1):
                if word1[i-1] == word2[j-1]:
                    dp[i][j] = dp[i-1][j-1]
                else:
                    dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1
        return dp[-1][-1]

300. 最长递增子序列 (2021.6.19)

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:
    def lengthOfLIS(self, nums: List[int]) -> int:
        # n = len(nums)
        # dp = [1]*n
        # for i in range(1, n):
        #     for j in range(i):
        #         if nums[i] > nums[j]:
        #             dp[i] = max(dp[i], dp[j]+1)
        # return max(dp)

        tail = []
        for x in nums:
            if not tail or x > tail[-1]:
                tail.append(x)
            else:
                l, r = 0, len(tail)-1
                while l <= r:
                    mid = (l+r) >> 1
                    if tail[mid] >= x:
                        loc = mid
                        r = mid - 1
                    else:
                        l = mid + 1
                tail[loc] = x
        return len(tail)

91. 解码方法 (2021.6.20)

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

        n = len(s)
        f0, f1, f2 = 0, 1, 0
        for i in range(1, n+1):
            f2 = 0
            if s[i-1] != '0':
                f2 += f1
            if i > 1 and s[i-2] != '0' and int(s[i-2:i]) <= 26:
                f2 += f0
            f1, f0 = f2, f1
        return f2

32. 最长有效括号 (2021.6.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
class Solution:
    def longestValidParentheses(self, s: str) -> int:
        # stack, res = [-1], 0
        # for index, char in enumerate(s):
        #     if char == '(':
        #         stack.append(index)
        #     else:
        #         stack.pop()
        #         if not stack:
        #             stack.append(index)
        #         else:
        #             res = max(res, index - stack[-1])
        # return res

        n = len(s)
        if n == 0:
            return 0

        dp = [0]*n
        for i in range(n):
            if s[i] == ")":
                pre = i- dp[i-1] -1
                if pre >= 0 and s[pre] == "(":
                    dp[i] = dp[i-1] + 2
                    if pre > 0:
                        dp[i] += dp[pre-1]
        return max(dp)

85. 最大矩形 (2021.6.21)

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:
    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        if not matrix or not matrix[0]:
            return 0
        # row, col = len(matrix), len(matrix[0])
        # width = [[0]*col for _ in range(row)]
        # for i in range(row):
        #     for j in range(col):
        #         if j == '0':
        #             width[i][j] = matrix[i][j]
        #         elif matrix[i][j] == '1':
        #             width[i][j] = width[i][j-1] + 1

        # res = 0
        # for i in range(row):
        #     for j in range(col):
        #         if matrix[i][j] == '0':
        #             continue
        #         wid = width[i][j]
        #         area = wid
        #         for k in range(i-1,-1,-1):
        #             wid = min(wid, width[k][j])
        #             area = max(area, wid*(i-k+1))
        #         res = max(res, area)
        # return res

        col = len(matrix[0])
        height = [0] * (col + 1)
        area = 0
        for row in matrix:
            for j in range(col):
                height[j] = height[j] + 1 if row[j] == '1' else 0

            stack= [-1]
            for i in range(col+1):
                while height[i] < height[stack[-1]]:
                    h = height[stack.pop()]
                    w = i - stack[-1] -1
                    area = max(area, w*h)
                stack.append(i)
        return area

115. 不同的子序列 (2021.6.21)

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        row, col = len(t), len(s)
        if row > col:
            return 0
        dp = [[1]*(col+1)] + [[0]*(col+1) for _ in range(row)]
        for i in range(1, row+1):
            for j in range(1, col+1):
                if t[i-1] == s[j-1]:
                    dp[i][j] = dp[i-1][j-1] + dp[i][j-1]
                else:
                    dp[i][j] = dp[i][j-1]
        return dp[-1][-1]

818. 赛车 (2021.6.21)

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    dp = {0:0}
    def racecar(self, target: int) -> int:
        if target in self.dp:
            return self.dp[target]
        n = target.bit_length()
        if 2**n - 1 == target:
            self.dp[target] = n
        else:
            self.dp[target] = self.racecar(2**n -1 - target)  + n + 1
            for i in range(n-1):
                self.dp[target] = min(self.dp[target], self.racecar(target - 2**(n-1) + 2**i) + n + i + 1)
        return self.dp[target]

字符串

709. 转换成小写字母 (2021.7.1)

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def toLowerCase(self, s: str) -> str:
        for i in s:
            if 65 <= ord(i) <= 90:
                s = s.replace(i, chr(ord(i) + 32))
        return s

        # new = ""
        # for i in s:
        #     if 65 <= ord(i) <= 90:
        #         i = chr(ord(i) + 32)
        #     new += i
        # return new

58. 最后一个单词的长度 (2021.7.1)

1
2
3
4
5
6
7
8
class Solution:
    def lengthOfLastWord(self, s: str) -> int:
        s_ = s.split()
        # if len(s_) == 0:
        #     return 0
        # else:
        #     return len(s_[-1])
        return 0 if len(s_) == 0 else len(s_[-1])

771. 宝石与石头 (2021.7.1)

1
2
3
4
5
6
7
class Solution:
    def numJewelsInStones(self, jewels: str, stones: str) -> int:
        count = 0
        for char in stones:
            if char in jewels:
                count += 1
        return count

387. 字符串中的第一个唯一字符 (2021.7.1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def firstUniqChar(self, s: str) -> int:
        # fre = [0]*256
        # for i in s:
        #     fre[ord(i)] += 1
        # for index, j in enumerate(s):
        #     if fre[ord(j)] == 1:
        #         return index
        # return -1

        fre = collections.Counter(s)
        for index, char in enumerate(s):
            if fre[char] == 1:
                return index
        return -1

8. 字符串转换整数 (atoi) (2021.7.1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import re
class Solution:
    def myAtoi(self, s: str) -> int:
        # if len(s) == 0: return 0
        # ls = list(s.strip())
        # if len(ls) == 0:
        #     return 0
        # sign = -1 if ls[0] == "-" else 1
        # if ls[0] in ['+', '-']:
        #     del ls[0]
        # index, res = 0, 0
        # while index < len(ls) and ls[index].isdigit():
        #     res = res * 10 + ord(ls[index]) - ord('0')
        #     index += 1
        # return max(-2**31, min(res*sign, 2**31-1))

        ls = re.findall(r'^[-\+]?\d+', s.lstrip())
        try:
            res = int(''.join(ls))
            return max(-2**31, min(res, 2**31-1))
        except:
            return 0

14. 最长公共前缀 (2021.7.1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        # res = ''
        # for index, char in enumerate(strs[0]):
        #     for s in strs[1:]:
        #         if index > len(s)-1 or s[index] != char:
        #             return res
        #     res += char
        # return res


        res = ''
        for i in zip(*strs):
            if len(set(i)) == 1:
                res += i[0]
            else:
                break
        return res

344. 反转字符串 (2021.7.1)

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        left, right = 0, len(s)-1
        while left < right:
            s[left], s[right] = s[right], s[left]
            left += 1
            right -= 1
        return s

541. 反转字符串 II (2021.7.1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def reverseStr(self, s: str, k: int) -> str:
        # ls = list(s)
        # for i in range(0, len(ls), 2*k):
        #     ls[i:i+k] = reversed(ls[i:i+k])
        # return ''.join(ls)


        ls = list(s)
        for i in range(0, len(ls), 2*k):
            left, right = i, min(i+k-1, len(ls)-1)
            while left < right:
                ls[left], ls[right] = ls[right], ls[left]
                left += 1
                right -= 1
        return ''.join(ls)

151. 翻转字符串里的单词 (2021.7.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
class Solution:
    def reverseWords(self, s: str) -> str:
        return ' '.join(reversed(s.split()))

        # ls = s.split()
        # left, right = 0, len(ls)-1
        # while left < right:
        #     ls[left], ls[right] = ls[right], ls[left]
        #     left += 1
        #     right -= 1
        # return ' '.join(ls)

        # left, right = 0, len(s)-1
        # while left <= right and s[left] == ' ':
        #     left += 1
        # while left <= right and s[right] == ' ':
        #     right -= 1
        # d, word = collections.deque(), []
        # while left <= right:
        #     if s[left] == ' ' and word:
        #         d.appendleft(''.join(word))
        #         word = []
        #     elif s[left] != ' ':
        #         word.append(s[left])
        #     left += 1
        # d.appendleft(''.join(word))
        # return " ".join(d)

557. 反转字符串中的单词 III (2021.7.1)

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def reverseWords(self, s: str) -> str:
        # ls = s.split()
        # res = []
        # for word in ls:
        #     res.append(''.join(reversed(word)))
        # return ' '.join(res)

        # return ' '.join(word[::-1] for word in s.split())

        return ' '.join(s.split()[::-1])[::-1]

917. 仅仅反转字母 (2021.7.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:
    def reverseOnlyLetters(self, s: str) -> str:
        d = [char for char in s if char.isalpha()]
        res = []
        for i in s:
            if i.isalpha():
                res.append(d.pop())
            else:
                res.append(i)
        return ''.join(res)

        # ls = list(s)
        # left, right = 0, len(ls)-1
        # while left < right:
        #     while left < right and not ls[left].isalpha():
        #         left += 1
        #     while left < right and not ls[right].isalpha():
        #         right -= 1
        #     ls[left], ls[right] = ls[right], ls[left]
        #     left += 1
        #     right -= 1
        # return ''.join(ls)

438. 找到字符串中所有字母异位词 (2021.7.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
from collections import Counter
class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        # lp, res = len(p), []
        # pc = Counter(p)
        # sc = Counter(s[:len(p)-1])
        # for i in range(0, len(s)-len(p)+1):
        #     sc[s[i+lp-1]] += 1
        #     if pc == sc: res.append(i)
        #     sc[s[i]] -= 1
        #     if sc[s[i]] == 0:
        #         del sc[s[i]]
        # return res


        pc = [0]*26
        sc = [0]*26
        res = []
        if len(s) < len(p): return res
        for i in range(len(p)):
            pc[ord(p[i])-ord('a')] += 1
            sc[ord(s[i])-ord('a')] += 1
        if pc == sc: res.append(0)
        for j in range(len(p), len(s)):
            sc[ord(s[j])-ord('a')] += 1
            sc[ord(s[j-len(p)])-ord('a')] -= 1
            if pc == sc:
                res.append(j-len(p)+1)
        return res

125. 验证回文串 (2021.7.1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def isPalindrome(self, s: str) -> bool:
        # ls = list(s)
        # left, right = 0, len(ls)-1
        # while left < right:
        #     while left < right and not ls[left].isalnum():
        #         left += 1
        #     while left < right and not ls[right].isalnum():
        #         right -= 1
        #     if ls[left].lower() != ls[right].lower():
        #         return False
        #     left += 1
        #     right -= 1
        # return True

        ls = ''.join(char.lower() for char in s if char.isalnum())
        return ls == ls[::-1]

680. 验证回文字符串 Ⅱ (2021.7.1)

1
2
3
4
5
6
7
8
9
10
class Solution:
    def validPalindrome(self, s: str) -> bool:
        left, right = 0, len(s)-1
        while left < right:
            if s[left] != s[right]:
                first, second = s[left:right], s[left+1:right+1]
                return first == first[::-1] or second == second[::-1]
            left += 1
            right -= 1
        return True

最长公共子串 (2021.7.1)

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def longestCommonSubstring(self, text1: str, text2: str) -> int:
        if not text1 or not text2:
            return 0
        m, n = len(text1), len(text2)
        dp = [[0]*(n+1) for _ in range(m+1)]
        for i in range(1, m+1):
            for j in range(1, n+1):
                if text1[i-1] == text2[j-1]:
                    dp[i][j] = dp[i-1][j-1] + 1
                else:
                    dp[i][j] = 0
        return max(max(row) for row in dp)

5. 最长回文子串 (2021.7.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
# class Solution:
#     def longestPalindrome(self, s: str) -> str:
#         res = ''
#         for i in range(len(s)):
#             res = max(self.helper(i, i, s), self.helper(i, i+1, s), res, key=len)
#         return res

#     def helper(self, l, r, s):
#         while l >= 0 and r < len(s) and s[l] == s[r]:
#             l -= 1
#             r += 1
#         return s[l+1:r]


class Solution:
    def longestPalindrome(self, s: str) -> str:
        n, max_len, res = len(s), 1, s[0]
        if n < 2: return s

        dp = [[False]*n for _ in range(n)]
        for i in range(n):
            for j in range(i):
                if s[i] == s[j] and (i-j+1 <= 3 or dp[i-1][j+1]):
                    dp[i][j] = True
                    if i-j+1 > max_len:
                        max_len = i-j+1
                        res = s[j:i+1]
        return res

10. 正则表达式匹配 (2021.7.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
35
36
37
38
39
class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        # if not p: return not s
        # first_match = bool(s) and p[0] in ['.', s[0]]
        # if len(p) >=2 and p[1] == '*':
        #     return (first_match and self.isMatch(s[1:], p)) or self.isMatch(s, p[2:])
        # return first_match and self.isMatch(s[1:], p[1:])


        # ls, lp = len(s), len(p)
        # memo = {}
        # def dp(i, j):
        #     if (i, j) in memo: return memo[(i, j)]
        #     if j == lp: return i == ls
        #     first_match = (i < ls) and p[j] in [s[i], '.']
        #     if j <= lp - 2 and p[j+1] == "*":
        #         tmp = dp(i, j+2) or (first_match and dp(i+1, j))
        #     else:
        #         tmp = first_match and dp(i+1, j+1)
        #     memo[(i, j)] = tmp
        #     return tmp
        # return dp(0, 0)


        m, n = len(p), len(s)
        dp = [[False]*(n+1) for _ in range(m+1)]
        dp[0][0] = True
        for i in range(2, m+1):
            dp[i][0] = dp[i-2][0] and p[i-1] == '*'

        for i in range(1, m+1):
            for j in range(1, n+1):
                if p[i-1] != '*':
                    dp[i][j] = dp[i-1][j-1] and (p[i-1] in [s[j-1], '.'])
                else:
                    dp[i][j] = dp[i-2][j]
                    if p[i-2] in [s[j-1], '.']:
                        dp[i][j] |= dp[i][j-1]
        return dp[-1][-1]

44. 通配符匹配 (2021.7.2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        m, n = len(s), len(p)
        dp = [[False]*(n+1) for _ in range(m+1)]
        dp[0][0] = True
        for j in range(1, n+1):
            if p[j-1] == '*':
                dp[0][j] = True
            else:
                break

        for i in range(1, m+1):
            for j in range(1, n+1):
                if p[j-1] == '*':
                    dp[i][j] = dp[i][j-1] or dp[i-1][j]
                else:
                    dp[i][j] = dp[i-1][j-1] and p[j-1] in [s[i-1], '?']
        return dp[-1][-1]

205. 同构字符串 (2021.7.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
class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        # n, st, ts = len(s), {}, {}
        # if n == 0: return False

        # for i in range(len(s)):
        #     if s[i] in st and st[s[i]] != t[i]:
        #         return False
        #     if t[i] in ts and ts[t[i]] != s[i]:
        #         return False
        #     st[s[i]] = t[i]
        #     ts[t[i]] = s[i]
        # return True


        # sl, tl = [0]*256, [0]*256
        # for i in range(len(s)):
        #     if sl[ord(s[i])] != tl[ord(t[i])]:
        #         return False
        #     sl[ord(s[i])] = i+1
        #     tl[ord(t[i])] = i+1
        # return True


        return len(set(zip(s,t))) == len(set(s)) == len(set(t))
-------------本文结束感谢您的阅读-------------