剑指offer 第三章 题16-26题解 Python版

Github

代码完整性

  • 基础功能;
  • 输入边界值;
  • 错误处理;

题16:数值的整数次方

此题不需要考虑大数问题,仅仅是计算整数次方,所以处理好特殊值就行了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution:
def Power(self, base, exponent):
"""计算base的exponent次方

Arguments:
base {int} -- 整数
exponent {int} -- 指数,可正可负

Returns:
int -- 结果
"""

if base == 0:
return 0
if base == 1:
return 1

abs_exponent = self.abs_exp(base, abs(exponent))
if exponent > 0:
return abs_exponent
else:
return 1 / abs_exponent

# 此处处理有个窍门,可以二分计算
def abs_exp(self, base, exponent):
if exponent == 0:
return 1
if exponent == 1:
return base

res = self.abs_exp(base, exponent >> 1)
res *= res
if exponent & 1 == 1:
res *= base
return res

题17:打印从1到最大的n位数

此题其实是想考察大数的处理,在python中,大数的影响几乎不存在,所以可以直接写。但是使用数组或者字符串表示大数的方式还是值得学一学。

1
2
3
4
5
6
7
8
9
def print_1_to_n(n):
if n < 1:
return

i = 1
while len(str(i)) <= n:
print(i)
i += 1
print(' ')

题18:删除链表的节点

题19:正则表达式匹配

这个题情况分析很复杂。因为*可以表示出现任意次,所以在pattern中出现*时,s的推进情况就很复杂,此时用递归获取结果是最容易想明白的。

以模式的第二个字符为判断标准,来构造递归,具体看代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution:
# s, pattern都是字符串
def match(self, s, pattern):
if len(s) == 0 and len(pattern) == 0:
return True
# 如果s长度不为0,而pattern长度为0,这种情况不可能匹配成功
elif len(s) != 0 and len(pattern) == 0:
return False
# 如果s长度为0, 而pattern长度不为0,那么可能会有pattern为'(.*)*'的情况
elif len(s) == 0 and len(pattern) != 0:
# 如果pattern第二位为0, pattern推进两个
if len(pattern) > 1 and pattern[1] == '*':
return self.match(s, pattern[2:])
else:
return False
# 如果s和pattern长度都不为0
else:
# pattern第二位为*
if len(pattern) > 1 and pattern[1] == '*':
# 如果s[0] != pattern[0]
if s[0] != pattern[0] and pattern[0] != '.':
return self.match(s, pattern[2:])
# 如果s[0] == pattern[0], 那么有三种情况
# 1. s不变,pattern后移两步(pattern前两个字符等价于空)
# 2. s右移一个, pattern右移两个 (pattern前两个字符等价于一个字符)
# 3. s右移一个, pattern不右移 (pattern前两个字符等价于多个字符))
else:
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

这个题是真的烦。。

题20:表示数值的字符串

这个题并没有什么意思,找到所有可有可无的片段凑正则就行了。

1
2
3
4
5
6
import re

class Solution:
# s字符串
def isNumeric(self, s):
return True if re.match(r"^[\+\-]?[0-9]*(\.[0-9]*)?([eE][\+\-]?[0-9]+)?$", s) else False

题21:调整数组顺序使奇数位于偶数前面

这个题可以借助荷兰国旗问题求解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

# -*- coding:utf-8 -*-
class Solution:
def reOrderArray(self, array):
if array is None or len(array) < 2:
return array

p1 = 0
p2 = len(array) - 1
while p1 < p2:
if self.is_even(array[p1]) and not self.is_even(array[p2]):
self.swap(array, p1, p2)

while not self.is_even(array[p1]):
p1 += 1
while self.is_even(array[p2]):
p2 -= 1

def is_even(self, item):
return item & 1 == 0

def swap(self, array, i, j):
array[i], array[j] = array[j], array[i]

如果要求保留原数组奇数间的顺序以及偶数间的顺序,借助了辅助数组的代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# -*- coding:utf-8 -*-
class Solution:
def is_even(self, item):
return item & 1 == 0

def reOrderArray(self, array):
if array is None or len(array) < 2:
return array

assi_array = []

for item in array:
if not self.is_even(item):
assi_array.append(item)
for item in array:
if self.is_even(item):
assi_array.append(item)

return assi_array

代码鲁棒性

  • 判断输入
  • 容错性

题22:链表中倒数第k个节点

题目:

输入一个链表,输出该链表中倒数第k个节点。本题从1开始计数,即尾节点为倒数第1个节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
# -*- coding:utf-8 -*-
class ListNode:
def __init__(self, x):
self.val = x
self.next = None


class Solution:
def FindKthToTail(self, head, k):
"""打印链表倒数第k个节点

Args:
head (ListNode): 链表头结点
k (int): 指定数字

Returns:
ListNode: 倒数第k个节点
"""

p_ahead = head
p_behind = head
while k > 0:
if p_ahead is None:
return None
p_ahead = p_ahead.next

k -= 1
while p_ahead is not None:
p_ahead = p_ahead.next
p_behind = p_behind.next
return p_behind

题23:链表中环的入口节点

题目:

如果一个链表中包含环,如何找出环的入口节点?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
# -*- coding:utf-8 -*-
class ListNode:
def __init__(self, x):
self.val = x
self.next = None


class Solution:
def EntryNodeOfLoop(self, pHead):
"""找到链表中环的入口节点

Args:
pHead (ListNode): 链表头结点

Returns:
ListNode: 入口节点(如果没有返回None)
"""

if pHead is None or pHead.next is None:
return None
p1 = p2 = pHead
while p2.next is not None:
p2 = p2.next.next
p1 = p1.next
if p1 == p2:
first_met = p1
count = 1
while p1.next != first_met:
p1 = p1.next
count += 1

p1 = p2 = pHead
for i in range(count):
p1 = p1.next
while p1 != p2:
p1 = p1.next
p2 = p2.next
return p1
return None

题24:反转链表

题目:

定义一个函数,输入一个链表的头节点,反转该链表并输出反转后链表的头节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# -*- coding:utf-8 -*-
class ListNode:
def __init__(self, x):
self.val = x
self.next = None


class Solution:
def ReverseList(self, pHead):
"""反转链表,返回反转后的头

Args:
pHead (ListNode): 链表头

Returns:
ListNode: 反转之后链表头
"""

if pHead is None or pHead.next is None:
return pHead
new_head = self.ReverseList(pHead.next)

pHead.next.next = pHead
pHead.next = None

return new_head

题25:合并两个排序的链表

题目:

输入两个递增排序的链表,合并这两个链表并使新链表中的节点仍然是递增排序的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
# -*- coding:utf-8 -*-
class ListNode:
def __init__(self, x):
self.val = x
self.next = None


class Solution:
def Merge(self, pHead1, pHead2):
"""合并两个排序链表
"""

if pHead1 is None:
return pHead2
elif pHead2 is None:
return pHead1

p1, p2 = pHead1, pHead2
merge_head = None
if p1.val < p2.val:
merge_head = p1
merge_head.next = self.Merge(p1.next, p2)
else:
merge_head = p2
merge_head.next = self.Merge(p1, p2.next)

return merge_head
  • 本文作者: 大护法
  • 本文链接: https://todebug.com/offer16-26/
  • 版权声明: 本博客所有文章除特别声明外,均采用 BY-NC-SA 4.0 许可协议。转载请注明出处!
0%