一魚多吃 用 巴斯卡三角的觀念，來解 三角數列和 Find Triangular Sum Leetcode #2221

Michael Dziedzic on Unsplash

這題的題目在這裡

題目會給定我們一個陣列，並且定義了一種三角形合併的操作。

當下這一排相鄰的兩項相加，對mod 10取餘數，會成為下一排的對應項，一直反覆操作，直到剩下一個元素為止。

要求我們返回最後一層的答案。

測試範例:

Example 1:

Input: nums = [1,2,3,4,5]
Output: 8
Explanation:
The above diagram depicts the process from which we obtain the triangular sum of the array.

Example 2:

Input: nums = [5]
Output: 5
Explanation:
Since there is only one element in nums, the triangular sum is the value of that element itself.

約束條件:

Constraints:

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

演算法:

除了傳統的模擬法，逐項相加以外，其實可以觀察相加的規律。

每一個項數 對應的貢獻次數，也就是係數，剛好就是前面我們學過巴斯卡三角的係數。

巴斯卡三角係數的計算過程

為了方便教學起見，我們最後再一起取 mod 10，答案仍然保持不變，是等價的。

以[1, 2, 3, 4, 5] 為例子:

[1, 2, 3, 4, ,5]

-> [1+2, 2+3, 3+4, 4+5]

#1貢獻一次，2貢獻兩次，3貢獻兩次，4貢獻兩次, 5貢獻一次

-> [1+2+2+3, 2+3+3+4, 3+4+4+5]

#1貢獻一次，2貢獻三次，3貢獻四次，4貢獻三次, 5貢獻一次

-> [1+2+2+3 + 2+3+3+4, 2+3+3+4 + 3+4+4+5]

#1貢獻一次，2貢獻四次，3貢獻六次，4貢獻四次, 5貢獻一次

-> [1+2+2+3 + 2+3+3+4 + 2+3+3+4 + 3+4+4+5]

#1貢獻一次，2貢獻四次，3貢獻六次，4貢獻四次, 5貢獻一次

已經剩下最後一個數了，直接相加得到48

48再取mod10 得到 8

最後答案就是 8

從計算過程中可以發現，每一個項數 對應的貢獻次數，也就是係數，剛好就是前面我們學過巴斯卡三角的係數。

這個範例[1,2,3,4,5]，陣列長度n=5

剛好對應到 n-1這一層的二項式係數

C(4, 0), C(4,1), C(4, 2), C(4, 3), C(4, 4) = 1, 4, 6, 4, 1

呼應到 (注意粗體的部分)

#1貢獻 一次，2貢獻 四次，3貢獻 六次，4貢獻 四次, 5貢獻 一次

結論:

陣列初始長度若為n，則每一項乘上C(n-1, i), i = 0 ~ n-1，再相加，取mod10，就是三角數列最後一層的數字，也是最終答案。

程式碼:

class Solution:
　def triangularSum(self, nums: List[int]) -> int:
　　
　　n = len(nums)
　　return sum( [ ( x * math.comb(n-1, i) )  for i, x in enumerate(nums) ] ) % 10

時間複雜度:

O(n) 逐項乘上二項式的係數，再相加，陣列總長度為O(n)

空間複雜度:

O(n) 會用到一個臨時的陣列buffer去做計算，長度為O(n)

學完這一題，記得回過頭去複習 巴斯卡三角I 和 巴斯卡三角II，背後的觀念和原理都是相通的喔。

Reference:

[1] Python O( n^2 ) by simulation [w/ Comment] - Find Triangular Sum of an Array - LeetCode