朱越峰
朱越峰
全部文章
分类
题解(13)
归档
标签
去牛客网
登录
/
注册
朱越峰的博客
全部文章
(共13篇)
题解 | #[ZJOI2010]COUNT 数字计数#
思路不是特别难以想到,但是计算流程繁琐,指针的数量大、位置易混淆。 考验的主要是耐心和细心。 def foo(a): """计算从0到a(含0和a)的所有整数中,各个数码出现的次数。""" k = len(str(a)) digs = list(map(int, list(s...
Python3
数学
2022-04-26
0
284
题解 | #打家劫舍(三)#
本题会有大规模测试用例,用深度优先搜索可能会超出迭代次数上限。也许可以通过手动指定迭代次数上限来解决这个问题,但我选择维护动态规划列表。 本质上和前两道打家劫舍没有什么区别,难度虚高了。 n = int(input()) pts = list(map(int, input().split())) ...
Python3
深度优先搜索
二叉树
动态规划
2022-04-21
0
315
题解 | #取数游戏#
对区间动态规划。 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
267
题解 | #过河#
对python来说,本题真正的难点在于l很大时如何不超时。 为此需要运用数论做一些粗浅的算法优化。 实际上还有很多能抠的细节没有抠,因为在python上的运行速度已经比较令人满意了,再去深究一些不能改变运算量数量级的地方意义不大。 注:由irises1412提供的答案应该是错误的,它通不过示例自测。...
Python3
动态规划
数学
2022-04-20
0
377
题解 | #正则表达式匹配#
二维动态规划。 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
350
题解 | #最少的完全平方数#
当做一般动态规划来做。 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
252
题解 | #求最小公倍数#
用辗转相除法计算最大公约数,再计算最小公倍数。 while True: try: a,b = map(int,input().split()) prod=a*b while min(a,b)!=0: if a < ...
Python3
数学
2022-04-16
0
194
题解 | #打家劫舍(二)#
分治法:将问题分为两种可能的情形处理,收集分类信息和处理每一种情形都只可以利用打家劫舍(一)的算法完成。 n = int(input()) nums = list(map(int, input().strip().split())) # 处理输入极短的情况,避免指针越界 if len(nums) ...
Python3
动态规划
2022-04-12
0
255
题解 | #最大子矩阵#
描述: 已知矩阵的大小定义为矩阵中所有元素的和。给定一个矩阵,你的任务是找到最大的非空(大小至少是1 * 1)子矩阵。 输入描述: 输入是一个N * N的矩阵。输入的第一行给出N (0 < N <= 100)。 再后面的若干行中,依次(首先从左到右给出第一行的N个整数,再从左到右给出第二...
Python3
动态规划
2022-03-23
0
256
题解 | #乘积为正数的最长连续子数组#
主程序将数组分割成若干个不含0的子数组,从而使的子数组的乘积不会是0. 在分割过程中,为了方便把正数用1表示,负数用0表示。 函数ml意为一个不含0的数组ll的乘积为正数的最长连续子数组点长度max_len。这又可以按ll中有多少负数分成三种情况: Case 1:含有偶数个负数,全部乘起来一定是正数...
Python3
2022-03-22
0
351
首页
上一页
1
2
下一页
末页