剑指Offer算法题解20-29

2019-05-27 本文已影响0人落地生涯

20 表示数值的字符串马上解题

题目描述

true："+100"，"5e2"，"-123"，"3.1416"，"-1E-16"

false："12e"，"1a3.14"，"1.2.3"，"+-5"，"12e+4.3"

解题思路

使用正则表达式进行匹配。

[] ：字符集合

() ：分组

? ：重复 0 ~ 1 次

+ ：重复 1 ~ n 次

* ：重复 0 ~ n 次

. ：任意字符

\\. ：转义后的 .

\\d ：数字

21 调整数组顺序使奇数位于偶数前面马上解题

题目描述

需要保证奇数和奇数，偶数和偶数之间的相对位置不变。

解题思路

方法一：创建一个新数组，时间复杂度 O(N)，空间复杂度 O(N)。

方法二：使用冒泡思想，每次都当前偶数上浮到当前最右边。时间复杂度 O(N2)，空间复杂度 O(1)，时间换空间。

代码

方法一：

方法二：

22 链表中倒数第 K 个结点马上解题

解题思路

设链表的长度为 N。设置两个指针 P1 和 P2，先让 P1 移动 K 个节点，则还有 N - K 个节点可以移动。此时让 P1 和 P2 同时移动，可以知道当 P1 移动到链表结尾时，P2 移动到第 N - K 个节点处，该位置就是倒数第 K 个节点。

代码

23 链表中环的入口结点马上解题

题目描述

一个链表中包含环，请找出该链表的环的入口结点。要求不能使用额外的空间。

解题思路

使用双指针，一个指针 fast 每次移动两个节点，一个指针 slow 每次移动一个节点。因为存在环，所以两个指针必定相遇在环中的某个节点上。假设相遇点在下图的 z1 位置，此时 fast 移动的节点数为 x+2y+z，slow 为 x+y，由于 fast 速度比 slow 快一倍，因此 x+2y+z=2(x+y)，得到 x=z。

在相遇点，slow 要到环的入口点还需要移动 z 个节点，如果让 fast 重新从头开始移动，并且速度变为每次移动一个节点，那么它到环入口点还需要移动 x 个节点。在上面已经推导出 x=z，因此 fast 和 slow 将在环入口点相遇。