位图法应用

     使用位图法判断整形数组是否存在重复。判断集合中存在重复是常见编程任务之一，当集合中数据量比较大时我们通常希望少进行几次扫描，这时双重循环法就不可取了。

     位图法比较适合于这种情况，它的做法是按照集合中最大元素max创建一个长度为max+1的新数组，然后再次扫描原数组，遇到几就给新数组的第几位置上 1，如遇到5就给新数组的第六个元素置1，这样下次再遇到5想置位时发现新数组的第六个元素已经是1了，这说明这次的数据肯定和以前的数据存在着重复。这种给新数组初始化时置零其后置一的做法类似于位图的处理方法故称位图法。它的运算次数最坏的情况为2N。如果已知数组的最大值即能事先给新数组定长的话效率还能提高一倍。

1-[位图问题]

给40亿个不重复的unsigned int的整数，没排过序的，然后再给一个数，如何快速判断这个数是否在那40亿个数当中

2-[投票问题]

投票，甲得 M，乙得 N，票一张一张计，求计票过程中甲始终领先乙的概率（M>N）。

既无法一一枚举，故而简化之，以六票分甲四乙二为例。

甲票标为 A，乙票标为 B，枚举所有情况：AAAABB、AAABAB、AAABBA、AABAAB、AABABA、AABBAA、……不再枚举，因为从 AABBAA 开始，已经不能满足甲始终领先了。

做如下操作：从左往右遍历，做压栈处理，一旦栈顶处 A 与 B 相遇，则双双弹出栈，若遍历过程中栈终始不为空，则满足条件，否则，不满足条件。

如是操作之道理：相遇的 AB 互相抵消，对甲的领先没有任何影响。若遍历过程中栈内始终不为空，表示始终有未被抵销的票；由于甲乙交替领先权的一个必要条件就是计票过程中栈被清空，也即需要完全抵销对方的优势才可，故而又由于最终甲胜，栈内必然始终不得为空，留下的一定是甲票。

我们将上述枚举处理一下，抵消者以 X 代替，则有 AAXXXX、AAXXXX、AXXXXA、AXXAXX、AXXXXA、XXXXAA、……凡是第一个为 X 者，则表示栈被清空过，因此我们需要序列的第一项为 A。

换种思路：让序列的首尾相连成圈，然后在某一处切断它，形成一种序列。由于有 M + N 个结点，因此有 M + N 种断法。假设从圆外向圆内切，下刀的右侧为新序列起始点，左侧为末尾点。注意这里，会形成许多种圈，比如 AAXXXX、AXXAXX 就是两种圈，分别是两个 A 相连和不相连。但无论有多少种圈，只有从圆外向圆内切，切在 A 的左侧断链，才能保证新序列第一项为 A，由于圆内总共有 M - N 个 A，故每种圆都有 M - N 种切法。故而，概率为 (R*( M - N )) / (R*( M + N ))。R 为圆的种数，可将 R 上下消元，得最后结果为 ( M - N ) / ( M + N )

3-[室内布线问题]

装修房子是一项颇为复杂的工程，现在需要写一个程序帮助房主设计室内电线的布局。
  首先，墙壁上插座的位置是固定的。插座间需要有电线相连，而且要布置得整齐美观，即要求每条线都与至少一条墙边平行，且嵌入四壁或者地板（不能走屋顶）。
  房主想要知道，要将所有插座连通，自己需要买的电线最短长度是多少（取整数）？

1、每个房间都有门，电线不可以穿门而过。图中给出一个有4个插座的房间的电线布局。
2、输出时应注意，题目要求取整数，但不能四舍五入，必须向上取整，因为电线短一点就不能保证连通。
输入要求：
输入有若干测试数据组成
每组数据的第1行包含房间的长，宽，高和插座的个数N（N为一个不超过20的正整数）。
接下来的N行中，第i行给出第i个插座的位置坐标（xi，yi，zi）；最后一行包含4个3元组（x1，y1，z1）…（x4，y4，z4），分别是长方形门框的4角的三维坐标。4个数字全部为0表示全部测试结束，不要对数据做任何处理。

