前往
大廳
主題

LeetCode - 1027. Longest Arithmetic Subsequence 解題心得

Not In My Back Yard | 2024-03-13 12:00:11 | 巴幣 0 | 人氣 39

題目連結:


題目意譯:
給定一個整數陣列 nums,回傳 nums 中最長的等差子序列之長度。

注意到:
一個子序列為可以從另一個陣列藉由刪除其中若干個元素(可以是零個)且不更動剩餘元素的相對順序而得到的一個陣列。
一個子序列 seq 如果滿足 seq[i + 1] - seq[i] 對於所有 i 值都成立(0 ≦ i < seq.length - 1),則該子序列為「等差」的。

限制:
2 ≦ nums.length ≦ 1000
0 ≦ nums[i] ≦ 500



範例測資:
範例 1:
輸入: nums = [3,6,9,12]
輸出: 4
解釋: 整個陣列即為一個等差子序列,其公差為 3。

範例 2:
輸入: nums = [9,4,7,2,10]
輸出: 3
解釋: 最長的子序列為 [4,7,10]。

範例 3:
輸入: nums = [20,1,15,3,10,5,8]
輸出: 4
解釋: 最長的子序列為 [20,15,10,5]。


解題思維:
這題的條件變成是「每一項與前一項之差值恰好為 d」且數值範圍變大(不再限於字母表,而是 0 ~ 500 之間的數字)之後,這便是本題固定公差為 d 時的解法。

而我們接下來只要窮舉出所有可能的公差,然後取所有等差子序列中的最長之長度即是所求。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作