剑指Offer笔记 [Python描述]

二维数组中的查找

题目描述：

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

[

[1,2,8,9],

[2,4,9,12],

[4,7,10,13],

[6,8,11,15]

]

给定 target = 7，返回 true。

给定 target = 3，返回 false。

数据范围: 矩阵的长宽满足 \(0 \leq n, m \leq 500\) ， 矩阵中的值满足 \(0 \leq v a l \leq 10^{9}\) 进阶：空间复杂度 \(O(1)\) ，时间复杂度 \(O(n+m)\)

输入描述：

7,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]


输出描述：

true


代码如下：

def find(target, array):
i = 0
j = len(array[0]) - 1
while i = 0:
base = array[i][j]
if target == base:
return True
elif target > base:
i += 1
else:
j -= 1
return False
print(find(4,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]))


替换空格

题目描述：

请实现一个函数，将一个字符串s中的每个空格替换成“%20”。

例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

数据范围: \(0 \leq \operatorname{len}(s) \leq 1000\) 。保证字符串中的字符为大写英文字母、小写英文字母和空格中的一种。 进阶：时间复杂度 \(O(n)\),空间复杂度 \(O(n)\)

输入描述：

"We Are Happy"
" "


输出描述：

"We%20Are%20Happy"
"%20"


代码如下：

def replaceSpace(s):
# write code here
s_len = len(s)
space_count = 0
for i in s:
if i == ' ':
space_count += 1
s_len += 2 * space_count
new_array = [' '] * s_len
j = 0
for i in range(len(s)):
if s[i] == ' ':
new_array[j] = '%'
new_array[j+1] = '2'
new_array[j+2] = '0'
j += 3
else:
new_array[j] = s[i]
j += 1
return ''.join(new_array)
print(replaceSpace('We Are Happy'))


从尾到头打印链表

题目描述：

输入一个链表的头节点，按链表从尾到头的顺序返回每个节点的值（用数组返回）。

如输入{1,2,3}的链表如下图:

返回一个数组为[3,2,1]

0 <= 链表长度 <= 10000

输入描述：

{67,0,24,58}


输出描述：

[58,24,0,67]


代码如下：

class ListNode(object):
def __init__(self, x):
self.val = x
self.next = None
# 解法1：用辅助栈存储
def printListFromTailToHead(listNode):
# write code here
stack = []
result_array = []
node_p = listNode
while node_p:
stack.append(node_p.val)
node_p = node_p.next
while stack:
result_array.append(stack.pop(-1))
return result_array
# 解法2：本身栈调用
result_array = []
def printListFromTailToHead(listNode):
# write code here
if listNode:
printListFromTailToHead(listNode.next)
result_array.append(listNode.val)
return result_array


重建二叉树

题目描述：

​ 给定节点数为 n 二叉树的前序遍历和中序遍历结果，请重建出该二叉树并返回它的头结点。

例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建出如下图所示。

提示:

1.vin.length == pre.length

2.pre 和 vin 均无重复元素

3.vin出现的元素均出现在 pre里

4.只需要返回根结点，系统会自动输出整颗树做答案对比

数据范围: \(n \leq 2000\) ，节点的值 \(-10000 \leq\) val \(\leq 10000\) 要求：空间复杂度 \(O(n)\), 时间复杂度 \(O(n)\)

输入描述：

[1,2,4,7,3,5,6,8],[4,7,2,1,5,3,8,6]


输出描述：

