- 每日一题：LeetCode：1716.计算力扣银行的钱
- 时间：2022-01-15
- 力扣难度：Easy
- 个人难度：Easy
- 算法：模拟、数学
2022-01-15：LeetCode：1716.计算力扣银行的钱
1. 题目描述
题目：原题链接
- Hercy 想要为购买第一辆车存钱。他每天都往力扣银行里存钱。
- 最开始，他在周一的时候存入 1 块钱。从周二到周日，他每天都比前一天多存入 1 块钱。在接下来每一个周一，他都会比前一个周一 多存入 1 块钱。
- 给你 n ，请你返回在第 n 天结束的时候他在力扣银行总共存了多少块钱
输入输出规范
- 输入：整型天数 n
- 输出：存入的总金额
输入输出示例
- 输入：n = 10
- 输出：37
2. 方法一：简单模拟
思路
- 本题要求指定天数后存入的总金额，根据题意可以得知，存钱是每 7 天周期性变化的，对于周一和一周其他六天要分类讨论
- 因为每一周的周二到周日比前一天多存一元，相当于比周一多存 i 元，i 表示是周几，取值范围(1 ~ 6)，注意 0 表示周一
- 对于下个周期的一周，周一存入的前比上个周一多一元，因此对每个周一进行++操作
- 遍历每一天，模拟整个过程
题解：直接模拟
1
2
3
4
5
6
7
8
9
10
11public int totalMoney1(int n) {
int money = 0;
int temp = 0;
for(int i = 0; i < n; i++) {
if(i % 7 == 0){
temp++;
}
money += temp + i % 7;
}
return money;
}复杂度分析：n 是输入的天数
- 时间复杂度：$O(n)$
- 空间复杂度：$O(1)$
3. 方法二：等差数列公式
思路：公式推导
- 因为存钱的规律每七天周期性变化，所以可以根据指定天数关于 7 的除数和余数来计算最终结果，而无需遍历每一天
- 对于多个完整的一周存入的钱，会构成一个等差数列，差值为7
- 对于单独出来的天数存入的钱，也会构成一个等差数列，差值为1
题解：公式推导
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16public int totalMoney(int n) {
int money = 0;
// 完整的周
int money0 = 1;
int week = n / 7;
int money1 = (money0 + 7) * 7 / 2; // 第一周
int moneyn = money1 + 7 * (week - 1); // 最后一周
money += (money1 + moneyn) * week / 2;
// 单独的天
int day = n % 7;
money1 = money0 + week;
moneyn = money1 + day - 1;
money += (money1 + moneyn) * day / 2;
return money;
}复杂度分析：n 是输入的天数
- 时间复杂度：$O(1)$
- 空间复杂度：$O(1)$
本文作者：
Chthollists
发布时间： 2022-01-15 14:18:45
最后更新： 2022-01-21 23:09:05
本文标题： 每日一题:LeetCode:1716.计算力扣银行的钱
本文链接： https://chthollists.github.io/post/3779e90b.html
版权声明： 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可。转载请注明作者和出处！
发布时间： 2022-01-15 14:18:45
最后更新： 2022-01-21 23:09:05
本文标题： 每日一题:LeetCode:1716.计算力扣银行的钱
本文链接： https://chthollists.github.io/post/3779e90b.html
版权声明： 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可。转载请注明作者和出处！
