ETH官方钱包

前往
大廳
主題

LeetCode - 2146. K Highest Ranked Items Within a Price Range 解題心得

Not In My Back Yard | 2022-08-28 12:00:08 | 巴幣 10 | 人氣 174

題目連結:


題目意譯:
你被給定一個索引值從 0 開始的大小為 m × n 之二維陣列 grid,其代表著一間店鋪中物品的分布地圖。grid 中的不同整數代表著以下事物:
0 代表著一道你無法通過的牆壁。
1 代表著一個你可以自由通行的格子。
其他正整數代表著該格子中擁有的物品之價格。同時,你也可以在這些格子中來去自如。

在相鄰的格子之間移動需要花費「一步」。

你同時也被給定整數陣列 pricing 和 start,其中 pricing = [low, high] 和 start = [row, col] 代表著你一開始位於 (row, col) 這個位置且只對價格位於 [low, high] 這個範圍(含端點)中的物品感興趣。其後,你又再被給定一整數 k。

你好奇價格位於給定範圍中的前 k 個最高級之物品所在的位置。級別之分級是以下列第一個不同的條件來決定的:
距離,其定義為從 start 到該位置的最短距離之長度(越短距離的有著更高的級別)。
價格(越低價格的有著更高的級別,但是前提是必須位於價格範圍中)。
列號(越小的列號者有著更高的級別)。
行號(越小的行號者有著更高的級別)。

回傳位於價格範圍中的前 k 個最高級之物品,其順序需以它們的級別排序(由高到低)。如果位於價格範圍中少於 k 個可以抵達的物品,則全數回傳即可。

限制:
m == grid.length
n == grid[i].length
1 ≦ m, n ≦ 10 ^ 5
1 ≦ m × n ≦ 10 ^ 5
0 ≦ grid[i][j] ≦ 10 ^ 5
pricing.length == 2
2 ≦ low ≦ high ≦ 10 ^ 5
start.length == 2
0 ≦ row ≦ m - 1
0 ≦ col ≦ n - 1
grid[row][col] > 0
1 ≦ k ≦ m × n



範例測資:
範例 1:
輸入: grid = [[1,2,0,1],[1,3,0,1],[0,2,5,1]], pricing = [2,5], start = [0,0], k = 3
輸出: [[0,1],[1,1],[2,1]]
解釋: 你開始於 (0, 0)。
在範圍為 [2, 5] 下,我們可以拿取位置 (0, 1) 、(1, 1) 、(2, 1) 和 (2, 2) 的物品。
這些物品的級別為以下順序:
- (0,1),其距離為 1。
- (1,1),其距離為 2。
- (2,1),其距離為 3。
- (2,2),其距離為 4。
因此,位於價格範圍中 3 個最高級的物品為 (0, 1) 、 (1, 1) 和 (2, 1)。

範例 2:
輸入: grid = [[1,2,0,1],[1,3,3,1],[0,2,5,1]], pricing = [2,3], start = [2,3], k = 2
輸出: [[2,1],[1,2]]
解釋: 你開始於 (2, 3)。
在範圍為 [2, 3] 下,我們可以拿取位置 (0, 1) 、(1, 1) 、(1, 2) 和 (2, 1) 的物品。
這些物品的級別為以下順序:
- (2,1),其距離為 2、價格為 2。
- (1,2),其距離為 2、價格為 3。
- (1,1),其距離為 3。
- (0,1),其距離為 4。
因此,位於價格範圍中 2 個最高級的物品為 (2, 1) 和 (1, 2)。

範例 3:
輸入: grid = [[1,1,1],[0,0,1],[2,3,4]], pricing = [2,3], start = [0,0], k = 3
輸出: [[2,1],[2,0]]
解釋: 你開始於 (0, 0)。
在範圍為 [2, 3] 下,我們可以拿取位置 (2, 0) 和 (2, 1) 的物品。
這些物品的級別為以下順序:
- (2,1),其距離為 5。
- (2,0),其距離為 6。
因此,位於價格範圍中 2 個最高級的物品為 (2, 0) 和 (2, 1)。
注意到雖然 k = 3,但是在價格範圍中只有 2 個物品可以抵達並拿取。


解題思維:
其實就是把地圖 grid 當作一個迷宮走(如這題),而且我們是從 start = [row, col] 這個位置開始一步一步地擴散到所有我們可以到的物品之位置。將這些位置連同該物品之價格(當然,價格超出範圍的就忽略)以及抵達所需步數(因為我們是用廣度優先搜尋(Breadth First Search,BFS)的精神來走,所以會是最短距離)一起記錄下來。

接著就是根據題意先按照距離小到大排、距離一樣按價格小到大排、價格一樣按列號小到大、最後如果連列號一樣就按照行號小到大去排。排完之後取前 k 個(如果不足 k 個就全取)即可。




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

創作回應

更多創作