本文共 1528 字，大约阅读时间需要 5 分钟。

算法编程题

1. 排序
   常考的有：冒泡排序、快速排序、归并排序、堆排序
2. 写一个lower_bound()函数
3. 手写全排列，并分析算法的复杂度。
   没有重复数字的：leetcode 46题，
   有重复数字的：leetcode 47题，
4. 给两个有序数组，怎样求第n大的数？（不能用辅助空间，最优方案？）
   leetcode 4题
5. 给一个无序数组，怎样求第n大的数？（不能用set,map和排序等等）等价于top-k问题，用堆实现即可。leetcode 215题，
6. 一个数组缺失了一个数，找出来？两个呢？三个呢？
   缺失一个数：leetcode 268题
   缺失多个数：leetcode 448题
7. 如何选取N个不重复的随机数？复杂度要低
8. 洗牌算法
9. 三数之和怎么做？时间复杂度多少？后两个指针的时候能用二分吗？时间复杂度？最坏？
   leetcode 15题，
10. vector的push_back操作
11. 100层楼和2个鸡蛋，存在某一极限楼层，从这个楼层以及以上楼层把鸡蛋摔下来，鸡蛋会碎，设计算法求最坏情况下的最少次数。如果是N层楼m个鸡蛋呢？ leetcode 887题

两个鸡蛋求解方法：

要求最少次数，就得保证每次都一样多的测试次数，假设在第n层放一次，如果最坏就是n次，如果不碎，就在n+(n-1)层放一次，不成功刚好也是1+(n-1)=n次，以此类推，就是n+(n-1)+(n-2)+…+1>=100时n的最小值，得出(n+1)*n/2>=100，n=14

所以最坏情况下只要十四次

投放楼层为14，27，35，46，56，65，73，80，86，91，95，98，100

12. 一个循环缓存区，存字符，实现push、pop、popall函数
    leetcode 622题
13. N个节点，给出M条边，无向图，求图中连通集的个数 (disjoint set)
14. 给你一个有向图，实现一种算法找到从一个点到另一个点的最短路径。
15. 算术表达式转后缀表达式比如a+(b-c)*d转化成abc-d*+
16. 给你一个多叉树，将这个多叉树转换成一个链表，只要父节点在子节点前面就可以。
17. 实现memorycopy函数，写一段内存复制的代码int mycpy(char* src, chardst, int len)。注意判断异常输入、判断重叠情况并倒序读入即可。手撕一个memcpy，然后问传入的前两个参数固定是void时每次赋值拷贝操作复制多少空间（我不会，大致是这么问）
18. 实现有溢出判定的strcpy函数，做的时候注意两个判定，一个是源和目的内存段重叠问题，可能需要从后往前复制避免重叠，再一个是注意溢出，超出内存的部分要截断。

#include 
   
    #include 
    
     char* strcpy(char* des, const char* src)//src为源指针所指向的字符串{
   	assert((des!=NULL) && (src!=NULL)); 	char *address = des;  	while((*des++ = *src++) != '\0')  		;  	return address;}
    
   

20. 一个二维平面，上面有很多店铺，(x,y)坐标，有的稀疏有的密集，现在要求给定点的最近店铺是哪一个？BFS？那么有没有更优的？比如说落在了稀疏区域怎么办？
21. top-K问题
    最小复杂度为O(n)
    leetcode 215题，
22. 一个字符串,找最长无重复字母子串。
    leetcode 3题，
23. 给一个字符串，只能添加不能删除和修改的情况下，判断最少添加多少个字符可以形成回文字符串
24. 两个栈实现队列
    leetcode 232题，

16.单链表原地排序

转载地址：https://blog.csdn.net/weixin_42490152/article/details/100938054 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！