Python基础

语法

{}

1
2
3
4
5
6
7
hash_table = {}
hash_table[6]=2
print(hash_table)
hash_table[2]=4
print(hash_table)

print(hash_table[6])
1
2
3
{6: 2}
{6: 2, 2: 4}
2

练习：https://leetcode.cn/problems/two-sum

[()]

1
2
3
4
5
my_list = [(3, 1), (2, 3), (1, 5)]
print(my_list)
print(my_list[0])
print(my_list[0][1])
print(my_list[0][0])
1
2
3
[(3, 1), (2, 3), (1, 5)]
(3, 1)
3

lambda

https://www.runoob.com/python3/python-lambda.html

lambda 参数: 表达式

例如，结合sort，根据每个元组的第二个元素对列表进行排序

1
2
3
my_list = [(1, 5), (2, 3), (3, 1)]
my_list.sort(key=lambda x: x[1])
print(my_list)
1
[(3, 1), (2, 3), (1, 5)]

练习：https://leetcode.cn/problems/two-sum

enumerate()

https://www.runoob.com/python/python-func-enumerate.html

1
2
3
4
5
>>> seasons = ['Spring', 'Summer', 'Fall', 'Winter']
>>> list(enumerate(seasons))
[(0, 'Spring'), (1, 'Summer'), (2, 'Fall'), (3, 'Winter')]
>>> list(enumerate(seasons, start=1))       # 下标从 1 开始
[(1, 'Spring'), (2, 'Summer'), (3, 'Fall'), (4, 'Winter')]

list(enumerate(seasons))相当于

1
2
3
4
5
6
7
>>> seasons = ['Spring', 'Summer', 'Fall', 'Winter']
>>> # indexed = list(enumerate(seasons))
>>> indexed = []
>>> for i in range(len(seasons)):
>>>     indexed.append((i, seasons[i]))
>>> print(indexed)
[(0, 'Spring'), (1, 'Summer'), (2, 'Fall'), (3, 'Winter')]

list(enumerate(seasons))也相当于

1
2
>>> indexed = [(i, num) for i, num in enumerate(seasons)]
[(0, 'Spring'), (1, 'Summer'), (2, 'Fall'), (3, 'Winter')]
1
2
3
nums = [3, 2, 4]
for i, num in enumerate(nums):
    print(i, num)
1
2
3
0 3
1 2
2 4

range()

range(start, stop[, step])

start: 计数从 start 开始。默认是从 0 开始。例如range（5）等价于range（0， 5）;

stop: 计数到 stop 结束，但不包括 stop。例如：range（0， 5） 是[0, 1, 2, 3, 4]没有5

step：步长，默认为1。例如：range（0， 5） 等价于 range(0, 5, 1)

extend()和append()

https://www.runoob.com/python/att-list-append.html

append() 方法向列表的尾部添加一个新的元素

extend() 函数用于在列表末尾一次性追加另一个序列中的多个值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def changeextend(str):
    "print string with extend"
    mylist.extend([7, 8, 9])
    return


def changeappend(str):
    "print string with append"
    mylist.append([7, 8, 9])
    return

mylist = [10, 20, 30]
print(f"print string mylist:{mylist}")
changeextend(mylist)
print(f"print extend mylist:{mylist}")
changeappend(mylist)
print(f"print append mylist:{mylist}")

1
2
3
print string mylist: [10, 20, 30]
print extend mylist: [10, 20, 30, 7, 8, 9]
print append mylist: [10, 20, 30, 7, 8, 9, [7, 8, 9]]

练习：https://leetcode.cn/problems/convert-the-temperature

算法

数

整数：是正整数、零、负整数的集合。

自然数：指非负整数，即0,1,2,3,4…

余数：在整数的除法中，只有能整除与不能整除两种情况。当不能整除时，就产生余数。

公因数(公约数)：它是一个能同时整除若干整数的整数。注：对任意的若干个正整数，1总是它们的公因数。最大公因数是指两个或多个整数公因数(公约数)中最大的一个。

公倍数：在两个或两个以上的自然数中，如果它们有相同的倍数，这些倍数就是它们的公倍数。注：最小公倍数是指两个或多个整数公倍数中最小的一个(除0以外)。

