[分类整理IV]微软等100题系列V0.1版：字符串+数组面试题集锦

微软等100题系列V1.0版整理IV：字符串+数组面试题集锦

July2010年12月30日

第4章 字符串+数组面试题

在微软等100题系列V0.1版中，此类字符串+数组的问题，占了足足22道。

可见 字符串+数组等基础问题之重要性。

接下来的俩天，我会加快分类整理完100题系列V0.1版，然后加紧整理完网友的答案回复，

最后，我挑选其中最为经典的几道题，直接在博客上贴出源码、答案。

为了迎接在2011年元旦之际，微软等数据结构+算法面试100题系列V0.2版的出炉。

请继续保持关注。谢谢。:D。July、十二月三十日。

[分类整理I]微软等100题系列V0.1版：c/c++基础面试题集锦
http://blog.csdn.net/v_JULY_v/archive/2010/12/14/6076111.aspx
[分类整理II]微软等100题系列V0.1版：链表面试题集锦
http://blog.csdn.net/v_JULY_v/archive/2010/12/14/6076139.aspx
[分类整理III]微软等100题系列V0.1版之三：栈、堆、队列面试题集锦
http://blog.csdn.net/v_JULY_v/archive/2010/12/17/6083098.aspx

--------------------------------

3.求子数组的最大和
题目：
输入一个整形数组，数组里有正数也有负数。
数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。
求所有子数组的和的最大值。要求时间复杂度为O(n)。

例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5，和最大的子数组为3, 10, -4, 7, 2，
因此输出为该子数组的和18。

第10题
翻转句子中单词的顺序。
题目：输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。

句子中单词以空格符隔开。为简单起见，标点符号和普通字母一样处理。
例如输入“I am a student.”，则输出“student. a am I”。

第14题：
题目：输入一个已经按升序排序过的数组和一个数字，
在数组中查找两个数，使得它们的和正好是输入的那个数字。
要求时间复杂度是O(n)。如果有多对数字的和等于输入的数字，输出任意一对即可。
例如输入数组1、2、4、7、11、15和数字15。由于4+11=15，因此输出4和11。

第17题：
题目：在一个字符串中找到第一个只出现一次的字符。如输入abaccdeff，则输出b。
分析：这道题是2006年google的一道笔试题。

第20题：
题目：输入一个表示整数的字符串，把该字符串转换成整数并输出。
例如输入字符串"345"，则输出整数345。

第25题：
写一个函数,它的原形是int continumax(char *outputstr,char *intputstr)
功能：
在字符串中找出连续最长的数字串，并把这个串的长度返回，
并把这个最长数字串付给其中一个函数参数outputstr所指内存。
例如："abcd12345ed125ss123456789"的首地址传给intputstr后，函数将返回9，
outputstr所指的值为123456789

26.左旋转字符串

题目：
定义字符串的左旋转操作：把字符串前面的若干个字符移动到字符串的尾部。

如把字符串abcdef左旋转2位得到字符串cdefab。请实现字符串左旋转的函数。
要求时间对长度为n的字符串操作的复杂度为O(n)，辅助内存为O(1)。

37.
有n个长为m+1的字符串，
如果某个字符串的最后m个字符与某个字符串的前m个字符匹配，则两个字符串可以联接，
问这n个字符串最多可以连成一个多长的字符串，如果出现循环，则返回错误。

45.雅虎：
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

48.微软：
一个数组是由一个递减数列左移若干位形成的，比如{4，3，2，1，6，5}
是由{6，5，4，3，2，1}左移两位形成的，在这种数组中查找某一个数。

51.和为n连续正数序列。
题目：输入一个正数n，输出所有和为n连续正数序列。

例如输入15，由于1+2+3+4+5=4+5+6=7+8=15，所以输出3个连续序列1-5、4-6和7-8。
分析：这是网易的一道面试题。

53.字符串的排列。
题目：输入一个字符串，打印出该字符串中字符的所有排列。
例如输入字符串abc，则输出由字符a、b、c所能排列出来的所有字符串
abc、acb、bac、bca、cab和cba。

分析：这是一道很好的考查对递归理解的编程题，
因此在过去一年中频繁出现在各大公司的面试、笔试题中。

54.调整数组顺序使奇数位于偶数前面。

题目：输入一个整数数组，调整数组中数字的顺序，使得所有奇数位于数组的前半部分，
所有偶数位于数组的后半部分。要求时间复杂度为O(n)。

56.最长公共字串。
题目：如果字符串一的所有字符按其在字符串中的顺序出现在另外一个字符串二中，

则字符串一称之为字符串二的子串。

