5801.消灭怪物的最大数量
难度：中等
题目：
你正在玩一款电子游戏，在游戏中你需要保护城市免受怪物侵袭。给你一个 下标从 0 开始 且长度为 n 的整数数组 dist ，其中 dist[i] 是第 i 个怪物与城市的 初始距离（单位：米）。
怪物以 恒定 的速度走向城市。给你一个长度为 n 的整数数组 speed 表示每个怪物的速度，其中 speed[i] 是第 i 个怪物的速度（单位：米/分）。
怪物从 第 0 分钟 时开始移动。你有一把武器，并可以 选择 在每一分钟的开始时使用，包括第 0 分钟。但是你无法在一分钟的中间使用武器。这种武器威力惊人，一次可以消灭任一还活着的怪物。
一旦任一怪物到达城市，你就输掉了这场游戏。如果某个怪物 恰 在某一分钟开始时到达城市，这会被视为 输掉 游戏，在你可以使用武器之前，游戏就会结束。
返回在你输掉游戏前可以消灭的怪物的 最大 数量。如果你可以在所有怪物到达城市前将它们全部消灭，返回 n 。
提示：
- n == dist.length == speed.length
- 1 <= n <= 10 ^ 5
- 1 <= dist[i], speed[i] <= 10 ^ 5
示例：
示例 1：
输入：dist = [1,3,4], speed = [1,1,1]
输出：3
解释：
第 0 分钟开始时，怪物的距离是 [1,3,4]，你消灭了第一个怪物。
第 1 分钟开始时，怪物的距离是 [X,2,3]，你没有消灭任何怪物。
第 2 分钟开始时，怪物的距离是 [X,1,2]，你消灭了第二个怪物。
第 3 分钟开始时，怪物的距离是 [X,X,1]，你消灭了第三个怪物。
所有 3 个怪物都可以被消灭。
示例 2：
输入：dist = [1,1,2,3], speed = [1,1,1,1]
输出：1
解释：
第 0 分钟开始时，怪物的距离是 [1,1,2,3]，你消灭了第一个怪物。
第 1 分钟开始时，怪物的距离是 [X,0,1,2]，你输掉了游戏。
你只能消灭 1 个怪物。
示例 3：
输入：dist = [3,2,4], speed = [5,3,2]
输出：1
解释：
第 0 分钟开始时，怪物的距离是 [3,2,4]，你消灭了第一个怪物。
第 1 分钟开始时，怪物的距离是 [X,0,2]，你输掉了游戏。
你只能消灭 1 个怪物。
分析：
这道题的第一个示例，简直恶心人，什么玩意儿么！其实就是一道很简单的贪心题目
- 我们将dist每个子数组除以speed，得到每个怪物还有几分钟到达城市。
- 然后将dist进行排序
- 之后从index = 1开始循环遍历dist，当剩余时间小于等于index时表示无法消灭怪物，此时退出即可。
解题：
class Solution:
def eliminateMaximum(self, dist, speed):
if not dist:
return 0
ln = len(dist)
for i in range(ln):
dist[i] = dist[i] / speed[i]
dist.sort()
for i in range(1, ln):
if dist[i] <= i:
return i
return ln
5802.统计好数字的数目
难度：中等
题目
我们称一个数字字符串是 好数字 当它满足（下标从 0 开始）偶数 下标处的数字为 偶数 且 奇数 下标处的数字为 质数 （2，3，5 或 7）。
比方说，"2582" 是好数字，因为偶数下标处的数字（2 和 8）是偶数且奇数下标处的数字（5 和 2）为质数。但 "3245" 不是 好数字，因为 3 在偶数下标处但不是偶数。
给你一个整数 n ，请你返回长度为 n 且为好数字的数字字符串 总数 。由于答案可能会很大，请你将它对 109 + 7 取余后返回 。
一个 数字字符串 是每一位都由 0 到 9 组成的字符串，且可能包含前导 0 。
提示：
- 1 <= n <= 10 ^ 15
示例
示例 1：
输入：n = 1
输出：5
解释：长度为 1 的好数字包括 "0"，"2"，"4"，"6"，"8" 。
示例 2：
输入：n = 4
输出：400
示例 3：
输入：n = 50
输出：564908303
分析
这道题目读起来有些绕，比赛的时候没睡醒，反复看了几遍，以为要计算N以内的的质数，仔细看才发现想错了，耽误很多时间。
数字N代表一个长度为N的字符串数字，其中字符串数字是可以包含前导零的。
那么N位的字符串的每一位数字又分为了两种场景：
- 偶数位需要为偶数 [0, 2, 4, 6, 8]
- 奇数位需要为质数 [2, 3, 5, 7] (10以内的质数)
下来我们就需要考虑N的奇偶性了：- 当N为偶数时，奇偶各占一半
- 当为奇数时，由于下标从0开始，所以奇数为N // 2,偶数位 N // 2 + 1
上面的内容都考虑完全后，咱们可以得到最终的计算公式：
5 ** 偶数位和 * 4 ** 奇数位和
但是这里需要注意N的取值范围是 1 <= n <= 10 ^ 15,
如果正常计算 5 ** 10 ^ 15 // 2,那你会哭死的...这里需要用到快速幂。
然而，很惭愧，学Python这么久了，一直觉得pow是一个无用的函数，直到今天打脸了。
但比较开心的一点是，刷题的目的，不就是为了查漏补缺吗？
pow函数解析
pow() 方法返回 x ** y（x的y次方） 的值。
pow(x, y[, z])
函数是计算x的y次方，如果z在存在，则再对结果进行取模，其结果等效于pow(x,y) %z
注意：pow() 通过内置的方法直接调用，内置方法会把参数作为整型，
而 math 模块则会把参数转换为 float。
import math
math.pow( x, y )
至于快速幂的实现，这里就不细说了，大家可以参照下50题。
50.Pow(x, n)
可气的当时这道题暴力做的，所以 今天你今天偷的懒，总有一天要补回来！
所以，气不气，三行代码的解题，因为知识点学习不到位，导致不会就是不会...
解题
class Solution:
def countGoodNumbers(self, n):
mod = 10 ** 9 + 7
i,j = divmod(n,2)
return pow(5,i + j,mod) * pow(4,i,mod) % mod
欢迎关注我的公众号: 清风Python，带你每日学习Python算法刷题的同时，了解更多python小知识。
我的个人博客：https://qingfengpython.cn
网友评论