Python一周小结

Python特性

输入输出

1. 输入

   • 单值输入input()、int(input()

   • 确定值个数：map(int, input().split())

   • 未知个数的一行存于列表 ：list(map(int, input().split()) or list(int(i) for i in input().split())

   • 二维数组输入：

     n = int(input())
     arr = []
     for i in range(n) :
         arr.append(list(map(int, input().split())))
     

   • 未声明终止的输入

     try:
         while True:
             s = input()
     except:
         pass
     '
     运行
     运行

2. 输出print

   • end = "xxxx" :输出字符串以xxxx结尾

   • print自带换行

   • “xxx”.join(strlist) : 将字符串列表中字符串之间以"xxx"连接返回新的字符串

   • format格式输出：{[field_name][!conversion][:format_spec]}

     • 位置匹配：
       1. 不带编号{}，按顺序匹配
       2. 带数字编号：数字对应于索引
       3. 关键字：用关键字对应
     • 格式转换 : format_spec
       • +,- ,
       • s, d, f:10.4f表示宽度为10，保留4位小数

   • %占位符类似于c，但要把真实值统一放在%()中

   • 保留小数可以用round函数，round(v, 2)

   • f-string

     • f'{field_name [:format_spec]}'

format_spec     ::=  [[fill]align][sign][#][0][width][grouping_option][.precision][type]
fill            ::=  <any character>
align           ::=  "<" | ">" | "=" | "^"
sign            ::=  "+" | "-" | " "
width           ::=  digit+
grouping_option ::=  "_" | ","
precision       ::=  digit+
type            ::=  "b" | "c" | "d" | "e" | "E" | "f" | "F" | "g" | "G" | "n" | "o" | "s" | "x" | "X" | "%"

3. 初始化、复制与声明全局变量

   1. 初始化

      • 初始化一个一维数组[0] * n
      • 初始化一个二维数组list([0] * n for _ in range(m))

   2. 复制

      • 浅拷贝：一般复制引用，与原变量指向同一个值，一般=都是浅拷贝
      • 深拷贝 ： 创建一个副本，并将变量指向它，通常使用deepcopy，一维数组可使用切片操作

   3. 全局变量：当函数需要改变外部变量的引用时，应该在函数体内将变量声明为global

4. 栈与队列

   1. 栈用list模拟即可，push和pop对应于append和pop
   2. 队列可以引入collection的deque，push对应于appendleft，pop对应于pop

5. 比较函数cmp和sort、sorted

   应用于key参数，使用functools的cmp_to_key方法，cmp函数自定义，当返回正数则交换，负数不交换

6. 字典

   1. 字典的键不能为迭代器
   2. 创建{}, dict()
   3. 查：直接用关键字，和get函数get(key, defaultnum)
   4. 添加，修改：关键字和值
   5. 删除del + 关键字
   6. 遍历，items()、keys()、values()

算法方面

快排：分治

下面假设对nums数组排序， l为左边界， r为右边界

1. 确定分界点：可以是nums[l]、nums[r]、nums[(l + r) >> 2]，设为d
2. 调整区间：将小于d的元素放到相对于大于d元素的左边，大于d的放在右边
3. 递归处理左右两端

调整区间的两种方法

1. 每次调整区间用三个列表存，left、mid、right，left存小于d的元素，mid存等于d的元素，right存大于d的元素，最后将这三个列表连接即可
2. 双指针法: 没啥好讲的，碰到左右两边都需要交换的话，换一下。

归并排序 ：分治

待排序数组为nums, 左边界为l，右边界为r

1. 确定分界点：mid = （l + r）>> 1
2. 递归分隔
3. 合并：双指针法

可利用切片整体赋值
总结：快排属于尾递归，对应于树的遍历属于前序遍历，归并排序是首递归，对应于后序遍历

高精度（大乌龙）

Python不讲高精度

前缀和与差分

前缀和

数值数组A，前缀和数组S，满足如下定义

S[i] = A[0] + A[1] +…+A[i]

应用：求一段数的和

A[i ~ j] = S[j] - S[i - 1]
使得原本O(n)的操作，只需要O(1)

差分

差分是前缀和的逆过程，假设数组A和数组B，
数组B的前i个元素和恰好等于A数组的第i个元素。我们称B数组为A数组的差分数组

应用：可以对一段连续的数进行统一操作

双指针

1. 指向两个序列
2. 维护一个序列的一段区间

双指针的作用

对暴力遍历的优化

模板

j = 0 或者 右边界
for i in range(len(nums)) :
	while (j 满足边界条件 and check(i, j)) : 或者 if。。。
		控制边界
	题目逻辑

离散化与合并区间

离散化

1. 我自己的定义：一个超大数组，需要对数组中有限的位置进行操作，而离散化是将这有限的位置挨个存进一个数组a，并进行排序和去重，然后将需要的操作映射到一个数组b上，顺序和数组a一致。
2. 作用：面对一个无限的序列时的有限操作，有效的压缩了空间

合并区间

这题是我的老熟人了，在刷代码随想录的时候就遇到了，贪心！贪心！贪心！
这题由于只让求个数所以处理逻辑相对简单一点

1. 贪心策略：局部最优解：第i个区间在碰到的外层比i + 1个区间内层大时，更新当前维护的区间的最外层：即i和i + 1区间最外层的最大值，否则则将结果 + 1（这里我是将原来区间个数一个个减去的）

DFS && BFS

DFS：

1. 其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次.
2. DFS自带回溯，应用于枚举和存在性问题

BFS ：

1. 属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。
2. 找最优解：dp是其中特例
3. 模板

queue que #用于宽搜
graph g
hash_map[] #用于存每一步的结果
que.push(root)
while len(que) != 0 :
	q = que.pop()
	if q exits path : #如果q存在通往下个节点的路
		do something #vertical sngx 题目逻辑，状态转移
		que.push(q)
		hash_map(graph, q) # 记录状态

一些小技巧

1. 模拟C语言的
   do....while(..)

   while True :
   	do something
   	if something :
   		break
   

2. 可以对列表切片赋值，也可以对列表赋值切片

3. 对于图中方向的模拟可以使用一个DIRC = [[-1, 0],[0, 1], [1, 0], [0, -1]]和模运算来控制方位走向

4. 字符串模拟二维数组n * m,对于字符串中索引x，对应于二维数组是 [x // n, y % m],二维数组中[x, y],对应于字符串索引为x * n + y

5. 字符串不能修改！！！！