1. 有一个整数数组,请求出两两之差绝对值最小的值。记住,只要得出最小值即可,不需要求出是哪两个数。(Microsoft) 方法1:两两作差求绝对值,并取最小,O( n2 )。 方法2:排序,相邻两点作差求绝对值,并取最小,O( nlgn ). 方法3:有没有O( n )的解法?网上有如下解法: 设数组A = { a1, a2, … , an }, 求 s = min( |ai - aj| ), 其中1<= i, j <=n. 设B = { b1, b2, … , bn-1 }, 且 bi = ai – ai+1 即:b1 = a1 – a2, b2 = a2 – a3, b3 = a3 – a4, …
于是有如下规律: 例如:a3 – a5 = ( a3 – a4 ) + ( a4 – a5 ) =b3 + b4 a1 – a6 = b1 + b2 + … + b5 即:ai – aj = bi + … + bj-1 则数组A中任意两个数的差,都可以用数组B中一个字段的和表示。 则原问题可以转换为: 在数组B中,求连续的某一段,使其和的绝对值最小。(只求最小值,不需要知道具体是哪些数) 例如 B = { 1, -2, 3, -1, -9, 7, -5, 6 }; 则绝对值最小值为0,具体是{ -2, 3, -1 } 或 {3, -1, -9, 7}
网上的解法,一般到这里就没下文了。只是简单的提了一下,类似于最大子序列的和。具体怎么做,还要自己想想。 最大子序列和利用DP,可O( n )求解。这题咋做?纠结。
2. 写一个函数,检查字符是否是整数,如果是,返回其整数值。(或者:怎样只用4行代码编写出一个从字符串到长整形的函数?) 据说此题是,Microsoft的大牛只有了4行代码就给出了答案。 可惜,不知道是怎么写的。自己试着写写,当然可能会不至4行。单纯追求行数,也没什么意义,如果你愿意可以把所有的程序都写成一行。 注意: 1. 处理前导空格 2. 处理正负号 3. 处理进制(16进制、8进制、10进制) 4. 非法字符( 0---9, a---f, A---F) 5. 注意整数的范围,不能溢出
3. 给出一个函数来输出一个字符串的所有排列 方法1: 一个简单的DFS。从后往前不断交互。N个字母求全排列,O( n! )。具体实现,看代码吧。 方法2: 如果不会写递归,也可以利用STL。STL里有一个next_permutation函数。利用这个函数可以返回大于原字符串的下一个字典序列。当字符串为最大字典序列时,函数返回false。这样只要先对原字符串排序,然后不断调用next_permuation即可。
4.请编写实现malloc()内存分配函数功能一样的代码 这题比较难,要是不懂点OS的内存管理,根本就无从下手。 我们知道调用malloc()后,OS就要想方设法为我们返回一块空闲空间。这就涉及到OS的内存管理。OS的内存管理可以这样考虑: 假设整块内存有128K 初始状态,128K都是空闲 第一次请求,申请了16k,空闲112K 第二次请求,申请了32K,空闲80K 第三次请求,申请了8K,空闲72K 第二次请求申请的32K被释放,空闲108K 第四次请求,申请了24K,空闲84K … 从上面的例子可以看出,一整块连续的空闲内存块,经过一段时间的使用,会被无情的划分为许多小块。这些小块大小不等,并且有的空闲、有的被占用。 当调用malloc时,OS就沿内存扫描,找到一块够大的空闲块,从中划分出要使用的部分,将这部分标记为己分配,并返回这部分的首地址。如果,空闲的块都是些小的碎片,那就悲具了(当然,OS可以把将相邻的空闲块合并,再尝试)。
现在,模拟一下malloc的过程: 为了便于管理,首先定义内存控制块mcb。这个mcb记录两个信息:块是否空闲、块的大小。即,每个分配出去的块,其实都带有一个mcb,只不过这个mcb位于块的最前端,返回该用户的指针刚好指向mcb之后,所以对用户是不可见的。 现在,就可以处理free了。Free只要把已分配的内存块重新标记为空闲即可,这里当然要用到该快的mcb了。 Malloc简单来说,就是维护几个指针,根据分配请求修改指针位置。对于要分配的块,将标记置位己分配,并返回这部分的首地址。 参考http://lklkdawei.blog.163.com/blog/static/32574109200881445518891/,这里讲的很清楚,还附有代码,我就不狗尾续貂了。 5. 字符串A的后几个字节和字符串B的前几个字节重叠。 这题似乎没什么玄机,就是个简单的字符串处理。使用strlen和memcpy可以完成,见代码。
6. 怎样编写一个程序,把一个有序整数数组放到二叉树中? 由数组建立排序二叉树。因为数组已排序,所以可以进行类似排序二叉树上的查找。感觉有点类似先序遍历,每次先处理根节点,然后分别是左子树、右子树。具体做法是: 1.整个数组对应一个二叉树,则中间元素对应二叉树的根节点 2.中间元素左边的部分对应左子树、右边的部分对应右子树 3.对左右两部分再继续递归调用。
7. 怎样从顶部开始逐层打印二叉树结点数据?请编程。 用队列容易实现。网上有人说有非队列的实现,不过还是用指针把每一层的点都连了起来,然后逐层打印。这种方法和用队列把每层的节点存起来大同小异。
8.怎样把一个链表掉个顺序(也就是反序,注意链表的边界条件并考虑空链表)? 这题主要看有没有额外存储空间的限制。 如果没有,可以重新生成一个链表,该链表是原链表的反序。具体做的时候,每次只需把新节点插入的头结点的前面即可。此时,空间复杂度O(n). 如果有存储空间的限制,要求为O(1),即只能用常数个辅助变量。这时可以用三个指针来实现。首先,需要一个指针cur,指向要反向的节点。因为链表反序,指针要指向前一个,而单链表无法直接得到前一个,所以需要一个指针pre。然后,当指针cur反向后,就无法指向下一个,所以需要一个指针next,用于保存cur的下一个。这样只要遍历整个链表,不断使指针cur所指节点反向即可。
9.请编写能直接实现int atoi(const char * pstr)函数功能的代码。 需要注意的问题: 1.前导白空 2.正负号 3.不同进制 4.非法字符 5.Int范围
10.编程实现两个正整数的除法,当然不能用除法操作符。 // return x/y. int div(const int x, const int y) { .... }
a/b=x, 即求a里面有多少个b. 方法一:枚举,b*1,b*2,b*3,…,直到b*x == a 或 b*x < a && b*(x+1) > a,复杂度O( a/b)这样 方法二: 除了x = 1+…+1(x个1相加),x还可以用2的幂的和表示(如4 = 2^2, 7 = 2^2+2+1 )。不用逐一枚举,类似折半查找。不断划分区间,用区间比较。 不断尝试b*(1<<0),b*(1<<1),b*(1<<2),…, 直到b*(1<<m) < a && b*(1<<m+1) > a, 则从a - b*(1<<m),然后再重新开始。
11.在排序数组中,找出给定数字的出现次数。比如[1, 2, 2, 2, 3] 中的出现次数是次。 方法一:直接遍历,首先找到这个数,然后逐一计数,O(n)可完成。 方法二:二分查找,首先找到这个数的第一个,记录其位置。再二分查找,找到这个数的最后一个,记录其位置。最后下边相减,O(lgn)可完成。虽然两次都是二分查找,但还是略微有点区别。 LowerSearch把相等的情况划归到左半部分,所以计算mid时要向下取整。 UpperSearch把相等的情况划归到右半部分,所以计算mid时要向上取整。
12.平面上N个点,每两个点都确定一条直线,求出斜率最大的那条直线所通过的两个点(斜率不存在的情况不考虑)。时间效率越高越好。 按照一般的方法,逐个求斜率比较,O(n^2)可完成。有没有更快的方法?有。 对所有的点按x坐标排序,然后只比较相邻两点的斜率即可。复杂度O( nlgn )。当然,只要有了算法,编程实现很容易,关键是为什么? 我不会严格的证明,只能朴素的理解一下。 设有三个点A、B、C 如果A、B、C在一条直线上,则斜率相等 如果A、B、C不在一条直线上,则构成三角形ABC。不妨设Xa < Xb < Xc 即按照x坐标排序后,A、B相邻,B、C相邻。也就是说,三角形中AC为最长边。如图,显然Kab和Kbc中至少有个大于Kac.
13.一个整数数列,元素取值可能是~65535中的任意一个数,相同数值不会重复出现。是例外,可以反复出现。 请设计一个算法,当你从该数列中随意选取个数值,判断这个数值是否连续相邻。 注意: - 5个数值允许是乱序的。比如:8 7 5 0 6 - 0可以通配任意数值。比如:7 5 0 6 中的可以通配成或者 - 0可以多次出现。 - 复杂度如果是O(n2)则不得分。
首先对这5个数进行排序。 如果5个数中没有0,那么用最大值 – 最小值。如果差值= 4,则连续。否则,不连续。 如果5个数中有0,则0必然排在最前面。依旧最大值 – 最小值。当差值取1,说明只有2个非0数,必然连续,则其余的数都可用0补齐。那么在连续的情况下差值最大取多少?最大值为4。这时必然有一个数不连续,但是可以用0补. 综上: 1. 先排序 2. 用非零最大值 - 非零最小值,如果差值<=4,则连续。否则,不连续。 3. 处理没有非零最大值或非零最小值的情况。 A. 全为零,必连续 B. 只用一个非0值,也连续 14.设计一个算法,找出二叉树上任意两个结点的最近共同父结点。复杂度如果是O(n2)则不得分。 经典的LCA问题,有非常成熟的解法,用tarjan算法或转换为RMQ问题。Tarjan自己没写过。这里是RMQ的解法。对于RMQ也有多种解法,比如线段树、ST等。这里讨论一下ST算法。 RMQ问题:RMQ( A, i, j )表示在数组A中求A[i]…A[j]之间最小值的下标。
首先,把LCA转换为RMQ问题。 对二叉树进行DFS,记录每个节点被访问的顺序。因为有回溯,除了根节点,每个节点都被访问2次。设二叉树有n个节点,则DFS完成后回记录2n-1个节点,然后由这些节点构成数组path,该数字记录了DFS遍历节点的顺序。 在进行DFS时,同时记录各节点的层数,组成数组level。 对二叉树上的任意两点x和y, 找到x 、y在数组path中第一次出现的位置,记为pos(x), pos(y)。则path[ pos(x) ]…path[ pos(y) ]代表在二叉树上从x遍历到y的一条路径,那么该路径上level最小的点就是x 、y的LCA。 即LCA( A, i, j ) = RMQ( level, pos(x), pos(y) )
RMQ问题的ST求解。ST,实质上属于DP。 定义:dp[i][j]表示数字A中,A[i]…A[i+2^j-1]中(即由A[i]开始的连续2^j个元素)最小值的下标 状态转换方程:dp[i][j] = Min( dp[i][j-1], dp[i+2^(j-1)][j-1] ); 大概解释一下:状态方程把A[i]…A[i+2^j-1]共2^j个元素,分成两部分A[i]…A[i+2^(j-1)-1]和A[[i+2^(j-1)]…A[j],每部分2^( j-1 )个元素,然后取两部分的最小值即可。 上述部分,其实就是个DP的预处理过程。完成了预处理,最后就是RMQ问题的求解, RMQ( A, i, j ) = ? 有了上述的dp[][],只要想办法把A[i]…A[j]分成两部分,使每部分的长度为2^k。这样就可以查dp[][]数组了。对于这两部分有什么要求吗?两部分合起来刚好覆盖整个[ i, j ]区间,这当然是最好的了。但是,有时很难取到整数,所以连部分通常是交叉的,甚至每一部分几乎覆盖了整个区间。 即,2^k = j - i + 1,则可求 k=lg( j-i+1 )。k是下取整。 最终:RMQ( A, i, j ) = Min( dp[i][k], dp[j-2^k+1][j] ) RMQ的ST求解见代码
15.一棵排序二叉树,令f=(最大值+最小值)/2,设计一个算法,找出距离f值最近、大于f值的结点。复杂度如果是O(n2)则不得分。
16. 一个整数数列,元素取值可能是1~N(N是一个较大的正整数)中的任意一个数,相同数值不会重复出现。设计一个算法,找出数列中符合条件的数对的个数,满足数对中两数的和等于N+1。复杂度最好是O(n),如果是O(n2)则不得分 这题要求O(n),我能想到就是:使用一个有N个元素的数组,然后用数值作为数组的下标,然后遍历数组。
|
|
来自: nuster > 《cplusplus》