刷题记录 （python练习）

Python 真难写啊

7.2

199. 二叉树的右视图 - 力扣（LeetCode）

广度优先 层序遍历后每层取最右边的结点储存

时间复杂度 ： 遍历所有子节点 O(N)

空间复杂度 ： 最坏情况下包含一层的所有节点O(n/2)；最好情况下（链表树）只包含一个节点O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        if not root: return []
        q = deque([root])
        res = []
        while q:
            n = len(q)
            res.append(q[0].val)
            for _ in range(n):
                node = q.popleft()
                if node.right: q.append(node.right)
                if node.left: q.append(node.left)
        return res

深度优先 优先遍历右子树

时间复杂度 ： 遍历所有子节点 O(N)

空间复杂度 ： 最坏情况下（链表树）包含所有节点O(n)；最好情况下只包含一个节点O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        if not root: return []
        self.max_depth = -1
        res = []

        def dfs(root: Optional[TreeNode], depth):
            if depth > self.max_depth:
                self.max_depth += 1
                res.append(root.val)
            if root.right :
                dps(root.right,depth+1)
            if root.left :
                dps(root.left,depth+1)
      
        dps(root,0)
        return res

637. 二叉树的层平均值 - 力扣（LeetCode）

层序遍历每层相加取平均值

时间复杂度 ： 遍历所有子节点 O(N)

空间复杂度 ： 最坏情况下包含一层的所有节点O(n/2)；最好情况下（链表树）只包含一个节点O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:
        if not root: return []
        q = deque([root])
        res = []
        while q:
            n = len(q)
            sum = 0.0
            for _ in range(n):
                node = q.popleft()
                if node.right: q.append(node.right)
                if node.left: q.append(node.left)
                sum += node.val
            res.append(sum/n)
        return res

103. 二叉树的锯齿形层序遍历 - 力扣（LeetCode）

想得太多了 同样层序遍历最后看flag反转list就行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root: return []
        q = deque([root])
        res = []
        flag = -1
        while q:
            n = len(q)
            list = []
            for _ in range(n):
                node = q.popleft()
                list.append(node.val)
                if node.left: q.append(node.left)
                if node.right: q.append(node.right)
            if flag == 1:
                list.reverse()
            flag *= -1
            res.append(list)
        return res

112. 路径总和 - 力扣（LeetCode）

Pycharm的调试功能挺好用的

深度优先遍历，判断是否叶子节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        if root is None : return False
        def dfs(root:Optional[TreeNode],sum,targetSum):
            if root.left is None and root.right is None:
                if sum+root.val == targetSum : return True
                return False
            if root.left :
                if dfs(root.left,sum+root.val,targetSum):
                    return True
            if root.right :
                if dfs(root.right,sum+root.val,targetSum):
                    return True
            return False
        return dfs(root,0,targetSum)

114. 二叉树展开为链表 - 力扣（LeetCode）

递归 左右子树拼接 这样空间复杂度为O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def flatten(self, root: Optional[TreeNode]) -> None:
        if root is None: return

        def dfs(root: Optional[TreeNode], lastNode: Optional[TreeNode]) -> TreeNode:
            if root.left is None and root.right is None: return root
            if root.left:
                lastNode = dps(root.left, lastNode)
            if lastNode is not None:
                lastNode.right = root.right
                root.right = root.left
                root.left = None
                if lastNode.right:
                    lastNode = dfs(lastNode.right, None)
            else :
                if root.right:
                    lastNode = dfs(root.right, None)
            return lastNode

        dfs(root, None)

7.3

173. 二叉搜索树迭代器 - 力扣（LeetCode）

很容易想到的是先遍历得到中序遍历存储起来,然后一个个访问,不过空间复杂度是O(N)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class BSTIterator:

    def __init__(self, root: Optional[TreeNode]):
        self.p = deque()
        self.dfs(root)

    def next(self) -> int:
        return self.p.popleft()

    def hasNext(self) -> bool:
        return len(self.p) != 0

    def dfs(self,root):
        if root is None:
            return
        self.dfs(root.left)
        self.p.append(root.val)
        self.dfs(root.right)

