乘法原理 list 里枚举右端点
求两两组合的数组，比如list里求(a,b)数对的数量。
- 顺序枚举b，每次ans增加此时a的数量。即只计算左边的。避免重复。
- 或者求子数组的数量，顺序枚举右边的。计算总数。
排列组合
计算公式：
计算公式：
另外 C(0,0) = 1， 0 的为 1。
组合数性质
大组合数求解边模
利用组合数性质. o(n2)
def comb_mod(self, n, m, mod=10 ** 9 + 7):
'''
大组合数计算C(n,m)，边求边mod, 利用组合数性质C(n,m) = 1*C(n-1,m-1) + C(n-1,m)
'''
dp = [[0 for _ in range(n+1)] for _ in range(n+1)]
dp[0][0] = 1
for i in range(1, n+1):
dp[i][0] = 1
for j in range(1, i+1):
dp[i][j] = (dp[i-1][j-1] + dp[i-1][j]) % mod
return dp[n][m]
组合数求和公式
python中排列组合
# 组合
math.comb # n! / (k! * (n - k)!)
math.perm # n! / (n - k)!
求组合数 小球放盒子
默认问题为 n 个小球放到 m 个盒子里，题型共有三项要求，球是否相同，盒子是否相同，能否有空盒。
- 球相同，盒子不同，不能有空盒。 实质就是把 n 个小球分为 m 组。插板法。
C(n-1,m-1) - 球相同，盒子不同，可以有空盒。对于每个盒子，我们都给他一个球，那么上一个问题就和这问题一样了，所以我们可以看做自己有 n+m 个小球，然后我们在排列完之后在每一组都删去一个小球，这样就能枚举出有空盒的情况了。
C(n+m-1,m-1) - 其他复杂情况看参考。
容斥原理
Inclusion-exclusion principle
定理：
容斥原理在排列组合里常用。
比如100127. 给小朋友们分糖果 II 合法方案数 = 总方案数 - 不合法方案数。不合法方案就是A,B,C的并集，然后要A+B+C求和后还要多减去一些重叠的部分。
插板法求各方案数。 用容斥定理将重叠的不合法方案数求出。
这个题目也可以容斥原理： 100126. 重新排列后包含指定子字符串的字符串数目 容斥原理做法参考: https://leetcode.cn/circle/discuss/BLgiV1/
等差等比数列
复杂的复杂度计算
幂函数和对数函数和指数函数对比
####
- 幂函数：x^n. 增长速度受限于 n 值，即便 n 很大，增长速度也是有限的。
- 指数函数：n ^ x, 增长速度随 x 增加变得极其迅速。
- 在 x 较小时，幂函数可能比指数函数大, 但x增大时指数函数的增长速度远快于幂函数，
调和级数
这里有用到： link
二项式定理
在状态压缩中，枚举子集时可能就会用到。
中位数
在一步操作中，你可以使数组中的一个元素加 1 或者减 1 ，所有数都靠近中位数可使所有数组元素相等时移动数最少。 相关题目： 最少移动次数使数组元素相等 II
即中位数到所有数距离和最小，如果是偶数，可以在中位数两侧的数据构成的区间内任意取值，对结果无影响证明：
另一个相似题目：有cost，需转化拆分，然后再算中位数，6216. 使数组相等的最小开销
# 在nums的[l,r]区间位置中，找中位数mid和一个切分位置，这个位置后面的元素的都>= mid，前面元素都<= mid
# nums是有序的list，方法时间复杂度O(1)
def findMid(self, nums: List[int], l=None, r=None):
n = len(nums)
if l is None and r is None:
i = 0
j = n - 1
else:
i = l, j = r
if (j - i + 1) % 2 == 0:
# 长度偶数时，中位数是中间两个数的平均数，这里取整数对求距离总和结果无影响，+0.5/-0.5而已。
# 如果是用于求移动树，其实这里直接中间第一个元素就可以，因+1,-1都对结果无影响
# 所以mid可以直接是nums[n//2], index是n//2
index = (i + j + 1) // 2
v = (nums[index] + nums[index - 1]) // 2
else:
index = (i + j) // 2
v = nums[index]
return [v, index]
# 统计改nums为相等数组的最小sum
# nums是有序的list，方法时间复杂度O(n)
def sumDistancesToMid(self, nums: List[int], l=None, r=None):
mid, index = self.findMid(nums)
pre = Pre(nums)
n = len(nums)
if l is None and r is None:
i = 0
j = n - 1
res = 0
res += (index - i) * mid - pre.get_pre(i, index - 1)
res += pre.get_pre(index, j) - (j - index + 1) * mid
return res
素数
判断是否素数 o(sqrt(N))
# 判断某数是否是素数 o(sqrt(n))
def is_prime(a):
if a <= 1: return False
import math
for i in range(2, int(math.sqrt(a) + 1)):
if a % i == 0: return False
return True
求 1-n 的所有素数 筛法 o(N)
埃氏筛法
# 求1-n每个数的素数，以下时间复杂度O(nloglogn) 接近o(n)
# 如果我们从小到大考虑每个数，然后同时把当前这个数的所有（比自己大的）倍数记为合数，那么运行结束的时候没有被标记的数就是素数了。
# Eratosthenes 筛法（埃拉托斯特尼筛法，简称埃氏筛法）
def get_all_prime(n):
a = [False] * n
res = []
for i in range(2, n):
if a[i]: continue
# a[i]是素数
res.append(i)
for j in range(2 * i, n, i):
a[j] = True
return res
线性筛法 也称为 Euler 筛法（欧拉筛法）
埃氏筛法仍有优化空间，它会将一个合数重复多次标记。有没有什么办法省掉无意义的步骤呢？答案是肯定的。
如果能让每个合数都只被标记一次，那么时间复杂度就可以降到 o(n)了。
def get_all_prime(n):
a = [False] * n
res = []
for i in range(2, n):
if a[i]: continue
# a[i]是素数
res.append(i)
for j in range(2 * i, n, i):
if a[j]: break # 多了个这行
a[j] = True
return res
平方数
生成所有平方数
平方序列：1,4,9,16,..
间隔：3,5,7,…
间隔为等差数列，使用这个特性可以得到从 1 开始的平方序列。
3 的 n 次方
public boolean isPowerOfThree(int n) {
return n > 0 && (1162261467 % n == 0);
}
除法
# b % a == 0
# 表示b能被a整除，a可以整除b, 被除数永远都是有这个『被』
表示b能被a整除，a可以整除b, 被除数永远都是有这个『被』
大整数除法，除法中取模。
有负数的除法求模 不同语言可能不同
摘自网络， 待考证
比如a 除以 b，求对应商和余数。不同语言可能不同
计算-7 Mod 4
那么：a = -7；b = 4；
第一步：求整数商c，c应该是-1.75，如进行求模运算c = -2（向负无穷方向舍入），求余运算则c = -1（向0方向舍入）；
第二步：计算模和余数的公式相同，但因c的值不同，求模时r = 1，求余时r = -3。
当符号不一致时，结果不一样。求模运算结果的符号和b一致，求余运算结果的符号和a一致。
在C/C++, C#, JAVA, PHP这几门主流语言中，%运算符都是做取余运算，而在python中的%是做取模运算。
python求商是向负无穷靠近，而其他是靠近0.
本地最新实验，其实是 python 会把结果变成正数。 Mac m1 OS.
-7 % 4 = 1. -3 % 4 = 1
因数理论
素数分解
每一个数都可以分解成素数的乘积，例如 84 = 22 _ 31 _ 50 _ 71 _ 110 _ 130 _ 170 * …
整除
令 x = 2m0 _ 3m1 _ 5m2 _ 7m3 _ 11m4 * …
令 y = 2n0 _ 3n1 _ 5n2 _ 7n3 _ 11n4 * …
如果 x 整除 y（y mod x == 0），则对于所有 i，mi <= ni。
最大公约数最小公倍数的素数表示
每个质因数的乘积
x 和 y 的最大公约数为：gcd(x,y) = 2min(m0,n0) _ 3min(m1,n1) _ 5min(m2,n2) * …
x 和 y 的最小公倍数为：lcm(x,y) = 2max(m0,n0) _ 3max(m1,n1) _ 5max(m2,n2) * …
约数个数和约数之和
如果 N = p1^c1 _ p2^c2 _ … _pk^ck 约数个数： (c1 + 1) _ (c2 + 1) _ … _ (ck + 1) 约数之和： (p1^0 + p1^1 + … + p1^c1) _ … _ (pk^0 + pk^1 + … + pk^ck)
因数相关问题
试除法求所有约数:
求一个数的因子列表 o(sqrt(n))
o(sqrt(n))
divisors = []
d = 1
while d * d <= k: # 预处理 k 的所有因子
if k % d == 0:
divisors.append(d)
if d * d < k: # 避免 d= k/d的情况，此时如果append会重复
divisors.append(k / d)
d += 1
统计 1-n 每个数的因子列表 o(nlogn)
o(nlogn)
MX = 100001
divisors = [[] for _ in range(MX)] # 每个value就是key的因子列表，乘积肯定>value，因为因子之间可能有倍数
for i in range(1, MX): # 预处理每个数的所有因子，时间复杂度 O(MlogM)，M=1e5
for j in range(i, MX, i):
divisors[j].append(i)
分解质因数
求某数质因数列表 o(sqrt(N))
o(sqrt(N))
求某数的质因数列表，比如 8，是[2,2,2]
枚举[2, sqrt(n)+1), 如果是质因数，就接着除，最大大于 1，它本身就是质数。
也叫 求欧拉函数
# 求质因数列表
def breakdown(N):
result = []
from math import sqrt
for i in range(2, int(sqrt(N)) + 1):
if N % i == 0: # 如果 i 能够整除 N，说明 i 为 N 的一个质因子。
while N % i == 0:
N = N // i
result.append(i)
if N != 1: # 说明再经过操作之后 N 留下了一个素数
result.append(N)
return result
统计 1-n 每个数的质因数列表
筛法求欧拉函数
类似，暂时不写。
gcd 求最大公约数和最小公倍数 欧几里得算法
欧几里得算法
class Math1:
def gcd(self, a, b):
if b == 0:
return a
return self.gcd(b, a % b)
最小公倍数就是 a*b/gcd(a,b)
gcd性质
如果ax+by=1, 则gcd(x,y) = 1
多个数求最大公约数和最小公倍数
多个数的最大公约数:
def gcd_list(self, nums):
import math
cur = nums[0]
for i in range(1, len(nums)):
cur = math.gcd(cur, nums[i])
return cur
多个数的最小公倍数:
注意这里不是直接多个数乘积除以他们的gcd呀，而且不断一个一个加计算的。
def lcm_list(self, nums):
import math
prod = 1
for v in nums:
prod = prod * v / math.gcd(prod, v)
return prod
1到n里有多少个数可整除a?
n//a
1到n里有多少个a的因数?
def calcu(x,a):
'''
1-x中有多少个因数a， 比如1-26里有5，10, 15, 20, 各自1个5， 5*5两个5，一共6个
'''
r = 0
while x:
# 贡献5的数量，贡献5*5的数量，贡献5*5*5的数量
r += x //a
x //= a
return r
print(calcu(26, 5))
取模问题
大数相乘取模
def prod(d=[], mod=10 ** 9 + 7):
r = d[0] % mod
for v in d[1:]:
r *= v
r %= mod
return r
大数相除取模 费马小定理
如果a/b,然后a和b都是大数要取模，这时不能相乘取模来计算
(a/b)%c=(a%c)/(b%c)是不成立的
# 原: i//j%MOD
# 现: i*modInverse(j)%MOD
MOD = int(1e9 + 7)
class BigIntDivide:
def mod_inverse(sefl, i):
# 调用取模的乘幂运算, pow复杂度是log(exp)即log(MOD)
return pow(i, MOD - 2, MOD)
def divide_mod(self, a, b):
'''
计算(a/b) % MOD, 除法变乘法，前提是b和MOD互为质数
'''
# 如果有多个b,比如a/b1/b2, 那就可以递归。a*mod_inverse(b1) % mod * mod_inverse(b2) % mod这样
return a * self.mod_inverse(b) % MOD
def divide_mods(self, a, b=[]):
'''
计算a /(b1*b2*b3) % MOD等形式，前提是b和MOD互为质数
'''
r = a % MOD
for i, v in enumerate(b):
r *= self.mod_inverse(v)
r %= MOD
return r
大数幂取模
r = pow(base=2, exp=3, mod=3)
print(r)
(i-j)%k == 0的转换
(i-j)%k == 0, 可等价于i % k == j % k. 这样可以用 map 来记录，比如前缀和常见问题。
阶乘
import math
math.factorial(3)
分配问题
a能否分成满足条件的两份，其中只能分给指定一份
2513. 最小化两个数组中的最大值 给你两个数组 arr1 和 arr2 ，它们一开始都是空的。你需要往它们中添加正整数，使它们满足以下条件：
arr1 包含 uniqueCnt1 个 互不相同 的正整数，每个整数都 不能 被 divisor1 整除 。 arr2 包含 uniqueCnt2 个 互不相同 的正整数，每个整数都 不能 被 divisor2 整除 。 arr1 和 arr2 中的元素 互不相同 。 给你 divisor1 ，divisor2 ，uniqueCnt1 和 uniqueCnt2 ，请你返回两个数组中 最大元素 的 最小值 。
参考， link
Key: 判断过程中分为三类：保证在范围内有充足的数不是第一个数的倍数；不是第二个数的倍数；不为公倍数的数总数不少于总共要取的数。根据这三个条件即得到结果。
将 s 个物品分成大小为 k 或 (k+1) 的的最少组数
将 s 个物品分成大小为 k 或 (k+1) 的的最少组数：
- 情况1：首先尝试将 s 个物品分成大小是 (k+1) 的组，这样会分出 d1 = ⌊ (s/(k+1)) ⌋ 组，并且还剩下 r1 = s mod (k+1) 的物品。
- 若 r1 = 0，则直接分成 d1 组即可。
- 否则，如果 d1 + r1 ≥ k，则可以组成新的一组，总共可以分成 (d1+1) 组。
- 情况2：接下来尝试将 s 个物品分成大小是 k 的组，这样会分出 d2 = ⌊ (s/k) ⌋ 组，并且还剩下 r2 = s mod k 的物品。
- 因为 d2 组的大小都是最小值 k，所以不能再拿出物品和 r2 凑成新的一组，而是反过来要把 r2 塞进每一组里。由于 d2 组的每一组最多再加入一个物品。因此如果 r2 ≤ d2，那么就可以把所有物品分成 d2 组。
- 如果所有尝试都失败，那么这些物品不能被分成大小是 k 和 (k+1) 的组。
def min_groups(s, k):
divisor = s // (k + 1)
remainder = s % (k + 1)
cnt = 0
if remainder == 0:
cnt += divisor
elif divisor + remainder >= k:
cnt += divisor + 1
else:
divisor = s // k
remainder = s % k
# cnt == -1 表示无法分组
if remainder > divisor:
cnt = -1
else:
cnt += divisor
# print(s, k, cnt)
return cnt
位运算
a xor b ==c 则 a = b xor c.
进制转换
def baseX(self, n, x):
'''
进制转换，10进制变x进制
:return: 数组，每个数是该位上数
'''
ans = []
while n != 0:
n, b = divmod(n, x)
ans.append(b)
ans.reverse()
return ans
def base10(self, n=[], x=2):
'''
从x进制转成10进制
'''
ans = 0
for v in n:
ans *= x
ans += v
return ans
负进制的转换
个人blog 1017. 负二进制转换 可以任何负进制转换
class Solution:
def baseNeg2(self, n: int) -> str:
if n == 0:
return '0'
ans = []
b = -2
while n != 0:
x = n % b
ans.append(str(abs(x)))
if x < 0:
x += abs(b) # 变成正数
n = (n - x) // b
ans = ans[::-1]
return "".join(ans)
小数的进制转换
十进制小数转二进制数：“乘以 2 取整，顺序排列”（乘 2 取整法）
例： (0．625)10= (0．101)2
幂
快速幂 O(logk)
求 m^k mod p，时间复杂度 O(logk)。
int qmi(int m, int k, int p)
{
int res = 1 % p, t = m;
while (k)
{
if (k&1) res = res * t % p;
t = t * t % p;
k >>= 1;
}
return res;
}
求根号
牛顿迭代法
求根号变种 小数精度
while l<=r不用变，只需要变步长即可。eps 可以比期望精度再小一个量级。
def f(x, eps):
l, r = 0, max(x, 1)
while l <= r:
mid = (l + r) / 2
if int(mid) * int(mid) == x:
return int(mid)
if mid * mid > x:
r = mid - eps
else:
l = mid + eps
return r
if __name__ == '__main__':
eps = 1e-3
# print(f(4, eps))
# print(f(8, eps))
# print(f(9, eps))
print(f(0.04, 1e-10))
数字与中文英文转换
阿拉伯数字转中文
200001010200 -> 二千亿零一百零一万零二百
- 倒序，结果放到stack里，最后reverse.
- 一个单位，一个数字。遇到0就没单位了。0还会省略
// 1 最后一位是 0 的情况下，需要忽略，
// 2 中间某一位是 0 的情况下，不要加上 十百千万 这种
// 3 中间如果有多个 0 ，只需要保留一位 0
let chinese = [
'零',
'一',
'二',
'三',
'四',
'五',
'六',
'七',
'八',
'九'
]
let units = [
'十',
'百',
'千',
'万'
]
// 解法：
// 1. 判断当前位数匹配到 Chinese 中，然后获取到对应的中文
// 2. 然后判断当前是多少位数，然后看是十百千万这种
// 尝试使用 reduce 写一下
// 注意的点：
// 1 最后一位是 0 的情况下，需要忽略，
// 2 中间某一位是 0 的情况下，不要加上 十百千万 这种
// 3 中间如果有多个 0 ，只需要保留一位 0
function toChinese(num) {
let str = '' + num;
let res = '';
// 需要使用倒序而不是正序
for (let len = str.length, i = len - 1; i >= 0; i--) {
// 末尾如果是 0，则忽略
if (i == len - 1 && str[i] == 0) {
continue;
}
// 如果某位数是 0 ，则不要加上 十百千万 这种
if (i == len - 1 || str[i] == 0) {
// 如果下一位还是 0，那么当前这位就可以忽略
// 为什么这里不是 i - 1 而是 i + 1呢
if (str[i + 1] == 0) {
continue;
}
res += chinese[str[i]];
}
else {
// 单位的索引 和 数字的索引 不一样
res += units[len - 1 - i - 1] + chinese[str[i]];
}
}
return res.split('').reverse().join('');
}
中文转阿拉伯数字
顺序处理
- 临时数字变量
- 遇到单位就乘以临时数字变量加到结果并重置，数字变0，单位变1.
- 最后将数字加到结果。
def chinese_to_digits(chinese_num):
chinese_digits = {'零': 0, '一': 1, '二': 2, '三': 3, '四': 4, '五': 5, '六': 6, '七': 7, '八': 8, '九': 9}
chinese_units = {'十': 10, '百': 100, '千': 1000, '万': 10000, '亿': 100000000}
result = 0
temp_num = 0
temp_unit = 1 # 当前数字的倍数单位
for char in chinese_num:
if char in chinese_digits: # 如果是数字
temp_num = chinese_digits[char]
elif char in chinese_units: # 如果是单位
unit_value = chinese_units[char]
if unit_value >= 10000: # 处理 "万" 或 "亿"
result += (temp_num * temp_unit) # 将当前级别的值加到结果中
result *= unit_value # 将整个结果乘以单位（万或亿）
temp_num = 0 # 清零当前累积值
temp_unit = 1 # 重置单位
else:
temp_unit = unit_value # 对于"十"、"百"、"千"，更新当前倍数单位
result += (temp_num * temp_unit) # 将当前数字乘以倍数单位并加入结果
temp_num = 0 # 清零当前累积的数字
temp_unit = 1 # 重置单位
# 最后将剩余的数字加到结果
result += temp_num * temp_unit
return result
# 测试
chinese_num = "二百零五"
result = chinese_to_digits(chinese_num)
print(result) # 输出: 205
chinese_num = "十"
result = chinese_to_digits(chinese_num)
print(result) # 输出: 10
chinese_num = "二十万三千四百五十六"
result = chinese_to_digits(chinese_num)
print(result) # 输出: 203456
chinese_num = "八十九万零三十"
result = chinese_to_digits(chinese_num)
print(result) # 输出: 890030
中英文互转
三位一组。来处理。
参考 Acwing 数学
参考 本文只涉及部分