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

解题思路

这道题需要理解存钱的规律：每周的存钱模式是固定的，但每个新周一的起始金额会比前一周的周一多1元。

解法一：数学公式（推荐）

我们可以将总天数分解为完整的周数和剩余天数：

  • 完整周数：weeks = n / 7
  • 剩余天数：days = n % 7

对于完整的周：

  • 第一周存钱：1+2+3+4+5+6+7 = 28
  • 第二周存钱：2+3+4+5+6+7+8 = 35 = 28+7
  • 第k周存钱：28+(k-1)*7

完整周的总和可以用等差数列求和公式计算。

对于剩余的天数，需要计算从第(weeks+1)个周一开始的前days天的存钱总和。

解法二：模拟

直接模拟存钱过程，跟踪当前是周几和当前周一的起始金额，逐天计算存钱数量。这种方法简单直观但效率较低。

数学公式解法时间复杂度更优，是推荐解法。

代码实现

class Solution {
public:
    int totalMoney(int n) {
        int weeks = n / 7;
        int days = n % 7;
        
        // 完整周的总和：weeks个等差数列的和
        // 第k周的和为 28 + (k-1) * 7
        int completeWeeks = weeks * 28 + weeks * (weeks - 1) * 7 / 2;
        
        // 剩余天数的和：第(weeks+1)周的前days天
        int remainingDays = days * (weeks + 1) + days * (days - 1) / 2;
        
        return completeWeeks + remainingDays;
    }
};

class Solution:
    def totalMoney(self, n: int) -> int:
        weeks = n // 7
        days = n % 7
        
        # 完整周的总和
        complete_weeks = weeks * 28 + weeks * (weeks - 1) * 7 // 2
        
        # 剩余天数的和
        remaining_days = days * (weeks + 1) + days * (days - 1) // 2
        
        return complete_weeks + remaining_days

public class Solution {
    public int TotalMoney(int n) {
        int weeks = n / 7;
        int days = n % 7;
        
        // 完整周的总和
        int completeWeeks = weeks * 28 + weeks * (weeks - 1) * 7 / 2;
        
        // 剩余天数的和
        int remainingDays = days * (weeks + 1) + days * (days - 1) / 2;
        
        return completeWeeks + remainingDays;
    }
}

var totalMoney = function(n) {
    const weeks = Math.floor(n / 7);
    const days = n % 7;
    
    // 完整周的总和
    const completeWeeks = weeks * 28 + weeks * (weeks - 1) * 7 / 2;
    
    // 剩余天数的和
    const remainingDays = days * (weeks + 1) + days * (days - 1) / 2;
    
    return completeWeeks + remainingDays;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度数学公式解法模拟解法
时间复杂度O(1)O(n)
空间复杂度O(1)O(1)

相关题目