刷题记录合辑

标题不含题号，题号写在正文与 description 中。

12. Integer to Roman

思路
代码

思路

尝试1 - 模拟: 一个一个对应，进行整除然后看效果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def intToRoman(self, num: int) -> str:
        base  = [1000,900,500,400,100,90,50,40,10,9,5,4,1]
        symbol = ["M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"]
        
        res = []
        cnt = 0
        while num and cnt < 13:
            t = num // base[cnt] 
            for i in range(t):
                res.append(symbol[cnt])
            num = num % base[cnt]
            cnt += 1
        return ''.join(res)

总结
join 是字符串的方法，应该写成 ''.join(res)

112. Path Sum

思路
代码
二分查找
题解
二分查找

思路

尝试1 - dfs: 通过

改进1 - dfs: 通过

  • 将判断逻辑调整到之后
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# 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 hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        def dfs(node, x) -> bool:
            if x+node.val == targetSum and node.left == None and node.right == None:
                return True
            if node.left != None and dfs(node.left, x + node.val) == True:
                return True
            if node.right != None and dfs(node.right, x + node.val) == True:
                return True
            return False
        if root == None:
            return False
        return dfs(root, 0)
        


        
1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        def dfs(node, x) -> bool:
            if node.left != None and dfs(node.left, x + node.val) == True:
                return True
            if node.right != None and dfs(node.right, x + node.val) == True:
                return True
            return False if node.right !=None or node.left != None else node.val +x == targetSum
        if root == None:
            return False
        return dfs(root, 0)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
```
{% endtabs %}

*总结*

---

## 1091. Shortest Path in Binary Matrix

{% tabs active:2 align:left %}
<!-- tab 思路 -->

**思路**  
尝试1 - dfs: 超时

尝试2 - bfs: 正确

<!-- tab 代码 -->

```python

        
1
2
3
4
```

<!-- tab 题解 -->
```python

总结

118. Pascal’s Triangle

思路
代码
题解

思路
模拟

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        res = []
        for i in range(0, numRows):
            res.append([0] * (i+1) )
            if i == 0:
                res[0][0] = 1
                continue
            res[i][-1] = 1
            for j in range(0, i):
                if j == 0:
                    res[i][j] = 1
                    continue
                res[i][j] = res[i-1][j]+ res[i-1][j-1]
        return res
        
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        res = []
        for i in range(0, numRows):
            res.append([0] * (i+1) )
            res[i][0] = 1
            res[i][-1] = 1
            if i == 0: 
                continue
            for j in range(0, i):
                res[i][j] = res[i-1][j]+ res[i-1][j-1]
        return res

总结
不难，但是很多细节要注意，首先是最开始的append是[0] * (i+1) 而不是[[0]*(i+1)]
其次头尾最开始都需要设置成1

129. Sum Root to Leaf Numbers

思路
代码
题解
二分查找

思路

尝试1 – dfs:通过

  • 直接dfs然后计算就可以了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 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 sumNumbers(self, root: Optional[TreeNode]) -> int:
        def dfs(node, x):
            if node==None: return 0
            if node.left == None and node.right == None:
                return x*10+ node.val
            else:
                return dfs(node.left, x*10+node.val)+ dfs(node.right, x*10+node.val)
        return dfs(root, 0)

        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
```

{% endtabs %}

**总结**

---

## 相关题目

* 

---

## 知识点小结

* 

---

{% folding  模板 open:false %}


{% tabs active:2 align:left %}
<!-- tab 思路 -->

**思路**  

<!-- tab 代码 -->

```python
        
1
2
3
4
```

<!-- tab 题解 -->
```python

总结

模板

思路
代码
二分查找

思路 

1
        
1
2
3
4
```

<!-- tab 题解 -->
```python

总结

许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。