剑指offer刷题记录

前言

为了避免每次在牛客IDE上做题的紧张,我决定重新刷几遍《剑指offer》,记录下每次遇到的坑点。

03 重复数字

一看就知道需要调换数组中的元素使它应该到指定的位置。

这里的坑点是当进行交换的时候,不能简单进行交换,因为会进行修改,所以切记需要保存下来才可以修改。

04 二维数组查找

从右上角开始判断的题目,注意二维数组如果是空的判断。

05 替换空格

对于java来说不是问题。

06 从尾到头打印单项链表

两种思路,一种是通过利用额外的空间存储,另外一种是通过递归的方法。

如果你想通过反转链表来做,需要和面试官交流,因为一般不让修改原始数据。

第一种通过额外的存储空间,我的习惯使用deque,记得不要一边遍历,一边删除。

第二种是递归。

07 重建二叉树

递归没问题。递归的跳出的条件是start>end,我一开始写了start>=end,这样会漏掉几个数字。

然后记得搞清楚加一减一即可。

08 二叉树中序遍历的下一个

如果一个节点有右节点,那么就是右节点下的最左的那个节点。

如果一个节点它没有右节点,同时它又是左节点,那么就应该遍历父节点。

如果一个节点它没有右节点,同时它也不是左节点,那么就继续往上找,直到找到根节点。

09 两个栈来完成队列

一个栈只负责用来Push,另外一个栈只负责用来pop,一旦另外一个栈没东西了,就从第一个栈中倒过去。

那如何用两个队列来实现栈呢?只需要把n-1个元素出队列放到另外一个队列中,然后把队列中剩余的那个弹出即可。

10 斐波那契数列

比较简单就跳过了。

11 找出旋转数组中最小的数字

这题比较难。首先需要和最右边right进行比较,如果两者相等,那么则是right=mid,而不是right = mid-1

12 矩阵中的路径

DFS,注意是进去的时候需要判断,目标位置的数值和当前的index是否相等。

13 机器人的运动范围

感觉没什么意思,这题我就跳过了。

14 剪绳子

就是简单的取3出来。

15 二进制中1的个数

只需要n&(n-1),就可以消去其中最后的一个1。当然也可以用>>>来进行右移。

扩展:如果把一个二进制通过转变01来变成另外一个二进制,可以让两者进行异或^然后来计算

16 数值的整数次方

这道题有几个坑,首先要考虑幂次的正负,不能简单的把负数直接改成正的,因为最低的负数是不能直接变正数的。其次是记得把中间的结果记下来。

17 打印从1-n个9的的所有数字

看一眼,就知道是DFS做的。注意考虑大数的问题。

18 删除链表节点

???那手动写一个链表吧

扩展:如何删除链表中的重复节点。注意头部的问题。

19 正则表达式匹配

我觉得难度太大了,面试官是不会问的。

20 表示数值的字符串

….意义不明

21 使所有奇数位于偶数前面

如果只是要求这样,可以直接用双指针完成。

但是如果是要求算法的稳定性,那么必然是需要花费O(n2)的时间,或者拿O(n)的空间来作为代价的。

思路是这样的,每一轮,我都把一个偶数通过交换的方式给换到最后面,然后下一轮就减一来减少总遍历个数来完成。非常类似冒泡。

22 删除倒数第K个节点

利用快慢指针来做,需要注意和面试官讨论K的范围。

23 链表中环的入口

这道题首先应该跟面试官交流是否确保链表中有环,如果有的话再去找环。

总结:对于链表的

24 反转链表

常考常考!!一定要记得非常熟练!

还需要掌握递归的方法。但是递归真的是恶心了。

25 合并两个有序链表

我之前写的代码比较恶心,所以需要掌握以下简介的写法。而且这里我写的时候想的是新创建一个节点,然后复制,这里相当于浪费了非常多的空间,其实只需要对原来的链表进行修改就可以了。

而且同时需要掌握递归和非递归两种写法。

扩展:掌握K个有序链表的排序,利用的是小顶堆。

26 树的子结构

终于到树了。树的题目十有八九肯定是递归。这里我第一次写的时候有问题,其实是需要两个递归,但是我只用了一个。

27 二叉树的镜像

交换左右子树,并且对左右子树进行相同的操作即可。还可以使用非递归的方法,就是利用BFS进行遍历,然后对于每个出栈的元素,交换它的左右子树即可。

28 判断二叉树是否对称

这个题真的是做一次不会,做一次不会。

首先你需要自己实现一个函数来判断两个节点是否是对称的,然后需要判断

29 矩阵打印

我自己做的方法是统计出一共有多少个节点要打印,这样能够防止多打印造成的越界等问题的发生。不过这种题目其实非常不适合在面试的时候考查。

30 最小栈

利用一个辅助栈来完成的。这里需要注意的是,当辅助栈是空的时候,就直接把当前的元素放进去,这是我踩过的坑。

31 栈的出栈入栈顺序

照着自己的思路来,就是简单的模拟。

32 BFS打印二叉树

用一个队列就可以了。毫无难度。

记得最后一层是全部是null的层,所以需要判断一下再入。或者是直接不把null给加到队列中去也行。

如果是之字形打印的话,可以通过reverse做一下。

33 二叉搜索树的后序遍历

第一种方法,递归。第一次写的太复杂了。可以从头开始遍历,然后找到第一个比end大的数字,这个数字是右边子树的开始,然后接着开始往下找,看能不能找到第一个比它小的数字,如果能找到则必然不是。

第二种方法,单调栈,单调栈比较难,但是还是要掌握的。

34 二叉树中和为某个值

我自己做的是利用递归,看别人做的是利用的前序遍历做的。

其实用DFS做的思路是最清晰最好的。

35 复杂链表的复制

emmmm 就是每个节点之后复制一下,然后就能找到random之后的节点了。

36 二叉搜索树和双向链表

把二叉搜索树变成一个双向链表。字节二面问的问题,我当时没写出来,而且写的巨复杂。

37 序列化二叉树

可以利用BFS进行遍历,这样就是一个满二叉树。然后满二叉树可以直接用

38 字符串的排列

很简单的DFS,但是要求的是不能重复的,所以需要注意。不能重复的话,只需要确保之后没有被访问即可。

扩展:不是每个都需要选择的话怎么做?这个其实更简单,都不需要visited数组了,只需要对每个元素,选择放入或者不放入即可。

39 数组中超过一半的数字

摩尔投票法。或者是利用快排的partition来找到中位数。

40 最小的K个数

那最小堆就可以了。也可以用partition来完成。

41 超大数据流中找到中位数

这个不会。

42 连续子数组的最大和

这题切记,我们计算的是当前这个数字之前的和,如果之前的和已经小于0了,那么就不要了,否则才加上去,然后取最大。

45 数组中拼接成最小的数字

任取两个数字,按照它们之间的大小进行排序,比较s1+s2拼接而成的字符串与s2+s1拼接而成的哪个大,就用哪个。

47 礼物的最大值

DP规划,没什么好说的,也没什么坑。

48 最长不含重复字符的字符串

用滑动窗口做的。方便简洁。MD之前用的hashmap恶心死了。

49 丑数

这主要是讲述了用时间换空间。

50 第一个只出现一次的字符

对,就是记录下每个字符出现的次数,然后对其进行操作即可。别想得太复杂了。

51 逆序对的个数

涉及到归并排序。