《挑战程序设计竞赛》读书笔记（五）尺取法。本文介绍了尺取法。针对尺取法的思想，扩展介绍了双指针这种比较通用的方法，并给出了几个例子和对应的解法。

《挑战程序设计竞赛》2.6节第一道题中讲解了求线段上格点个数的问题，该解答给出了结果，但中间过程省略了不少内容。本文补充了相关的证明和解释。
问题描述如下：
格点是指平面坐标系中，横纵坐标都是整数的点。给定平面上两个格点，P1(x1,y1)，P2(x2,y2)，则线段P1P2上除了P1和P2外，有几个格点？事实上，该问题答案为|x2-x1|和|y2-y1|的最大公约数减1，并给出了一个图示。本文对该结论给出了证明。

逛Quora的时候，看到一个有趣的问题。”What are the best programming interview questions you've ever asked or been asked?” （在编程面试中，你问过或者被问过的最好的问题是什么）里面有几道题目很有意思，在这里分享给大家。
第一道题：有一个长度为N+1的数组，里面的元素都是1~N的整数，但有些数字可能重复多次。例如1,1,3 ,3或者 1,3,2,2。现在要求打印出重复的数字（有多个数字重复时，可打印任意一个）。
第二道题目：去掉大小王的52张扑克牌，你和你的朋友事先约定一种策略，使得：我任意给你5张扑克牌，你选择一张留下，剩余的4张给你的朋友，你的朋友能够根据事先约定的策略，知道你留下的牌是什么。
从连续不断的数字流中随机选取一个数字（数字流只能过一遍），要求保证任意时刻，已经过去的数字流中任意一个数字被选中的概率相等。
给定整数N，计算从1到N的数字的二进制表示中所有1的个数。