没有合适的资源?快使用搜索试试~ 我知道了~
2_16337341_朱志儒1
需积分: 0 0 下载量 30 浏览量
2022-08-03
15:33:37
上传
评论
收藏 359KB PDF 举报
温馨提示
试读
11页
16337341 朱志儒After robbing those houses on that street, the thief has found himse
资源详情
资源评论
资源推荐
算法设计与应用基础: Homework No 2
16337341 朱志儒
1. House Robber II (#213)
After robbing those houses on that street, the thief has found himself a new place for his thievery so
that he will not get too much attention. This time, all houses at this place are arranged in a circle.
That means the first house is the neighbor of the last one. Meanwhile, the security system for these
houses remain the same as for those in the previous street.
Given a list of non-negative integers representing the amount of money of each house, determine
the maximum amount of money you can rob tonight without alerting the police.
解题思路:若列表长度为 0 则输出 0,若长度为 1 则输出第一个元素,若长度为 2 则输出第
一个和第二个中的最大的那个,若长度大于 2 则声明两个列表,第一个列表存储 0 到 n-2 最
大和,第二个列表存储 1 到 n-1 最大的和,最后返回两个列表最后一个元素中最大的那个。
代码如下:
class Solution:
def rob(self, nums):
n = len(nums)
result1 = [i for i in range(0, n - 1)]
result2 = result1[:]
if n == 0:
return 0
elif n == 1:
return nums[0]
elif n == 2:
return max(nums)
else:
result1[0] = nums[0]
result1[1] = max(nums[0], nums[1])
for i in range(2, n - 1):
result1[i] = max(result1[i - 2] + nums[i], result1[i - 1])
result2[0] = nums[1]
result2[1] = max(nums[1], nums[2])
for i in range(3, n):
result2[i-1] = max(result2[i-3] + nums[i], result2[i-2])
return max(result2[-1], result1[-1])
结果:
2. Triangle (#120)
Given a triangle, find the minimum path sum from top to bottom. Each step you may move to
adjacent numbers on the row below.
For example, given the following triangle
[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).
Note: Bonus point if you are able to do this using only O(n) extra space, where n is the total
number of rows in the triangle.
解题思路:构建动态规划数组,保存前一行和当前行符合题目要求的路径和,以自底向上的
方式,最终归一到第
0 行的 0 元素位置。那么动态规划数组的第 0 个元素即为最小路径和。
代码如下:
class Solution:
def minimumTotal(self, triangle):
"""
:type triangle: List[List[int]]
:rtype: int
"""
result = triangle[-1]
for i in range(len(triangle) - 2, -1, -1):
for j in range(len(triangle[i])):
result[j] = min(result[j], result[j + 1]) + triangle[i][j]
return result[0]
结果:
3. Jump Game (#55)
Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Determine if you are able to reach the last index.
For example:
A = [2,3,1,1,4], return true.
A = [3,2,1,0,4], return false.
解题思路:遍历列表,根据列表元素的值递增下标 pos,当 pos >= len(nums) - 1 时,
则返回 true,如果 pos 的增长为 0 时,则返回 false。
代码如下:
class Solution:
def canJump(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
pos = 0
剩余10页未读,继续阅读
内酷少女
- 粉丝: 16
- 资源: 302
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论0