0%

要解决的问题

假设有一个源源吐出不同球的机器, 只有装下10个球的袋子,每一个吐出的球,要么放入袋子,要么永远扔掉,如何做到机器吐出每一个球之后,所有吐出的球都等概率被放进袋子里

规则

吐出1到10号球,完全入袋, 引入随机函数f(i),提供一个值i,等概率返回1-i的一个数字, 当K号球吐出的时候(K>10) ,我们通过以下决策决定是否要入袋

  1. 引入随机函数:f(K) , 如果返回10以内的数,则入袋,如果返回10以外的数,则扔掉, 即:10/K的概率决定球是否入袋。

  2. 第一步中如果决定入袋,那么袋子中已经存在的球以等概率丢弃一个。

证明

情况1

当K为1~10号的时候,根据我们的规则,入袋概率100%,每个球等概率

情况2

当K为任意一个大于10的数,我们假设K为927,即:当927这个编号的球吐出来的时候,我们考虑:

A. 1 ~ 10 号球的入袋概率

B. 大于10号小于等于927号球的入袋概率

如果A和B都可以说明等概率

那么可以推广到普遍情况都是等概率的。

A情况,927号球到来的时候,我们可以考虑一下5号球的入袋概率是多少?

5号球需要存活到927号球到来,必须满足:

  1. 11号球来的时候,5号球活下来

  2. 12号球来的时候,5号球活下来

  3. 926号球来的时候,5号球活下来

11号球来的时候,5号球怎么活下来呢?先看一下,11号球到来,5号球如果没有活下来的概率q,那么5号球活下来的概率就是 1 - q

首先,根据我们的规则,11号球要以10/11概率被选中入袋,且5号球要以非常倒霉的情况1/10概率被选中要替换,那么,11号球到来,5号球被替换的概率为:

1
(10/11 * 1/10) = 1/11

那么5号球活下来的概率就是

1
1 - 1/11 = 10/11

12号球到来的时候,5号球活下来的概率同理,可以计算出为11/12

13号球到来的时候,5号球活下来的概率同理,可以计算出为12/13

….

927号球到来的时候,5号球活来的概率同理:可以计算出为926/927

所以,5号球活下来的概率为:

1
10/11 * 11/12 * 12/13 ... * 925/926 * 926/927 = 10/927

同理,1 ~ 10 号球任意一号都可以按照5号球的计算方式计算,概率均为:10/927

A情况是等概率的

再看B情况,我们可以假设一个大于10但是小于927的球,比如,15号球,考虑入袋概率

15号球要在927号球到来的时候,还在袋子中,则需要保证:

15号球在当时被吐出的时候,以10/15概率被选中,且在

16号球到来的时候,15号球活下来,概率根据A的计算逻辑,为15/16

17号球到来的时候,15号球活下来, 同理,为16/17

….

926号球到来的时候,15号球活下来,概率为925/926

927号球到来的时候,15号球活下来,概率为926/927

所以,927号球到来的时候,15号球活下来的概率是:

1
10/15 * 15/16 * 16/17 .... * 925/926 * 926/927 = 10/927

同理,任意大于10小于927号球的概率都可以根据15号球的计算逻辑推算出来,均为10/927

A情况和B情况概率都是10/927

所以规则满足了题目的要求。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
public class Code_0058_ReservoirSampling {
public static class RandomBox {
private int[] bag;
// 袋子容量
private int capacity;
// 第几号球
private int count;

public RandomBox(int capacity) {
bag = new int[capacity];
this.capacity = capacity;
count = 0;
}

// 随机函数,等概率生成1-max之间随机的一个数字
// Math.random() -> 生成[0,1)范围内的数
// (int)i 是对i进行向下取整
private int rand(int max) {
return (int) (Math.random() * max) + 1;
}

public void add(int num) {
// 球个数增加
count++;
// 如果球的个数没有超过容量
if (count <= capacity) {
// 则入袋
bag[count - 1] = num;
} else if (rand(count) <= capacity) {
// 否则以N/count的概率入袋
bag[rand(capacity) - 1] = num;
}
}

// 返回袋子中最终选中的球
public int[] choices() {
int[] res = new int[capacity];
System.arraycopy(bag, 0, res, 0, capacity);
return res;
}

}
}

更多

算法和数据结构笔记

参考资料

作者:Grey

原文地址: 微服务架构设计模式概述

说明

本文内容是《微服务架构设计模式》这本书的学习笔记

