对于像我一样英语水平不高的,建议看 slides 而不是 notes。
对于像我一样英语水平不高的,建议看 slides 而不是 notes。
寒假入门一下 Python,主要关注语法特性。中英文可能混杂,塑料英语见谅。
加入了部分 CS50 的内容。
原版英文笔记见 https://cs50.harvard.edu/python/2022/notes/。
注意 Python 和 C/C++ 的简要区别:
1 | num = 1 |
in
关键字,以处理复杂类型的成员: 1 | people = { |
if name in people:
to search the keys of our dictionary for a name
. If the key exists, then we can get the value with the bracket notation, people[name]
.if "You" in "DoYou Can":
。print(f"Hello, {name}")
。详细用法现查。1 | >>> x = 1 |
[::]
Slice:[::-1]
。random.choice([list]) random.shufffle([])
, str.upper().lower().title()
。sys.argv (-> list)
读取 command line 的内容。assert
断言来终止程序。requests
:1 | import requests |
match
:1 | match name: |
1 | | hello.py |
whereas `test_hello.py` will be treated the same level as `hello.py`, i.e., you can `import hello` in `test_hello.py`.
run `pytest test`.
with
keyword, which will close the file for us after we’re finished:1 | with open("phonebook.csv", "a") as file: |
Lecture 6,7 are skipped.
student = Student()
is creating an object/instance of that class.name
as an attibute while student.name
is accessing an instance variable.raise
,制造异常配合 try…except。__init__, __str__
@property
实现对成员赋值的加工处理@property \n def house(self)
, and after that, ‘setter func’ @house.setter \n def house(self, house)
,那么当操作 object.house
时上述函数会被自动调用。似乎拥有先后次序。它们均可以被 __init__
调用,尽管似乎位置顺序相反。1 | class Student: |
So now technically we have
_house
;house
.object._house
是 accessible 的。Python 没有 public/private/protected 关键字来限制访问。student.house = "Ravenclaw"
作为其语法糖。@classmethod
使得其不依赖类的实体而被调用。1 | class Hat: |
因此,借助此修饰可以将读取并创建实例的工作整合进 class 里。
1 | class Student: |
注意:technically 这里的 cls() 当然可以使用 Student() 来替代。推测可能是出于后续继承等的原因。在这个程序段中,此处的 cls 总是当前类。
Inheritance: Design your classes in a hierarchical(分层) fashion. 避免 duplication。
1 | class Wizard: |
多继承暂时 skipped。
Python 支持重载运算符,需查询相应符号对应的保留函数名。
1 | class Vault: |
这里的左右类型不必相同。
set
In math, a set would be considered a set of numbers without any duplicates.
In the text editor window, code as follows:
1 | students = [ |
Notice how we have a list of dictionaries, each being a student. An empty list called houses
is created. We iterate through each student
in students
. If a student’s house
is not in houses
, we append to our list of houses
.
It turns out we can use the built-in set
features to eliminate duplicates.
In the text editor window, code as follows:
1 | students = [ |
Notice how no checking needs to be included to ensure there are no duplicates. The set
object takes care of this for us automatically.
In other programming languages, there is the notion of global variables that are accessible to any function.
Python 建议使用 OOP,尽量规避全局变量的使用。
1 | class Account: |
Notice how we use account = Account()
to create an account. Classes allow us to solve this issue of needing a global variable more cleanly because these instance variables are accessible to all the methods of this class utilizing self
.
Constants are typically denoted by capital variable names and are placed at the top of our code. Though this looks like a constant, in reality, Python actually has no mechanism to prevent us from changing that value within our code! Instead, you’re on the honor system: if a variable name is written in all caps, just don’t change it!
One can create a class “constant”:
1 | class Cat: |
Because MEOWS
is defined outside of any particular class method, all of them have access to that value via Cat.MEOWS
.
Python does require the explicit declaration of types. 然而,Python 是强类型语言,几乎不容忍隐式的类型转换。引入 type hint 以便于在正式运行前进行从头到尾推导的类型检查。
A type hint can be added to give Python a hint of what type of variable or function should expect. In the text editor window, code as follows:
1 | def meow(n: int) -> None: |
You can use docstrings to standardize how you document the features of a function. In the text editor window, code as follows:
1 | def meow(n): |
Established tools, such as Sphinx, can be used to parse docstrings and automatically create documentation for us in the form of web pages and PDF files such that you can publish and share with others.
You can learn more in Python’s documentation of docstrings.
argparse
argparse
.一个序列 seq 在去赋值和传参时会被自动解包。赋值举例:
1 | first, _ = input("What's your name? ").split(" ") |
‘=’ 左右变量的个数必须相同。注意,这里等号的左侧事实上也是一个被解包的序列,其类型可以被指定但没有必要。比如,下面的写法是可被接受的:
[s, _] = "Your name".split()
A *
unpacks the sequence of a list(seq) and passes in each of its individual elements to a function:
1 | def total(galleons, sickles, knuts): |
被解包后的序列本身没有类型、不能做左右值,不能在程序中独立存在。用于传参时,等价于传入恰好数量的 arguments。
解包 dict 时,会把 key 的内容去引号解析为 parameters, 相当于指定参数名地传参。理所当然地,dict 内部的顺序对结果没有影响。
1 | def total(galleons, sickles, knuts): |
args
and kwargs
Recall the prototype for the print
function:
1 | print(*objects, sep=' ', end='\n', file=sys.stdout, flush=False) |
We can tell our function to expect a presently unknown number positional arguments. We can also tell it to expect a presently unknown number of keyword arguments. In the text editor window, code as follows:
1 | def f(*args, **kwargs): |
args
are positional arguments, such as those we provide to print like print("Hello", "World")
. 类型为 tuple. 接收未指定名称的参数。
kwargs
are named arguments, or “keyword arguments”, such as those we provide to print like print(end="")
. 类型为 dict.
可以使用 kwargs
接收所有被指定 parameter 名的参数,也可以在函数定义处指明你关心的特定名称的参数。
In the text editor window, code as follows:
1 | def main(): |
Notice how *words
allows for many arguments to be taken by the function.
map
Hints of functional programming: where functions have side effects without a return value.
1 | def main(): |
Notice how the yell
function is simply yelled.
map(func, iterable) 将 iterable 的每一项用 func 作用后,返回这个整体。
1 | def main(): |
List comprehensions allow you to create a list on the fly in one elegant one-liner.
1 | students = [ |
Notice how the dictionary will be constructed with key-value pairs.
1 | students = ["Hermione", "Harry", "Ron"] |
filter
filter(function, iterable) 将 iterable 的每一项判断 func 作用后是否为真,返回结果为真的相应值的整体。
filter
can also use lambda functions as follows:
1 | students = [ |
enumerate
We may wish to provide some ranking of each student. In the text editor window, code as follows:
1 | students = ["Hermione", "Harry", "Ron"] |
Notice how each student is enumerated when running this code.
Utilizing enumeration, we can do the same:
1 | students = ["Hermione", "Harry", "Ron"] |
Notice how enumerate presents the index and the value of each student
.
You can learn more in Python’s documentation of enumerate
.
当需要生成一个 iterable 并对其每一项操作时,在生成函数中使用 yield 使得 iterable 每生成一项便传入相应操作中处理。一次操作完成后,生成器再生成第二项传入,以此类推,以避免 iterable 的体积过大。
1 | def main(): |
Notice how yield
provides only one value at a time while the for
loop keeps working.
若 $ax \equiv 1 \pmod b$,则称 $x$ 是 $a$ 关于模 $b$ 的逆元,常记做 $a^{-1}$。
上式等价于 $ax + by = 1$,因此,一种求逆元的方法就是利用扩欧解方程 $ax + by = 1$。
显然,逆元不一定存在:其存在的充要条件为 $(a, b) = 1$。
推论:$p$ 是质数,$p$ 不整除 $a$,则 $a$ 模 $p$ 的逆元存在。
又称辗转相除法,迭代求两数 gcd。
由 $(a, b) = (a, ka + b)$ 的性质,$\gcd(a, b) = \gcd(b, a\bmod b)$。容易证明这么做的复杂度是 $O(\log n)$。
注意:$\gcd(0, a) = a$。
预处理向上跳 $2^k$ 步的结果数组 f[k][x]
。
求的时候先把两个点跳到一个深度。这里有一个特判,如果重合直接返回这个点。
然后log值从大往小枚举,两个点一起不断向上跳,直至父亲相同,直接返回父节点。
可以 $O(n)$ 预处理log值,把单次查询复杂度降到 $O(常数)$。
复杂度:预处理 $O(n \log n)$,查询 $O(1)$
时间戳:搜索时第几个搜索到这个点。如搜索顺序是1->2->3->6,则6的时间戳为4
连通分量:对于图G来的一个子图中,任意两个点都可以彼此到达,这个子图就被称为图G的连通分量(一个点就是最小的连通分量)
最大连通分量:对于图G的一个子图,这个子图为图G的连通分量,且是图G所有连通分量中包含节点数最多的那个,即为G的最大联通分量
1 |
|
1 |
|
$$
F(i,j)=
\begin{cases}
F(i-1,j)& j \leq w_i\\
\max{F(i-1,j),F(i-1,j-w_i)+v_i}& j > w_i
\end{cases}
$$
注意二维转换成一维的时候,$j$ 要从后向前枚举,因为每次的新结果都是根据上一个结果来求得的,从后向前可避免重复取同一物品。