计算力扣银行的钱

难度: Easy

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

Submission

运行时间: 20 ms

内存: 15.9 MB

class Solution:
    def totalMoney(self, n: int) -> int:
        weeks = n // 7  # Number of full weeks
        days = n % 7  # Remaining days after full weeks
        
        # Calculate the total money for full weeks
        total_money = 0
        base = 1
        for _ in range(weeks):
            total_money += sum(range(base, base + 7))
            base += 1
        
        # Calculate the total money for remaining days
        total_money += sum(range(base, base + days))
        
        return total_money

solution = Solution()
n = 10
result = solution.totalMoney(n)
print(result)  # Output: 37

Explain

题解首先通过整除和取余操作将天数分解为完整的周数和剩余的天数。对于每一完整的周，采用循环来计算每周存款的总额，每周的存款起始金额比上一周多1块钱。计算完所有完整的周之后，再计算剩余天数的存款总额。通过累加每周的存款和剩余天数的存款得到最终的总金额。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def totalMoney(self, n: int) -> int:
        weeks = n // 7  # 计算完整周数
        days = n % 7  # 计算除完整周外的剩余天数

        # 初始化总金额为0
        total_money = 0
        base = 1  # 每周的起始存款金额
        for _ in range(weeks):
            # 计算一周的存款总额，并累加到总金额
            total_money += sum(range(base, base + 7))
            base += 1  # 下一周的起始存款比上一周多1块钱

        # 计算剩余天数的存款总额
        total_money += sum(range(base, base + days))

        return total_money

solution = Solution()
n = 10
result = solution.totalMoney(n)
print(result)  # 输出: 37

Explore

使用循环处理每周的存款是因为每周的起始存款金额递增，不是一个固定值。虽然可以通过数学公式直接计算每周的存款总额（即等差数列求和公式），每周的存款总额可以表达为 `28 + 7*(base-1)`，其中 `base` 是该周的起始存款金额。但是，计算多周的总存款仍然需要一种方式来累加每周的结果，即便这可以通过更复杂的数学公式（如求和公式的嵌套应用）完成，实现可能不如直接使用循环直观或易于理解。

`base`变量代表每周开始的第一天的存款金额。其值在每周增加1，因此在计算完所有完整周后，`base`的值为初始值1加上完整周数`weeks`。例如，如果有3周，则在计算剩余天数的存款时，`base`将开始于4。

是的，这种使用方式已经考虑了所有边界情况。`range(base, base + days)`在`days`为0时，结果是一个空范围，因此`sum(range(base, base + days))`将返回0，这意味着没有额外的存款金额被添加，适用于剩余天数为0的情况。

解决方案适用于从非常小到非常大的`n`值。对于小值，如`n=1`，算法迅速通过直接计算少量数据解决问题。对于大值，如`n=10000`，虽然算法仍有效，但其效率主要受限于循环的使用，因为必须对每一周进行迭代和计算。虽然这种方法的时间复杂度是线性的，对于非常大的输入，执行时间会随之增长，但在实际应用中通常是可接受的。