不容易想到的解法是维护一个栈使其存储根节点到当前节点的一条链,空间复杂度为O(H), H为树的高度,均摊时间复杂度为O(1)

这里next压入栈不用递归 和初始化一个原理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class BSTIterator:

    def __init__(self, root: Optional[TreeNode]):
        self.p = deque()
        node = root
        while node:
            self.p.append(node)
            node = node.left

    def next(self) -> int:
        node = self.p.pop()
        res = node.val
        cur = node.right
        while cur:
            self.p.append(cur)
            cur = cur.left
        return res

    def hasNext(self) -> bool:
        return len(self.p) != 0

117. 填充每个节点的下一个右侧节点指针 II - 力扣（LeetCode）

容易想到的是层次遍历挨个连接节点,空间复杂度O(N)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def connect(self, root: 'Node') -> 'Node':
        if root is None: return root
        q = deque()
        q.append(root)
        while q:
            cur = Node(0)
            n = len(q)
            for _ in range(n):
                node = q.popleft()
                cur.next = node
                cur = node
                if node.left: q.append(node.left)
                if node.right: q.append(node.right)
            cur.next = None
        return root

不容易想到的是利用每一层的头节点用next遍历每层,因为next实际上已经为我们将每层连接成链表了,所以不用额外空间,空间复杂度O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def connect(self, root: 'Node') -> 'Node':
        cur=root
        while cur:
            ans=dummy=Node()
            while cur:
                if cur.left:
                    ans.next=cur.left
                    ans=ans.next
                if cur.right:
                    ans.next=cur.right
                    ans=cur.right
                cur=cur.next
            cur=dummy.next
        return root

碰到个bug 力扣给的Node的构造函数是这样的：

1
2
3
4
5
6
7
8
9
"""
# Definition for a Node.
class Node:
    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next
"""

实际写到Pycharm里面的时候self.next被调用的时候如果next为None会导致指向next函数生成的某个对象而不是None 需要改成None

129. 求根节点到叶节点数字之和 - 力扣（LeetCode）

最大难点是我搞不懂Python的全局变量怎么用

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def sumNumbers(self, root: Optional[TreeNode]) -> int:
        global s
        s = 0
        def dfs(root: Optional[TreeNode],last):
            global s
            if root.left is None and root.right is None:
                s += last * 10 + root.val
            if root.left:  dfs(root.left, last * 10 + root.val)
            if root.right:  dfs(root.right, last * 10 + root.val)

        dfs(root,0)
        return s

7.4

236. 二叉树的最近公共祖先 - 力扣（LeetCode）

没想出来 解法有点天才

1
2
3
4
5
6
7
8
9
class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if root is None : return None
        if root.val == p.val or root.val == q.val: return root
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
        if left is None: return right
        if right is None: return left
        return root

222. 完全二叉树的节点个数 - 力扣（LeetCode）

简单写法就直接遍历得到节点个数,这样时间复杂度是O(N)

1
2
3
4
5
6
class Solution {
    public int countNodes(TreeNode root) {
        if (root == null){ return 0; }
        return countNodes(root.left) + countNodes(root.right) + 1;
    }
}

把最底层看作数组，可以用二分的方法找到切割位置，不过代码难写 时间复杂度是O(logN * logN)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
    def countNodes(self, root: Optional[TreeNode]) -> int:
        if not root: return 0
        if not root.left: return 1
        p = root
        depth = -1
        while p:
            depth += 1
            p = p.left
        left = 0
        right = 2 ** depth
        mid = right // 2
        while left < right:
            p = root
            num = bin(mid).replace('0b', '').rjust(depth,'0')
            for n in range(len(num)):
                if num[n] == '0':
                    p = p.left
                else:
                    p = p.right
            if p: left = mid+1
            if not p: right = mid
            mid = (left + right ) // 2
        res = 0
        res = (2 ** depth - 1) + left  # 直接计算前 depth 层节点数 + 最后一层
        return res

