前往
大廳
主題

LeetCode - 0491. Non-decreasing Subsequences 解題心得

Not In My Back Yard | 2023-12-23 12:00:01 | 巴幣 0 | 人氣 44

題目連結:


題目意譯:
給定一整數陣列 nums,回傳給定陣列中所有可能的相異且至少有兩個元素之非遞減子序列。你可以按照任意順序回傳。

限制:
1 ≦ nums.length ≦ 15
-100 ≦ nums[i] ≦ 100



範例測資:
範例 1:
輸入: nums = [4,6,7,7]
輸出: [[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]

範例 2:
輸入: nums = [4,4,3,2,1]
輸出: [[4,4]]


解題思維:
因為 nums 的長度最大為 15,所以我們可以使用 0 ~ 2 ^ (nums.length) - 1 代表著每一個可能的子序列。例如說十進位的 5 寫成二進位為 101,所以可以代表某個子序列有著 nums[0] 、 nums[2] 等等。

因此就掃過所有子序列判斷是否為非遞減。如果是則加進答案陣列之中。最後便可以得到所有非遞減子序列(記得檢查子序列長度至少應為 2)。




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

創作回應

更多創作