互质数：公因数只有1的两个非零自然数，叫做互质数。

1
2
3
4
5
6
7
Q：1是3和5的公倍数吗
A：1不是3和5的公倍数。
公倍数是指在两个或两个以上的自然数中，如果它们有相同的倍数，这些倍数就是它们的公倍数。3的倍数有 3、6、9、12、15、18……5的倍数有5、10、15、20、25……可以看出3和5的最小公倍数是15，它们的公倍数还有30、45、60……都是15的倍数，而1小于它们的最小公倍数15，所以1不是3和5的公倍数。

Q：1是8和24的最大公因数吗
A：1是8和24的公因数，但不是最大公因数。
因为8的因数有1、2、4、8，24的因数有1、2、3、4、6、8、12、24，所以8和24的公因数有1、2、4、8，其中最大公因数是8。

Python函数求最大公约数和最小公倍数https://www.bilibili.com/video/BV1X741167ZX

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
def f1(a, b):
    """最小公倍数"""
    if a > b:
        greater = a
    else:
        greater = b
    while greater % a != 0 or greater % b != 0:
        greater += 1
    return greater


def f1_2(a, b):
    """最小公倍数-优化"""
    # 最小公倍数至少是a、b其中一个的倍数。
    # 假如a > b，此时可以直接用a的倍数对b取余。
    if a > b:
        greater = a
        smaller = b
    else:
        greater = b
        smaller = a
    i = 1
    while greater * i % smaller != 0:
        i += 1
    return greater * i


def f2(a, b):
    """最大公因数"""
    if a > b:
        greater = a
        smaller = b
    else:
        greater = b
        smaller = a
    for i in range(smaller): # 0~smaller-1
        if smaller % (smaller-i) == 0 and greater % (smaller-i) == 0:
            return smaller-i

num1 = 12
num2 = 18
ans = f1_2(num1, num2)
print(ans)
ans = f2(num1, num2)
print(ans)
1
2
36
6

练习：https://leetcode.cn/problems/smallest-even-multiple/description/

扩展：

GCD算法(欧几里得演算法)求解最大公因数

(A,B)=(B,R)(A,B)=(B,R)

A=B+RA=B+R

讲解：https://www.bilibili.com/video/BV19r4y127fu

1
2
3
4
5
6
def gcd(a, b):
    """欧几里得演算法求解最大公因数"""
    "A=B+R (A,B)=(B,R)"
    while b: # b为0时跳出
        a,b = b,a%b
    return a

LCM算法求最小公倍数

对于任意两个正整数a和b，它们的最小公倍数等于它们的乘积除以它们的最大公约数，即

lcm(a,b)=(a∗b)/gcd(a,b)lcm(a, b) = (a * b) / gcd(a, b) 

1
2
3
def lcm(a, b):
    """lcm最小公倍数"""
    return (a*b)/gcd(a, b)

LeetCode的TreeNode

题源：https://leetcode.cn/problems/root-equals-sum-of-children

1
2
3
4
5
6
7
8
9
10
11
12
# 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 checkTree(self, root: Optional[TreeNode]) -> bool:
        if root.val == root.right.val + root.left.val:
            return True
        else:
            return False

将TreeNode单独拿出来分析：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 定义 TreeNode 类
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# 创建节点
root = TreeNode(1) # 把root对象的val变量赋值为1
left_child = TreeNode(2)
right_child = TreeNode(3)

# 连接节点形成树结构
root.left = left_child
root.right = right_child
1
2
3
4
Q：为什么可以root.left = left_child这样赋值？
A：类是对象的蓝图，它定义了对象的属性和方法。
__init__方法是类的构造函数，在创建TreeNode类的实例时会自动调用。
从内存的角度来看，每个TreeNode实例都在内存中占据一块独立的空间。当执行root.left = left_child 时，root实例的left属性存储的是left_child实例在内存中的地址，这样就建立了两个节点之间的连接关系，从而构建出二叉树的结构。

回到题源就可以理解为什么可以使用root.right.val得到左子节点的值了。因为self.left存储当前节点左子节点的引用，可以通过这个属性来访问或操作左子节点，进而访问左子节点的值