朱越峰
朱越峰
全部文章
分类
题解(13)
归档
标签
去牛客网
登录
/
注册
朱越峰的博客
全部文章
(共9篇)
题解 | #打家劫舍(三)#
本题会有大规模测试用例,用深度优先搜索可能会超出迭代次数上限。也许可以通过手动指定迭代次数上限来解决这个问题,但我选择维护动态规划列表。 本质上和前两道打家劫舍没有什么区别,难度虚高了。 n = int(input()) pts = list(map(int, input().split())) ...
Python3
深度优先搜索
二叉树
动态规划
2022-04-21
0
328
题解 | #取数游戏#
对区间动态规划。 n = int(input()) aa = list(map(int, input().split())) bb = list(map(int, input().split()))[::-1] # dp[i][j]是这一族问题中输入为aa[i:j+1]和bb[i:j+1]时的解。...
Python3
动态规划
2022-04-21
0
279
题解 | #过河#
对python来说,本题真正的难点在于l很大时如何不超时。 为此需要运用数论做一些粗浅的算法优化。 实际上还有很多能抠的细节没有抠,因为在python上的运行速度已经比较令人满意了,再去深究一些不能改变运算量数量级的地方意义不大。 注:由irises1412提供的答案应该是错误的,它通不过示例自测。...
Python3
动态规划
数学
2022-04-20
0
404
题解 | #正则表达式匹配#
二维动态规划。 def match(p, s): m, n = len(p), len(s) # 初始化边界: # 1、dp[0][0] = True,空模式空字符串,匹配成功; # 2、dp[0][j] = False,空模式无法匹配非空字符串; # 3、d...
Python3
动态规划
2022-04-19
0
376
题解 | #最少的完全平方数#
当做一般动态规划来做。 tar = int(input()) # dp[i] 是和为i+1所需的完全平方数的最小数量 dp = [float('inf') for _ in range(tar)] # 初始化:记录完全平方数的位置 for i in range(int(tar**0.5)): ...
Python3
动态规划
2022-04-17
0
272
题解 | #打家劫舍(二)#
分治法:将问题分为两种可能的情形处理,收集分类信息和处理每一种情形都只可以利用打家劫舍(一)的算法完成。 n = int(input()) nums = list(map(int, input().strip().split())) # 处理输入极短的情况,避免指针越界 if len(nums) ...
Python3
动态规划
2022-04-12
0
265
题解 | #最大子矩阵#
描述: 已知矩阵的大小定义为矩阵中所有元素的和。给定一个矩阵,你的任务是找到最大的非空(大小至少是1 * 1)子矩阵。 输入描述: 输入是一个N * N的矩阵。输入的第一行给出N (0 < N <= 100)。 再后面的若干行中,依次(首先从左到右给出第一行的N个整数,再从左到右给出第二...
Python3
动态规划
2022-03-23
0
276
题解 | #连续子数组的最大乘积#
以下用maxnum表示以x结尾的连续子数组中乘积最大者。minnum同理。用res持续maxnum迭代过程中取到的最大值。 以x.next结尾的连续子数组的乘积除以x.next一定是1或者某个以x结尾的连续子数组的乘积,从而在minnum和maxnum之间并且不等式的两个端点都可以取到。因此,新的m...
Python3
动态规划
2022-03-22
10
492
题解 | #密码截取# (最长对称连续子串)
分最长对称子串的长度是奇数(k)还是偶数(l)处理。 ss = input() l,i = 2,0 # l=2n while (0<=i) and (i< len(ss)-l+1): if ss[i:i+l] == ss[i:i+l][::-1]: l += ...
Python3
动态规划
2022-03-13
0
198