2021 年 1 月 15 日 LeetCode No.1716 计算力扣银行的钱

原贴地址：https://dawnmagnet.github.io/algorithm-station/docs/2022/1/15

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

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

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

示例 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

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/calculate-money-in-leetcode-bank著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路分析

这道题其实主要是一道数学题，首先我们要完成一个函数，函数在数学上就是指给一些输入，返回一些输出，这样的形式就叫函数，而在这道题中，我们要计算一个由输入n确定的一个数字序列的和，并且作为返回值，那么我们来分析一下这个数字序列的特征。

拿题目中的示例来看

$(1+2+3+4+5+6+7)+(2+3+4+5+6+7+8)+(3+4+5+6+7+8)=96$

在这个示例中，存在明眼人都能看出来的两个部分：

• 一部分是$(1+2+3+4+5+6+7)+(2+3+4+5+6+7+8)$这些组成的，一组七个，非常规整

• 还有一部分是$(3+4+5+6+7+8)$这样的，没有完整的七个，这一部分只有可能出现在序列的末尾

• 根据题意我们能够知道，完整的 7 个是一个星期，不完整的 7 个只有可能出现在序列的末尾

那么我们将其分解成两个部分来进行运算：

• 对于第一部分，我们将其整体进行求和，也就是七个一组我们先算一下，发现很有规律，计算的结果为$28,28+7,28+14,28+21,...$
  

• 对于第二部分，我们也可以发现它是一个等差序列，但其中第一个数字需要用 n 来计算得到。我们假设$n=k\ast 7+b$，也就是 k 组完整的周加上 b 个单独的末尾天数。那么第二个等差序列可以用如下字母来表示：$k+1,k+2,k+3,...,k+b$
  

可以看出，前一个序列和后一个序列都是等差数列，那么可以使用等差数列的公式进行快速的计算，不需要循环。

PS：不会等差数列公式的同学可以自学一下初中数学

那么我们将其计算一下：

• 第一个等差数列的首项是$28$，末项是$21+7\ast k$，项数是$k$
  

• 第二个等差数列的首项是$k+1$，末项是$k+b$，项数是$b$
  

带入公式即可得到最后的答案表达式为$(49+k\ast 7)\ast k/2+(2\ast k+b+1)\ast b/2$，有的时候你也不用非得化简，比如不需要把$k$乘进去，因为这样计算机反倒多算几步

Rust 代码

impl Solution {    pub fn total_money(n: i32) -> i32 {        let k = n / 7;        let b = n % 7;        (49 + k * 7) * k / 2 + (2 * k + b + 1) * b / 2    }}