星球狂想战队|常见算法笔试和面试题整理（带答案）本文不打算介绍那些高逼格的算法

本文不打算介绍那些高逼格的算法，就讲讲最近在面试过程中遇到的算法题以及面试的时候给出的答案。算法可以说是解决所有问题的基石。很多东西都可以转换为算法问题，学习算法最大的作用就是更清楚地了解了很多东西。正所谓是，知其然更知其所以然。很多人都觉得程序就是数据结构+算法+适当的注释。不学算法，那就不要学编程了。虽然说可能没这么夸张，因为实际上还是有很多小项目是不需要太多算法的，都是代码一个劲的往上叠加就行了。但是就算没那么夸张，但是作为一个程序员，逻辑思维就是算法的思路还是很重要的。
第1题
输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点，只调整指针的指向。 10/614//481216转换成双向链表4=6=8=10=12=14=16 。首先我们定义的二元查找树节点的数据结构如下：structBSTreeNode{intm_nValue;//valueofnodeBSTreeNode*m_pLeft;//leftchildofnodeBSTreeNode*m_pRight;//rightchildofnode};
第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/512/47则打印出两条路径：10,12和10,5,7 。
二元树节点的数据结构定义为：structBinaryTreeNode//anodeinthebinarytree{intm_nValue;//valueofnodeBinaryTreeNode*m_pLeft;//leftchildofnodeBinaryTreeNode*m_pRight;//rightchildofnode};
第5题
查找最小的k个元素题目：输入n个整数，输出其中最小的k个。例如输入1 ， 2 ， 3 ， 4 ， 5 ， 6 ， 7和8这8个数字，则最小的4个数字为1 ， 2 ， 3和4 。
举一个例子，数值:0,1,2,3,4,5,6,7,8,9分配:6,2,1,0,0,0,1,0,0,00在下排出现了6次， 1在下排出现了2次， 2在下排出现了1次， 3在下排出现了0次....以此类推..
第7题微软亚院之编程判断俩个链表是否相交给出俩个单向链表的头指针，比如h1 ， h2 ，判断这俩个链表是否相交。为了简化问题，我们假设俩个链表均不带环。
问题扩展：1.如果链表可能有环列?2.如果需要求出俩个链表相交的第一个节点列?
第8题此贴选一些比较怪的题，，由于其中题目本身与算法关系不大，仅考考思维。特此并作一题。 1.有两个房间，一间房里有三盏灯，另一间房有控制着三盏灯的三个开关，