Markin_Wang - 个人主页动态

02-26 17:27

# 16:58 import sys import math # dp[i]: 数为i时的最小个数完全平方数 # dp[i] = 1 if i等于某个平方数， else dp[i] = min(dp[i-k] + 1, k 为某个平方数，dp[i]的最小值肯定是dp[i-某个平方数]+1，因此可以把k限制在平方数的个数上 # 为了加速， n = int(input()) candidates = [] m = 1 max_num = 10**4 dp = [max_num+1] * (n+1) while m*m <= n: candidates.append(m*m) ...

0 点赞评论收藏

02-15 00:18

The University of Warwick 算法工程师

题解 | [NOIP2002 普及组] 过河卒 Python3

import sys # 23:28 # 动态规划 dp[i][j]为从 （0，0）到 （i，j)的条数 # 可以从上面来，也可以从左边来 # dp[i+1][j] = dp[i][j] + dp[i+1][j-1]，且 (i,j), (i+1,j-1)不为马能吃掉的点，否则不加该点 n, m, x, y = list(map(int, input().split())) dp = [[0]*(m+1) for _ in range(n+1)] dp[0][0] = 1 # 初始化dp[0][i] for i in range(1,m+1): # 第一行，只能从右边走 ...

0 点赞评论收藏

02-14 12:01

The University of Warwick 算法工程师

题解 | 有多少个不同的二叉搜索树 Python3

import sys # 11:28 # 假设之前的1～i个数，i个节点，有d[i]个不同的构成方法 # 新加i+1, d[i+1] = ? # 1. 因为 i+1 >i, 所以可以直接作为根节点，i的左右搜索树作为i的左子节点 # 2. 因为 i+1 > i, 所以可以直接加在 i的所有搜索树的最右边作为叶子节点 # 3. 也可以在右边的每一层作为某一层有子树的根节点，其他的点则调整为左子树，即其可在右子树的每一个位置 # 对于第3点，需要知道右节点有多少个节点，因此需考虑根节点的值， # 重新考虑如何计算dp[i+1] # 有i个节点的时候，当以j为根节点，左边有1～j...

0 点赞评论收藏

02-08 17:35

The University of Warwick 算法工程师

题解 | 乘积为正数的最长连续子数组 Py3

# 17:11 # 17:33完成 # 假设已知以j结尾最长的满足题意的的子数组长度，求j+1时的长度 # 此时得考虑数组a[j+1]的正负，需要考虑正负情况，因此动态规划的数组也需要考虑正负 # dp1[j]为以j结尾的时候，最长的乘积为正数的子数组长度 # dp2[j]为以j结尾的时候，最长的乘积为负数的子数组长度 n = int(input()) nums = list(map(int,input().split())) dp1 = [0]*(n+1) dp2= [0]*(n+1) for j in range(1,n+1): if nums[j-1] == 0: ...

0 点赞评论收藏

01-07 23:49

The University of Warwick 算法工程师

题解 | 信封嵌套

import sys # 22:51 # 首先简化问题，将信封按照长或者宽从小到大排序 # 那么考虑多少层嵌套，只需要考虑当前信封前，有多少信封的宽（或者长）小于当前信封， # 相当于找最长的递增子序列，假设dp[i]为以信封i为结尾的嵌套层数， # dp[i] = max(dp[0~i-1]中满足width 小于当前信封的dp[j] +1) from collections import defaultdict n = int(input()) letters = [] for _ in range(n): letter = list(map(int,input(...

0 点赞评论收藏

01-07 10:40

The University of Warwick 算法工程师

题解 | 环形数组的连续子数组最大和

import sys # 9:55 # 两种情况 # 1 最大值不过环，按正常线性数组来求 # 2， 最大值过环，这个连续过环的数组的和，等于整个数组的和减去这个环头和尾的和，相当于最大的过环连续子数组和，等于整个数组的和， # 减去线性里连续的子数组的最小和。 # 特殊情况 (1) 如果数组全为负数，要求非空，那么此时最大值为max(nums) # (2) 如果数组全为正数，此时最大值为整体和，这个可以处理，主要需要处理一下情况（1） n = int(input()) nums = list(map(int, input().split())) total = sum(nums) ...

0 点赞评论收藏

01-06 23:17

The University of Warwick 算法工程师

题解 | 连续子数组的最大乘积

import sys # 6:13 # dp[i][j]为子数组i~j的乘积，dp[i][j]=dp[i][j-1]*nums[j] # 直接用超内存，其实因为dp[i][j]的更新和i没关系，就可以改为1维的dp[j]为当前i到j的值 # 最后发现还是运行超时,检查剪枝策略 # (1) 当当前max_v>0并且nums[i-1]>0的时候，这个分枝可以剪掉，因为缺少乘一个正整数肯定会使max_v减小 # 还是超时 # 重新考虑问题 # 假设 dp[i]为以i结尾的最大连续子数组乘积 # 讨论形成最大值的情况，最大值为max_v，当下一个num为正数的时候，最大值为max_...

0 点赞评论收藏

01-04 22:57

The University of Warwick 算法工程师

题解 | 打家劫舍(二)

