面试常问算法题

1. 给定两个矩阵，问它们是否有交集

注意：这里的交集只要是存在任意两个点相交即为存在交集

对于矩阵X和矩阵Y，对于其四个角分别称为A,B,C,D，分别对应左上，右上，右下，左下四个角
必然存在A,B,C,D四个角中的任意一个角，这里以角A为例；
或者矩阵X的角被矩阵Y的角包围，或者矩阵Y的角被矩阵X的角包围，这里以矩阵X的角A被矩阵Y的角A包围为例；
那么拿矩阵X的角A去和矩阵Y的角C比较，如果说矩阵X的角A在矩阵Y的角C包围范围内，则说明两个矩阵有交集

包围范围：
左上角，包围范围为右下
左下角，包围范围为右上
右上角，包围范围为左下
右下角，包围范围为左上

struct Rec {
	// x1 <= x2, y1 <= y2，表示这个矩阵四个角的坐标值
	// top left: (x1, y2)
	// top right: (x2, y2)
	// bottom left: (x1, y1)
	// bottom right: (x2, y1)
	int x1, y1;
	int x2, y2; 
	Rec(int x1, int y1, int x2, int y2) : x1(x1), x2(x2), y1(y1), y2(y2) {}
	void out() {
		printf("------------------\n");
		printf("bottom left: (%d, %d)\n", x1, y1);
		printf("top right: (%d, %d)\n", x2, y2);
		printf("------------------\n");
	}
};

Rec R1(0, 0, 1, 1); 
Rec R2(0, 0, 2, 2);

2. rand_x()生成rand_y()

问题在于：如何使得生成\([1,y]\)的概率相等

对于这个问题，可以类比二维数组的实际存储形式。
二维数组的空间内存是一维的，即\(a[0][last]\)的下一个地址为\(a[1][0]\)
我们可以生成两次\(rand\_x\)，第一次用第一维，第二用在第二维，这样每个数生成的概率就是\(\frac{1}{x^2}\)
当生成的总数尽可能接近\(y\)的倍数，那么不能被映射的数就更少，本次操作的结果有效程度就更高

考虑如果\(x\)生成的总数是\(y\)的倍数，此时每个数都可以恰好映射。

这种情况发生在：\(y \mod x = 0\)时
此时\([1,y]\)中，\([kx+1,(k+1)x]\)映射到\([1,x]\)，其中\(k\geq 0\)

本质来说，我们通过类比二维数组的存储形式
实际上：如果我们有\(rand\_x()\)，可以等概率获得\([1,x\times x]\)
那么如果我们有\(rand\_a()\)和\(rand\_b()\)，就可以等概率获得\([1,a\times b]\)，这里既可以\(a\)做第一维，\(b\)做第二维，也可以\(b\)做第一维，\(a\)做第二维。

以\(rand\_7()\)生成\(rand\_10()\)为例
第一次我们生成了\([1,49]\)，其中\([1,40]\)可以对应映射到\([1,10]\)，\([41,49]\)可以看成我们在进行一次\(rand\_7()\)后得到的\(rand\_9()\)
再次利用\(rand\_7()\)获得\([1,63]\)，此时的\([1,60]\)映射到\([1,63]\)，\([61,63]\)可以看成我们在进行\(rand\_7()\)和\(rand\_9()\)后得到的\(rand\_3()\)
再次利用\(rand\_7()\)获得\([1,21]\)，此时的\([1,20]\)映射到\([1,20]\)，\([1,1]\)直接丢弃，因为和\(rand\_1()\)和\(rand\_()7\)只能得到\(rand\_7()\)，此时完成

这里我们可以看到，当\(rand\_x()\)和\(rand\_temp()\)得到的\(x\times temp < y\)时，已经无法覆盖\([1,y]\)了，这个\(temp\)就没什么用了，可以结束采样了。

这里单次被拒绝采样后，进行\(rand\_temp()\)和\(rand\_7()\)再次采样的概率相等，这是因为不管是被采样的部分和拒绝采样后再次采样的部分，映射到\([1,10]\)的概率都是相同的，相加后依然相同 。