没有合适的资源?快使用搜索试试~ 我知道了~
首页编程艺术系列升级:面试算法心得与优化
编程艺术系列升级:面试算法心得与优化
需积分: 10 53 下载量 137 浏览量
更新于2024-07-20
3
收藏 2.95MB PDF 举报
《编程之法:面试和算法心得》是一系列深入解析和分享编程面试中常见算法问题的文章集合。作者July在2010年开始整理微软面试的100题,并在此基础上提炼出更具有代表性和深度的问题,将其扩展成一系列详细的编程问题解答。这个系列自2011年4月发布以来,深受编程爱好者和专业人士的欢迎,他们通过博客互动,提供了宝贵的改进建议、代码分享和bug纠正。 项目目标是将这些经典文章进行优化和整合,形成一个便于学习和交流的平台,以便读者能够更好地理解和提升自己的算法技能,同时准备面试。作者鼓励社区成员积极参与,对代码进行修正、优化和提出建议,通过Pull Request或Issue的形式共同维护和完善这个项目。 项目的代码风格指南十分细致,包括但不限于: 1. 缩进:采用4个空格,保持运算符后有一个空格,循环语句末尾的分号后面留空格。 2. 括号:大括号独立成行,即使单行代码也要求使用括号。 3. 指针表示:C语言中,指针前后的空格处理,如`int *p`而非`int * p`。 4. 标点符号:中文部分使用全角标点,英文代码和数学公式使用半角标点。 5. 注释:统一使用中文注释,通常使用`//`而非`/*...*/`。 6. 命名规范:类名首字母大写,函数名根据长度和意义决定大小写规则,变量名遵循清晰易懂的原则,尽量使用全名表达功能,特殊情况下的简写需明确。 通过这个项目,参与者不仅能够提高算法技能,还能培养良好的编程习惯和团队协作精神。《编程之法—面试和算法心得》不仅是技术学习的资源库,也是提升编程素养和职业竞争力的有效途径。
资源详情
资源推荐
分析:使用后缀数组,对一个字符串生成相应的后缀数组后,然后再排序,排完序依次检测相邻的两个字符串的开
头公共部分。 这样的时间复杂度为:
生成后缀数组 O(N)
排序 O(NlogN*N) 最后面的 N 是因为字符串比较也是 O(N)
依次检测相邻的两个字符串 O(N * N)
故最终总的时间复杂度是 O(N^2*logN)
16、字符串的删除16、字符串的删除
删除模式串中出现的字符,如“welcome to asted”,模式串为“aeiou”那么得到的字符串为“wlcm t std",要求
性能最优。
17、字符串的移动17、字符串的移动
字符串为*号和26个字母的任意组合,把 *号都移动到最左侧,把字母移到最右侧并保持相对顺序不变,要求时间和
空间复杂度最小。
18、字符串的包含18、字符串的包含
输入:
L:“hello”“july”
S:“hellomehellojuly”
输出:S中包含的L一个单词,要求这个单词只出现一次,如果有多个出现一次的,输出第一个这样的单词。
19、倒数第n个元素19、倒数第n个元素
链表倒数第n个元素。
提示:设置一前一后两个指针,一个指针步长为1,另一个指针步长为n,当一个指针走到链表尾端时,另一指针指
向的元素即为链表倒数第n个元素。
20、回文字符串20、回文字符串
将一个很长的字符串,分割成一段一段的子字符串,子字符串都是回文字符串。有回文字符串就输出最长的,没有
回文就输出一个一个的字符。
例如:
habbafgh
输出h,abba,f,g,h。
提示:一般的人会想到用后缀数组来解决这个问题。
21、最长连续字符21、最长连续字符
用递归算法写一个函数,求字符串最长连续字符的长度,比如aaaabbcc的长度为4,aabb的长度为2,ab的长度为
1。
22、字符串反转22、字符串反转
实现字符串反转函数。
22、字符串压缩22、字符串压缩
编程之法:面试和算法心得
- 15 -© 本文档使用 看云 构建
通过键盘输入一串小写字母(a~z)组成的字符串。请编写一个字符串压缩程序,将字符串中连续出席的重复字母进行
压缩,并输出压缩后的字符串。 压缩规则:
仅压缩连续重复出现的字符。比如字符串"abcbc"由于无连续重复字符,压缩后的字符串还是"abcbc"。
压缩字段的格式为"字符重复的次数+字符"。例如:字符串"xxxyyyyyyz"压缩后就成为"3x6yz"。
要求实现函数: void stringZip(const char *pInputStr, long lInputLen, char *pOutputStr);
输入pInputStr: 输入字符串lInputLen: 输入字符串长度
输出 pOutputStr: 输出字符串,空间已经开辟好,与输入字符串等长;
注意:只需要完成该函数功能算法,中间不需要有任何IO的输入输出
示例
输入:“cccddecc” 输出:“3c2de2c”
输入:“adef” 输出:“adef”
输入:“pppppppp” 输出:“8p”
23、集合的差集23、集合的差集
已知集合A和B的元素分别用不含头结点的单链表存储,请求集合A与B的差集,并将结果保存在集合A的单链表中。
例如,若集合A={5,10,20,15,25,30},集合B={5,15,35,25},完成计算后A={10,20,30}。
24、最长公共子串24、最长公共子串
给定字符串A和B,输出A和B中的第一个最长公共子串,比如A=“wepiabc B=“pabcni”,则输出“abc”。
25、均分0125、均分01
给定一个字符串,长度不超过100,其中只包含字符0和1,并且字符0和1出现得次数都是偶数。你可以把字符串任意
切分,把切分后得字符串任意分给两个人,让两个人得到的0的总个数相等,得到的1的总个数也相等。
例如,输入串是010111,我们可以把串切位01, 011,和1,把第1段和第3段放在一起分给一个人,第二段分给另外一
个人,这样每个人都得到了1个0和两个1。我们要做的是让切分的次数尽可能少。
考虑到最差情况,则是把字符串切分(n - 1)次形成n个长度为1的串。
26、合法字符串26、合法字符串
用n个不同的字符(编号1 - n),组成一个字符串,有如下2点要求:
1、对于编号为i 的字符,如果2 * i > n,则该字符可以作为最后一个字符,但如果该字符不是作为最后一个字符
的话,则该字符后面可以接任意字符;
2、对于编号为i的字符,如果2 * i = 2 * i。
问有多少长度为M且符合条件的字符串。
例如:N = 2,M = 3。则abb, bab, bbb是符合条件的字符串,剩下的均为不符合条件的字符串。
假定n和m皆满足:2
第二章 数组
编程之法:面试和算法心得
- 16 -© 本文档使用 看云 构建
2.0 本章导读
笔试和面试中,除了字符串,另一类出现频率极高的问题便是与数组相关的问题。在阅读完第1章和本第二章后,读
者会慢慢了解到解决面试编程题的有几种常用思路。首先一般考虑“万能的”暴力穷举(递归、回溯),如求n个数
的全排列或八皇后(N皇后问题)。但因为穷举时间复杂度通常过高,所以需要考虑更好的方法,如分治法(通过分
而治之,然后归并),以及空间换时间(如活用哈希表)。
此外,选择合适的数据结构可以显著提升效率,如寻找最小的k个数中,用堆代替数组。
再有,如果题目允许排序,则可以考虑排序。比如,寻找和为定值的两个数中,先排序,然后用前后两个指针往中
间扫。而如果如果已经排好序了(如杨氏矩阵查找中),则想想有无必要二分。但是,如果题目不允许排序呢?这
个时候,我们可以考虑不改变数列顺序的贪心算法(如最小生成树Prim、Kruskal及最短路dijkstra),或动态规划
(如 01背包问题,每一步都在决策)。
最后,注意细节处理,不要忽略边界条件,如字符串转换成整数。
2.1 寻找最小的 k 个数
题目描述
输入n个整数,输出其中最小的k个。
分析与解法
解法一
要求一个序列中最小的k个数,按照惯有的思维方式,则是先对这个序列从小到大排序,然后输出前面的最小的k个
数。
至于选取什么的排序方法,我想你可能会第一时间想到快速排序(我们知道,快速排序平均所费时间为 n*logn ),
然后再遍历序列中前k个元素输出即可。因此,总的时间复杂度: O(n * log n)+O(k)=O(n * log n) 。
解法二
咱们再进一步想想,题目没有要求最小的k个数有序,也没要求最后n-k个数有序。既然如此,就没有必要对所有元
素进行排序。这时,咱们想到了用选择或交换排序,即:
1、遍历n个数,把最先遍历到的k个数存入到大小为k的数组中,假设它们即是最小的k个数; 2、对这k个数,利用
选择或交换排序找到这k个元素中的最大值kmax(找最大值需要遍历这k个数,时间复杂度为 O(k) ); 3、继续
遍历剩余n-k个数。假设每一次遍历到的新的元素的值为x,把x与kmax比较:如果 x = kmax ,则继续遍历不更新
数组。
每次遍历,更新或不更新数组的所用的时间为 O(k) 或 O(0) 。故整趟下来,时间复杂度为
n*O(k)=O(n*k) 。
解法三
编程之法:面试和算法心得
- 17 -© 本文档使用 看云 构建
更好的办法是维护容量为k的最大堆,原理跟解法二的方法相似:
1、用容量为k的最大堆存储最先遍历到的k个数,同样假设它们即是最小的k个数;
2、堆中元素是有序的,令k1
2.2 寻找和为定值的两个数
题目描述
输入一个数组和一个数字,在数组中查找两个数,使得它们的和正好是输入的那个数字。
要求时间复杂度是O(N)。如果有多对数字的和等于输入的数字,输出任意一对即可。
例如输入数组1、2、4、7、11、15和数字15。由于4+11=15,因此输出4和11。
分析与解法
咱们试着一步一步解决这个问题(注意阐述中数列有序无序的区别):
直接穷举,从数组中任意选取两个数,判定它们的和是否为输入的那个数字。此举复杂度为O(N^2)。很显然,我们
要寻找效率更高的解法
题目相当于,对每个a[i],查找sum-a[i]是否也在原始序列中,每一次要查找的时间都要花费为O(N),这样下来,最
终找到两个数还是需要O(N^2)的复杂度。那如何提高查找判断的速度呢?
答案是二分查找,可以将O(N)的查找时间提高到O(log N),这样对于N个a[i],都要花logN的时间去查找相对应的
sum-a[i]是否在原始序列中,总的时间复杂度已降为O(N log N),且空间复杂度为O(1)。 (如果有序,直接二分
O(N log N),如果无序,先排序后二分,复杂度同样为O(N log N + N log N)= O(N log N),空间复杂度总为
O(1))。
可以继续优化做到时间O(N)么?
解法一
根据前面的分析,a[i]在序列中,如果a[i]+a[k]=sum的话,那么sum-a[i](a[k])也必然在序列中。 举个例子,如
下: 原始序列:
1、 2、 4、 7、11、15
用输入数字15减一下各个数,得到对应的序列为:
14、13、11、8、4、 0
第一个数组以一指针i 从数组最左端开始向右扫描,第二个数组以一指针j 从数组最右端开始向左扫描,如果第一个
数组出现了和第二个数组一样的数,即a[_i]=a[_j],就找出这俩个数来了。 如上,i,j最终在第一个,和第二个序列
中找到了相同的数4和11,所以符合条件的两个数,即为4+11=15。 怎么样,两端同时查找,时间复杂度瞬间缩短
到了O(N),但却同时需要O(N)的空间存储第二个数组。
解法二
当题目对时间复杂度要求比较严格时,我们可以考虑下用空间换时间,上述解法一即是此思想,此外,构造hash表
编程之法:面试和算法心得
- 18 -© 本文档使用 看云 构建
也是典型的用空间换时间的处理办法。
即给定一个数字,根据hash映射查找另一个数字是否也在数组中,只需用O(1)的时间,前提是经过O(N)时间的预处
理,和用O(N)的空间构造hash表。
但能否做到在时间复杂度为O(N)的情况下,空间复杂度能进一步降低达到O(1)呢?
解法三
如果数组是无序的,先排序(N log N),然后用两个指针i,j,各自指向数组的首尾两端,令i=0,j=n-1,然后
i++,j--,逐次判断a[i]+a[j]?=sum,
如果某一刻a[i]+a[j] > sum,则要想办法让sum的值减小,所以此刻i不动,j--;
如果某一刻a[i]+a[j] < sum,则要想办法让sum的值增大,所以此刻i++,j不动。
所以,数组无序的时候,时间复杂度最终为O(N log N + N)=O(N log N)。
如果原数组是有序的,则不需要事先的排序,直接用两指针分别从头和尾向中间扫描,O(N)搞定,且空间复杂度还
是O(1)。
下面,咱们先来实现此思路(这里假定数组已经是有序的),代码可以如下编写:
void TwoSum(int data[], unsigned int length, int sum)
{
//sort(s, s+n); 如果数组非有序的,那就事先排好序O(N log N)
int begin = 0;
int end = length - 1;
//俩头夹逼,或称两个指针两端扫描法,很经典的方法,O(N)
while (begin < end)
{
long currSum = data[begin] + data[end];
if (currSum == sum)
{
//题目只要求输出满足条件的任意一对即可
printf("%d %d\n", data[begin], data[end]);
//如果需要所有满足条件的数组对,则需要加上下面两条语句:
//begin++
//end--
break;
}
else{
if (currSum < sum)
begin++;
else
end--;
}
}
}
编程之法:面试和算法心得
- 19 -© 本文档使用 看云 构建
剩余136页未读,继续阅读
VIP_Neo
- 粉丝: 95
- 资源: 23
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- 计算机人脸表情动画技术发展综述
- 关系数据库的关键字搜索技术综述:模型、架构与未来趋势
- 迭代自适应逆滤波在语音情感识别中的应用
- 概念知识树在旅游领域智能分析中的应用
- 构建is-a层次与OWL本体集成:理论与算法
- 基于语义元的相似度计算方法研究:改进与有效性验证
- 网格梯度多密度聚类算法:去噪与高效聚类
- 网格服务工作流动态调度算法PGSWA研究
- 突发事件连锁反应网络模型与应急预警分析
- BA网络上的病毒营销与网站推广仿真研究
- 离散HSMM故障预测模型:有效提升系统状态预测
- 煤矿安全评价:信息融合与可拓理论的应用
- 多维度Petri网工作流模型MD_WFN:统一建模与应用研究
- 面向过程追踪的知识安全描述方法
- 基于收益的软件过程资源调度优化策略
- 多核环境下基于数据流Java的Web服务器优化实现提升性能
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功