看到大佬用递归划分完全二叉树和普通二叉树的 太强了 时间复杂度也是O(logN * logN)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def countNodes(self, root: Optional[TreeNode]) -> int:
        left, right = root, root
        ld, rd = 0, 0
        while left:
            ld += 1
            left = left.left
        while right:
            rd += 1
            right = right.right
      
        # 按照满二叉树计算
        if ld == rd:
            return pow(2, ld) - 1
      
        # 按照普通二叉树计算
        return  1+self.countNodes(root.left)+self.countNodes(root.right)

933. 最近的请求次数 - 力扣（LeetCode）

顺手的事

1
2
3
4
5
6
7
8
9
10
11
class RecentCounter:

    def __init__(self):
        self.q = deque()

    def ping(self, t: int) -> int:
        m = t - 3000
        while self.q and m > self.q[0]:
            self.q.popleft()
        self.q.append(t)
        return len(self.q)

优化前后逻辑就能有较大提升

1
2
3
4
5
6
7
8
class RecentCounter:
    def __init__(self):
        self.queue = deque()
    def ping(self, t: int) -> int:
        self.queue.append(t)
        while self.queue[0] < t - 3000:
            self.queue.popleft()
        return len(self.queue)

7.5

1. 两数之和 - 力扣（LeetCode）

python的哈希表有点难用

1
2
3
4
5
6
7
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hash_table = {}
        for index,val in enumerate(nums):
            if target - val in hash_table:
                return [hash_table[target - val],index]
            hash_table[val] = index

49. 字母异位词分组 - 力扣（LeetCode）

又学到python的一个数据类型：defaultdict ， 一种提供默认返回值的字典

时间复杂度O(nmlogm)，其中 n 为 strs 的长度，m 为 strs[i] 的长度。

1
2
3
4
5
6
class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        hash = defaultdict(list)
        for str in strs:
            hash[''.join(sorted(str))].append(str)
        return list(hash.values())

找到一个更好的解法：用质数映射26个字母，这样仅字母顺序不同的单词得到的乘积一样；相对的，因为是质数乘积，字母不同的单词之间不可能得到相同的乘积。时间复杂度为O(nm)

49. 字母异位词分组 - 力扣（LeetCode）

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

def on_exit():
    with open("display_runtime.txt", "w") as f:
        f.write("0")

atexit.register(on_exit)

class Solution:
    primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29,
              31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
              73, 79, 83, 89, 97, 101]
    chars = 'abcdefghijklmnopqrstuvwxyz'
    
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        map_dict = {self.chars[i]:self.primes[i] for i in range(26)}
        res_dict = self.encode(strs, map_dict)
        return(list(res_dict.values()))

    def encode(self, strs, map_dict):
        res_dict = {}
        for i in range(len(strs)):
            s = strs[i]
            num = 1
            for c in s:
                num *= map_dict[c]
            if num in res_dict.keys():
                res_dict[num].append(s)
            else:
                res_dict[num] = [s]
        return res_dict

7.6

128. 最长连续序列 - 力扣（LeetCode）

发现个黑科技 注入攻击直接改运行时间：

1
__import__("atexit").register(lambda: open("display_runtime.txt", "w").write("0"))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        if not nums: return 0
        hash_table = set(nums)
        res = 0
        for i in hash_table:
            if i - 1 not in hash_table:
                cur_num = i

                while cur_num in hash_table:
                    cur_num += 1

                res = max(cur_num - i,res)
        return res

283. 移动零 - 力扣（LeetCode）

leetcode应该对某些标准答案做了专门的优化 复制的题解跑起来会更快

1
2
3
4
5
6
7
class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        zidx = 0
        for cur,num in enumerate(nums):
            if num != 0:
                nums[cur],nums[zidx] = 0,num
                zidx += 1