题目

Hercy 想要为购买第一辆车存钱。他 每天 都往力扣银行里存钱。
最开始，他在周一的时候存入 1 块钱。从周二到周日，他每天都比前一天多存入 1 块钱。在接下来每一个周一，他都会比 前一个周一 多存入 1 块钱。
给你 n ，请你返回在第 n 天结束的时候他在力扣银行总共存了多少块钱。
示例 1：

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

示例 2：

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

示例 3：

  1. 输入：n = 20
  2. 输出：96
  3. 解释：第 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

我的结果和解题

image.png
哈哈哈太尴尬了这执行用时和内存消耗..果然算法能力太弱了…

题解

方法一：暴力计算
image.png

class Solution:
    def totalMoney(self, n: int) -> int:
        week, day = 1, 1
        res = 0
        for i in range(n):
            res += week + day - 1
            day += 1
            if day == 8:
                day = 1
                week += 1
        return res

复杂度分析

时间复杂度：O(n)。需要遍历一次 n 得到答案。
空间复杂度：O(1)。只需要用到常数空间。

方法二：等差数列求和进行优化

因为每周七天存的钱之和比上一周多 7 块，因此每周存的钱之和的序列是一个等差数列，我们可以用等差数列求和公式来求出所有完整的周存的钱总和。剩下的天数里，每天存的钱也是一个等差数列，可以用相同的公式进行求和。最后把两者相加可以得到答案。

class Solution:
    def totalMoney(self, n: int) -> int:
        # 所有完整的周存的钱
        weekNumber = n // 7
        firstWeekMoney = (1 + 7) * 7 // 2
        lastWeekMoney = firstWeekMoney + 7 * (weekNumber - 1)
        weekMoney = (firstWeekMoney + lastWeekMoney) * weekNumber // 2
        # 剩下的不能构成一个完整的周的天数里存的钱
        dayNumber = n % 7
        firstDayMoney = 1 + weekNumber
        lastDayMoney = firstDayMoney + dayNumber - 1
        dayMoney = (firstDayMoney + lastDayMoney) * dayNumber // 2
        return weekMoney + dayMoney

复杂度分析

时间复杂度：O(1)。只需要用到常数时间。
空间复杂度：O(1)。只需要用到常数空间。

等差数列公式

等差数列{an}的通项公式为：an=a1+(n-1)d
前n项和公式为：Sn=n*a1+n(n-1)d/2 或 Sn=n(a1+an)/2