位图作为一种简高效使用内存的数据结构，在很多场合都能够用最省的内存表达大量的数据。我对位图最早的印象来自于《编程珠玑》中用位图结构来存储电话号码。感叹其简单、方便。本质上，位图是一个存储单个位的数组，每一个位表示一个数组元素。例如如果我们需要标记100万用户的在线状态，则可以将每个用户对应到一个位，只需要100万个位（约0.125M内存)的位图就可以表示了。如下图所示，在线的用户标记为绿色。其存储则可表示为 {01010011 0011…}。
但是对于某些比较稀疏的位图，其存储效率也会有一些问题。如果100万用户平均只有100个人在线，那另外的999,900个位就浪费掉了。例如在第1位有一个用户，第1,000,000位有个用户，需要1M个位来保存。既浪费了存储空间，也带来大量无用的运算。在前不久我们的应用中就有这种问题。未经压缩的位图保存到数据库中，结果大量的IO操作对数据库的性能造成较大影响。
因为稀疏的位图比较多，比较直接地就想去掉中间的这些空白位，于是就想这样表示：存储第一个位的值（0或1），接着将接下来的所有值相同的位的数目保存为一个整数，再保存接下来另的一类连续位的数目，依此类推。如：{0000 0000 1000 0000 0000 1100 0001 0000 …… } 保存为 0,7,1,11,2,5…。 如果是一百万个位，只有第一个和最后一个是1{10000 …. …. 1}，则保存为{1,999998,1}只需要三个整数就可以了！（注：实际上，早有人完整地将这种方法实现了，参考D-Gap Compression）
于是对比较稀疏的位图应用这种方法，由于大部分位图都是比较稀疏，90%以上的位图的体积最终缩小了10倍。在测试过程中，发现最终存储的是大量的小整数（小于1000）。这些小整数其实可以用更短的类型来表示，于是应用变长编码来处理。其原理是每一个字节的高位做标识，其余7位存储值。1标识从这个字节开始是一个新的整数，0表示是上一个字节的延续。则区间[1, 2^7 )中的整数占用一个字节，[2^7, 2^14)中的整数占用两个字节，依次类推。
最终，90%以上的位图体积压缩了30倍以上。
今天又做了个斐波那契数列相关的题目：上台阶，每次可走一台阶和两台阶，问上10个台阶有多少种走法。 （出处：阅微堂. EMC笔试 ， 89种) 。 上次的农夫养牛问题也是个斐波那契问题。
对于斐波那契这一类问题，因为特征过于鲜明，可以一看题目就套上，用的联想的思维方式就解决了。不过如果是在不熟悉此类问题时，首先是根据题目估计可用演绎推理来解决，然后尝试 f(1), f(2), f(3) = f(2)+f(1) 之类的推理。 演绎/推理确实是一项十分重要的解题方法，尤其是在对问题领域不熟悉的时候。
延伸阅读：
- 刘未鹏：知其所以然地学习（以算法为例）
有关25马问题，目前有很多讨论，但是还没有看到真正解决问题的讨论。
TopLanguage 上我的发言：我的发言是8次，应该是正确的，但是还没有找出数学上的理由。
TopLanguage上一个较早的讨论：这个讨论是相对比较意义的，有人说：
其实这个就是kth smallest element的算法，MIT 的 Introduction to Algorithms 里有详细的分析。
参见：http://videolectures.net/mit6046jf05_demaine_lec06/
还有人说：
这个问题应该是磁盘排序的问题的变种吧 在不能计时的情况下 我觉得n * n 匹马 m 条跑道起码需要
两个Blog文章：http://fayaa.com/tiku/view/91/ （有篇评论值得研究，说到是8场）
http://blog.solrex.cn/articles/25-horses-problem.html#comment-1738 （我对他的做法做了评论）
题： 有无序的实数列V[N]，要求求里面大小相邻的实数的差的最大值，关键是要求线性空间和线性时间
题目来自CSDN论坛里的讨论，很多网友给出了他们的意见。
其实这个问题要求线性时间条件下，通常会让我们想到桶排序；接着关键是考虑怎么减少桶排序中对桶中各数的排序即可想到解决方法。我的算法如下：
- 主要是先找出最大的数与最小的数，然后构造一个n个桶，桶的下标与数的关系为： index = (v[i]-min)/(max-min/n).
- 遍历数列，将数值插入到对应的桶中。每个桶最多保留最小和最大的两个元素，不需要多余的数。
- 遍历所有的桶，记录每个桶之间有多少个空桶到数据flags中，并求出最大连续空桶数 maxGap。
- 最后遍历flags数组，对于空桶数 >= maxGap -1 的元素，计算从前面的最近的不为空的桶中的大元素与当前桶中的最小元素的差，最终找出最大差。
主算法：
max,min ← GetMaxAndMin (v)
bucks[n];
for i = 0 to n-1
buckNo ← get buck no: (v[i]-min) / (max-min/n) //计算桶下标（如果不为整数，取较小的数的绝对值）
if buck[ buckNo ] is empty: insert v[i]
if buck[buckNo].length == 1 : //insert v[i] 与原来的数构成正序关系
if buck[buckNo].length == 2 : //与原来的2元素按正序关系排列，去掉中间的数，仍然是2个元素
// 标记每个不为空的桶元素之前有多少个空桶
flags[n]; //记录每个桶之前的空桶数目
maxgaps = 0;
tempgaps = 0;
for i ← FindFirstNotEmptyBuck (bucks) to n-1
if buck[i] is empty then
tempgaps ++
else
flags[i] ← tempgaps;
maxgaps ← GetMax (tempgaps, maxgaps)
tempgaps = 0;
// 计算最大的相邻的最大值
maxNeighbor == null;
for i ← 0 to n-1
if maxgaps - flag[i] < 2 then
maxNeighbor ← GetMax(COMPUTE_MAX(bucks,i,flag[i]), maxNeighbor)
return maxNeighborCOMPUTE_MAX(bucks,i,gap) :
//常数级别，取头或取尾
return GetMinEle(bucks, i) - getMaxEle(bucks, i - gap -1)
<pre lang="c">GetMaxAndMin (v):
max, min, i
n ← v.length
if n%2 == 0 then
if V[1] > V[0] then
max ← V[1]; min ← V[0];
else
max ← V[0]; min ← V[1];
i = 2;
else
max = min = V[0];
i = 1;
for i to n-2
if v[i+1] > v[i] then
min ←GetMin(min, v[i]);
max ← GetMax(max, v[i+1])
else
min ←GetMin(min, v[i+1]);
max ← GetMax(max, v[i])
i++; //每次取两个数
return (max,min)FindFirstNotEmptyBuck (bucks)
for i ← 0 to n-1
if tempgapstart == -1 then
if buck[i] is empty then
break
else
continue;
return i;
算法题来自 CSDN ：http://topic.csdn.net/u/20091001/15/40BF4993-8ED7-45CC-968F-97C524DAE3C4.html
问题： 一个农夫养了一头牛，三年后，这头牛每年会生出1头牛，生出来的牛三年后，又可以每年生出一头牛……问农夫10年后有多少头牛?n年呢？
这个问题的数学模型是类似于斐波那契（Fibonacci）数列，其计算式为：
F(n) = 1 , n<3
或
F(n) = F(n-3) + F(n-1) , n >=3
十年后是28头牛。实现算法时该贴提到了两种实现方式，一种是用过程的方法实现该数列，另一种是面向对象的方法实现。第二种方法确实更好一些，但是原帖实现似乎并不理想。
问题：
给你n个数a[1], a[2], …, a[n]，(0[1]。
这个题目看上去与动态规划很类似，在于其解的特点。设数列的前 n 个数的最大值为 F(n)，则：
证明从略。
代码如下：
package com.feihoo.test;
public class MaxSequenceValue {
static int[] nums = { 2, 4, -3, 9, 30, -30, 20, 0, 34, -2, -45, 12, -8, 11 };
public static void main(String[] args) {
int minLen = 2;
int maxLen = 4;
int[] m = new int[nums.length];
m[minLen - 1] = 0;
for (int i = minLen; i < nums.length; i++)
compute(i, m, minLen, maxLen);
int largest = m[minLen];
for (int i = minLen + 1; i < nums.length; i++)
if (largest < m[i])
largest = m[i];
System.out.println(largest);
}
private static void compute(int n, int[] m, int minLen, int maxLen) {
m[n] = m[n - 1];
for (int len = minLen; len < maxLen && n - len >= 0; len++) {
int re = nums[n];
for (int i = n - 1; i > n - len; i--)
re += nums[i];
if (m[n] < re)
m[n] = re;
}
}
}参考：
1. 来源： 动态规划习题
Recent Comments