刻意練習 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代码】

【运行结果】

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180605G1L6FJ00?refer=cp_1026
  • 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 cloudcommunity@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券