注意：这里假设长方体形状的房间完全位于三维直角坐标系的第一象限内，而且有一个角落在原点上。地板位于x-y平面。题目数据保证，每个插座仅属于四面墙中的一面，门上没有插座。要求每段电线的两端必须仅与插座连接，电线之间不能互相交叉焊接。

输出要求：
对每一组测试，在一行里输出要将所有插座连通需要买的电线的最短整数长度。

输入例子：
10 10 10 4
0 1 3.3
2.5 0 2
5 0 0.8
5 10 1
0 0 0 0 0 3 1.5 0 0 1.5 0 3
0 0 0 0

输出例子
21

4-[找最大值及其下标]

已知：
a[0] = 0;
a[1] = 1;
...
...
a[2*i] = a[i];
a[2*i+1] = a[i] + a[i+1];
问题：
给定任意一个i（0 <i <2000000)
求a[0]到a[i]之间的最大值，以及其下标。

5-[线段求交]

线段求交问题
问题：写一段多线程代码，用来查找在三维空间内相交的线段对。线段的输入文件和输出结果文件将在命令行上指定。

输入格式：输入文件是一个文本文件，它的第一行将包含一个整数 N，表示文件内包含的线段数。后面的 N 行将包含线段的 4 个（可打印）字符名称和用来表示线段两个 (x,y,z) 端点的 6 个整数。其中的前 3 个数字是一个端点的坐标，后 3 个数字是另一个端点的坐标。求解此问题的程序只要能在 32 位平台上正确运行即可满足精度要求。

输出格式：使用某种人类可读的格式。列出所输入线段中的每一对相交线段。如果没有交点，则打印一条消息说明无交点。

输入文件示例：
===================
8
AAAA -6 1 3 -8 4 -4
BBBB 3 -9 0 -3 -1 6
CCCC -1 -7 2 -4 -8 -4
DDDD 0 0 0 -1 6 2
EEEE 0 3 8 5 3 -7
FFFF 3 6 4 -4 0 -2
GGGG 8 -1 0 7 9 0
HHHH 11 8 0 10 -4 -3
输出文件示例：
====================
Segments that intersect:
DDDD FFFF
计时：将使用总执行时间进行计分。

6-[电梯问题]

问题如下:
一座楼里没有楼梯，只有一架电梯，电梯一次最多只能乘3人，已知楼共有20层，每层有一个人，每个人都有1~20中唯一的编号，他们要去对应的楼层。
  电梯初始状态：在一楼。
  目标状态：每个人在相应楼层。
试编写一个算法，完成目标状态，而且使电梯移动最小距离。

我的思路:
尽可能让电梯满载运行,而且优先解决远处的需求.使得电梯的运行轨迹类似于一个作往复运动的弹簧由于阻尼最后停下来. 对于正态分布的情况, 电梯最后的状态应接近于中点. 理想情况是对于平均分布的输入集合,电梯的运行层数为每个人的(需行层数+3+3)/3,之所以要加两个3是因为电梯在最初运行和达到目标的时候分别有一段必须空载的距离(在初始状态,电梯至少要运行三层才能装满). 当然对于大量数据来说, 实际运行的効率应该趋近这个最优结果的渐近线.

评论

1 楼 somefuture 2016-08-18  

第四题怎麼用位图法。写了半天没出来，用了下面的，速度很快
private static int seed = 2000000;

public static void main(String[] args) throws InterruptedException {
Random random = new Random();
int i = random.nextInt(seed);
System.err.println(i);
Thread.sleep(20);
int[] ints = new int[i];
int position = 0;
int start = 0;
for (int j = 0; j < i; j++) {
if (j < 2) {
ints[j] = j;
} else if (j >> 1 << 1 == j) {
ints[j] = ints[j >> 1];
} else {
ints[j] = ints[j >> 1] + ints[(j >> 1) + 1];
}
if (ints[j] > start) {
position = j;
start = ints[j];
}
}
System.err.println(position + ";;" + ints[position]);
}