主題

LeetCode - 1893. Check if All the Integers in a Range Are Covered 解題心得

Not In My Back Yard | 2021-09-23 00:00:03 | 巴幣 0 | 人氣 32

題目連結:


題目意譯:
你被給定一個 2D 整數陣列 ranges 以及兩整數 left 和 right 。每個 range[i] = [starti, endi] 代表著一個範圍於 starti 於 endi 之間(含端點)。

回傳真(True)如果於閉區間 [left, right] 中的每個整數都至少涵蓋於 ranges 的其中一個區間中;反之,回傳假(False)。

一個整數 x 涵蓋於區間 ranges[i] = [starti, endi] 如果 starti ≦ x ≦ endi 。

限制:
1 ≦ ranges.length ≦ 50
1 ≦ starti ≦ endi ≦ 50
1 ≦ left ≦ right ≦ 50



範例測資:
範例 1:
輸入: ranges = [[1,2],[3,4],[5,6]], left = 2, right = 5
輸出: true
解釋: 介於 2 到 5 之間的每個整數都有被涵蓋:
- 2 涵蓋於第一個範圍。.
- 3 和 4 涵蓋於第二個範圍。
- 5 涵蓋於第三個範圍。

範例 2:
輸入: ranges = [[1,10],[10,20]], left = 21, right = 21
輸出: false
解釋: 21 沒有涵蓋於任何範圍中。


解題思維:
因為本題的數字相當地小,因此用一個布林陣列表示每個數字有沒有被涵蓋。然後把 ranges 中每個範圍 ranges[i] = [starti, endi] 中的所有數字都設為「有被涵蓋」。

接著檢查 [left, right] 是否都是「有被涵蓋」即可。




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

創作回應

更多創作