Medium

题目描述

给你一个下标从 0 开始的整数数组 nums，其中 nums[i] 是 0 到 9 之间的一个数字。

nums 的 三角和 是执行以下操作以后最后剩下元素的值：

  1. nums 初始包含 n 个元素。如果 n == 1 ，结束 操作。否则，创建一个新的下标从 0 开始的长度为 n - 1 的数组 newNums 。
  2. 对于满足 0 <= i < n - 1 的下标 i ，newNums[i] = (nums[i] + nums[i+1]) % 10，其中 % 表示取余运算。
  3. 将 newNums 替换 nums 。
  4. 从步骤 1 开始 重复 整个过程。

请你返回 nums 的三角和。

示例 1：

输入：nums = [1,2,3,4,5]
输出：8
解释：
上述图表描述了获取数组三角和的过程。

示例 2：

输入：nums = [5]
输出：5
解释：
由于 nums 中只有一个元素，三角和为该元素自身。

提示：

  • 1 <= nums.length <= 1000
  • 0 <= nums[i] <= 9

解题思路

这道题要求我们模拟一个三角形化简的过程，每一轮将相邻两个数字相加再对10取模，直到只剩一个数字。

解法一：直接模拟（推荐） 按照题目描述直接模拟整个过程。每一轮创建新数组，计算相邻元素之和的模10值，直到数组长度为1。时间复杂度为O(n²)，空间复杂度为O(n)。

解法二：原地模拟优化 为了节省空间，可以直接在原数组上进行操作。每一轮从左到右更新数组元素，将当前元素替换为它与下一个元素的和模10。这样可以将空间复杂度优化到O(1)。

解法三：数学优化 从数学角度分析，最终结果实际上是原数组各位置元素的线性组合，系数遵循帕斯卡三角形的规律。可以利用组合数学预先计算系数，但考虑到n的范围较小，直接模拟更简单高效。

对于这道题，直接模拟是最直观和实用的解法，代码简洁易懂，性能也完全满足题目要求。

代码实现

class Solution {
public:
    int triangularSum(vector<int>& nums) {
        int n = nums.size();
        while (n > 1) {
            for (int i = 0; i < n - 1; i++) {
                nums[i] = (nums[i] + nums[i + 1]) % 10;
            }
            n--;
        }
        return nums[0];
    }
};

class Solution:
    def triangularSum(self, nums: List[int]) -> int:
        n = len(nums)
        while n > 1:
            for i in range(n - 1):
                nums[i] = (nums[i] + nums[i + 1]) % 10
            n -= 1
        return nums[0]

public class Solution {
    public int TriangularSum(int[] nums) {
        int n = nums.Length;
        while (n > 1) {
            for (int i = 0; i < n - 1; i++) {
                nums[i] = (nums[i] + nums[i + 1]) % 10;
            }
            n--;
        }
        return nums[0];
    }
}

var triangularSum = function(nums) {
    let n = nums.length;
    while (n > 1) {
        for (let i = 0; i < n - 1; i++) {
            nums[i] = (nums[i] + nums[i + 1]) % 10;
        }
        n--;
    }
    return nums[0];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n²)需要进行n-1轮操作，第i轮需要处理n-i个元素
空间复杂度O(1)原地修改数组，只使用常数额外空间

相关题目