前往
大廳
主題

LeetCode - 2601. Prime Subtraction Operation 解題心得

Not In My Back Yard | 2024-05-27 12:00:07 | 巴幣 0 | 人氣 51

題目連結:


題目意譯:
你被給定一個索引值從 0 開始且長度為 n 的整數陣列 nums。

你可以執行以下操作任意次:
    選定一個你尚未挑選過得索引值 i ,並選定一個嚴格小於 nums[i] 的質數 p。然後將 nums[i] 減去 p。

如果你可以用上述的操作讓 nums 變為一個嚴格遞增的陣列,則回傳真(True);反之,回傳假(False)。

一個嚴格遞增的陣列為一個陣列,其中每一個元素都會大於其「前一個」元素。

限制:
1 ≦ nums.length ≦ 1000
1 ≦ nums[i] ≦ 1000
nums.length == n



範例測資:
範例 1:
輸入: nums = [4,9,6,10]
輸出: true
解釋: 在第一次操作中:In the first operation: 選定 i = 0 、 p = 3,接著把 nums[0] 減去 3。此時 nums 變為 [1,9,6,10]。
在第二次操作中:i = 1 、 p = 7,將 nums[1] 減去 7。此時 nums 變為 [1,2,6,10]。
經過第二次操作後,nums 變成嚴格遞增。因此答案為真。

範例 2:
輸入: nums = [6,8,11,12]
輸出: true
解釋: 一開始 nums 就已經是嚴格遞增了,因此我們不需要任何操作。

範例 3:
輸入: nums = [5,8,3]
輸出: false
解釋: 可以證明我們不可能執行任意次操作來使得 nums 變成嚴格遞增。所以答案為假。


解題思維:
可以先建立一個 1 ~ 1000 的質數表。

接著可以看到如果存在某個方式可以讓 nums 變成嚴格遞增且 nums[0] 不變,則必定存在著讓 nums[0] 先根據一次操作變小的另一種令 nums 變為嚴格遞增的方式(其實就是隨便拿一種方式,然後直接將 nums[0] 變小即可)。

因此我們可以直接將 nums[0] 變到盡可能地小(先前建立的質數表這個時候可以加速找質數的過程),然後想辦法處理剩下的數字。

而此時類似的結論也可以套用於 nums[1] 、 nums[2] 等等。也就是說我們可以把 nums[1] 變小,但記得不應小於等於 nums[0](當然,這邊是指已經做過操作之後的 nums[0]。後面同理);同樣地,可以將 nums[2] 變小但不得小於等於 nums[1],以此類推。

而一旦我們發現某個 nums[i] 在套用操作之前就滿足 ≦ nums[i - 1],則代表不存在任何方式將 nums 變成嚴格遞增(可以看到上述的方式會讓所有數字盡可能地小,所以如果這都做不到則不行)。因此回傳假;而如果我們可以一路暢通到結尾,則回傳真。




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

創作回應

更多創作