1716 计算力扣银行的钱

发表于

这是我参与11月更文挑战的第24天，活动详情查看：2021最后一次更文挑战

  1. 计算力扣银行的钱

Hercy 想要为购买第一辆车存钱。他 每天 都往力扣银行里存钱。

最开始，他在周一的时候存入 1 块钱。从周二到周日，他每天都比前一天多存入 1 块钱。在接下来每一个周一，他都会比 前一个周一 多存入 1 块钱。

给你 n ，请你返回在第 n 天结束的时候他在力扣银行总共存了多少块钱。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
ini复制代码示例 1：

输入：n = 4
输出：10
解释：第 4 天后，总额为 1 + 2 + 3 + 4 = 10 。

示例 2：

输入：n = 10
输出：37
解释：第 10 天后，总额为 (1 + 2 + 3 + 4 + 5 + 6 + 7) + (2 + 3 + 4) = 37 。注意到第二个星期一，Hercy 存入 2 块钱。

示例 3：

输入：n = 20
输出：96
解释：第 20 天后，总额为 (1 + 2 + 3 + 4 + 5 + 6 + 7) + (2 + 3 + 4 + 5 + 6 + 7 + 8) + (3 + 4 + 5 + 6 + 7 + 8) = 96 。

提示：

1 <= n <= 1000

解题思路

直接模拟存钱的过程

  1. 在周一的时候存入 1 块钱。从周二到周日，每天都比前一天多存入 1 块钱。
  2. 下一周的周一需要比上一周的周一存入更多的钱，从周二到周日，还是保持每天都比前一天多存入 1 块钱的规律
  3. 直到第n天，返回存入的总和

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
cpp复制代码class Solution {
public:
    int totalMoney(int n) {
        int pre=0,sum=0,cur=0;
        for (int i = 0; i < n; ++i) {
            if (i%7==0)
            {
              pre++;
              cur=pre;
            }else cur++;
            sum+=cur;
        }
        return sum;
    }
};

优化思路

  1. 对于每一周，一定会存下28元，因为：1+2+3+4+5+6+7=28，所以当有r个完整的一周时，会存下 28 * n 元；
  2. 从第二周开始，每一周都会比前面一周多7元；
  3. 第r周，会多存下 7*(1+2+3+..+r-1)元。根据等差数列的求和公式，可推导出：7r(r - 1)/2 元；
  4. 而最后不能构成完整一周的那几天也是利用相同的思想，可以拆分为 1+2+…mod 和 r * mod。
1
2
3
4
5
6
7
cpp复制代码class Solution {
public:
    int totalMoney(int n) {
        int r=n/7,mod=n%7;
        return (28 * r)+ (7 * r * (r - 1) / 2)+ (r * mod)+ (mod * (mod + 1) / 2);
    }
};

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%