生活随笔
收集整理的這篇文章主要介紹了
LeetCode 2146. 价格范围内最高排名的 K 样物品（BFS）
小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.
文章目錄
1. 題目
給你一個下標從 0 開始的二維整數(shù)數(shù)組 grid ，它的大小為 m x n ，表示一個商店中物品的分布圖。數(shù)組中的整數(shù)含義為：
- 0 表示無法穿越的一堵墻。
- 1 表示可以自由通過的一個空格子。
- 所有其他正整數(shù)表示該格子內(nèi)的一樣物品的價格。你可以自由經(jīng)過這些格子。
從一個格子走到上下左右相鄰格子花費 1 步。
同時給你一個整數(shù)數(shù)組 pricing 和 start ，其中 pricing = [low, high] 且 start = [row, col] ，表示你開始位置為 (row, col) ，同時你只對物品價格在 閉區(qū)間 [low, high] 之內(nèi)的物品感興趣。同時給你一個整數(shù) k 。
你想知道給定范圍 內(nèi) 且 排名最高 的 k 件物品的 位置 。排名按照優(yōu)先級從高到低的以下規(guī)則制定：
- 距離：定義為從 start 到一件物品的最短路徑需要的步數(shù)（較近 距離的排名更高）。
- 價格：較低 價格的物品有更高優(yōu)先級，但只考慮在給定范圍之內(nèi)的價格。
- 行坐標：較小 行坐標的有更高優(yōu)先級。
- 列坐標：較小 列坐標的有更高優(yōu)先級。
請你返回給定價格內(nèi)排名最高的 k 件物品的坐標，將它們按照排名排序后返回。
如果給定價格內(nèi)少于 k 件物品，那么請將它們的坐標 全部 返回。
示例 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
所以，給定價格范圍內(nèi)排名最高的
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
所以，給定價格范圍內(nèi)排名最高的
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
所以，給定價格范圍內(nèi)排名最高的
2 件物品的坐標為
(2,1) 和
(2,0) 。
注意，k
= 3 但給定價格范圍內(nèi)只有
2 件物品。提示：
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
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/k-highest-ranked-items-within-a-price-range
著作權歸領扣網(wǎng)絡所有。商業(yè)轉載請聯(lián)系官方授權，非商業(yè)轉載請注明出處。
2. 解題
- BFS 遍歷 地圖，記錄步數(shù)，價錢，橫縱坐標
- 對答案進行排序輸出
class Solution:from collections
import deque
def highestRankedKItems(self
, grid
: List
[List
[int]], pricing
: List
[int], start
: List
[int], k
: int) -> List
[List
[int]]:m
, n
= len(grid
), len(grid
[0])ans
= []vis
= [[False for _
in range(n
)] for _
in range(m
)]dir = [[1,0],[0,1],[-1,0],[0,-1]]q
= deque
([])q
.append
(start
)vis
[start
[0]][start
[1]] = Truestep
= 0while len(q
):size
= len(q
)for _
in range(size
):x
, y
= q
[0]q
.popleft
()if pricing
[0] <= grid
[x
][y
] <= pricing
[1]:ans
.append
((step
, grid
[x
][y
], x
, y
))if grid
[x
][y
] > 0:for d
in range(4):nx
= x
+dir[d
][0]ny
= y
+dir[d
][1]if nx
>=0 and nx
<m
and ny
>=0 and ny
<n
and not vis
[nx
][ny
]:q
.append
([nx
, ny
])vis
[nx
][ny
] = Truestep
+= 1ans
.sort
(key
=lambda x
: [x
[0],x
[1],x
[2],x
[3]])return [[x
[2],x
[3]] for x
in ans
[:k
]]
1056 ms 53.5 MB Python3
我的CSDN博客地址 https://michael.blog.csdn.net/
長按或掃碼關注我的公眾號（Michael阿明），一起加油、一起學習進步！
總結
以上是生活随笔為你收集整理的LeetCode 2146. 价格范围内最高排名的 K 样物品（BFS）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。
