0.(原第8题) (1)用一种算法使通用字符串相匹配。 (2)颠倒一个字符串。优化速度。优化空间。 (3)颠倒一个句子中的词的顺序,比如将“我叫克丽丝”转换为“克丽丝叫我”,实现速度最快,移动最少。 (4)找到一个子字符串。优化速度。优化空间。 (5)比较两个字符串,用O(n)时间和恒量空间。
1.(原第10题)
----------------------------------------------------------------------- 翻转句子中单词的顺序。 题目:输入一个英文句子,翻转句子中单词的顺序,但单词内字符的顺序不变。句子中单词以空格符隔开。 为简单起见,标点符号和普通字母一样处理。 例如输入“I am a student.”,则输出“student. a am I”。 2.(原第17题) ------------------------------------------------------------------------ 题目:在一个字符串中找到第一个只出现一次的字符。如输入abaccdeff,则输出b。 分析:这道题是2006年google的一道笔试题。 3.(原第20题) ------------------------------------------------------------------------ 题目:输入一个表示整数的字符串,把该字符串转换成整数并输出。 例如输入字符串"345",则输出整数345。 4.(原第25题) ------------------------------------------------------------------------- 写一个函数,它的原形是int continumax(char *outputstr,char *intputstr) 功能: 在字符串中找出连续最长的数字串,并把这个串的长度返回, 并把这个最长数字串付给其中一个函数参数outputstr所指内存。 例如:"abcd12345ed125ss123456789"的首地址传给intputstr后,函数将返回9, outputstr所指的值为123456789 5.(原第26题) -------------------------------------------------------------------------- 左旋转字符串 题目: 定义字符串的左旋转操作:把字符串前面的若干个字符移动到字符串的尾部。 如把字符串abcdef左旋转2位得到字符串cdefab。请实现字符串左旋转的函数。 要求时间对长度为n的字符串操作的复杂度为O(n),辅助内存为O(1)。 6.(原第33题) ---------------------------------------------------------------------------- 实现一个挺高级的字符匹配算法: 给一串很长字符串,要求找到符合要求的字符串,例如目的串:123 1******3***2 ,12*****3这些都要找出来 其实就是类似一些和谐系统。。。。。 7.(原第37题) ---------------------------------------------------------------------------- 有n个长为m+1的字符串, 如果某个字符串的最后m个字符与某个字符串的前m个字符匹配,则两个字符串可以联接, 问这n个字符串最多可以连成一个多长的字符串,如果出现循环,则返回错误。 8.(原第46题) ----------------------------------------------------------------------------- 搜狐: 四对括号可以有多少种匹配排列方式?比如两对括号可以有两种:()()和(()) 9.(原第53题) ----------------------------------------------------------------------------- 字符串的排列。 题目:输入一个字符串,打印出该字符串中字符的所有排列。 例如输入字符串abc,则输出由字符a、b、c所能排列出来的所有字符串abc、acb、bac、bca、cab和cba。 分析:这是一道很好的考查对递归理解的编程题, 因此在过去一年中频繁出现在各大公司的面试、笔试题中。 10.(原第56题) ------------------------------------------------------------------------------ 最长公共子串。 题目:如果字符串一的所有字符按其在字符串中的顺序出现在另外一个字符串二中, 则字符串一称之为字符串二的子串。 注意,并不要求子串(字符串一)的字符必须连续出现在字符串二中。 请编写一个函数,输入两个字符串,求它们的最长公共子串,并打印出最长公共子串。 例如:输入两个字符串BDCABA和ABCBDAB,字符串BCBA和BDAB都是是它们的最长公共子串, 则输出它们的长度4,并打印任意一个子串。 分析:求最长公共子串(Longest Common Subsequence, LCS)是一道非常经典的动态规划题, 因此一些重视算法的公司像MicroStrategy都把它当作面试题。 11.(原第63题) --------------------------------------------------------------------------------- 在字符串中删除特定的字符。 题目:输入两个字符串,从第一字符串中删除第二个字符串中所有的字符。例如,输入”They are students.” 和”aeiou”, 则删除之后的第一个字符串变成”Thy r stdnts.”。 分析:这是一道微软面试题。在微软的常见面试题中,与字符串相关的题目占了很大的一部 分,因为写程序操作字符串能很好的反映我们的编程基本功。 14.(原第70题) ---------------------------------------------------------------------------------- 给出一个函数来输出一个字符串的所有排列。 简单的回溯就可以实现了。当然排列的产生也有很多种算法,去看看组合数学, 还有逆序生成排列和一些不需要递归生成排列的方法。 印象中 Knuth 的<TAOCP>第一卷里面深入讲了排列的生成。这些算法的理解需要一定的数学功底,也需要一 定的灵感,有兴趣最好看看。 15.(原第73题) ---------------------------------------------------------------------------------- 对称字符串的最大长度。 题目:输入一个字符串,输出该字符串中对称的子字符串的最大长度。比如输入字符串“google”,由于该字符 串里最长的对称子字符串是“goog”,因此输出4。 分析:可能很多人都写过判断一个字符串是不是对称的函数,这个题目可以看成是该函数的加强版。 16.(原第79题(3)) ----------------------------------------------------------------------------------- 请编写能直接实现 strstr()函数功能的代码。 17.(原第81题(2)) ----------------------------------------------------------------------------------- 一个文件,内含一千万行字符串,每个字符串在1K 以内,要求找出所有相反的串对,如 abc 和 cba。 18.(原第83题(2)) ----------------------------------------------------------------------------------- 百度笔试题 用 C 语言实现函数 void * memmove(void *dest, const void *src, size_t n)。memmove 函数的功能是拷贝 src 所指的内存内容前 n 个字节到 dest 所指的地址上。 分析: 由于可以把任何类型的指针赋给 void 类型的指针, 这个函数主要是实现各种数据类型的拷贝。 19.(原第85题) ----------------------------------------------------------------------------------- 1.给出一个函数来复制两个字符串 A 和 B。字符串 A 的后几个字节和字符串 B 的前几个字节重叠。分析: 记住,这种题目往往就是考你对边界的考虑情况。 2.已知一个字符串,比如 asderwsde,寻找其中的一个子字符串比如 sde 的个数,如果没有返回0,有的话返 回子字符串的个数。 20.(原第87题(2)(3)) ------------------------------------------------------------------------------------ (1).求最大连续递增数字串(如“ads3sl456789DF3456ld345AA”中的“456789”) (2).实现 strstr 功能,即在父串中寻找子串首次出现的位置。 (笔试中常让面试者实现标准库中的一些函数) 21.(原第88题) ------------------------------------------------------------------------------------ 2005 年11 月金山笔试题。编码完成下面的处理函数。 函数将字符串中的字符'*'移到串的前部分,前面的非'*'字符后移,但不能改变非'*'字符的先后顺序,函数返回 串中字符'*'的数量。如原始串为:ab**cd**e*12,处理后为*****abcde12,函数并返回值为5。(要求使用尽量 少的时间和辅助空间) 22.(原第89题(2)(4)(5)) ------------------------------------------------------------------------------------ (1).编码实现字符串转整型的函数(实现函数 atoi 的功能),据说是神州数码笔试题。如将字符 串”+123”123, ”-0123”-123, “123CS45”123, “123.45CS”123, “CS123.45”0 (2).删除字符串中的数字并压缩字符串。如字符串”abc123de4fg56”处理后变为”abcdefg”。注意空间和效率。 (下面的算法只需要一次遍历,不需要开辟新空间,时间复杂度为 O(N)) (3).求两个串中的第一个最长子串(神州数码以前试题)。如"abractyeyt","dgdsaeactyey"的最大子串为"actyey"。 23.(原第90题(1)(2)) -------------------------------------------------------------------------------------- (1).不开辟用于交换数据的临时空间,如何完成字符串的逆序 (在技术一轮面试中,有些面试官会这样问)。 (2).删除串中指定的字符 (做此题时,千万不要开辟新空间,否则面试官可能认为你不适合做嵌入式开发) 24.(原第95题(1)) -------------------------------------------------------------------------------------- 华为面试题 判断一字符串是不是对称的,如:abccba 25.(原第96题) --------------------------------------------------------------------------------------- 08 年中兴校园招聘笔试题 编写 strcpy 函数 已知 strcpy 函数的原型是 char *strcpy(char *strDest, const char *strSrc); 其中 strDest 是目的字符串,strSrc 是源字符串。不调用 C++/C 的字符串库函数,请编写函数 strcpy ANSWER 26.(原第97题(1)(5)) 微软较简单的算法面试题 (1).编写反转字符串的程序,要求优化速度、优化空间。 (2).写一个函数,检查字符是否是整数,如果是,返回其整数值。 (或者:怎样只用4 行代码编写出一个从字符串到长整形的函数?) 27.(原第98题) ------------------------------------------------------------------------------------------ 微软面试题 1.给出一个函数来输出一个字符串的所有排列。 2.请编写实现 malloc()内存分配函数功能一样的代码。 3.给出一个函数来复制两个字符串 A 和 B。字符串 A 的后几个字节和字符串 B 的前几个字节重叠