→ WindSpread: !? 你也 04/21 23:41
→ leafff: 之前也發過 不過文已經被系統清掉了 04/21 23:46
https://leetcode.com/problems/count-the-hidden-sequences/description
2145. Count the Hidden Sequences
給定一個長度為n的數組differences，代表長度為n+1的隱藏數組兩元素之間的差。
再給定兩個整數upper與lower，分別代表該隱藏數組元素的上限與下限值。
返回隱藏數組的組合數目，如果不存在可滿足要求的隱藏數組，則返回0。
--
解題思路：
以隱藏數組的第一項為原點，令其為0，再根據differences所給的各元素之差，算出各元素與第一項的差。
再求各元素的最大值與最小值，其差距就是隱藏數組的上下限差距。
如果該差距大於upper與lower的差距，則不存在隱藏數組，否則答案就是upper與lower的差距減去該差距再加1。
--
Python code:
class Solution:
def numberOfArrays(self, differences: List[int], lower: int, upper: int) -
> int:
nums = [0] * (len(differences) + 1)
for i, dif in enumerate(differences):
nums[i+1] = nums[i] + dif
mx, mn = max(nums), min(nums)
return 0 if mx-mn > upper-lower else (upper-lower) - (mx-mn) + 1
--
https://i.imgur.com/AhNjoAu.jpeg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.163.166.20 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1745250005.A.556.html