Math

[caipengbo]

数学部分

• 几何问题
• 质数（素数），合数：筛选法求素数（素数表），最大公约数，最小公倍数
• 位运算
• 计算模拟
• 蓄水池抽样
• 随机

[caipengbo]

位运算

#7

caipengbo/Coding-Interviews#10

Java中的移位运算
int左移超过32位时候，先取余再进行移位
详见29题

[caipengbo]

几何

直线的五种表示法：

[caipengbo]

溢出问题

int a = 1000000000;
long b = 5 * (a+1);  // 溢出之后才转换long
long c = 5L * (a+1);

[caipengbo]

蓄水池抽样

[caipengbo]

随机数的取法

[min, max] 整数

Random random = new Random();
int rand = random.nextInt(max-min+1)+min;

nextInt(bound): [0, bound)
[min,max] double

Random random = new Random();
int rand = random.nextDouble()*(max-min)+min;

nextDouble() : [0.0, 1.0]

拒绝采样

拒绝采样：构造均匀分布，采样符合要求的