1.博弈论
1.1 定义
- 游戏论（Game Theory）
- 定义：双人（多人）做出多轮决策，每一次决策将影响之后的决策，规则和目标明确
- 一般假设所有人都足够聪明
- 求先手（后手）必胜策略
- 公平vs 非公平
- 平衡态：与终态有一样的性质，无论对手做什么，己方都可以做出相应的决策，将终态留给对手
1.2 放围棋游戏
- 有一个圆桌，两个人轮流往圆桌上放围棋，围棋不能重叠，谁先放不下谁输，请问先手是否有必胜策略
- 关键：每一步保证自己能放，平衡态
- 先手必胜策略：先手在圆桌的圆心放下一颗围棋，之后的每一个围棋都放在对手决策的圆心对称处
1.3 取石子游戏
- 有一个堆石子，N个。两个人轮流取1~K个石子，取到最后一个者赢，请问先手是否有必胜策略
- 关键：每一步保证自己能取，终态（平衡态）留给对手
- 先手必胜策略：开始取N % (K + 1)个，之后对手取X个，己方取K + 1 -X个，保持余数为0（平衡态）
- 如果是取到最后一个输呢？
变种：
- 有一个堆石子，N个。两个人轮流取1,2,4,…或2n个石子，取到最后一个者赢，请问先手是否有必胜策略
- 关键：每一步保证自己能取，终态（平衡态）留给对手
- 先手必胜策略：开始取N % 3个，之后对手取X个，己方取3 -X % 3个，保持余数为0（平衡态）
- 为什么？观察2n % 3
变种：
- 有N堆石子，每堆Ni个。两个人轮流取若干个石子，不能跨堆取，取到最后一个者赢，请问先手是否有必胜策略
- 关键：每一步保证自己能取，终态（平衡态）留给对手
- 先手必胜策略：开始取Xor(N i)，对方取X个，己方取Xor(N’ i)个，保持异或和为0（平衡态）
- 怎么保证每次都能取到想要的个数？
2.概率
2.1 定义
-
定义（大数定律）
- 无穷级数
- 条件概率
- 贝叶斯公式
- 朴素贝叶斯
2.2 题目1
- 有三个密封的箱子（A，B，C），其中两个是空的，另一个箱子里面有大奖。你并不知道奖在哪一个箱子里，但主持人知道。主持人先要你选择一个箱子（A），接着他把你没有选的箱子（B）打开，证明它是空的。最后主持人给你换箱子的机会，此时你该不该换箱子（C）？
- 关键：P(C有奖|选了A，主持人说B是空的) =？
2.3 题目2
- 有一苹果，两个人轮流抛硬币来决定谁吃这个苹果，先抛到正面者吃。问先抛者吃到苹果的概率是多少？
- 关键：P(先吃苹果) = P(第一次抛到)+ P(第二次抛到) + ….. + P(无穷多次)
2.4 题目3
- 世界上每十万人中就有一人是艾滋病患者
- 艾滋病的检测目前准确率是99%
- 假设你刚去做完艾滋病检验，得到的了检测报告，结果是阳性(A)！你会担心到什么程度？(B)
- 关键：贝叶斯公式
- P(B | A) = P(A | B) * P(B) / P(A)
2.5 题目4
- 有一对夫妇，先后生了两个孩子，其中一个孩子是女孩(A)，问另一个孩子是男孩(B)的概率是多大？
- 关键：条件概率公式
- P(B | A) = P(AB) / P(A)
- P(A) = 3 / 4
- P(AB) = 1 / 2
2.6 题目5
- 一条长度为L的线段，随机在其上选2个点，将线段分为3段，问这3个子段能组成一个三角形的概率是多少？
- 关键：列出不等式
- 随机选线段上两个点x，y，令y > x
- 三条线段长度为x，y –x，1 –y
- 两边之和大于第三边：x < 1/2; y > 1/2; y > x + 1/2
- 线性规划
3.数论
3.1 概念
- 讨论范围一般为整数
- 因数（约数），质数（素数），质因数，质因数分解
- 整除，余数，最大公约数（因数），最小公倍数
- 辗转相除法
- 筛法
- 求约数个数
- Mod运算
3.2 质因素分解
目标：将N质因素分解
（1）从小到大查找N在[2，Sqrt(N)]上的因数
（2）查找到的第一个因数为N的最小质因数P
（3）N = N / P，跳回（1）时间复杂度：O（Sqrt(n)）
空间复杂度：O（1）
Leetcode507
3.3 辗转相除法
目标：求最大公约数
起源：辗转相减法
GCD(a, b) = GCD(a, b –a), b > a证：设t为a, b的任意一个公约数，则有tp= a, tq= b，
b –a = t(q –p), 公约数仍在伪代码（递归写法）
intgcd(inta, intb)
if (a == 0) return b;
return gcd(b % a, a); //可以看做多次减法
时间复杂度：O（logn）
最小公倍数：LCM(a, b) = a * b / GCD(a, b)
3.4 筛法
目标：求[2, N]范围内所有质数
（1）将[2, N]所有整数加入集合A
（2）取出最小的整数P，删去A中P的倍数
（3）P一定是A内最小质数，跳回（2）
BTW：整个过程像是在纸上打洞，打出个筛子
时间复杂度：O（NlnlnN）
空间复杂度：O（N）Leetcode204. Count Primes
3.5 求约数个数
- 目标：求N的约数个数
暴力做法：for(1 .. N)
时间复杂度：O（N）
空间复杂度：O（1）
质因数分解
N = PI(aipi)，ai为质数
Ans= PI(pi + 1)
3.6 mod运算
Mod运算的一些性质
(a + b) % m = (a % m + b % m) % m
(a * b) % m = (a % m) * (b % m) % m
交换律：(a + b) % m = (b + a) % m 乘法
结合律：(a + b + c) % m = (a + (b + c)) % m 乘法
分配率：(a + b) * c % m = (ac + bc) % m判断N能不能被2整除
判断N能不能被3整除
判断N能不能被4整除
判断N能不能被5整除
判断N能不能被6整除
判断N能不能被8整除
.……Leetcode326
参考
- 1）面试求职 第四期
