佛山网站建设费用,淘宝代运营1个月多少钱,域名注册免费平台,360直播无插件高清足球本期问哥是志在必得#xff0c;这本算法书我已经觊觎许久#xff0c;而之前两次因为种种原因未能如愿。因此#xff0c;问哥这几天花了不少时间#xff0c;把所有之前在每日一练做过的题目重新梳理了一遍。苦心人#xff0c;天不负#xff0c;感谢官方大大#xff01; 第… 本期问哥是志在必得这本算法书我已经觊觎许久而之前两次因为种种原因未能如愿。因此问哥这几天花了不少时间把所有之前在每日一练做过的题目重新梳理了一遍。苦心人天不负感谢官方大大 第一题订班服 小A班级订班服了 可是小A是个小糊涂鬼整错了好多人的衣服的大小。 小A只能自己掏钱包来补钱了。 小A想知道自己至少需要买多少件衣服。 输入描述第一行输入一个整数n。(1n100)表示衣服的数量。 以下n行输入n个尺码。表示订单中衣服的尺码。 接下来n行输入n个尺码。小A订的衣服尺码。 尺码表M,S,L,XL,XLL,XLLL,XLLLL,XLLLLL。 输出描述输出至少需要买多少件衣服。 示例 示例输入 2 XL X M X 输出1分析
简单题。需要 n 件衣服买了 n 件衣服所以只要把需要的 n 件衣服每种尺码的个数减去已购买的衣服相应尺码的个数如果大于0就说明该尺码还需要购买。所以最直接的办法就是用哈希表记录每种尺码的个数然后再逐个检查。
Python已经提供了内置Counter类可以自动生成字典而且支持加减法连逐个检查这一步都省去了直接相减剩下的数字加在一起就是答案。
参考代码
n int(input().strip())
arr1 [input().strip() for _ in range(n)]
arr2 [input().strip() for _ in range(n)]
from collections import Counter
clothes Counter(arr1) - Counter(arr2)
print(sum(clothes.values())) 第二题争抢糖豆 抓糖豆小Q与小K都喜欢吃糖豆。 但是糖豆分两种超甜糖豆和普通糖豆。 现在有w个超甜糖豆和b个普通糖豆。 小Q和小K开始吃糖豆他们决定谁先吃到超甜糖豆谁就获胜。 小K每次吃的时候会捏碎一颗糖豆。 小Q先吃小Q想知道自己获胜的概率。 如果两个人都吃不到超甜糖豆小K获胜。 输入描述输入两个整数w,b。(0w,b1000) 输出描述答案保留9位小数。 示例 示例输入1 3输出0.500000000分析
也是以前考过的老题了。可以用递归或动态规划来做但本题的状态转移不太容易一眼发现所以可能不少人会觉得难。因为问到概率胜率所以本质上还是需要用数学来表达。
以动态规划为例递归容易超时我们用 表示当有 颗超甜糖豆和 颗普通糖豆时自己的胜率。因为先吃到超甜糖豆就获胜了所以自己要想获胜只能分成两种情况
先吃到超甜糖豆概率是 此情况下直接获胜先吃到普通糖豆但是对手也吃到普通糖豆所以游戏继续自己还有获胜的可能。这里有一个特判的情况如果只有一颗普通糖豆而自己先吃到普通糖豆的话无论如何也是输后面自然就不用算了。因此自己和对手都吃到普通糖豆的概率是 。如果一时看不懂可以多琢磨几遍乘号左边是自己吃到普通糖豆的概率右边是自己吃完后对方也吃到普通糖豆的概率看懂了再继续。
如果没有“捏碎糖豆”的操作分析到这就结束了状态转移就是把这两种情况的胜率加在一起方程如下 因为自己和对手总共吃了两颗普通糖豆所以上面第二种情况的概率还要乘以 才是胜率。
如果上面的内容理解了我们再来分析“捏碎糖豆”的情况。
捏碎糖豆也有两种情况
捏碎了普通糖豆。影响不大但是上面的第二种状态要接着乘上捏碎普通糖豆的概率再乘以 。合在一起的胜率就是 。捏碎了超甜糖豆。则二人虽不分胜负理论上自己还存在胜利的可能如果还剩下超甜糖豆的话但是同样地状态转移方程变了胜率变成了 。
这两种捏碎糖豆的情况属于同一决策层级可以加在一起。于是把捏碎糖豆考虑进来得到最终的状态转移方程如下 此外如之前所述还要考虑几个特判的情况
没有超甜糖豆胜率为0不用计算。没有普通糖豆胜率100%。只有一颗普通糖豆胜率为 因为如果自己先吃到普通糖豆必输。
很显然上面第二、三可以合并而第一条可以在初始化的时候把 的时候设置为0。代码如下 参考代码
w, b map(int, input().split())
dp [[0]*(b1) for _ in range(w1)]
for i in range(1, w1):for j in range(b1):if j 1:dp[i][j]i/(ij)else:dp[i][j]i/(ij)j/(ij)*(j-1)/(ij-1)*((j-2)/(ij-2)*dp[i][j-3]i/(ij-2)*dp[i-1][j-2])
print(f{dp[w][b]:.9f})
输出结果的时候要注意题目要求必须保留9位小数空位用0补全所以要设置占位符。 第三题走楼梯 现在有一截楼梯根据你的腿长你一次能走 1 级或 2 级楼梯已知你要走 n 级楼梯才能走到你的目的楼层请实现一个方法计算你走到目的楼层的方案数。 输入描述输入整数n。(1n50) 输出描述输出方案数。 示例 示例输入5输出 8 分析
很明显答案是斐波那契数列。因为一次只能走 1 级或 2 级楼梯所以第 n 级阶梯可以由 n-1 级阶梯走过来也可以由 n-2 级阶梯走过来。如果用函数 表示走上第 n 级阶梯的方案数可得 因为本题 n 范围较小1n50所以使用递归来做应该也没问题。不过更常用的做法是递推也算是斐波那契的模板题了。
参考代码
n int(input().strip())
a b 1
for _ in range(n):a, b b, ab
print(a) 第四题打家劫舍 一个小偷计划偷窃沿街的房屋。每间房内都藏有一定的现金影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统如果两间相邻的房屋在同一晚上被小偷闯入系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组计算不触动警报装置的情况下 一夜之内能够偷窃到的最高金额。 输入描述输入一个正整数n代表房屋的数量(n≤100)接着输入n个非负整数代表每间房屋的现金数量 输出描述小偷能偷取的最大金额。 示例 示例输入4 1 2 3 1输出4分析
力扣原题经典的打家劫舍系列但凡刷过点题的相信都做过。而且这里选取的是该系列最简单的一道动态规划入门题相关题解太多了这里问哥只简单说两句吧。
因为相邻的房屋不能同时被盗所以小偷在当前房屋只有两种选择不偷当前房屋——继承上个房屋可偷取的的最大金额偷当前房屋——上上个房屋可偷取的最大金额因为上个房屋不能偷加上当前房屋的金额而当前房屋可偷取的最大金额就等于这两种选择中较大的金额。
如果用 代表当前房屋可偷取的最大金额 表示当前房屋的金额可用公式表示如下 类似斐波那契数列可以看出 仅由 和 得到 是给定数组所以可以使用滚动数组优化空间换句话说就是只需要额外两个变量循环保存 和 的值即可。
参考代码
n int(input().strip())
arr [int(item) for item in input().strip().split()]
a b 0
for i in arr:a, b b, max(b, ai)
print(b)