import sys # 22:30 # 和打家劫舍不同的是环形 # 分两种情况，如果第一家偷，那么最后一家不能偷，最大的为dp1(n-1) # 如过第一家不偷，最大的为dp2(n),分为两种情况dp # 第一家偷, 第二家不能偷，相当于从第三家开始dp + 第一家的钱 # 第一家不偷，相当于从第二家开始dp n = int(input()) money = list(map(int, input().split())) dp1 = [0] * (n+1) # 第一家偷, 第二家不能偷，相当于从第三家开始dp dp2 = [0] * (n+2) # 第一家不偷，相当于从第二家开始dp ...

0 点赞评论收藏

2024-12-30 22:40

The University of Warwick 算法工程师

题解 | 删除相邻数字的最大分数

import sys # 分析： 当从小到达处理数字的时候， 计算当数组包含 0～i，考虑到数字i的时候，其只和i-1和i-2有关 # 即，当数组只包含0~i个数的时候的最高分dp[i],其最高分要么是我选择了第i个数，要么没选 # 如果选择了第i个数 dp[i] = dp[i-2] + i * count[i], 因为选了i，所以i-1不能选，和i-2有关 # 如果没选第i个数，dp[i] = dp[i-1], 并且因为选择数有得分，即dp[i]肯定>dp[i-2]，所以保证最优子结构 n = int(input()) nums = list(map(int,input().s...

0 点赞评论收藏

2024-12-28 23:24

The University of Warwick 算法工程师

题解 | 循环汉诺塔

import sys # 14:44 # 1. 分解子问题，还是分为挪底部（最后一块）和顶部（前n-1)块 # 2. A-->B的时候，先把前n-1块从A挪到B，再从B挪到C，再把底部挪到B，再把顶部从C挪到A再挪到B # 注意，顶部A-->C, 和最后C-->A的步数一样，都是把n-1挪两个盘 # 因此 AB(N) = 2 AC(N-1) + 1 # 3. A-->C的时候，先把顶部挪到B在挪到C,即AC(N-1), 底部A挪到B，一步，再把顶部从C挪到A，即挪一个盘=AB(N-1)，再把底部从B挪到C，一个步骤， 再把顶部从A挪到C，即AC(N-1) # AC(...

0 点赞评论收藏

2024-12-28 07:01

The University of Warwick 算法工程师

题解 | 汉诺塔问题

# # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param n int整型 # @return string字符串一维数组 # class Solution: def getSolution(self , n: int) -> List[str]: # write code here # 21:57 def solver(n, source,target,through): if n == 0: return [] ...

0 点赞评论收藏

2024-12-25 00:34

The University of Warwick 算法工程师

题解 | 相差不超过k的最多数 Python3

import sys # 本题相当于先排序，然后两个指针滑动窗口找左右指针范围内最多的数 # 当 right-left >k 的时候，滑动左，否则滑动右 n, k = list(map(int, input().split())) nums = list(map(int, input().split())) nums.sort() left, right = 0, 0 max_len = 0 while right<n: if nums[right] - nums[left] > k: max_len = max(max_len, righ...

0 点赞评论收藏

2024-12-24 06:14

The University of Warwick 算法工程师

题解 | 【模板】哈夫曼编码

import sys # 用优先级队列 # 超时，用例过7/10 # 估计最用dfs生成树，边合并边生成encoding应该能过 class Node: def __init__(self,weight=None,val=None) -> None: self.weight = weight self.val = val self.left = None self.right = None from queue import PriorityQueue n = int(input()) q = Priority...

0 点赞评论收藏

2024-12-15 09:30

The University of Warwick 算法工程师

题解 | 【模板】01背包 Python3

import sys # 0/1背包 # 动态规划，dp1[i][j]为考虑到第i个物品，容量为j的背包的最大价值，不考虑背包是否装满 # dp2[i][j] 考虑装满的情况下 # dp[i][j] = max(dp[i][j-v]+w,dp[i-1][j]) # dp1 和 dp2主要是初始化条件不同和一些遍历逻辑 # dp2要考虑到完全背包，比如主要结果dp2[i][j]是表示考虑到所有所有物品后完全背包的最大价值 # 那么 dp2[i][j] = max(dp2[i][j-v]+w,dp2[i-1][j]), 但是可能dp2[i][j-v]并没有一个完全背包解，因此需要有一个值来表征，用...

0 点赞评论收藏

2024-12-30 22:41

已编辑

The University of Warwick 算法工程师

题解 | [NOIP2001]装箱问题 Python3

import sys # 0-1 背包问题，动态规划解决 # 总共n个物品，V的容量 # 对于每个物品，在考虑最大容量的结果的时候，只有它被装进去，或者没有被装进去这两种情况 # 首先明确一点，对于n个物品V的容量的最后的解决方案，是可以由n2个物品V2的容量推导而来，n2<n, V2<V # dp[i][j] 表示当考虑第i个物品的时候，最大容量为j的时候最大的体积 # dp[i][j] = max(dp[i-1][j-v]+v, dp[i-1][j]) # dp[i-1[j-v]表示把物品i放进背包的情况 V = int(input()) n = int(input())...

0 点赞评论收藏

创作者周榜

关注他的用户也关注了：