单体应用转换成微服务可以考虑的几个维度

image

SOA和微服务的区别

SOA 微服务
协议 重量级(SOAP,WS*) REST或者RPC
数据管理 共享数据库 每个服务都有自己的数据模型和数据库
典型服务规模 较大的单体 较小的服务
阅读全文 »

题目描述

题目链接

思路

斐波那契数,通常用 F(n) 表示,形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始,后面的每一项数字都是前面两项数字的和。也就是:

F(0) = 0,F(1) = 1
F(n) = F(n - 1) + F(n - 2),其中 n > 1

暴力解法:递归版本

1
2
3
4
5
6
7
8
9
public static int fib(int N) {
if (N <= 0) {
return 0;
}
if (N == 1 || N == 2) {
return 1;
}
return fib(N - 1) + fib(N - 2);
}

暴力解法:迭代版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static int fib2(int N) {
if (N <= 0) {
return 0;
}
if (N == 1 || N == 2) {
return 1;
}
int first = 1;
int second = 1;
int result = 0;
for (int i = 3; i <= N; i++) {
result = first + second;
first = second;
second = result;
}
return result;
}

最优解

如果某个递归,除了初始项之外,具有如下的形式

1
F(N) = C1 * F(N) + C2 * F(N-1) + ... + Ck * F(N-k) ( C1...Ck 和k都是常数)

并且这个递归的表达式是严格的、不随条件转移的, 那么都存在类似斐波那契数列的优化,时间复杂度都能优化成O(logN),

斐波那契数列的通项公式

1
F(N) = F(N - 1) + F(N - 2)

斐波那契数列的任意项(以F2,F3,F4为例),都有如下公式:

1
2
|F2,F3| * |a,b| = |F3,F4|
|c,d|

其中,矩阵中a = 0, b = 1, c = 1, d = 1

所以针对斐波那契第N项,有

1
2
|F(N),F(N-1)|  = |F1,F2| * |0,1| ^ (N - 2)
|1,1|

所以优化的关键在于,求一个矩阵的(N - 2)次方如何更快,我们可以参考求一个整数的N次方如何最快,可以通过快速幂方式来计算。

比如:求6的5次方, 可以这样来求,先把5转换成二进制0101, 准备一个变量t,初始等于6, 准备一个变量ans, 初始等于1,从右到左遍历5的二进制位,如果遇到1则:ans *= tt *= t, 遇到0则不仅需要处理ans,只需要t *= t, 直到遍历完成5的二进制位,ans即为答案,整个复杂度为 O(logN), 详细可以参考: x的n次幂, 代码为:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public class LintCode_0428_PowXN {

// 类fabanacci问题
// pow X N ( N 转成2进制)
// 复杂度 log(N)
public static double myPow(double x, int n) {
int pow = Math.abs(n == Integer.MIN_VALUE ? n + 1 : n);
double ans = 1D;
double t = x;
while (pow != 0) {
if ((pow & 1) != 0) {
ans *= t;
}
pow >>= 1;
t *= t;
}
if (n == Integer.MIN_VALUE) {
ans *= x;
}
if (n < 0) {
ans = 1D / ans;
}
return ans;
}
}

回到斐波那契数列问题,一个矩阵的N次方,也可以优化成O(logN)的解法, 在斐波那契问题中, ans变量初始为单位矩阵,即:

1
2
|1,0| 
|0,1|

t 在斐波那契问题下初始为

1
2
|0,1| 
|1,1|

逻辑和求N的X次幂一样,只不过N的X次幂中 tans 变量都是数字相乘,而斐波那契问题是矩阵相乘,矩阵相乘的规则请参考线性代数的知识, 完整代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// 最优解 O(log^N)
public static int fib3(int N) {
if (N <= 0) {
return 0;
}
if (N == 1 || N == 2) {
return 1;
}
int[][] matrix = matrixPow(new int[][]{{0, 1}, {1, 1}}, N - 2);
return matrix[0][1] + matrix[1][1];
}

public static int[][] matrixPow(int[][] matrix, int n) {
int[][] ans = new int[][]{{1, 0}, {0, 1}};
int[][] t = matrix;
while (n != 0) {
if ((n & 1) != 0) {
ans = matrix(t, ans);
}
n >>= 1;
t = matrix(t, t);
}
return ans;
}

