刻意練習 CODE 001 005

Jun 5 2018 | DELIBERATE PRATICE |

Fight For Offer | 劍指Offer |

Tags | CODE |

转眼就到了六月份

为了准备接下来的秋招，我计划了这个系列，用来记录我平时看书总结的内容以及敲过的代码，仅此而已~

CODE 001： 找出数组中重复数字。

在一个长度为n的数组里的所有数字都在0~n-1的范围内。数组中某些数字是重复的，但不知道有那几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。例如，如果输入长度为7的数组，那么对应的输出的是重复的数字2或者3。

【解题思路】

题目中有说到，数组中的数组都是在0~n-1的范围之内。如果这个数组没有重复的数字，那么数组排序之后，数字i就会出现在下标为i的位置。但如果数组中有重复的数字，那么有些位置就可能存在多个数字，同时有些位置可能就没有数字。

首先对这个数组进行重新排序。重拍后的数组变成；

从头扫描排序后的数组：

如果是，就接着扫描下一个数字；

如果不是，再拿它和下标为m的数字进行比较；

如果它和下标为m的数字相等，就找到了一个重复的数字（该数字在下标为i和m的位置都出现了）；

如果不相等，就把它和第m个数字交换，把m放到属于它的位置。然后再接着扫描。

当扫描到下标为i的数字的时候，比较这个数字（用m表示）是不是等于下标i；

【Java代码】

【运行结果】

这里我找出了所有重复的数字

Code 002：不修改数组找出重复的数字

在一个长度为n+1的数字里的所有数字都在1~n的范围内，所以数组中至少有一个数字是重复的。请找出数组中任意一个重复的数字，但不能修改输入的数组。例如，如果输入长度为8的数组，那么对应的输出是重复的数字2或者3.

【解题思路】

题目中说的很清楚，不能修改输入的数组，所以很正常就可以想到：新建一个数组，由于数组中的数字都是在1~n范围内的，所以只要把数字逐个复制到新数字中对应的下标中，就可以轻易的发现重复的数字了。但是这个方案需要创建一个新的数组，需要O(n)的辅助空间。

尝试另一种思路：

把从1~n的数字从中间的数字m分为两部分，前面一半为1~m，后面一半为m+1~n；

统计1~m区间内的数字数目：

如果1~m的数目超过m，那么这一半的区间内一定包含重复的数字；

否则，另一半m+1~n的区间内一定包含重复的数字；

重复第一个步骤，直到找到一个重复的数字。

【Java代码】

【运行结果】

需要指出的是，这种算法并不能保证找出所有重复的数字。就上面的例子而言，就不能找出另一个重复的数字2，因为在1~2区间内有两个数字，并不能知道是两个2，也有可能是一个1，一个2，所以不能保证找出所有重复的数字。

如果想找出所有重复的数字，就只能牺牲空间效率了。

【运行结果】

CODE 003：二维数组中的查找

在一个二维数组中，每一行都按照从左到右递增的顺序排序， 每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

例如：输入二维数组{，，，}，查找数字7，则返回true。如果输入的数字是5，则返回false。

【解题思路】

普遍的思路都是把二维数组画成一个矩形，然后从数组中选取一个数字，然后比较选取的数字和待查找的数字，以缩小查找的范围。但是，如果选取的数字位置“不对”，会导致在缩小查找范围的时候，出现重叠区域，以至于让问题更加复杂。

选取数组中右上角的数字。

对比该数字和要待查找的数字之间的大小关系：

如果该数字等于待查找的数字，则查找结束；

如果该数字大于待查找的数字，则剔除这个数字所在的列；

如果该数字小于带查找的数字，则剔除这个数字所在的行；

重复以上步骤。

【Java代码】

CODE 004：替换空格

请实现一个函数，把字符串中的每一个空格替换成“%20”。例如，输入“We are happy.”，则输出“We%20are%20happy.”。

【解题思路】

常规的思路是，从头到尾扫描这个字符串，遇到空格就把它替换成%20，因为是一个空格字符串替换成三个字符串，所以空格后面的字符串的位置一定要移动，不然会覆盖后面的字符串。这样的话，就会有部分字符串出现多次移动的问题，效率低下。

上面是从前向后替换，换一种思路是否会有很大不同？如果从后向前替换呢？

先遍历一次字符串，计算出替换空格后字符串数组的长度，并创建一个新的临时数组；

准备两个引用，一个指向原来数组的末尾，为oldIndex；一个指向新数组的末尾，为newIndex；

从后往前遍历原字符串数组：

如果遇到一个空格，oldIndex减1。同时将“%20”插入，newIndex减3；

否则，将原数组的字符复制到新数组中，oldIndex和newIndex同时减1；

重复第三步骤，直到原来的数组遍历完。

【Java代码】

【运行结果】

CODE 005：从头到尾打印链表

输入一个链表的头结点，从头到尾反过来打印出每个节点的值。

【解题思路】

最自然的思路就是将这个链表的反过来，然后再从头到尾遍历一次链表。但这样涉及到修改链表结构的问题，那有没有一种可以不修改原来链表结构的方法呢?

有。仔细分析题目，遍历该链表只能是从头到尾遍历，但是最终打印是要从尾到头打印，这就是典型的“先进后出”啊，所以可以引入“栈”这个数据结构将链表遍历的每一个节点存储起来，最后在遍历“栈”进行输出。

【Java代码】

【运行结果】