倒水问题
问题描述：现有 8L 水，有一个 5L 的杯子和一个 3L 的杯子，如何得到 4L 的水？
问题解析：已知条件有三个杯子，8L、5L 和 3L。其中 8L 的杯子是满的。
解决方案：一共 7 步
- 将8L的水桶中的水，倒满5L的水桶，这时：8L水桶为3L、5L水桶为5L、3L水桶为0L
- 将5L的水桶中的水，倒满3L的水桶，这时：8L水桶为3L、5L水桶为2L、3L水桶为3L
- 将3L的水桶中的水，倒入8L的水桶，这时：8L水桶为6L、5L水桶为2L、3L水桶为0L
- 将5L的水桶中的水，倒入3L的水桶，这时：8L水桶为6L、5L水桶为0L、3L水桶为2L
- 将8L的水桶中的水，倒入5L的水桶，这时：8L水桶为1L、5L水桶为5L、3L水桶为2L
- 将5L的水桶中的水，倒满3L的水桶，这时：8L水桶为1L、5L水桶为4L、3L水桶为3L
- 将3L的水桶中的水，倒入8L的水桶，这时：8L水桶为4L、5L水桶为4L、3L水桶为0L
摘自：PHP/06-三个水桶等分8升水的问题 -《算法的乐趣》.md at master · xinliangnote/PHP
圆桌放硬币问题
问题描述：一张圆桌子，两个玩家轮流在桌子上放硬币，直到桌子放不下为止。而最后一个放硬币的人赢。请问如果我先放，如何保证我肯定赢？
问题解析：
- 这是一个空间问题
- 圆是一个对称的图形，除了圆心之外，其余点都能找到对称点。
解决方案：先行者在桌子中心放置一枚硬币，以后的硬币总是放在与后行者刚才放的地方相对称的位置。这样，只要后行者能放，先行者一定也有地方放。先行者必胜。
放球问题
问题描述：现在有50个红球，50个蓝球，给小明两个袋子，一个袋子能装任意个球(0~100)。 现由小明将这100个球，以一定方法装入这两个袋子。找另找一个不明真相的路人，闭眼，随机从两个袋子中随机选择一个袋子并摸一个球。要使得他摸出红球的概率最高，小明分配这100个球的最佳方案是什么？
问题解析：设从 1 号袋子取出红球概率是 s1，从 2 号袋子取出红球概率是 s2。则取出红球的概率 。题目变为求 `
解决方案：1号袋放入 1 个红球，剩下所有球放入 2 号袋时，概率最大，等于
直接切面问题
摘自：n条直线最多把平面分割成几部分？ n个平面最多把空间分割成几部分？_C/C++_Chunzhen的博客-CSDN博客
问题描述：n条直线最多把平面分割成几部分？
问题解析：
- 对于已有的
条直线，将平面切割为
个平面。
- 那么增加一条直线，它最多与前n条直线有n个交点，于是被它穿过的区域一分为二，那么增加的区域数等于穿过的区域数
- 穿过的区域数等于这条线被切割的段数
- 于是，就有了
答案：
如何估计湖中鱼的数量？
原理：抽样
具体方法：从湖中捞出 K 条鱼，然后进行标记，放回湖中；过段时间，再捞出 n 条鱼，其中有 k 条鱼是标记的，设 N 是湖中鱼总数，则有如下等式
数组中重复的数字
问题描述：在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。
问题解析：
- 特点：数组长度为
n，数组内的数字大小不会超过n-1。 - 如果使用
hashmap是无法充分利用该数组的特点。 - 数组内的元素可以当作数组下标；数组内的元素人为修改成超过
n-1就可以表示为被访问过。
解决方案
// 关键点：数组长度为 n，数组的元素只能是 0~n-1
// 思想：元素可以作为下标，当重复的元素得到的下标也是相同的，即重复的元素变为下标时，会访问同一个元素。
public boolean duplicate(int numbers[]) {
int length = numbers.length;
if(numbers == null || length < 1)
return false;
for(int i=0;i<length;i++){
// 将当前元素作为下标，访问number[index]。当后续元素出现了当前元素相同值时，必定会得到相同的index。
int index = numbers[i] % length;
if(numbers[index] >= length){ // 当访问的元素超过n-1时，表明该位置的元素之前被访问过
return true;
}
// 由于原先的元素大小不超过n-1，先加一个n，则该元素超过了n-1，表明该元素呗访问过
numbers[index] = numbers[index] + length;
}
return false;
}
网友评论