public static int[][] matrix(int[][] A, int[][] B) {
int[][] result = new int[2][2];
result[0][0] = A[0][0] * B[0][0] + A[0][1] * B[1][0];
result[0][1] = A[0][0] * B[0][1] + A[0][1] * B[1][1];
result[1][0] = A[1][0] * B[0][0] + A[1][1] * B[1][0];
result[1][1] = A[1][0] * B[0][1] + A[1][1] * B[1][1];
return result;
}

类斐波那契问题都可以用如上的优化方法来计算,

例如,某个问题的第N项的通项公式是:

1
F(N) = 6 * F(N-1) + 3 * F(N-5)

那么,要求其第N项的值,可以转换成如下矩阵公式,

1
|Fn,Fn-1,Fn-2,Fn-3,Fn-4| = |F5,F4,F3,F2,F1|x|5x5|^(N-5)

列出其中前几个项并带入求出|5x5| 这个5 乘以 5的矩阵中每个位置的数字,然后参考快速幂的算法,即可解答。

更多

算法和数据结构笔记

参考资料

作者:Grey

原文地址:Linux学习笔记

说明

本文中Linux基于CentOS 7,主要是日常学到的一些笔记,所以内容相对零散。

/目录下文件夹主要作用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
[root@linux /]# ll /
total 16
lrwxrwxrwx. 1 root root 7 Aug 17 02:40 bin -> usr/bin
dr-xr-xr-x. 5 root root 4096 Sep 13 22:03 boot
drwxr-xr-x. 20 root root 3200 Sep 13 21:58 dev
drwxr-xr-x. 74 root root 8192 Sep 13 22:03 etc
drwxr-xr-x. 2 root root 6 Apr 11 2018 home
lrwxrwxrwx. 1 root root 7 Aug 17 02:40 lib -> usr/lib
lrwxrwxrwx. 1 root root 9 Aug 17 02:40 lib64 -> usr/lib64
drwxr-xr-x. 2 root root 6 Apr 11 2018 media
drwxr-xr-x. 2 root root 6 Apr 11 2018 mnt
drwxr-xr-x. 2 root root 6 Apr 11 2018 opt
dr-xr-xr-x. 109 root root 0 Sep 13 21:58 proc
dr-xr-x---. 2 root root 151 Sep 13 21:59 root
drwxr-xr-x. 25 root root 740 Sep 13 22:03 run
lrwxrwxrwx. 1 root root 8 Aug 17 02:40 sbin -> usr/sbin
drwxr-xr-x. 2 root root 6 Apr 11 2018 srv
dr-xr-xr-x. 13 root root 0 Sep 13 21:58 sys
drwxrwxrwt. 8 root root 172 Sep 13 22:58 tmp
drwxr-xr-x. 13 root root 155 Aug 17 02:40 usr
drwxr-xr-x. 19 root root 267 Aug 17 02:45 var

其中:

/boot

系统启动相关的文件,如内核,initrd,以及grub(bootloader)

/dev

设备文件

/etc

配置文件

/home

用户的家目录,每一个用户的家目录通常默认为:/home/USERNAME

/root

管理员的家目录

/lib

库文件

/media

挂载点目录,移动设备

/mnt

挂载点目录,额外的临时文件系统

/opt

可选目录,第三方程序的安装目录

/proc

伪文件系统,内核映射文件

/sys

伪文件系统,跟硬件设备相关的属性映射文件

/tmp

临时文件,/var/tmp

/var

可变化的文件,比如:日志文件,数据文件

/bin

可执行文件,用户命令

/sbin

管理命令

文件系统相关命令

df 显示磁盘的使用情况

du 显示文件系统的使用情况

ls 显示目录

Linux中的文件类型

- 普通文件

d 目录文件

b 块设备文件(block)

c 字符设备文件

l 符号链接文件(symbolic link file)

p 命令管道文件(pipe)

s 套接字文件(socket)

文件基本信息说明

image

image

阅读全文 »

作者:Grey

原文地址:Spring如何解决循环依赖

如果X这个类依赖了Y,Y这个类依赖了X,就产生了循环依赖。在普通Java(非Spring框架下),这并不是一个问题。

参考如下示例代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Demo {
public static void main(String[] args) {
X a = new X();
Y b = new Y();
a.y = b;
b.x = a;
System.out.println(a);
System.out.println(b);
}
}

class X {
Y y;
}

class Y {
X x;
}

但是Spring创建对象由于有相对复杂的生命周期,所以可能会导致循环依赖的问题,我们将如上代码转换成使用Spring的方式:

阅读全文 »