分享一个手机游戏——Coin Pusher
- 更新时间 2026-04-04 23:21:58
楔子
大家好，我是张桃狮。
换了新手机后，我发现有几个游戏不能玩了。
其中就包括我非常喜欢的金币推土机Coin Dozer。
不管新版还是老版，Coin Dozer在我的手机上都无法正常打开。
以往每天在电梯里的时候，我都是靠这款游戏消磨时光。
现在突然玩不了了，心里还有点怅然若失。
我在Google Play上搜索coin，出来一款叫Coin Pusher的推币机游戏，感觉跟Coin Dozer差不多。
安装到手机上打开一看，两款游戏的玩法果然大差不差，但是还是有一些不同。
Coin Pusher的道具多了一个金币塔，每次推倒金币塔都会特别爽快。
目前我已经打到49级，Coin Pusher的其他玩法可以参考游戏全破计划——Coin Dozer，我就不赘述了。
现在看看自己8年前写的东东，感觉都有点臊得慌。
时间真是一把杀猪刀，将一个爱玩游戏的小镇青年，变成了一个职场摸鱼油腻中年。
我预测这篇发布以后，又会有人在微信公众号后台找我要下载地址。
所以我用夸克网盘给大家分享了Coin Pusher的APK，地址如下。
链接：https://pan.quark.cn/s/10eec38e5ff6
大家自己去下载吧。
咱们闲话少数，继续力扣刷题学Python。
力扣LCP 18. 早餐组合
小扣在秋日市集选择了一家早餐摊位，一维整型数组 staple 中记录了每种主食的价格，一维整型数组 drinks 中记录了每种饮料的价格。小扣的计划选择一份主食和一款饮料，且花费不超过 x 元。请返回小扣共有多少种购买方案。
注意：答案需要以 1e9 + 7 (1000000007) 为底取模，如：计算初始结果为：1000000008，请返回 1
示例 1：
输入：staple = [10,20,5], drinks = [5,5,2], x = 15
输出：6
解释：小扣有 6 种购买方案，所选主食与所选饮料在数组中对应的下标分别是： 第 1 种方案：staple[0] + drinks[0] = 10 + 5 = 15； 第 2 种方案：staple[0] + drinks[1] = 10 + 5 = 15； 第 3 种方案：staple[0] + drinks[2] = 10 + 2 = 12； 第 4 种方案：staple[2] + drinks[0] = 5 + 5 = 10； 第 5 种方案：staple[2] + drinks[1] = 5 + 5 = 10； 第 6 种方案：staple[2] + drinks[2] = 5 + 2 = 7。
示例 2：
输入：staple = [2,1,1], drinks = [8,9,5,1], x = 9
输出：8
解释：小扣有 8 种购买方案，所选主食与所选饮料在数组中对应的下标分别是： 第 1 种方案：staple[0] + drinks[2] = 2 + 5 = 7； 第 2 种方案：staple[0] + drinks[3] = 2 + 1 = 3； 第 3 种方案：staple[1] + drinks[0] = 1 + 8 = 9； 第 4 种方案：staple[1] + drinks[2] = 1 + 5 = 6； 第 5 种方案：staple[1] + drinks[3] = 1 + 1 = 2； 第 6 种方案：staple[2] + drinks[0] = 1 + 8 = 9； 第 7 种方案：staple[2] + drinks[2] = 1 + 5 = 6； 第 8 种方案：staple[2] + drinks[3] = 1 + 1 = 2；
提示：
1 <= staple.length <=
1 <= drinks.length <=
1 <= staple[i],drinks[i] <=
1 <= x <= 2*
我的思路
最简单的暴力循环解法。
class Solution: def breakfastNumber(self, staple: List[int], drinks: List[int], x: int) -> int: ret=0 for s in staple: for d in drinks: if s + d <= x: ret += 1 return ret力扣提交超时了：（
豆包说这个代码的时间复杂度O()，空间复杂度O(1)。
豆包给出的代码，我做了点修改
from typing import Listimport bisectclass Solution: def breakfastNumber(self, staple: List[int], drinks: List[int], x: int) -> int: MOD = 10**9 + 7 # 题目要求取模！ staple.sort() drinks.sort() res = 0 for s in staple: # 剩下最多能买多少钱的饮料 remain = x - s if remain <= 0: break # 二分查找：有多少饮料 <= remain cnt = bisect.bisect_right(drinks, remain) res += cnt return res % MOD力扣提交通过，时间复杂度 O(n log n)，空间复杂度 O(1)。
题目要求取模，是为了防止数据溢出。
python其实没有这个问题。
bisect是Python自带的二分查找模块，专门给已排好序的列表用。
bisect自带4个核心函数。
假设列表 a 已按升序排列。
bisect.bisect_left(a, x)
查找 x 在 a 中的最左插入点。
若 x 已存在，返回第一个 x 的位置。
bisect.bisect_right(a, x)（别名 bisect）
查找 x 在 a 中的最右插入点。
若 x 已存在，返回最后一个 x 之后的位置。
bisect.insort_left(a, x)
在 bisect_left 找到的位置，就地插入 x。
bisect.insort_right(a, x)（别名 insort）
在 bisect_right 找到的位置，就地插入 x。
这道题没有官方题解，以下代码来自网友。
力扣网友ZZ.H的代码
class Solution: def breakfastNumber(self, staple: List[int], drinks: List[int], x: int) -> int: ans = 0 # 开一个数组，下标代表主食价格，值是该价格的主食数量 arr = [0 for i in range(x+1)] # 统计每种主食价格出现次数 for sta in staple: if sta < x: # 主食本身就 >=x 就不可能搭配 arr[sta] += 1 # 求前缀和：arr[i] 表示价格 <=i 的主食总数 for i in range(2, x): arr[i] += arr[i-1] # 对每个饮料，求能搭配的主食数量 for drink in drinks: lt = x - drink # 主食最多只能花 lt 元 if lt <= 0: continue ans += arr[lt] # 直接加上前缀和 return ans % (10 ** 9 + 7)力扣提交通过，时间复杂度O (N+M+X)，空间复杂度O (X)。
求前缀和的操作让我大跌眼镜，我喜欢这种野路子方法。
对于这道题，这个代码是最快的。
有人说如果X是一个非常大的数，这个代码并不一定是最优解。
但是X如果无限大，这道题就没有意义了呀。
我都这么有钱了，还不能想吃啥吃啥，想喝啥喝啥吗？还用的着这么抠抠索索的吗？
豆包给出的双指针最优解
from typing import Listclass Solution: def breakfastNumber(self, staple: List[int], drinks: List[int], x: int) -> int: MOD = 10**9 + 7 staple.sort() drinks.sort() n = len(staple) m = len(drinks) res = 0 # 双指针：主食从左往右，饮料从右往左 j = m - 1 for i in range(n): # 找到当前主食能搭配的最大饮料价格 while j >= 0 and staple[i] + drinks[j] > x: j -= 1 # 剩下 0~j 都能配 res += j + 1 return res % MOD力扣提交通过，时间复杂度O (N log N + M log M)，空间复杂度O (log N + log M)。
这个代码一看就是学院派风格。
相比力扣网友ZZ.H的代码，可以无视X的大小是最大的优点。
我曾经想过通过排序来降低时间复杂度，不过我没有想到双指针，残念。
我是个编程爱好者，小白级别的，如果你跟我一样希望通过力扣刷题，学习各种奇妙的算法，可以关注我，大家一起学习。
