\ 【算法杂谈 1】 从一道面试题再看三路快排partition
【算法杂谈 1】 从一道面试题再看三路快排partition
全栈工程师
创业者，全栈工程师。对技术开发，产品设计、前端后端，ios，html5，移动，桌面都有接触。拥有多款独立App作品。对一切可编程的东西有浓厚兴趣。相信编程改变一切。希望和大家交流程序之美：）个人公众号：是不是很酷。
作者的热门手记
在这次分享中，我将为大家回顾一下排序算法，同时，详细解析一下LeetCode中第75个问题：。这个问题是Facebook，Microsoft和Pocket Gems的面试题。在LeetCode中难度标记为Medium：）
在我的课程中，我向大家详细介绍了快速排序这个最经典的排序算法。在这里为大家简单复习一下，没有学习这门课程的同学，也可以简单看到一个轮廓。
快速排序算法的思路是每次选择一个元素作为标的点（pivot），将整个数组的所有元素分为小于这个元素和大于这个元素两部分，之后再递归地对左右两部分分别进行这个过程，直至整个数组有序。
显然，在这个过程中，“选择一个元素作为标的点（pivot），将整个数组的所有元素分为小于这个元素和大于这个元素两部分”这步操作是最重要的，也是快速排序的核心所在。这个步骤被称为 Partition。
如果使用一个辅助空间来实现Partition是一件非常简单的事情。但是如果不使用辅助空间，原地（in place）地进行partition，可能就稍微有些难度了。虽然有难度，但绝非高不可攀。有兴趣的同学，不妨把这个问题看作是一个面试题，自己实现一下看看：）（这是一个基础的需要大家能够进行白板编程的问题，请大家一定打好基础）
我们在课程中首先介绍了Partition的一个经典实现，代码简单优雅的令人发指：
（以下代码均使用C++代码，请其他语言的同学看懂逻辑以后尝试转换成自己熟悉的语言：））
// v为pivot，初始存储在arr[l]的位置
int j = // 循环过程保持 arr[l+1...j] & arr[j+1...i) & v
for( int i = l + 1 ; i &= i ++ )
if( arr[i] & v )
swap( arr[++j] , arr[i] );
swap( arr[l] , arr[j]);
// 此时，j指向pivot的正确位置
关于这个算法的动画演示，课程中有详细介绍，不再赘述。有兴趣的同学或者印象不深的同学，强烈建议用自己的小的测试用例（6-10个数据即可），用纸笔自己走一遍这个程序，加深理解：）
但我们很快就发现，这样的一个快排，在面临有序或者近乎有序的数组时，会退化成为一个O(n^2)的算法。于是我们使用了一个很简单的随机选取pivot的方式来处理这个问题。这步随机化让快速排序的时间期望成为了O(nlogn)，并且只有极低的概率退化为O(n^2)。关于这一点，背后的数学证明比较复杂，对背后的数学不感兴趣的同学，只要相信这个结论就好了。事实上，n不需要太大，在100这个量级，其退化成O(n^2)算法的概率就已经低于大家彩票中大奖的概率了：）
但是，我们又会发现，这样的一个快排，面对有大量重复元素的数据时，还是有可能退化成O(n^2)级别的。于是我们介绍了双路快排的Partition思路。通过这个思路，我们可以进一步优化，提出三路快排的思想。三路快排要做的事情，其实就是将数组分成三部分：小于v，等于v和大于v，之后递归的对小于v和大于v部分进行排序就好了。
三路快排的Partition代码是这样的。依然是，这个算法的动画演示，课程中有详细介绍，不再赘述。有兴趣的同学或者印象不深的同学，强烈建议用自己的小的测试用例（6-10个数据即可），用纸笔自己走一遍这个程序，加深理解：）
// v为pivot，初始存储在arr[l]的位置
// 循环过程中保持 arr[l+1...lt] & v
int gt = r + 1;
// 循环过程中保持 arr[gt...r] & v
int i = l+1;
// 循环过程中保持 arr[lt+1...i) == v
while( i & gt ){
if( arr[i] & v ){
swap( arr[i++], arr[lt+1]); lt ++;
else if( arr[i] & v ){
swap( arr[i], arr[gt-1]); gt --;
else // arr[i] == v
swap( arr[l] , arr[lt] );
// 此时 arr[lt...gt-1]部分为数组中元素等于v的部分
// 之后只需要递归地对arr[l...lt-1]和arr[gt...r]两部分进行三路快排即可
三路快排如此好的解决了近乎有序的数组和有大量重复数组的元素排序问题，以至于在很多语言的标准库中，排序接口使用的就是三路快排的思路，比如Java语言：）
好了，我们非常快速地回顾了一遍快速排序算法。下面，我们来看已到面试题：LeetCode上编号为75的题目：。请英文好，或者想练习英文的同学，直接点链接读题。只想阅读中文的同学，可以直接看下面的分析。
这个问题，LeetCode告诉我们，是Facebook，Microsoft和Pocket Gems的面试题。在LeetCode中难度标记为Medium。怎么样，是不是觉得很高大上？
题目大意是：有一个数组，其中的元素取值只有可能是0，1，2。为这样一个数组排序。
当然了，面对这个问题，大多数同学已经会想，肯定不是用普通的排序算法完成这个任务吧？嗯，既然题目有特殊的条件，肯定有其他的思路，但是如果在真正的面试或者笔试或者机试中，如果你一时没有更好的解法，用最笨的方法也比没有方法强。这就好像在实际项目中，我们不一定一上来就采用最优的解法解决问题，我们首先要解决问题，再谈优化。所以，这样解决问题，我觉得不寒碜：）
/// 解法一：直接使用排序接口，时间复杂度O(nlogn)
class Solution {
void sortColors(vector&int&& nums) {
sort( nums.begin(), nums.end() );
不过就像我们前面介绍的一样，这样的解法未免没有充分利用我们的数据的特殊性。要知道，我们的数据取值只有三种可能啊！那么，我们其实可以非常方便的使用一次扫面，计算出0，1，2三个元素的个数，然后直接把他们再按照0，1，2的顺序和个数，放回原数组不就好了！这样，我们只需要两次遍历：第一次统计元素个数，第二次放回原数组，就解决了问题！
/// 解法二：基于计数排序的解法，时间复杂度O(n)，需要两遍遍历
class Solution {
void sortColors(vector&int&& nums) {
int count[3] = {0};
// count[i]表示元素i的个数
for( int i = 0 ; i & nums.size() ; i ++ ){
assert( nums[i] &= 0 && nums[i] &= 2 );
count[ nums[i] ] += 1;
int index = 0;
for( int i = 0 ; i & count[0] ; i ++ ) // 安置count[0]个0
nums[index++] = 0;
for( int i = 0 ; i & count[1] ; i ++ ) // 安置count[1]个1
nums[index++] = 1;
for( int i = 0 ; i & count[2] ; i ++ ) // 安置count[2]个2
nums[index++] = 2;
上面的代码很好理解，在这里提示大家两个小问题。
大家可以看到，在第一遍遍历的时候，我添加了一个assert语句，来确保传入的nums中的每个元素，取值确实都是0，1，2的。这让我们的代码更严谨。当然了，对于错误处理，我们也可以抛异常或者走别的逻辑，在这里，我简单的使用assert。在面试过程中，表明我care这个问题了，点到即可。
大家可以看到，后面我是用了三次循环，分别按照0, 1, 2三个元素。这在这个问题中是有效的，但是如果我们的nums的取值范围是0-100呢？0-1000呢？事实上，同样的思路依然有效。但是，我们在第二次遍历安置元素的时候，就不能使用这样的写法了。那要怎么写？在这里给大家留一个小练习：）
事实上，这个算法的思路，就是计数排序（Counting Sort）算法的思路。计数排序可以使用O(n)的时间，来解决元素取值范围固定且相对较小的一组数据的排序问题。怎么样？是不是非常有意思？如果我们为我们的待排序数组加上一些条件限制，就能突破O(nlogn)这个界限。
实际上，我们经常说的排序算法复杂度至少为O(nlogn)，是有一个前提的，即我们的排序算法是基于元素间的比较的。换句话，严谨地说：基于比较的排序算法，其时间复杂度至少为O(nlogn)的。仔细看看我们上面的计数排序的思路，元素之间根本没有进行比较，我们不需要在任何时候看诸如nums[i]和nums[j]之间的大小关系。
非基于比较的排序算法还有一些，有兴趣以后再向大家介绍。在这里，希望大家通过这个问题，能够自学计数排序算法，完成一个更加灵活的计数排序算法的接口：）
算法有意思的地方就在于，我们总能问自己，是否可以做得更好？上面的解法将算法的时间复杂度降为了O(n)这个级别，但是需要进行两遍遍历。我们有没有可能使用一遍遍历完成这个问题？
再看看这个问题：将只有0,1,2三种元素的数组排序。如果我们对这个数组进行三路快排的话，并且选择1是pivot，那么第一次partition的过程，就会把数组分成小于1的部分和大于1的部分，也就是所有的0在1的左边；所有的2在1的右边，就已经完成了排序！换句话说，我们对整个数组进行一次以1为pivot的三路快排的partition就完成了排序！而且，只进行了一次遍历！
所以，我们只需要根据这个特殊的情况，改写三路快排的partition的思想就好了！在这里，我建议大家不要看之前的三路快排partition的代码，自己手写一下。我给出的参考答案如下：
/// 解法三：基于三路快排的partition的解法，时间复杂度O(n)，只需要一边遍历
class Solution {
void sortColors(vector&int&& nums) {
int i = 0;
// nums[0..&i) == 0
int j = 0;
// nums[i..&j) == 1
int k = nums.size(); // nums[k..&n) == 2
while( j & k ){
if( nums[j] == 1 )
else if( nums[j] == 0 )
swap( nums[i++] , nums[j++] );
else{ // nums[j] == 2
assert( nums[j] == 2 );
swap( nums[j] , nums[k-1] );
怎么样，是不是很酷？另外，我们的课程曾经提到过，swap操作背后其实有三个步骤。很多问题，我们可以用赋值操作替代swap操作，来进行常数级的优化。有兴趣的同学不妨试试看？对于这个问题，我们可以很容易的抛弃swap操作来完成：）
到这里，这个问题就为大家讲解完了。有没有觉得很简单的一个问题，也能引申出好多有意思的东西？
关于以上解析中，留的一些关于这道题目的更多优化解法，可以参加这个repo:
我们下一次分享见：）
关于我的更多文章，欢迎关注我的个人公众号：是不是很酷：）
相关标签：
本文原创发布于慕课网 ，转载请注明出处，谢谢合作！
请登录后，发表评论
评论（Enter+Ctrl）
评论加载中...
评论加载中...
Copyright (C)
All Rights Reserved | 京ICP备 号-2动态规划算法入门，需要搞懂这5个问题
我的图书馆
动态规划算法入门，需要搞懂这5个问题
不久前不少人留言说要介绍介绍动态规划，今天我们就来介绍介绍什么是动态规划。动态规划算法是现实中非常的一个算法。之前我们做过一个判断送餐的骑手能否在规定时间内送完手头的外卖，就用了这个算法。（当然，算出来的只是一个理论的结果，但可以防止骑手一下子接太多单，最后造成用户投诉）。后面如果有机会会介绍一下这个问题的实现。这个问题挺有趣的。可以抛出来给大家思考一下。现在有一个骑手，知道他的坐标，然后有一些外卖订单，我们知道每个订单的位置还有预计送达时间。我们能否快速判断这个骑手能否在规定时间内把这批订单送完。相比于直接搜索，动态规划往往更加高效。现在我们通过5个问题，来认识什么是动态规划。第一，什么是动态规划？动态规划（英语：Dynamic programming，简称DP）是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。重点在后半句，把问题分解成简单子问题进行解决。与之类似的有另外一个算法，分治。他俩最大的区别在于子问题之间是否相关联。第二， 动态规划的思想？动态规划的思想很简单，就是分解问题求解，然后再合并子问题的解。第三， 哪些问题可以用动态规划来解决？接下来的内容可能比较难以理解，我们通过一个经典的面试题，然后接着讲。最长上升子序列（LIS），有一串序列，要求找出它的一串子序列，这串子序列可以不连续，但必须满足它是严格的单调递増的且为最长的。把这个长度输出。示例：1 7 3 5 9 4 8 结果为4。1.最优子结构性质。如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质（即满足最优化原理）。上面的题目。如果我们假设f[3]表示以a[3]结尾的最长上升子序列，那么转移到它的子问题一定要是最优的。也就是从f[2]也要求是最优的。2.无后效性。即子问题的解一旦确定，就不再改变，不受在这之后、包含它的更大的问题的求解决策影响。如同上面那个问题，我们从左往右计算，右边后算的结果不会影响到左边的结果，即满足无后效性。3.子问题重叠性质。即同不同的子问题，可能都需要计算同一个另外的子问题。当我们要求已5为结尾的序列最多有多少个的时候，我们需要知道已3结尾的有多少个。当我们求以9结尾的序列最多有多少个的时候，我们又要去计算以3结尾的有多少个。这就是子问题重叠了。第四， 动态规划题目的解题策略大概怎么样。动态规划一般解决问题的流程可以如下面：初始状态→│决策１│→│决策２│→…→│决策ｎ│→结束状态1.首先是划分阶段，将问题分解为子问题。2.表示状态，如何用相应的数据结构表示每个子问题的状态。3.确定转移方程，子问题与子问题之间的关系已经方程的转移。4.确定边界。初始状态的边界，何时结束之类等。我们用上面的这个教程，来解决上面的LIS问题。首先，划分状态，我们确定了一下子问题，以第i个数结尾的最长上升子序列是多少。其次，表示状态，我们用f[i]表示以第i个数结尾的最长上升子序列是多少。第三转移方程，我们另j&i，不难看出，需要a[j]&a[i]才进行状态转移。所以f[i] = max{f[j] 1},a[j]&a[i]第四，边界条件,初始f[i] = 1,因为序列最少可以是他本身。结束条件为f[n-1](base 0)第五, 动态规划的题目大致可以分为几类？动态规划常见的模型有4大类：线性模型例如经典的上面的LIS问题，还有公共子序列问题树形模型区间模型背包问题例如经典的0-1背包,多重背包。好了，懂了这五个问题，基本上就算入门了。其实算法这种东西，并不是靠看一篇教程就能够马上理解的。后面，我们会在《一日一算法题》的系列中，再继续谈一谈动态规划。最后其实有一个有趣的问题，有没有人想尝试用《》枚举算法解决上面的LIS问题呢。复杂度又是多少呢？
你是否大概知道什么是动态规划 (单选)
大概明了，给小编加鸡腿
不懂，关注小编坐等其他题目
原创不易，欢迎大家关注我的头条号，也可以关注我的微信公众号（ddpcyh）,后续会提供算法学习资料，一起来学习算法吧。
TA的最新馆藏
喜欢该文的人也喜欢数据结构与算法面试题80道 - CSDN博客
数据结构与算法面试题80道
由于这些题，实在太火了。所以，应广大网友建议要求，在此把之前已整理公布的前80题，
现在，一次性分享出来。此也算是前80题第一次集体亮相。
此些题，已有上万人，看到或见识到，若私自据为己有，必定为有知之人识破，付出代价。
所以，作者声明：
本人July对以上所有任何内容和资料享有版权，转载请注明作者本人July出处。
向你的厚道致敬。谢谢。
----------------------------------------------------------------------------------------------------------------
1.把二元查找树转变成排序的双向链表
输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。
要求不能创建任何新的结点，只调整指针的指向。
&转换成双向链表
4=6=8=10=12=14=16。
&首先我们定义的二元查找树 节点的数据结构如下：
&struct BSTreeNode
&int m_nV // value of node
&BSTreeNode *m_pL // left child of node
&BSTreeNode *m_pR // right child of node
2.设计包含min函数的栈。
定义栈的数据结构，要求添加一个min函数，能够得到栈的最小元素。
要求函数min、push以及pop的时间复杂度都是O(1)。
3.求子数组的最大和
输入一个整形数组，数组里有正数也有负数。
数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。
求所有子数组的和的最大值。要求时间复杂度为O(n)。
例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5，和最大的子数组为3, 10, -4, 7, 2，
因此输出为该子数组的和18。
4.在二元树中找出和为某一值的所有路径
题目：输入一个整数和一棵二元树。
从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。
打印出和与输入整数相等的所有路径。
例如 输入整数22和如下二元树
则打印出两条路径：10, 12和10, 5, 7。
二元树节点的数据结构定义为：
struct BinaryTreeNode // a node in the binary tree
int m_nV // value of node
BinaryTreeNode *m_pL // left child of node
BinaryTreeNode *m_pR // right child of node
5.查找最小的k个元素
题目：输入n个整数，输出其中最小的k个。
例如输入1，2，3，4，5，6，7和8这8个数字，则最小的4个数字为1，2，3和4。
腾讯面试题：
给你10分钟时间，根据上排给出十个数，在其下排填出对应的十个数
要求下排每个数都是先前上排那十个数在下排出现的次数。
上排的十个数如下：
【0，1，2，3，4，5，6，7，8，9】
举一个例子，
数值: 0,1,2,3,4,5,6,7,8,9
分配: 6,2,1,0,0,0,1,0,0,0
0在下排出现了6次，1在下排出现了2次，
2在下排出现了1次，3在下排出现了0次....
以此类推..
微软亚院之编程判断俩个链表是否相交
给出俩个单向链表的头指针，比如h1，h2，判断这俩个链表是否相交。
为了简化问题，我们假设俩个链表均不带环。
问题扩展：
1.如果链表可能有环列?
2.如果需要求出俩个链表相交的第一个节点列?
此贴选一些 比较怪的题，，由于其中题目本身与算法关系不大，仅考考思维。特此并作一题。
1.有两个房间，一间房里有三盏灯，另一间房有控制着三盏灯的三个开关，
这两个房间是 分割开的，从一间里不能看到另一间的情况。
现在要求受训者分别进这两房间一次，然后判断出这三盏灯分别是由哪个开关控制的。
有什么办法呢？
2.你让一些人为你工作了七天，你要用一根金条作为报酬。金条被分成七小块，每天给出一块。
如果你只能将金条切割两次，你怎样分给这些工人?
3.　★用一种算法来颠倒一个链接表的顺序。现在在不用递归式的情况下做一遍。
　　★用一种算法在一个循环的链接表里插入一个节点，但不得穿越链接表。
　　★用一种算法整理一个数组。你为什么选择这种方法?
　　★用一种算法使通用字符串相匹配。
　　★颠倒一个字符串。优化速度。优化空间。
　　★颠倒一个句子中的词的顺序，比如将“我叫克丽丝”转换为“克丽丝叫我”，
实现速度最快，移动最少。
　　★找到一个子字符串。优化速度。优化空间。
　　★比较两个字符串，用O(n)时间和恒量空间。
　 　★假设你有一个用1001个整数组成的数组，这些整数是任意排列的，但是你知道所有的整数都在1到1000(包括1000)之间。此外，除一个数字出现 两次外，其他所有数字只出现一次。假设你只能对这个数组做一次处理，用一种算法找出重复的那个数字。如果你在运算中使用了辅助的存储方式，那么你能找到不 用这种方式的算法吗?
　　★不用乘法或加法增加8倍。现在用同样的方法增加7倍。
判断整数序列是不是二元查找树的后序遍历结果
题目：输入一个整数数组，判断该数组是不是某二元查找树的后序遍历的结果。
如果是返回true，否则返回false。
例如输入5、7、6、9、11、10、8，由于这一整数序列是如下树的后序遍历结果：
&&&&&&&& 8
&&&& 6&&& 10
&&& / \&/ \
&& 5&7 9&11
因此返回true。
如果输入7、4、6、5，没有哪棵树的后序遍历的结果是这个序列，因此返回false。
翻转句子中单词的顺序。
题目：输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。
句子中单词以空格符隔开。为简单起见，标点符号和普通字母一样处理。
例如输入“I am a student.”，则输出“student. a am I”。
求二叉树中节点的最大距离...
如果我们把二叉树看成一个图，父子节点之间的连线看成是双向的，
我们姑且定义&距离&为两节点之间边的个数。
写一个程序，
求一棵二叉树中相距最远的两个节点之间的距离。
题目：求1+2+…+n，
要求不能使用乘除法、for、while、if、else、switch、case等关键字以及条件判断语句（A?B:C）。
题目：输入一个单向链表，输出该链表中倒数第k个结点。链表的倒数第0个结点为链表的尾指针。
链表结点定义如下：&
struct ListNode
&ListNode* m_pN
题目：输入一个已经按升序排序过的数组和一个数字，
在数组中查找两个数，使得它们的和正好是输入的那个数字。
要求时间复杂度是O(n)。如果有多对数字的和等于输入的数字，输出任意一对即可。
例如输入数组1、2、4、7、11、15和数字15。由于4+11=15，因此输出4和11。
题目：输入一颗二元查找树，将该树转换为它的镜像，
即在转换后的二元查找树中，左子树的结点都大于右子树的结点。
用递归和循环两种方法完成树的镜像转换。&
例如输入：
定义二元查找树的结点为：
struct BSTreeNode // a node in the binary search tree (BST)
&int m_nV // value of node
&BSTreeNode *m_pL // left child of node
&BSTreeNode *m_pR // right child of node
题目（微软）：
输入一颗二元树，从上往下按层打印树的每个结点，同一层中按照从左往右的顺序打印。&
输出8 6 10 5 7 9 11。
题目：在一个字符串中找到第一个只出现一次的字符。如输入abaccdeff，则输出b。&
分析：这道题是2006年google的一道笔试题。
题目：n个数字（0,1,…,n-1）形成一个圆圈，从数字0开始，
每次从这个圆圈中删除第m个数字（第一个为当前数字本身，第二个为当前数字的下一个数字）。
当一个数字删除后，从被删除数字的下一个继续删除第m个数字。
求出在这个圆圈中剩下的最后一个数字。
July：我想，这个题目，不少人已经 见识过了。
题目：定义Fibonacci数列如下：&
f(n)= 1 n=1
&\ f(n-1)+f(n-2) n=2
输入n，用最快的方法求该数列的第n项。
分析：在很多C语言教科书中讲到递归函数的时候，都会用Fibonacci作为例子。
因此很多程序员对这道题的递归解法非常熟悉，但....呵呵，你知道的。。
题目：输入一个表示整数的字符串，把该字符串转换成整数并输出。
例如输入字符串&345&，则输出整数345。
2010年中兴面试题
编程求解：
输入两个整数 n 和 m，从数列1，2，3.......n 中 随意取几个数,
使其和等于 m ,要求将其中所有的可能组合列出来.
有4张红色的牌和4张蓝色的牌，主持人先拿任意两张，再分别在A、B、C三人额头上贴任意两张牌，
A、B、C三人都可以看见其余两人额头上的牌，看完后让他们猜自己额头上是什么颜色的牌，
A说不知道，B说不知道，C说不知道，然后A说知道了。
请教如何推理，A是怎么知道的。
如果用程序，又怎么实现呢？
用最简单，最快速的方法计算出下面这个圆形是否和正方形相交。&&
3D坐标系 原点(0.0,0.0,0.0)
半径r = 3.0
圆心o = (*.*, 0.0, *.*)
4个角坐标;&
1:(*.*, 0.0, *.*)
2:(*.*, 0.0, *.*)
3:(*.*, 0.0, *.*)
4:(*.*, 0.0, *.*)
链表操作，
（1）.单链表就地逆置，
（2）合并链表
写一个函数,它的原形是int continumax(char *outputstr,char *intputstr)
在字符串中找出连续最长的数字串，并把这个串的长度返回，
并把这个最长数字串付给其中一个函数参数outputstr所指内存。
例如：&abcd1ss&的首地址传给intputstr后，函数将返回9，
outputstr所指的值为
26.左旋转字符串
定义字符串的左旋转操作：把字符串前面的若干个字符移动到字符串的尾部。
如把字符串abcdef左旋转2位得到字符串cdefab。请实现字符串左旋转的函数。
要求时间对长度为n的字符串操作的复杂度为O(n)，辅助内存为O(1)。
27.跳台阶问题
题目：一个台阶总共有n级，如果一次可以跳1级，也可以跳2级。
求总共有多少总跳法，并分析算法的时间复杂度。
这道题最近经常出现，包括MicroStrategy等比较重视算法的公司
都曾先后选用过个这道题作为面试题或者笔试题。
28.整数的二进制表示中1的个数
题目：输入一个整数，求该整数的二进制表达中有多少个1。
例如输入10，由于其二进制表示为1010，有两个1，因此输出2。
这是一道很基本的考查位运算的面试题。
包括微软在内的很多公司都曾采用过这道题。
29.栈的push、pop序列
题目：输入两个整数序列。其中一个序列表示栈的push顺序，
判断另一个序列有没有可能是对应的pop顺序。
为了简单起见，我们假设push序列的任意两个整数都是不相等的。&
比如输入的push序列是1、2、3、4、5，那么4、5、3、2、1就有可能是一个pop系列。
因为可以有如下的push和pop序列：
push 1，push 2，push 3，push 4，pop，push 5，pop，pop，pop，pop，
这样得到的pop序列就是4、5、3、2、1。
但序列4、3、5、1、2就不可能是push序列1、2、3、4、5的pop序列。
30.在从1到n的正数中1出现的次数
题目：输入一个整数n，求从1到n这n个整数的十进制表示中1出现的次数。
例如输入12，从1到12这些整数中包含1 的数字有1，10，11和12，1一共出现了5次。
分析：这是一道广为流传的google面试题。
31.华为面试题：
一类似于蜂窝的结构的图，进行搜索最短路径（要求5分钟）
有两个序列a,b，大小都为n,序列元素的值任意整数，无序；
要求：通过交换a,b中的元素，使[序列a元素的和]与[序列b元素的和]之间的差最小。
var a=[100,99,98,1,2, 3];
var b=[1, 2, 3, 4,5,40];
实现一个挺高级的字符匹配算法：
给一串很长字符串，要求找到符合要求的字符串，例如目的串：123
1******3***2 ,12*****3这些都要找出来
其实就是类似一些和谐系统。。。。。
实现一个队列。
队列的应用场景为：
一个生产者线程将int类型的数入列，一个消费者线程将int类型的数出列
求一个矩阵中最大的二维矩阵(元素和最大).如:
中最大的是:
要求:(1)写出算法;(2)分析时间复杂度;(3)用C写出关键代码
第36题-40题（有些题目搜集于CSDN上的网友，已标明）：
36.引用自网友：longzuo
谷歌笔试：
n支队伍比赛，分别编号为0，1，2。。。。n-1，已知它们之间的实力对比关系，
存储在一个二维数组w[n][n]中，w[i][j] 的值代表编号为i，j的队伍中更强的一支。
所以w[i][j]=i 或者j，现在给出它们的出场顺序，并存储在数组order[n]中，
比如order[n] = {4,3,5,8,1......}，那么第一轮比赛就是 4对3， 5对8。.......
胜者晋级，败者淘汰，同一轮淘汰的所有队伍排名不再细分，即可以随便排，
下一轮由上一轮的胜者按照顺序，再依次两两比，比如可能是4对5,直至出现第一名
编程实现，给出二维数组w，一维数组order 和 用于输出比赛名次的数组result[n]，
求出result。
有n个长为m+1的字符串，
如果某个字符串的最后m个字符与某个字符串的前m个字符匹配，则两个字符串可以联接，
问这n个字符串最多可以连成一个多长的字符串，如果出现循环，则返回错误。
百度面试：
1.用天平（只能比较，不能称重）从一堆小球中找出其中唯一一个较轻的，使用x次天平，
最多可以从y个小球中找出较轻的那个，求y与x的关系式。
2.有一个很大很大的输入流，大到没有存储器可以将其存储下来，
而且只输入一次，如何从这个输入流中随机取得m个记录。
3.大量的URL字符串，如何从中去除重复的，优化时间空间复杂度
网易有道笔试：
求一个二叉树中任意两个节点间的最大距离，
两个节点的距离的定义是 这两个节点间边的个数，
比如某个孩子节点和父节点间的距离是1，和相邻兄弟节点间的距离是2，优化时间空间复杂度。
求一个有向连通图的割点，割点的定义是，如果除去此节点和与其相关的边，
有向图不再连通，描述算法。
40.百度研发笔试题
引用自：zp
1)设计一个栈结构，满足一下条件：min，push，pop操作的时间复杂度为O(1)。
2)一串首尾相连的珠子(m个)，有N种颜色(N&=10)，
设计一个算法，取出其中一段，要求包含所有N中颜色，并使长度最短。
并分析时间复杂度与空间复杂度。
3)设计一个系统处理词语搭配问题，比如说 中国 和人民可以搭配，
则中国人民 人民中国都有效。要求：
&*系统每秒的查询数量可能上千次；
&*词语的数量级为10W；
&*每个词至多可以与1W个词搭配
当用户输入中国人民的时候，要求返回与这个搭配词组相关的信息。
41.求固晶机的晶元查找程序
晶元盘由数目不详的大小一样的晶元组成，晶元并不一定全布满晶元盘，
照相机每次这能匹配一个晶元，如匹配过，则拾取该晶元，
若匹配不过，照相机则按测好的晶元间距移到下一个位置。
求遍历晶元盘的算法 求思路。
42.请修改append函数，利用这个函数实现：
两个非降序链表的并集，1-&2-&3 和 2-&3-&5 并为 1-&2-&3-&5
另外只能输出结果，不能修改两个链表的数据。
43.递归和非递归俩种方法实现二叉树的前序遍历。
44.腾讯面试题：
1.设计一个魔方（六面）的程序。
2.有一千万条短信，有重复，以文本文件的形式保存，一行一条，有重复。
请用5分钟时间，找出重复出现最多的前10条。
3.收藏了1万条url，现在给你一条url，如何找出相似的url。（面试官不解释何为相似）
1.对于一个整数矩阵，存在一种运算，对矩阵中任意元素加一时，需要其相邻（上下左右）
某一个元素也加一，现给出一正数矩阵，判断其是否能够由一个全零矩阵经过上述运算得到。
2.一个整数数组，长度为n，将其分为m份，使各份的和相等，求m的最大值
&&比如{3，2，4，3，6} 可以分成{3，2，4，3，6} m=1;
&{3,6}{2,4,3} m=2
&{3,3}{2,4}{6} m=3 所以m的最大值为3
四对括号可以有多少种匹配排列方式？比如两对括号可以有两种：（）（）和（（））
47.创新工场：
求一个数组的最长递减子序列 比如{9，4，3，2，5，4，3，2}的最长递减子序列为{9，5，4，3，2}
一个数组是由一个递减数列左移若干位形成的，比如{4，3，2，1，6，5}
是由{6，5，4，3，2，1}左移两位形成的，在这种数组中查找某一个数。
49.一道看上去很吓人的算法面试题：
如何对n个数进行排序，要求时间复杂度O(n)，空间复杂度O(1)
50.网易有道笔试：
1.求一个二叉树中任意两个节点间的最大距离，两个节点的距离的定义是 这两个节点间边的个数，
比如某个孩子节点和父节点间的距离是1，和相邻兄弟节点间的距离是2，优化时间空间复杂度。
2.求一个有向连通图的割点，割点的定义是，
如果除去此节点和与其相关的边，有向图不再连通，描述算法。
-------------------------------------------------------------------
51.和为n连续正数序列。
题目：输入一个正数n，输出所有和为n连续正数序列。
例如输入15，由于1+2+3+4+5=4+5+6=7+8=15，所以输出3个连续序列1-5、4-6和7-8。
分析：这是网易的一道面试题。
52.二元树的深度。
题目：输入一棵二元树的根结点，求该树的深度。
从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。
例如：输入二元树：
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& 10
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& /&&&& \
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& 6&&&&&&& 14
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& /&&&&&&&& /&& \
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& 4&&&&& &&&12&&&& 16
输出该树的深度3。
二元树的结点定义如下：
struct SBinaryTreeNode // a node of the binary tree
&&&&& int&&&&&&&&&&&&&& m_nV // value of node
&&&&& SBinaryTreeNode&*m_pL&// left child of node
&&&&& SBinaryTreeNode&*m_pR // right child of node
分析：这道题本质上还是考查二元树的遍历。
53.字符串的排列。
题目：输入一个字符串，打印出该字符串中字符的所有排列。
例如输入字符串abc，则输出由字符a、b、c所能排列出来的所有字符串
abc、acb、bac、bca、cab和cba。
分析：这是一道很好的考查对递归理解的编程题，
因此在过去一年中频繁出现在各大公司的面试、笔试题中。
54.调整数组顺序使奇数位于偶数前面。
题目：输入一个整数数组，调整数组中数字的顺序，使得所有奇数位于数组的前半部分，
所有偶数位于数组的后半部分。要求时间复杂度为O(n)。
题目：类CMyString的声明如下：
class CMyString
&&&&& CMyString(char* pData = NULL);
&&&&& CMyString(const CMyString& str);
&&&&& ~CMyString(void);
&&&&& CMyString& operator = (const CMyString& str);
&&&&& char* m_pD
请实现其赋值运算符的重载函数，要求异常安全，即当对一个对象进行赋值时发生异常，对象的状态不能改变。
56.最长公共字串。
题目：如果字符串一的所有字符按其在字符串中的顺序出现在另外一个字符串二中，
则字符串一称之为字符串二的子串。
注意，并不要求子串（字符串一）的字符必须连续出现在字符串二中。
请编写一个函数，输入两个字符串，求它们的最长公共子串，并打印出最长公共子串。
例如：输入两个字符串BDCABA和ABCBDAB，字符串BCBA和BDAB都是是它们的最长公共子串，
则输出它们的长度4，并打印任意一个子串。
分析：求最长公共子串（Longest Common Subsequence, LCS）是一道非常经典的动态规划题，
因此一些重视算法的公司像MicroStrategy都把它当作面试题。
57.用俩个栈实现队列。
题目：某队列的声明如下：
template&typename T& class CQueue
&&&&& CQueue() {}
&&&&& ~CQueue() {}
&&&&& void appendTail(const T& node);&// append a element to tail
&&&&& void deleteHead();&&&&&&&&&&&&&& // remove a element from head
&&&& T& m_stack1;
&&&& T& m_stack2;
分析：从上面的类的声明中，我们发现在队列中有两个栈。
因此这道题实质上是要求我们用两个栈来实现一个队列。
相信大家对栈和队列的基本性质都非常了解了：栈是一种后入先出的数据容器，
因此对队列进行的插入和删除操作都是在栈顶上进行；队列是一种先入先出的数据容器，
我们总是把新元素插入到队列的尾部，而从队列的头部删除元素。
58.从尾到头输出链表。
题目：输入一个链表的头结点，从尾到头反过来输出每个结点的值。链表结点定义如下：
struct ListNode
&&&&& int&&&&&& m_nK
&&&&& ListNode* m_pN
分析：这是一道很有意思的面试题。
该题以及它的变体经常出现在各大公司的面试、笔试题中。
59.不能被继承的类。
题目：用C++设计一个不能被继承的类。
分析：这是Adobe公司2007年校园招聘的最新笔试题。
这道题除了考察应聘者的C++基本功底外，还能考察反应能力，是一道很好的题目。
60.在O（1）时间内删除链表结点。
题目：给定链表的头指针和一个结点指针，在O(1)时间删除该结点。链表结点的定义如下：
struct ListNode
&&&&& int&&&&&&& m_nK
&&&&& ListNode*&m_pN
函数的声明如下：
void DeleteNode(ListNode* pListHead, ListNode* pToBeDeleted);
分析：这是一道广为流传的Google面试题，能有效考察我们的编程基本功，还能考察我们的反应速度，
更重要的是，还能考察我们对时间复杂度的理解。
-------------------------------------------------------------------------
61.找出数组中两个只出现一次的数字
题目：一个整型数组里除了两个数字之外，其他的数字都出现了两次。
请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
分析：这是一道很新颖的关于位运算的面试题。
62.找出链表的第一个公共结点。
题目：两个单向链表，找出它们的第一个公共结点。
链表的结点定义为：
struct ListNode
&&&&& int&&&&&&&& m_nK
&&&&& ListNode*&& m_pN
分析：这是一道微软的面试题。微软非常喜欢与链表相关的题目，
因此在微软的面试题中，链表出现的概率相当高。
63.在字符串中删除特定的字符。
题目：输入两个字符串，从第一字符串中删除第二个字符串中所有的字符。例如，输入”They are students.”和”aeiou”，
则删除之后的第一个字符串变成”Thy r stdnts.”。
分析：这是一道微软面试题。在微软的常见面试题中，与字符串相关的题目占了很大的一部分，
因为写程序操作字符串能很好的反映我们的编程基本功。
64. 寻找丑数。
题目：我们把只包含因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，
但14不是，因为它包含因子7。习惯上我们把1当做是第一个丑数。
求按从小到大的顺序的第1500个丑数。
分析：这是一道在网络上广为流传的面试题，据说google曾经采用过这道题。
65.输出1到最大的N位数
题目：输入数字n，按顺序输出从1最大的n位10进制数。比如输入3，
则输出1、2、3一直到最大的3位数即999。
分析：这是一道很有意思的题目。看起来很简单，其实里面却有不少的玄机。
66.颠倒栈。
题目：用递归颠倒一个栈。例如输入栈{1, 2, 3, 4, 5}，1在栈顶。
颠倒之后的栈为{5, 4, 3, 2, 1}，5处在栈顶。
67.俩个闲玩娱乐。
1.扑克牌的顺子
从扑克牌中随机抽5张牌，判断是不是一个顺子，即这5张牌是不是连续的。
2-10为数字本身，A为1，J为11，Q为12，K为13，而大小王可以看成任意数字。
2.n个骰子的点数。
把n个骰子扔在地上，所有骰子朝上一面的点数之和为S。输入n，
打印出S的所有可能的值出现的概率。
68.把数组排成最小的数。
题目：输入一个正整数数组，将它们连接起来排成一个数，输出能排出的所有数字中最小的一个。
例如输入数组{32,&321}，则输出这两个能排成的最小数字32132。
请给出解决问题的算法，并证明该算法。
分析：这是09年6月份百度的一道面试题，
从这道题我们可以看出百度对应聘者在算法方面有很高的要求。
69.旋转数组中的最小元素。
题目：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个排好序的数组的一个旋转，
输出旋转数组的最小元素。例如数组{3, 4, 5, 1, 2}为{1, 2, 3, 4, 5}的一个旋转，该数组的最小值为1。
&&&&分析：这道题最直观的解法并不难。从头到尾遍历数组一次，就能找出最小的元素，
时间复杂度显然是O(N)。但这个思路没有利用输入数组的特性，我们应该能找到更好的解法。
70.给出一个函数来输出一个字符串的所有排列。
ANSWER 简单的回溯就可以实现了。当然排列的产生也有很多种算法，去看看组合数学，
还有逆序生成排列和一些不需要递归生成排列的方法。
印象中Knuth的&TAOCP&第一卷里面深入讲了排列的生成。这些算法的理解需要一定的数学功底，
也需要一定的灵感，有兴趣最好看看。
71.数值的整数次方。
题目：实现函数double Power(double base, int exponent)，求base的exponent次方。
不需要考虑溢出。
分析：这是一道看起来很简单的问题。可能有不少的人在看到题目后30秒写出如下的代码：
double Power(double base, int exponent)
&&&&& double result = 1.0;
&&&&& for(int i = 1; i &= ++i)
&&&&&&&&&&& result *=
题目：设计一个类，我们只能生成该类的一个实例。
分析：只能生成一个实例的类是实现了Singleton模式的类型。
73.对策字符串的最大长度。
题目：输入一个字符串，输出该字符串中对称的子字符串的最大长度。
比如输入字符串“google”，由于该字符串里最长的对称子字符串是“goog”，因此输出4。
分析：可能很多人都写过判断一个字符串是不是对称的函数，这个题目可以看成是该函数的加强版。
74.数组中超过出现次数超过一半的数字
题目：数组中有一个数字出现的次数超过了数组长度的一半，找出这个数字。
分析：这是一道广为流传的面试题，包括百度、微软和Google在内的多家公司都
曾经采用过这个题目。要几十分钟的时间里很好地解答这道题，
除了较好的编程能力之外，还需要较快的反应和较强的逻辑思维能力。
75.二叉树两个结点的最低共同父结点
题目：二叉树的结点定义如下：
struct TreeNode
&&& int m_
&&& TreeNode* m_pL
&&& TreeNode* m_pR
输入二叉树中的两个结点，输出这两个结点在数中最低的共同父结点。
分析：求数中两个结点的最低共同结点是面试中经常出现的一个问题。这个问题至少有两个变种。
76.复杂链表的复制
题目：有一个复杂链表，其结点除了有一个m_pNext指针指向下一个结点外，
还有一个m_pSibling指向链表中的任一结点或者NULL。其结点的C++定义如下：
&struct ComplexNode
&&& int m_nV
&&& ComplexNode* m_pN
&&& ComplexNode* m_pS
下图是一个含有5个结点的该类型复杂链表。
图中实线箭头表示m_pNext指针，虚线箭头表示m_pSibling指针。为简单起见，
指向NULL的指针没有画出。&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
请完成函数ComplexNode* Clone(ComplexNode* pHead)，以复制一个复杂链表。
分析：在常见的数据结构上稍加变化，这是一种很新颖的面试题。
要在不到一个小时的时间里解决这种类型的题目，我们需要较快的反应能力，
对数据结构透彻的理解以及扎实的编程功底。
77.关于链表问题的面试题目如下：
1.给定单链表，检测是否有环。
&使用两个指针p1,p2从链表头开始遍历，p1每次前进一步，p2每次前进两步。如果p2到达链表尾部，
说明无环，否则p1、p2必然会在某个时刻相遇(p1==p2)，从而检测到链表中有环。
2.给定两个单链表(head1, head2)，检测两个链表是否有交点，如果有返回第一个交点。
&&&&&&&&如果head1==head2，那么显然相交，直接返回head1。
否则，分别从head1,head2开始遍历两个链表获得其长度len1与len2，假设len1&=len2，
那么指针p1由head1开始向后移动len1-len2步，指针p2=head2，
下面p1、p2每次向后前进一步并比较p1p2是否相等，如果相等即返回该结点，
否则说明两个链表没有交点。
3.给定单链表(head)，如果有环的话请返回从头结点进入环的第一个节点。
&&&&&&&&运用题一，我们可以检查链表中是否有环。
&&&&&&&&如果有环，那么p1p2重合点p必然在环中。从p点断开环，
方法为：p1=p, p2=p-&next, p-&next=NULL。此时，原单链表可以看作两条单链表，
一条从head开始，另一条从p2开始，于是运用题二的方法，我们找到它们的第一个交点即为所求。
4.只给定单链表中某个结点p(并非最后一个结点，即p-&next!=NULL)指针，删除该结点。
&办法很简单，首先是放p中数据,然后将p-&next的数据copy入p中，接下来删除p-&next即可。
5.只给定单链表中某个结点p(非空结点)，在p前面插入一个结点。
&&办法与前者类似，首先分配一个结点q，将q插入在p后，接下来将p中的数据copy入q中，
然后再将要插入的数据记录在p中。
78.链表和数组的区别在哪里？
分析：主要在基本概念上的理解。
但是最好能考虑的全面一点，现在公司招人的竞争可能就在细节上产生，
谁比较仔细，谁获胜的机会就大。
1.编写实现链表排序的一种算法。说明为什么你会选择用这样的方法？
2.编写实现数组排序的一种算法。说明为什么你会选择用这样的方法？
3.请编写能直接实现strstr()函数功能的代码。
80.阿里巴巴一道笔试题
12个高矮不同的人,排成两排,每排必须是从矮到高排列,而且第二排比对应的第一排的人高,问排列方式有多少种?
这个笔试题,很YD,因为把某个递归关系隐藏得很深。
本文已收录于以下专栏：
相关文章推荐
1、说明：一般解决大数据问题有两个思路：
1）先将与这道题相关的所有的数据结构进行使用一遍，如果有合适的就直接进行使用
2）如果不能直接使用，一般就要进行哈希切分，然后再使用合适...
一趟快速排序的算法是：
1）设置两个变量i、j，排序开始的时候：i=0，j=N-1；
2）以第一个数组元素作为关键数据，赋值给key，即key=A[0]；
3）从j开始向前搜索，即由...
1、假设淘宝一天有5亿条成交数据，求出销量最高的100个商品并给出算法的时间复杂度。
先用哈希，统计每个商品的成交次数，然后再用在N个数中找出前K大个数的方法找出成交次数最多的前100个商品。
经典算法面试题及答案 
分类： C/C++
1. 时针分针重合几次
表面上有60个小格，每小格代表一分钟，
数据结构与算法，这个部分的内容其实是十分的庞大，要想都覆盖到不太容易。在校学习阶段我们可能需要对每种结构，每种算法都学习，但是找工作笔试或者面试的时候，要在很短的时间内考察一个人这方面的能力，把每种结...
并查集（Disjoint set或者Union-find set）是一种树型的数据结构，常用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。
http://blog.csdn.net/sxingming/article/details/python 3.4#!/usr/bin/env python
#_*_ coding...
今天整理了一下关于动态规划的内容，道理都知道，但是python来描述的方面参考较少，整理如下，希望对你有所帮助，实验代码均经过测试。
请先好好阅读如下内容–什么是动态规划？
摘录于《算法图解》
项目中经常需要用到String的一些操作，结合看到的一些前人的工具类抽取，编写了如下针对String的常用操作的工具类，供大家参考。
/**   
 * @Copyright © 2017 Sun...
他的最新文章
讲师：何宇健
讲师：董岩
您举报文章：
举报原因：
原文地址：
原因补充：
(最多只允许输入30个字)}