剑指offer(13)

剑指Offer(13)

综合

**更新：此题解 markdown 源文件已放到 Github [https://github.com/dox1994/offer-coding-interviews-python](https://github.com/dox1994/offer-coding-interviews-python)，欢迎前去给个小星星鸭！**
---
## 把字符串转换成整数
### 问题 
将一个字符串转换成一个整数(实现Integer.valueOf(string)的功能，但是string不符合数字要求时返回0)，要求不能使用字符串转换整数的库函数。 数值为0或者字符串不是一个合法的数值则返回0。
### 思路 
逐个位来判断和累加计算就行，但需要注意各种各样的特殊情况要考虑周全。 
比如，以+ - 开头的、字符串不能出现字母等其他符号、+-不能出现在中间，以及空字符串、只有+-字符的字符串等。
### 代码 
```python 
# -*- coding:utf-8 -*- 
class Solution: 
 def StrToInt(self, s): 
 # write code here 
 minus = 1 
 number = 0 
 if not s: 
 return number 
 if s[0] == '+': 
 if len(s) > 1: 
 s = s[1:] 
 else: 
 return 0 
 elif s[0] == '-': 
 minus = -1 
 if len(s) > 1: 
 s = s[1:] 
 else: 
 return 0 
 for i in range(0, len(s)): 
 if '0' <= s[i] <= '9': 
 number = number * 10 + ord(s[i]) - ord('0') 
 else: 
 return 0 
 return number * minus 
```
## 数组中重复的数字
### 问题 
在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。
### 思路 
基本的思路就是建一个hash表，读数先判断是否重复，不重复就放进去读下一个，直到找到第一个重复的。
另外可以进行排序，然后判断是否有相邻两个数重复。
但注意题目中条件，所有数字都在0到n-1范围内。因此无需开辟额外空间，可以直接在数组上做标记。读到数字时，将数组中该数字作为下标的位置的数字，减去n，作为标记。下次读到相同数字，去其下标位置，发现数字值小于0，说明已经被标记过，那么这个就是重复数字了。
一些细节：之所以不用加上n的方法来标记，是因为可能会导致数字过大溢出（减去n就不会，因为只要n不溢出， -n-1 就不溢出， -n-1+一个正数 就也不会溢出）。也不能乘以-1来做标记，因为这种方法对0就没法做标记了。
### 代码 
```python 
# -*- coding:utf-8 -*- 
class Solution: 
 # 返回值格式：函数返回True/False，找到任意重复的一个值并赋值到duplication[0] 
 def duplicate(self, numbers, duplication): 
 length = len(numbers) 
 for num in numbers: 
 if num >= 0: 
 # 直接按num为下标去找 
 index = num 
 else: 
 # 如果此处已被标记，则下标要按此处的值 num+length 去找 
 index = num + length 
 if numbers[index] < 0: 
 # 找到重复 
 duplication[0] = numbers[index] + length 
 return True 
 else: 
 # 不重复，则做下标记 
 numbers[index] -= length 
 return False 
```
## 构建乘积数组 
### 问题 
给定一个数组A[0,1,...,n-1],请构建一个数组B[0,1,...,n-1],其中B中的元素B[i]=A[0]*A[1]*...*A[i-1]*A[i+1]*...*A[n-1]。不能使用除法。
### 思路 
如果可以使用除法，则先求出A所有元素的积，再依此对每个位置做除法就行（注意考虑到0的情况！）
让我们以一种清楚点的方式来看这个题，其实对B的每一个元素，都可以以下标i，把整个乘积分为前后两个部分：
![](/uploads/images/084855b0-c946-11e8-8843-fa163e7a698c.jpg)
具体到实现上，可以先做左下部分，即做一个循环，从上往下，B中当前元素的值，是A中对应的一个值和前一个B的值相乘得到。然后再对右上部分做一个循环，此时就要单独开辟一个temp来存储累乘值，从下往上把右上部分的值补全。
### 代码 
``` 
# -*- coding:utf-8 -*- 
class Solution: 
 def multiply(self, A): 
 if not A: 
 return [] 
 B = [1] * len(A) 
 # 先从上往下累乘左下半 
 for i in range(1, len(A)): 
 # 无需额外开辟temp存储累乘值，因为累乘值就是B[i-1] 
 B[i] = B[i-1] * A[i-1] 
 # 再从下往上累乘右上半 
 temp = 1 # 需要额外开辟temp来存储累乘值了 
 for i in range(len(A)-2, -1, -1): 
 temp *= A[i+1] 
 B[i] *= temp 
 return B 
```
## 正则表达式匹配 
### 问题 
请实现一个函数用来匹配包括'.'和'*'的正则表达式。模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但是与"aa.a"和"ab*a"均不匹配
### 思路 
重点是要思路清晰吧……只能说很容易就忽略各种各样的情况，导致无法通过所有用例。
对初始输入的判断： 
如果s和pattern都为空，则True；如果s不空，而pattern为空，则直接False.
然后来读取pattern中的每个字符： 
- 如果当前pattern字符的后面不是* ，则说明只可匹配1个 
 - 如果当前pattern字符是.的话，可匹配1个任意字符 
 - 如果不是点，则只能匹配给出的字符，若不匹配则直接返回 
 - 完成后两者均往后+1，继续判断 
- 如果当前pattern字符的后面是* ，说明当前pattern字符可匹配0-任意多个。 
 - 如果当前pattern字符与串的字符不一致，而且当前字符不是点，则当作是 * 的不匹配情况，pattern往后+2而字符串不变 
 - 否则其他情况： 
 - 要么共匹配0个，pattern往后+2，字符串不变 
 - 要么共匹配1个，字符串往后+1, pattern 往后+2 
 - 要么先匹配1个，留待继续匹配，此时字符串+1， pattern不变 
 - 然后继续匹配后面的是否match；
### 代码 
```python 
# -*- coding:utf-8 -*- 
class Solution: 
 # s, pattern都是字符串 
 def match(self, s, pattern): 
 # 如果s与pattern都为空，则True 
 if len(s) == 0 and len(pattern) == 0: 
 return True 
 # 如果s不为空，而pattern为空，则False 
 elif len(s) != 0 and len(pattern) == 0: 
 return False 
 # 如果s为空，而pattern不为空，则需要判断 
 elif len(s) == 0 and len(pattern) != 0: 
 # pattern中的第二个字符为*，则pattern后移两位继续比较 
 if len(pattern) > 1 and pattern[1] == '*': 
 return self.match(s, pattern[2:]) 
 else: 
 return False 
 # s与pattern都不为空的情况 
 else: 
 # pattern的第二个字符为*的情况 
 if len(pattern) > 1 and pattern[1] == '*': 
 # s与pattern的第一个元素不同，则s不变，pattern后移两位，相当于pattern前两位当成空 
 if s[0] != pattern[0] and pattern[0] != '.': 
 return self.match(s, pattern[2:]) 
 else: 
 # 如果s[0]与pattern[0]相同，且pattern[1]为*，这个时候有三种情况 
 # pattern后移2个，s不变；相当于把pattern前两位当成空，匹配后面的 
 # pattern后移2个，s后移1个；相当于pattern前两位与s[0]匹配 
 # pattern不变，s后移1个；相当于pattern前两位，与s中的多位进行匹配，因为*可以匹配多位 
 return self.match(s, pattern[2:]) or self.match(s[1:], pattern[2:]) or self.match(s[1:], pattern) 
 # pattern第二个字符不为*的情况 
 else: 
 if s[0] == pattern[0] or pattern[0] == '.': 
 return self.match(s[1:], pattern[1:]) 
 else: 
 return False 
```
## 表示数值的字符串 
### 问题 
请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串"+100","5e2","-123","3.1416"和"-1E-16"都表示数值。 但是"12e","1a3.14","1.2.3","+-5"和"12e+4.3"都不是。
### 思路 
以下为剑指Offer上的思路： 
表示数值的字符串遵循模式 <code>A[.[B]][e|EC]</code> 或者 <code>.B[e|EC]</code>。其中，A为数值的整数部分，B为小数部分，C为指数部分。要满足以下条件： 
- 可以没有A部分，或者没有B部分，但不能AB同时没有 
- AC均可能以+-开头的0-9字符 
- B也是0-9字符但不能有+-号
判断时，从左到右扫描字符串，先尽可能地扫描出整数部分A，碰到小数点再扫描得到B，碰到e或E再扫描得到C。
### 代码
按剑指 Offer 上的思路，来写代码如下： 
```python 
# -*- coding:utf-8 -*- 
class Solution: 
 def __init__(self): 
 self.cursor = 0
 def isNumeric(self, s): 
 if not s: 
 return False 
 # 先判断是否存在A部分 
 numeric = self.scan_integer(s) 
 # 如果出现小数点，则判断小数部分 
 if (self.cursor < len(s)) and s[self.cursor] == '.': 
 self.cursor += 1 
 # 用or的原因是，既可以没有A部分，也可以没有B部分，也可以AB都有，但不能AB都没有 
 numeric = self.scan_unsigned_integer(s) or numeric 
 # 如果出现e，则判断指数部分 
 if (self.cursor < len(s)) and (s[self.cursor] == 'e' or s[self.cursor] == 'E'): 
 self.cursor += 1 
 # 用and的原因是，既然出现了E，后面必须要有整数，且E的前面必须是已判断好了的合法数字 
 numeric = numeric and self.scan_integer(s)
 return numeric and self.cursor == len(s)
 def scan_integer(self, s): 
 # 作用：扫描字符串从当前cursor位置往后，是否有整数 
 # 先处理掉前面的符号位（如果没有符号位就不处理，无影响） 
 if (self.cursor < len(s)) and (s[self.cursor] == '+' or s[self.cursor] == '-'): 
 self.cursor += 1 
 # 再调用判断无符号整数的方法 
 return self.scan_unsigned_integer(s)
 def scan_unsigned_integer(self, s): 
 # 作用：扫描字符串从当前cursor位置往后，是否有无符号整数 
 # 先记下cursor本来的位置 
 original_cursor = self.cursor 
 # 遇到 0-9 数字就往后移动cursor 
 while (self.cursor < len(s)) and ('0' <= s[self.cursor] <= '9'): 
 self.cursor += 1 
 # 如果cursor比最初后移了，说明有无符号整数 
 return self.cursor > original_cursor 
```
另有思路，用有限自动机来实现，这个感觉是挺好的，而且具有扎实的计算机基础，判断过程也会更严谨。 具体见 https://www.nowcoder.com/questionTerminal/6f8c901d091949a5837e24bb82a731f2
此外，再贴牛客上的一个实现思路： 
```python 
# -*- coding:utf-8 -*- 
class Solution: 
 # s字符串 
 def isNumeric(self, s): 
 # 标记符号、小数点、e是否出现过 
 sign = False 
 decimal = False 
 has_e = False 
 for i in range(len(s)): 
 if s[i] == 'e' or s[i] == 'E': 
 if i == len(s) - 1: 
 return False # E后面必须跟数字，E不可以在字符串结尾 
 if has_e: 
 return False # 不可以出现两个E 
 has_e = True 
 elif s[i] == '+' or s[i] == '-': 
 if sign and (s[i-1] != 'e' and s[i-1] != 'E'): 
 return False # 如果是第二次出现符号，符号必须跟在E之后 
 if (not sign) and (i > 0) and (s[i-1] != 'e' and s[i-1] != 'E'): 
 return False # 如果第一次出现符号，且不是在开头出现，则必须紧跟在E之后 
 sign = True 
 elif s[i] == '.': 
 if has_e or decimal: 
 return False # E后面不能出现小数点，或小数点不能出现两次 
 decimal = True 
 elif s[i] < '0' or s[i] > '9': 
 return False # 不合法字符 
 return True 
```
## 第一个只出现一次的字符
### 问题 
请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符"go"时，第一个只出现一次的字符是"g"。当从该字符流中读出前六个字符“google"时，第一个只出现一次的字符是"l"。
如果当前字符流没有存在出现一次的字符，返回#字符。
（注：本题就是求字符串中第一个只出现一次的字符，但是把具体代码实现稍微做了变化，也即模拟了一个字符流，需要通过insert函数每次插入一个字符，然后通过 fisrt_appear_once获取当前状态下的字符串里的第一个只出现一次的字符）
### 思路 
（刷题后遗症就是这道题明明觉得有好多种方法可以实现，但还是怀疑自己没有想到最优的方法，也是醉了……）
最基本的方法就是，从当前串开头开始读，读到每个字符就往后扫一遍看是否有重样的， 直到找到第一个不重样的。时间复杂度n^2。
另外方法自然就是建hash表啦，先扫一遍串，记下每个字符出现的次数，再扫一遍串同时查询每个字符出现的次数，遇到出现次数为1的就是第一个只出现一次的字符了。
### 代码 
```python 
# -*- coding:utf-8 -*- 
class Solution: 
 def __init__(self): 
 self.stream = [] 
 self.counter = {} 
 # 返回对应char 
 def FirstAppearingOnce(self): 
 for c in self.stream: 
 if self.counter[c] == 1: 
 return c 
 return '#'
 def Insert(self, char): 
 if char in self.counter: 
 self.counter[char] += 1 
 else: 
 self.counter[char] = 1 
 self.stream.append(char) 
```
## 链表中环的入口结点
### 问题 
给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。
### 思路 
![](/uploads/images/60225484-ca1d-11e8-8843-fa163e7a698c.png) 
首先要确定是否包含环。（这个题在第二版书中是位于 链表倒数第k个结点 之后的，所以思路上会有些类似。）确定的方法是，两个指针同时从头出发，一个一次走一步，一个一次走两步，当快指针和慢指针重逢了，说明存在环，如果快指针走到了链表末尾，也没有和慢的重逢过，说明不包含环。
第二步是找出环的入口。仍然可以用两个指针，如图的环有4个节点，那么让p1先走4步，然后p1 p2 一起走，当两个指针重逢时，由于两个指针差距应该是环的长度，而他俩重逢了，说明p1已经绕环走了一圈，重逢的位置就是环的入口。
如何找到环的长度？在前面判断是否有环时，如果快慢指针相遇则说明有环，此时相遇的节点必定在环中，记住这个节点然后从它出发，等再次回到这个节点时就走了一圈，就得到环的长度了。
所以这个题的关键在于，要知道如何判断是否包含环、如何计算环长度、如何通过两个指针差距的方法找到环的入口。
### 代码 
```python 
# -*- coding:utf-8 -*- 
# class ListNode: 
# def __init__(self, x): 
# self.val = x 
# self.next = None 
class Solution: 
 def EntryNodeOfLoop(self, pHead): 
 if not pHead: 
 return None 
 fast = pHead 
 slow = pHead 
 has_loop = False 
 # 先判断是否有环 
 while fast: 
 if fast.next: 
 fast = fast.next.next 
 else: # fast已经走到最后的节点了 
 return None 
 slow = slow.next 
 if fast == slow: 
 has_loop = True 
 break 
 if not has_loop: 
 return None 
 # 统计环中节点个数 
 count = 1 
 fast = fast.next 
 while slow != fast: 
 fast = fast.next 
 count += 1 
 # 寻找环的入口 
 fast = pHead 
 slow = pHead 
 while count > 0: 
 fast = fast.next 
 count -= 1 
 while fast != slow: 
 fast = fast.next 
 slow = slow.next 
 return fast 
```
另有一种很简洁的python写法： 
```python 
class Solution: 
 def EntryNodeOfLoop(self, pHead): 
 slow, fast = pHead, pHead 
 while fast and fast.next: 
 slow = slow.next 
 fast = fast.next.next 
 if slow == fast: # 有环 
 slow2 = pHead # 直接让slow继续走，另从head同步开始走了？？ 
 while slow != slow2: 
 slow = slow.next 
 slow2 = slow2.next 
 return slow 
```
为何判断有环之后，从相遇的点开始，直接让slow和head出发的slow2继续走，等相遇时就是入口了呢？难道不需要先计算一下环长？
不妨这样来算一下，当fast和slow相遇时， l_fast = l_slow + ring = 2 x l_slow，换言之，l_slow = ring ！ 相遇时slow走过的距离，就已经是环的长度了！所以无需再去费劲计算环长，还要让一个指针先走过环长步，因为费了一大圈兜兜转转，最开始相遇的地方，就已经是要找的地方了……
## 删除链表中重复的结点 
### 问题 
在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5
### 思路 
首先构造一个空的头节点（以防出现 1->1 这样的链表，应当返回空），然后有两个指针，pre指向当前已经处理好了的链表，而last指向当前正在处理的节点。
对于每个节点 
- 如果它和它后面的值相同，那么就让它一直往后走，直到它和它后面的值不相同，然后把它后面的节点，接到当前处理完链表的后面； 
- 如果它和它后面的值不同，就直接接到链表上，然后继续往后找即可
### 代码 
``` 
class Solution: 
 def deleteDuplication(self, pHead): 
 # 空，或者只有一个节点，直接返回 
 if (not pHead) or (not pHead.next): 
 return pHead 
 # 构造一个新的头节点 
 head = ListNode(0) 
 head.next = pHead 
 pre = head 
 last = head.next 
 while last: 
 # 当前节点有next，且和它的next值相同，说明这一串都要被抛弃 
 if last.next and last.val == last.next.val: 
 while last.next and last.val == last.next.val: 
 last = last.next 
 pre.next = last.next 
 last = last.next 
 # 当前节点没有next，或者和它的next值不同，则将此节点接入链表，并继续往后走 
 else: 
 pre = pre.next 
 last = last.next 
 return head.next 
```

剑指offer(13)

剑指Offer(13)

近期文章

近期评论

标签

热门

文章归档

分类目录

功能