剑指offer || 动态规划
剑指offer中有关
动态规划
的题目汇总
面试题14：剪绳子
题目：剪绳子
给你一根长度为n的绳子，请把绳子剪成m段（m,n都是整数，n > 1 并且 m > 1), 每段绳子的长度记为k[0],k[1],…,k[m]。请问 k[0] * k[1]* …*k[m]可能的最大乘积是多少？
例子：当绳子的长度是8时，我们把它剪成长度为2、3 、3的三段，此时的最大乘积是18
`
思路
- 动态规划
代码
#################面试题14#######################
#剪绳子
class Solution:
def maxProdectAfterCutting_solution(self,length):
product = []
if length <2:
return 0
elif length == 2:
return 1
elif length == 3:
return 2
product.extend([0,1,2,3])
max = 0
for i in range(4,length+1):
for j in range(1,i//2+1):
area = product[j] * product[i-j]
if max < area:
max = area
product.append(max)
return max
测试
################测试1#################
#功能测试
s = Solution()
s.maxProdectAfterCutting_solution(5)
面试题42：连续子数组的最大和
题目：连续子数组的最大和
输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(n)
输入： 数组[1,-2,3,10,-4,7,2,-5],和最大的子数组为[3,10,-4,7,2]
输出：，因此输出该数组的和为18
思路
代码
#################面试题42#######################
#连续子数组的最大和
def FindGreatestSumOfSubArray(Array):
if not Array:
return
n = len(Array)
maxSumArrayOfsubArray = [0] *(n+1)
maxSum = float('-inf')
for i in range(1,n+1):
if maxSumArrayOfsubArray[i-1] <= 0:
maxSumArrayOfsubArray[i] = Array[i-1]
else:
maxSumArrayOfsubArray[i] = maxSumArrayOfsubArray[i-1] + Array[i-1]
if maxSum < maxSumArrayOfsubArray[i]:
maxSum = maxSumArrayOfsubArray[i]
return maxSum
测试
################测试1#################
#功能测试
#
Array = [1,-2,3,10,-4,7,2,-5]
result = FindGreatestSumOfSubArray(Array)
print(result)
Array = [-2,-3,-10,-4,-7,-2,-5]
result = FindGreatestSumOfSubArray(Array)
print(result)
Array = [2,3,10,4,7,2,5]
result = FindGreatestSumOfSubArray(Array)
print(result)
面试题47：礼物的最大价值
题目：礼物的最大价值
在一个m*n的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值，可以从棋盘的左上角开始拿格子里的礼物，并每次向左或右移动一格，直到到达棋盘的右下角。给定棋盘及其礼物，计算最多能拿到多少价值的礼物
例如：
1 10 3 8
12 2 9 6
5 7 4 11
3 7 16 5`
思路
- 动态规划求解
-
f
(
i
,
j
)
=
m
a
x
(
f
(
i
−
1
,
j
)
,
f
(
i
,
j
−
1
)
)
+
g
i
f
t
[
i
,
j
]
f(
i
,
j
)
=
m
a
x
(
f
(
i
−
1
,
j
)
,
f
(
i
,
j
−
1
)
)
+
g
i
f
t
[
i
,
j
]
代码
#################面试题47#######################
#礼物的最大价值
def getMaxValue_solution1(values):
if not values:
return 0
rows = len(values)
if not isinstance(values[0], list):
maxValue = sum(values)
return maxValue
else:
cols = len(values[0])
if cols == 1:
maxValue = 0
for row in range(rows):
maxValue += values[row][0]
return maxValue
maxValues = [[0] * cols] * rows
for i in range(rows):
for j in range(cols):
left = 0
up = 0
if i > 0: # i=0 边界
up = maxValues[i - 1][j]
if j > 0:
left = maxValues[i][j - 1]
maxValues[i][j] = max(left, up) + values[i][j]
maxValue = maxValues[rows - 1][cols - 1]
return maxValue
#########优化#############
# 只用一个一维数组来代替二维数组maxValues
# 该数组前面j个数字分别是当前i行前面j个格子礼物的最大价值
# 之后的数字分别保存i-1行，n-j个格子的礼物的最大价值
def getMaxValue_solution2(values):
if not values:
return 0
rows = len(values)
if not isinstance(values[0], list):
maxValue = sum(values)
return maxValue
else:
cols = len(values[0])
if cols == 1:
maxValue = 0
for row in range(rows):
maxValue += values[row][0]
return maxValue
maxValues = [0] * cols
for i in range(rows):
for j in range(cols):
left = 0
up = 0
if i > 0: # i=0 边界
up = maxValues[j]
if j > 0:
left = maxValues[j - 1]
maxValues[j] = max(left, up) + values[i][j]
maxValue = maxValues[cols - 1]
return maxValue
测试
################测试1#################
#功能测试
# 功能测试
# 多行多列的矩阵
values = [[1, 10, 3, 8], [12, 2, 9, 6], [5, 7, 4, 11], [3, 7, 16, 5]]
getMaxValue_solution1(values)
# 一行或一列矩阵
values = [1, 10, 3, 8] # 一行
getMaxValue_solution1(values)
values = [[1], [10], [3], [8]] # 一列
getMaxValue_solution1(values)
# 只有一个数字的矩阵
values = [1]
getMaxValue_solution1(values)
# 特殊输入测试
getMaxValue_solution1(None)
##############优化后测试##########
# 功能测试
# 多行多列的矩阵
values = [[1, 10, 3, 8], [12, 2, 9, 6], [5, 7, 4, 11], [3, 7, 16, 5]]
getMaxValue_solution2(values)
# 一行或一列矩阵
values = [1, 10, 3, 8] # 一行
getMaxValue_solution2(values)
values = [[1], [10], [3], [8]] # 一列
getMaxValue_solution2(values)
# 只有一个数字的矩阵
values = [1]
getMaxValue_solution2(values)
# 特殊输入测试
getMaxValue_solution2(None)
面试题48：最长不含重复字符的子字符串
题目：最长不含重复字符的子字符串
请从字符串中找出一个最长的不包含重复字符的子字符串，计算最长该子字符串的长度.假设字符串中只包含’a’ ~ ‘z’ 的字符
`输入： 字符串’arabcacfr’
输出：最长的不包含重复字符的子字符串是'acfr'
思路
动态规划
f
(
i
)
f
(
i
)
:以第i个字符为结尾的不包含重复字符的子字符串的最长长度
(1) 第i个字符之前没出现过，
f
(
i
)
=
f
(
i
−
1
)
+
1
f
(
i
)
=
f
(
i
−
1
)
+
1
(2) 第i个字符之前已经出现过。
计算第i个字符和它上次出现在字符串中的位置的距离，d
1、
d
<
=
f
(
i
−
1
)
d
<=
f
(
i
−
1
)
第i个字符上次出现在f(i-1)对应的最长子字符串之中
f
(
i
)
=
d
f
(
i
)
=
d
2、
d
>
f
(
i
−
1
)
d
>
f
(
i
−
1
)
第i个字符上次出现在f(i-1)对应的最长子字符串之前
f
(
i
)
=
f
(
i
−
1
)
+
1
f
(
i
)
=
f
(
i
−
1
)
+
1
代码
#################面试题48#######################
#最长不含重复字符的子字符串
def longestSubstringWithoutDuplication(string):
curLength = 0
maxLength = 0
position = [-1] * 26 # 26个字母
if not string:
return None
for i in range(len(string)):
preIndex = position[ord(string[i]) - ord('a')]
if preIndex < 0 or i - preIndex > curLength:
curLength += 1
else:
if curLength > maxLength:
maxLength = curLength
curLength = i - preIndex
position[ord(string[i]) - ord('a')] = i
if curLength > maxLength:
maxLength = curLength
return maxLength
测试
################测试1#################
# 功能测试
# 包含多个字符的字符串
longestSubstringWithoutDuplication('arabcacfr')
# 只有一个字符的字符串
longestSubstringWithoutDuplication('a')
# 所有字符都相同的字符串
longestSubstringWithoutDuplication('aaaa')
# 特殊输入测试
longestSubstringWithoutDuplication(None)