线段树： 线段树适合于处理区间。如图组织管理区间。 节点可以存放不同的数据，在书中实现了RMQ（Range Minimum Query）操作的数据结构。 RMQ是指给定若干个数据a[]，找出a[i…j]的最小值，同时允许更新a[k]。 针对RMQ，线段树的每个节点维护对应区间的最小值。如图 ...

3.2节讲了一个很通用的方法，叫尺取法。 尺取法通常设定前后两个指针，不断地按照某种策略移动前后指针，考察前后指针所限定的区间。 例如例题3.2.1：给定长度为n的整数序列，求出总和不小于S的连续子序列的长度的最小值。按照尺取法，设定前后指针s=0,t=0,然后将s向前 ...

《挑战程序设计竞赛》读书笔记（四）格点问题的证明 《挑战程序设计竞赛》2.6节第一道题中讲解了求线段上格点个数的问题，该解答给出了结果，但中间过程省略了不少内容。本文补充了相关的证明和解释。 问题描述如下： 格点是指平面坐标系中，横纵坐标都是整数的点。给定平面上两个格点，P1(x1,y1)， ...

2.5节图1. 图的搜索图的搜索可以用BFS和DFS。 二分图问题描述如下：给定一个图，判定是否可以用两种颜色涂顶点，使得有边相邻的两个顶点不同色。 这个问题可以用DFS遍历求解。着色时，确定当前点的颜色后，当前点相邻的点的颜色也随之确定。在DFS遍历过程中，如果没有出现着色冲突，说明可以用 ...

在读《挑战程序设计竞赛》时，想到了以前玩的一个小游戏—青蛙交换位置游戏。 游戏说明: (1) 用鼠标点青蛙头部向前跳，两边不同顏色的青蛙互換位置是最終目標. (2) 可以前進一步. (3) 最多只能跳過一個青蛙. (4) 一次一步，不限顏色 (5) 只能前進.不能後退. (6) 按红色箭头 ...

过了第一章的热身题之后，随后的题目难多了。本文只是对书中的部分题目，做了笔记。更多题目和详解，读者请参考原书和《算法导论》，《计算机算法设计与分析》（王晓东）等书。 2.2节贪心法贪心法是不断地取当前最优策略的算法设计方法。 找零钱问题：对于1,5,10,50,100,500面值的硬币各有C ...

超哥之前推荐过《挑战程序设计竞赛》一书。书名虽然说是应对竞赛，但该书同样适合于像我这样的普通的程序员用来提高一下算法能力。 今天读了几页，感觉收获很大，希望将来能够啃完，同时推荐给各位读者。 关于运行时间的估算 对于复杂度为O(n2)的算法，如果n<=1000，则要执行106 ...

在Quora上看到一个有趣的问题。”What are the best programming interview questions you’ve ever asked or been asked?” （在编程面试中，你问过或者被问过的最好的问题是什么）里面有几道题目很有意思，在这里分享给 ...

前两天同学聚会，聊到找工作的经历，发现很多细节记不起来了。今天回忆一下，权作备忘。 腾讯实习实验室不允许实习，不过师兄强烈建议找个实习，而且学校旁边就是腾讯，所以申请了腾讯的实习生。 该笔试题不难，最后一道题是选作。选择一是给一个长度为N的数字数组，要求将第i个元素变为其他N-1个数的乘积， ...

Cwinux源码解析系列系列说明： 本系列对Cwinux 2.3.7的部分代码进行了解析。如本系列第一篇博文所述，Cwinux是一个框架，结构比较复杂，从底层socket fd读取并构造消息，Reactor模式，创建线程池，Commander模式处理消息，以及更为复杂的异步Task等都有涉及 ...