{1,2,3,4,#,5,6,#,7,#,#,8}
说明：
返回根节点，系统会输出整颗二叉树对比结果，重建结果如题面图示


代码如下：

class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
# 返回构造的TreeNode根节点
def reConstructBinaryTree(pre, tin):
# write code here
if not pre:
return None
root_val = pre[0]
root = TreeNode(root_val)
for i in range(len(tin)):
if tin[i] == root_val:
break
root.left = reConstructBinaryTree(pre[1:1+i], tin[:i])
root.right = reConstructBinaryTree(pre[1+i:], tin[i+1:])

return root
def preorder(root):
if root:
preorder(root.left)
print(root.val)
preorder(root.right)
preorder(reConstructBinaryTree([1,2,3,4,5,6,7],[3,2,4,1,6,5,7]))


用两个栈实现队列

题目描述：

用两个栈来实现一个队列，使用n个元素来完成 n 次在队列尾部插入整数(push)和n次在队列头部删除整数(pop)的功能。 队列中的元素为int类型。保证操作合法，即保证pop操作时队列内已有元素。

数据范围: \(n \leq 1000\) 要求: 存储 \(n\) 个元綁的空间复杂度为 \(O(n)\) ，揷入与删除的时间复杂度都是 \(O(1)\)

输入描述：

["PSH1","PSH2","POP","POP"]


输出描述：

1,2
说明：
"PSH1":代表将1插入队列尾部
"PSH2":代表将2插入队列尾部
"POP“:代表删除一个元素，先进先出=>返回1
"POP“:代表删除一个元素，先进先出=>返回2


代码如下：

class CQueue(object):
def __init__(self):
self.stack1 = []
self.stack2 = []
def appendTail(self, value):
self.stack1.append(value)

def deleteHead(self):
if not self.stack2:
while self.stack1:
self.stack2.append(self.stack1.pop(-1))
if len(self.stack2) == 0:
return -1
return self.stack2.pop(-1)


• 思路
  
  一个栈用来存储，pop时弹出stack2，stack2为空，pop出stack1存储在stack2中。

旋转数组的最小数字

题目描述：

有一个长度为 n 的非降序数组，比如[1,2,3,4,5]，将它进行旋转，即把一个数组最开始的若干个元素搬到数组的末尾，变成一个旋转数组，比如变成了[3,4,5,1,2]，或者[4,5,1,2,3]这样的。请问，给定这样一个旋转数组，求数组中的最小值。

数据范围: \(1 \leq n \leq 10000\) ，数组中任意元龶的值: \(0 \leq\) val \(\leq 10000\) 要求: 空间复杂度: \(O(1)\) ，时间复杂度: \(O(\operatorname{logn})\)

输入描述：

[3,4,5,1,2]


输出描述：

1


代码如下：

class Solution(object):
def minArray(self, numbers):
low, high = 0, len(numbers) - 1
while low mid = (high+low) / 2
if numbers[mid] > numbers[high]:
low = mid + 1
elif numbers[mid] high = mid
else:
if (numbers[high - 1] > numbers[high]): # 确保正确的下标
low = high
break
high -= 1 # 如果numbers[hign-1]=numbers[high]的情况
return numbers[low]


思路

总体二分：

• if mid大于high, low = mid - 1


• if mid小于high, high = mid


• 直到mid=high，取此位置的数

斐波那契数列

题目描述：

大家都知道斐波那契数列，现在要求输入一个正整数 \(n\) ，请你输出斐波那契数列的第 \(n\) 项。 韭波那契数列是一个满足 \(f i b(x)=\left\{\begin{array}{rc}1 & x=1,2 \\ f i b(x-1)+f i b(x-2) & x>2\end{array}\right.\)

• 数据范围: \(1 \leq n \leq 39\)


• 要求: 空间复杂度 \(O(1)\) ，时间复杂度 \(O(n)\) ，本题也有时间复杂度 \(O(\operatorname{logn})\) 的解法

输入描述：

一个正整数n
4


输出描述：

输出一个正整数。
3
根据斐波那契数列的定义可知，fib(1)=1,fib(2)=1,fib(3)=fib(3-1)+fib(3-2)=2,fib(4)=fib(4-1)+fib(4-2)=3，所以答案为4。


代码如下：

def Fibonacci(n):
# write code here
f1 = 0
f2 = 1
if n == 0: return f1
elif n == 1: return f2
for _ in range(n-1):
f2, f1 = f1+f2, f2
return f2
print(Fibonacci(3))


跳台阶

题目描述：

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

数据范围: \(0 \leq n \leq 40\)

要求: 时间复杂度: \(O(n)\) ，空间复杂度: \(O(1)\)

输入描述：

2


输出描述：

2
说明：
青蛙要跳上两级台阶有两种跳法，分别是：先跳一级，再跳一级或者直接跳两级。因此答案为2


代码如下：

class Solution(object):
def numWays(self, n):
if n == 0: return 1
f1 = 1
f2 = 2
if n == 1: return f1
if n == 2: return f2
for _ in range(n-2):
f2, f1 = f1+f2, f2
return f2 % 1000000007


思路

假设对于第n级台阶，总共有f(n)种跳法.

那么f(n) = f(n-1) + f(n-2)，其中f(1)=1,f(2)=2

跳台阶扩展问题

题目描述：

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶(n为正整数)总共有多少种跳法。

数据范围: \(1 \leq n \leq 20\)

进阶：空间复杂度 \(O(1) ，\) 时间复杂度 \(O(1)\)

输入描述：

3


输出描述：

4


代码如下：

def jumpFloorII(number):
# write code here
f1 = 1
if number == 1: return f1
for _ in range(number-1):
f1 = 2*f1
return f1


思路

f(1)=1, f(2)=2, f(3)=4, f(4)=8 设n+1级f(n+1),有

f(n+1) = f(1) + f(2) + ... + f(n)

f(n+2) = f(1) + f(2) + ... + f(n+1)

f(n+2)= 2f(1) + 2f(2) + ... + 2f(n)

故得f(n+2) = 2f(n+1)

矩形覆盖

题目描述：

我们可以用 21 的小矩形横着或者竖着去覆盖更大的矩形。请问用 n 个 21 的小矩形无重叠地覆盖一个 2*n 的大矩形，从同一个方向看总共有多少种不同的方法？

数据范围: \(0 \leq n \leq 38\)

进阶：空间复杂度 \(O(1)\) ，时间复杂度 \(O(n)\)

注意：约定 n == 0 时，输出 0

比如n=3时，2*3的矩形块有3种不同的覆盖方法(从同一个方向看)：

输入描述：

//2*1的小矩形的总个数n
4


输出描述：

5


代码如下：

def rectCover(number):
# write code here
f1 = 1
f2 = 2
if number == 1: return f1
if number == 2: return f2
for _ in range(number-2):
f2, f1 = f1 + f2, f2
return f2
print(rectCover(3))


思路

f(1) = 1

f(2) = 2

f(n) = f(n-1) + f(n-2)

二进制中1的个数

题目描述：

输入一个整数 n ，输出该数32位二进制表示中1的个数。其中负数用补码表示。

数据范围: \(-2^{31}<=n<=2^{31}-1\)

即范围为: \(-2147483648<=n<=2147483647\)

输入描述：

10
-1


输出描述：

2
32
说明：
1. 十进制中10的32位二进制表示为0000 0000 0000 0000 0000 0000 0000 1010，其中有两个1。
2. 负数使用补码表示 ，-1的32位二进制表示为1111 1111 1111 1111 1111 1111 1111 1111，其中32个1


代码如下：


def Power(base, exponent):
# write code here
if expOnent== 0: return 1
flag = 1
if exponent <0:
exponent *= -1
flag = 0
temp = base
res = 1
while(exponent):
if exponent & 1:
res *= temp
temp *= temp
expOnent= exponent >> 1
return res if flag else 1.0/res
print(Power(2, 1))


思路

如果n!=0，n的二进制中至少有一个1

• 如果1在最低位，n-1 & n 得到的数正好将这个1，变成0。


• 如果1不在最低位，n-1 & n 得到的数正好将这个1，变成0。

因此我们判断n-1 & n 能够循环运行的次数就可以判断二进制中有多少个1了。

在python中需要使用c_int()函数，不然负数不会变成0。

数值的整数次方

题目描述：

实现函数 double Power(double base, int exponent)，求base的exponent次方。

数据范围: \(\mid\) base \(|\leq 100,\), exponent \(\mid \leq 100\),保证最终结果一定满足 \(|v a l| \leq 10^{4}\) 进阶：空间复杂度 \(O(1)\) ，时间复杂度 \(O(n)\)

输入描述：

2.00000,-2


输出描述：

0.25000
2的-2次方等于1/4=0.25


代码如下：

from ctypes import *
def NumberOf1(n):
# write code here
cnt = 0
while c_int(n).value:
n = n & (n-1)
cnt += 1
print(c_int(n), n)
return cnt
print(NumberOf1(-3))


调整数组顺序使奇数位于偶数前面(一)

题目描述：

输入一个长度为 n 整数数组，数组里面不含有相同的元素，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前面部分，所有的偶数位于数组的后面部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

数据范围: \(0 \leq n \leq 5000\) ，数组中每个数的值 \(0 \leq\) val \(\leq 10000\)

要求: 时间复杂度 \(O(n)\) ，空间复杂度 \(O(n)\)

进阶：时间复杂度 \(O\left(n^{2}\right)\) ，空间复杂度 \(O(1)\)

输入描述：

[2,4,6,5,7]


输出描述：

[5,7,2,4,6]


代码如下：

def reOrderArray(array):
# write code here
odd_cnt = 0
res = [0] * len(array)
# 统计个数
for n in array:
if n % 2 != 0:
odd_cnt += 1
# 填坑
odd_i = 0
even_i = odd_cnt
for i in range(len(array)):
if array[i] % 2 != 0:
res[odd_i] = array[i]
odd_i += 1
else:
res[even_i] = array[i]
even_i += 1
return res


链表中倒数最后k个结点

题目描述：

输入一个长度为 n 的链表，设链表中的元素的值为 ai ，返回该链表中倒数第k个节点。

如果该链表长度小于k，请返回一个长度为 0 的链表。

数据范围: \(0 \leq n \leq 10^{5} ， 0 \leq a_{i} \leq 10^{9} ， 0 \leq k \leq 10^{9}\)

要求: 空间复杂度 \(O(n)\) ，时间复杂度 \(O(n)\)

进阶: 空间复杂度 \(O(1)\) ，时间复杂度 \(O(n)\)

例如输入{1,2,3,4,5},2时，对应的链表结构如下图所示：

其中蓝色部分为该链表的最后2个结点，所以返回倒数第2个结点（也即结点值为4的结点）即可，系统会打印后面所有的节点来比较。

输入描述：

{1,2,3,4,5},2


输出描述：

{4,5}
说明：
返回倒数第2个节点4，系统会打印后面所有的节点来比较。


代码如下：

class ListNode:
def __init__(self, x):
self.val = x
self.next = None
def FindKthToTail(head, k):
# write code here
if not head: return None
fast_p = head
slow_p = head
for _ in range(k):
if fast_p:
fast_p = fast_p.next
else:
return None
while fast_p:
fast_p = fast_p.next
slow_p = slow_p.next
return slow_p


思路

用快慢指针，快指针比慢指针快k步，到尾结点了慢指针就是倒数第k个结点。

反转链表

题目描述：

给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)，长度为n，反转该链表后，返回新链表的表头。

数据范围: \(n \leq 1000\) 要求: 空间复杂度 \(O(1)\) ，时间复杂度 \(O(n)\)

如当输入链表{1,2,3}时，

经反转后，原链表变为{3,2,1}，所以对应的输出为{3,2,1}。

以上转换过程如下图所示：

输入描述：

{1,2,3}


输出描述：

{3,2,1}


代码如下：

class ListNode:
def __init__(self, x):
self.val = x
self.next = None
def ReverseList(pHead):
# write code here
if not pHead: return None
head = ListNode(0)
head.next = pHead
p = pHead
while(p.next):
tp = p.next
p.next = p.next.next
tp.next = head.next
head.next = tp
return head.next


思路

假设翻转1->2->3->4->5，步骤如下：

head->4->3->2->1->5
p tp


• 1.我们将p的next指向tp的next


• 2.将tp的next指向head的next


• 3.将head的next指向tp

合并有序链表

题目描述：

输入两个递增的链表，单个链表的长度为 \(n\) ，合并这两个链表并使新链表中的节点仍然是递增排序的。

数据范围: \(0 \leq n \leq 1000 ，-1000 \leq {\text { 节点值 } \leq 1000}{}\)

要求：空间㚉杂度 \(O(1) ，\) 时间复杂度 \(O(n)\)

如输入{1,3,5},{2,4,6}时，合并后的链表为{1,2,3,4,5,6}，所以对应的输出为{1,2,3,4,5,6}，转换过程如下图所示：

或输入{-1,2,4},{1,3,4}时，合并后的链表为{-1,1,2,3,4,4}，所以对应的输出为{-1,1,2,3,4,4}，转换过程如下图所示：

输入描述：

{-1,2,4},{1,3,4}


输出描述：

{-1,1,2,3,4,4}


代码如下：

class ListNode:
def __init__(self, x):
self.val = x
self.next = None
def Merge(pHead1, pHead2):
# write code here
res = ListNode(0)
head = res
while pHead1 and pHead2:
if pHead1.val <= pHead2.val:
head.next = pHead1
head = head.next
pHead1 = pHead1.next
else:
head.next = pHead2
head = head.next
pHead2 = pHead2.next

if pHead1:
head.next = pHead1
if pHead2:
head.next = pHead2
return res.next


树的子结构

题目描述：

输入两棵二叉树A，B，判断B是不是A的子结构。（我们约定空树不是任意一个树的子结构）

假如给定A为{8,8,7,9,2,#,#,#,#,4,7}，B为{8,9,2}，2个树的结构如下，可以看出B是A的子结构

数据范围:

0 <= A的节点个数 <= 10000

0 <= B的节点个数 <= 10000

输入描述：

{8,8,7,9,2,#,#,#,#,4,7},{8,9,2}


输出描述：

true


代码如下：

class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
def helper(treeA, treeB):
if not treeB:
return True
elif not treeA:
return False
elif treeA.val != treeB.val:
return False
else:
return helper(treeA.left, treeB.left) and helper(treeA.right, treeB.right)
def HasSubtree(pRoot1, pRoot2):
# write code here
if not pRoot1 or not pRoot2: return False
# 2 是不是 1的子树
res = False
if pRoot1.val == pRoot2.val:
res = helper(pRoot1, pRoot2)
if res:
return True
else:
return HasSubtree(pRoot1.left, pRoot2) or HasSubtree(pRoot1.right, pRoot2)


思路

• 
  
  
  
  1. 遍历父结构
  
  
  
  


• 
  
  
  
  2. 判断子结构是否相同