校招面试手撕算法汇总

正文

所有题目都是从面经中提取而来，持续更新。

本人也是菜鸟一枚，帖子也会相应的发布自己对于题目的解法和看法，但是可能想得不够，也希望大家能够一起讨论，一起进步。

1.数组中找出所有重复数字？空间复杂度为O（1），时间复杂度最小？

实在没有O(1)的方法，只能实现O（n），欢迎讨论。

方案1：创建n个数字的数组，循环相加，将大于1的数字打印出来

方案2：map，先contains判断，存在就打印，不存在就put

2.一个二维数组只含0，1；将1围城的矩阵中所有的0的数字转换成1？

3.求链表中点？

4. 手写常用设计模式（单例）

饿汉懒汉的区别、好处、缺点都要会 这里可能会引申出单例的条件

5.手写生产者消费者模式？

不解释，不理解的，先背住再好好理解

6.100个0到100之间的整数排序

7.two sum问题到k sum问题

8.旋转数组二分查找

9.算 a + b, 不能用加号或减号

位运算，大家百度一下就可以了

10. 数组中超过一半的数

11. 大文件100亿个数字，求前m大的数

12.两个有序数组，求第k个数

13.最大连续子数组和

基础题，贪心。

14.二维数组中，每个元素有个数字，求某一个点到任意一点的sum和（只能向右或者向下） dp记录到每个点的sum

15.手写快速排序算法，并解释过程。

不会的，直接背吧......

16.重建二叉树

17.二分查找

18.从字符串中“aecbcda”找出不重复的字符组成的顺序子串“aecbd”,用最优的时空复杂度。

19.判断一个链表是否有环（我回答快慢指针，因此引出下一个问题）

两个指针，一个走1步，一个走2步，龟兔赛跑问题

20.一个数组，有正有负，把正的移到右边，负的移到左边。

21.两个队列实现栈

《剑指Offer》原题

请到「今天看啥」查看全文