这一章的前言部分很值得一看，特别是作者提到的另他印象深刻的一句话
A problem that seems difficult may have a simple, unexpected solution.
这章的原版名"Aha! Insight"，aha moment 的论述在心理学的领域早就诞生了，而且这个概念是有他的逻辑的，真是非常的神奇。Google 一下能看很多这方面的文章，知乎也有挺多的，似乎能总结出一些方法论呢，对咱平凡人思考问题解决问题确实有技巧性的提高，另外也很符合《Programming Pearls》所倡导的理念。
想想这章总结咱可以放前头了，特简单直白。原文是这么说的：
Unlike the advanced methods, the aha! insights of algorithms don't come only after extensive study; they're available to any programmer willing to think seriously before, during and after coding.
有点『曲不离口拳不离手』的意思，是不？好了，让我们看看这章主要阐述的问题吧！
问题
-
给定一个最多包含40亿个随机排列的32位整数的顺序文件，找出一个不在文件中的32位整数（在文件中至少缺少一个这样的数，为什么？）。在具有足够内存的情况下，如何解决该问题？如果有几个外部的“临时”文件可用，但是仅有几百字节的内存，又该如何解决该问题？
-
将一个n元一维向量左旋转i个位置。例如，当n=8且i=3时，向量abcdefgh旋转为defghabc。简单的代码使用一个n元的中间变量在n步内完成该工作。你能否仅使用数十个额外字节的存储空间，在正比于n的时间内完成向量的旋转？
- 给定一个英语词典，找出其中的所有变位词集合。例如，“pots","stop"和“tops"互为变位词，因为每个单词都可以通过改变其他单词中字母的顺序来得到。
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~思考5分钟先~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
好了，现在看看难吗？不是非常难吧。我相信解决方案多少都能有的，先说说我的。问题1，这里偷个懒可以直接用第一章的位图来解决，这需要一定的内存。问题2，因为左旋转数已知故按目标位替换。问题3，5分钟内没想出来，但可以摸出一种极其极其低效的方法，找出所有排列，然后比对，最后组合。当然希望你能够发现，最后一种方法在算法可行性的考虑上是不过关的:(
解决方案
对于问题1，作者给出的方案是从每个整数的32位的视角来考虑二分搜索。像对待位图那样通过每一位的0 or 1来设计算法，将数据二分。具体如下图所示：
总归是 2^32 = 4 294 967 296 > 4 000 000 000，一定是少数字的。现在就说假设2^32的全集为E，现有的40亿个数是C，少的那个集是D，我们总有：C + D = E。
那么经过0/1探测器二分后的数据集假设为 A 和 B，这里利用递归的思路，再通过服从单调递减的选集策略，筛选出至最后一个集合是空集，那这次空集的标记就是D集中的了，记录每次探测（分组）的标记就可以得到那个缺少的数了，代码如下：
package chpt2;
import com.google.common.primitives.Ints;
import java.text.DecimalFormat;
import java.util.LinkedList;
import java.util.List;
/**
* Created by wqi on 2016/10/23.
*/
public class Question2 {
private final char FLAG_A = '1';// 探测标志
private final char FLAG_B = '0';// 如上
private String D="";// 没出现的数
private int count = 0;// 相当于探测bit位的游标
private int digit;// 样本的二进制长度
public static void main(String[] args) {
int[] shu = {0, 1, 2, 3, 4, 5, 7};
Question2 q = new Question2();
List<Integer> integers = Ints.asList(shu);
q.digit = 3；
q.findAbsent(integers);
}
private List<Integer> group(List<Integer> E, char flag) {
List<Integer> result = new LinkedList<>();
for (int i : E) {
String s = Integer.toBinaryString(i);
DecimalFormat df = new DecimalFormat(generatePattern(this.digit));
char c = df.format(Integer.valueOf(s)).charAt(this.count - 1);
if (c == flag) {
result.add(i);
}
}
return result;
}
private String generatePattern(int count) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < count; i++) {
sb.append(0);
}
return sb.toString();
}
public void findAbsent(List<Integer> C) {
count = Integer.toBinaryString(C.size()).length();
List<Integer> A = this.group(C, FLAG_A);
List<Integer> B = this.group(C, FLAG_B);
if (C.size() == 0) {
String s = new StringBuilder(D).reverse().toString();
System.out.println("the absent number is " + Integer.parseInt(s, 2));
return;
}
if (A.size() > B.size()) {
D += FLAG_B;
this.findAbsent(B);
} else {
D += FLAG_A;
findAbsent(A);
}
}
}
大体的逻辑实现如上，也还有待完善的地方，例如：
没有把输入样本都转为32位整数(so lazy)；
没有充分考虑数集的稀疏程度和数组的长度做到弹性的匹配，比方说{242，32342432，6744566,...}就这种无规律来10个，也就是探测的次数没有和位数近似的场景。想了下，最后根据已知的输入整数位数对String D进行补0或者补1就可以了。
因为都是一边在这写一边实现的，时间长了有点累，另外说个写读书笔记的感受，就是这样读书的进度快不起来，但有助于消化书本的知识同时也加深理解。
本章还有两题，以及课后的习题讲解没涉及，待续。。。