注意，并不要求子串（字符串一）的字符必须连续出现在字符串二中。
请编写一个函数，输入两个字符串，求它们的最长公共子串，并打印出最长公共子串。

例如：输入两个字符串BDCABA和ABCBDAB，字符串BCBA和BDAB都是是它们的最长公共子串，
则输出它们的长度4，并打印任意一个子串。

分析：求最长公共子串（Longest Common Subsequence, LCS）是一道非常经典的动态规划题，
因此一些重视算法的公司像MicroStrategy都把它当作面试题。

63.在字符串中删除特定的字符。
题目：输入两个字符串，从第一字符串中删除第二个字符串中所有的字符。

例如，输入”They are students.”和”aeiou”，

则删除之后的第一个字符串变成”Thy r stdnts.”。

分析：这是一道微软面试题。在微软的常见面试题中，与字符串相关的题目占了很大的一部分，
因为写程序操作字符串能很好的反映我们的编程基本功。

69.旋转数组中的最小元素。
题目：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个排好序的数组的一个旋转，

输出旋转数组的最小元素。例如数组{3, 4, 5, 1, 2}为{1, 2, 3, 4, 5}的一个旋转，该数组的最小值为1。

分析：这道题最直观的解法并不难。从头到尾遍历数组一次，就能找出最小的元素，
时间复杂度显然是O(N)。但这个思路没有利用输入数组的特性，我们应该能找到更好的解法。

73.对策字符串的最大长度。
题目：输入一个字符串，输出该字符串中对称的子字符串的最大长度。
比如输入字符串“google”，由于该字符串里最长的对称子字符串是“goog”，因此输出4。

分析：可能很多人都写过判断一个字符串是不是对称的函数，这个题目可以看成是该函数的加强版。

85.又见字符串的问题
1.给出一个函数来复制两个字符串A和B。
字符串A的后几个字节和字符串B的前几个字节重叠。
分析：记住，这种题目往往就是考你对边界的考虑情况。
2.已知一个字符串，比如asderwsde,寻找其中的一个子字符串比如sde的个数，
如果没有返回0，有的话返回子字符串的个数。

88.2005年11月金山笔试题。编码完成下面的处理函数。
函数将字符串中的字符'*'移到串的前部分，

前面的非'*'字符后移，但不能改变非'*'字符的先后顺序，函数返回串中字符'*'的数量。
如原始串为：ab**cd**e*12，
处理后为*****abcde12，函数并返回值为5。（要求使用尽量少的时间和辅助空间）

93.在一个int数组里查找这样的数，它大于等于左侧所有数，小于等于右侧所有数。
直观想法是用两个数组a、b。a[i]、b[i]分别保存从前到i的最大的数和从后到i的最小的数，

一个解答：这需要两次遍历，然后再遍历一次原数组，
将所有data[i]>=a[i-1]&&data[i]<=b[i]的data[i]找出即可。

给出这个解答后，面试官有要求只能用一个辅助数组，且要求少遍历一次。

94.微软笔试题
求随机数构成的数组中找到长度大于=3的最长的等差数列9 d- x' W) w9 ?" o3 b0 R
输出等差数列由小到大:
如果没有符合条件的就输出
格式：
输入[1,3,0,5,-1,6]
输出[-1,1,3,5]
要求时间复杂度，空间复杂度尽量小

96.08年中兴校园招聘笔试题
1．编写strcpy 函数
已知strcpy 函数的原型是
char *strcpy(char *strDest, const char *strSrc);
其中strDest 是目的字符串，strSrc 是源字符串。
不调用C++/C 的字符串库函数，请编写函数 strcpy。

----------------

1.关于本微软等公司数据结构+算法面试100题系列V0.1版的郑重声明
http://blog.csdn.net/v_JULY_v/archive/2010/12/02/6050133.aspx
2.完整100题，请参见，
[珍藏版]微软等数据结构+算法面试100题全部出炉[100题首次完整亮相]
http://blog.csdn.net/v_JULY_v/archive/2010/12/06/6057286.aspx
3.更多详情，请参见，本人博客：
My Blog：
http://blog.csdn.net/v_JULY_v
4.所有的资源（题目+答案）下载地址：
http://v_july_v.download.csdn.net/
5.本微软等100题系列V0.1版，永久维护（网友，思路回复）地址：
http://topic.csdn.net/u/20101126/10/b4f12a00-6280-492f-b785-cb6835a63dc9.html

有问题，欢迎留言或来信。联系方式，见本博客公告栏。

作者声明:

本人July对本博客所有任何内容和资料享有版权，转载请注明作者本人July及出处。

永远，向您的厚道致敬。谢谢。July、二零一零年十二月三十日。