一魚多吃 用 巴斯卡三角的觀念，來解 三角數列和 Find Triangular Sum Leetcode #2221
題目會給定我們一個陣列，並且定義了一種三角形合併的操作。
當下這一排相鄰的兩項相加，對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 <= 10000 <= 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
你可能也想看
