LeetCode 筆記 - 3468. Find the Number of Copy Arrays

題目在此 3468. Find the Number of Copy Arrays

給定一個整數陣列 numsbounds, 其中 $bounds[i] = [lower_i, upper_i]$,請找出有多少個不同的整數陣列 original 可以經過某個整數 k 的加法運算後,變成 nums,且每個 original[i] 都在 bounds[i] 的範圍內。

  1. (copy[i] - copy[i - 1]) == (original[i] - original[i - 1]) for 1 <= i <= n - 1.
  2. lower[i] <= original[i] <= upper[i] for 0 <= i <= n - 1.

解題思維

這題的關鍵在於理解 copy 陣列是由 original 陣列加上一個整數 k 所得到的結果。因此,我們可以將問題轉化為尋找一個整數 k,使得對於每個 ioriginal[i] = copy[i] - k 都滿足 bounds[i][0] <= original[i] <= bounds[i][1]

所以簡單來,我們是要找出 k 的上下界。

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
def countArrays(self, original: List[int], bounds: List[List[int]]) -> int:

max_b = inf
min_b = -inf

for i in range(len(original)):
max_b = min(max_b, bounds[i][1] - original[i])
min_b = max(min_b, bounds[i][0] - original[i])

if max_b >= min_b:
return max_b - min_b + 1
return 0

也許你也會想看看