2146. 价格范围内最高排名的 K 样物品 - 力扣（LeetCode） (leetcode-cn.com)https://leetcode-cn.com/problems/k-highest-ranked-items-within-a-price-range/

题目描述

 

 

 

 解题思路

核心办法是：BFS+优先队列

第一个思想，就是从起点开始，向四周进行BFS。需要注意的是记录是否访问viewed的数组。

第二个思想，排序，按照BFS的方式遍历之后，先遍历到的层级的点，一定是距离最小的。

那么，就要考虑相同层级的点之间如何排序。这个排序的规则已经由题目规定，按照价格、坐标来排序。排序的关键就是写好优先队列的排序方法。

 解题代码

方法一

import java.util.*;public class Solution5973 {public static void main(String[] args) {int[][] grid = {{1, 2, 0, 1}, {1, 3, 3, 1}, {0, 2, 5, 1}};int[] pricing = {2, 3};int[] start = {2, 3};int k = 2;List<List<Integer>> res = new Solution5973().highestRankedKItems(grid, pricing, start, k);System.out.println(res);}public List<List<Integer>> highestRankedKItems(int[][] grid, int[] pricing, int[] start, int k) {Comparator<int[]> c = new Comparator<int[]>() {@Overridepublic int compare(int[] o1, int[] o2) {int o1x = o1[0];int o1y = o1[1];int o2x = o2[0];int o2y = o2[1];if (grid[o1x][o1y] < grid[o2x][o2y]) {return -1;} else if (grid[o1x][o1y] > grid[o2x][o2y]) {return 1;} else {if (o1x < o2x) {return -1;} else if (o1x > o2x) {return 1;} else {return o1y - o2y;}}}};List<List<Integer>> res = new ArrayList<>();int grid_x = grid.length;int grid_y = grid[0].length;int low = pricing[0];int high = pricing[1];// 定义BFS的观察路径boolean[][] viewed = new boolean[grid_x][grid_y];// 定义queueLinkedList<int[]> queue = new LinkedList<>();queue.add(start);while (!queue.isEmpty()) {int size = queue.size();PriorityQueue<int[]> priorityQueue = new PriorityQueue<>(c);for (int i = 0; i < size; i++) {int[] s = queue.poll();int x = s[0];int y = s[1];//处理当前点if (x >= 0 && x <= grid_x && y >= 0 && y <= grid_y &&!viewed[x][y] && grid[x][y] != 0) {queue.offer(new int[]{x, y});viewed[x][y] = true;if (grid[x][y] >= low && grid[x][y] <= high) {priorityQueue.add(new int[]{x, y});}// 扩展当前点的周围4个点if (x - 1 >= 0 && !viewed[x - 1][y] && grid[x - 1][y] != 0) {queue.offer(new int[]{x - 1, y});}if (x + 1 < grid_x && !viewed[x + 1][y] && grid[x + 1][y] != 0) {queue.offer(new int[]{x + 1, y});}if (y - 1 >= 0 && !viewed[x][y - 1] && grid[x][y - 1] != 0) {queue.offer(new int[]{x, y - 1});}if (y + 1 < grid_y && !viewed[x][y + 1] && grid[x][y + 1] != 0) {queue.offer(new int[]{x, y + 1});}}}//从优先队列中取数字while (!priorityQueue.isEmpty()) {int[] r = priorityQueue.poll();ArrayList<Integer> arrayList = new ArrayList<>();arrayList.add(r[0]);arrayList.add(r[1]);res.add(arrayList);if (res.size() == k) {return res;}}}return res;}}

方法二

public class Solution5973_2 {public static void main(String[] args) {int[][] grid = {{1, 2, 0, 1}, {1, 3, 3, 1}, {0, 2, 5, 1}};int[] pricing = {2, 3};int[] start = {2, 3};int k = 2;List<List<Integer>> res = new Solution5973_2().highestRankedKItems(grid, pricing, start, k);System.out.println(res);}public List<List<Integer>> highestRankedKItems(int[][] grid, int[] pricing, int[] start, int k) {Comparator<int[]> c = new Comparator<int[]>() {@Overridepublic int compare(int[] o1, int[] o2) {int o1x = o1[0];int o1y = o1[1];int o2x = o2[0];int o2y = o2[1];if (grid[o1x][o1y] < grid[o2x][o2y]) {return -1;} else if (grid[o1x][o1y] > grid[o2x][o2y]) {return 1;} else {if (o1x < o2x) {return -1;} else if (o1x > o2x) {return 1;} else {return o1y - o2y;}}}};List<List<Integer>> res = new ArrayList<>();int grid_x = grid.length;int grid_y = grid[0].length;LinkedList<int[]> queue = new LinkedList<>();boolean[][] viewed = new boolean[grid_x][grid_y];viewed[start[0]][start[1]] = true;if (grid[start[0]][start[1]] != 0) {queue.add(start);}if (grid[start[0]][start[1]] <= pricing[1] && grid[start[0]][start[1]] >= pricing[0]) {ArrayList<Integer> arrayList = new ArrayList<>();arrayList.add(start[0]);arrayList.add(start[1]);res.add(arrayList);if (res.size() == k) {return res;}}int low = pricing[0];int high = pricing[1];while (!queue.isEmpty()) {int size = queue.size();PriorityQueue<int[]> priorityQueue = new PriorityQueue<>(c);for (int i = 0; i < size; i++) {int[] s = queue.poll();int x = s[0];int y = s[1];// 扩展4个点if (x - 1 >= 0 && !viewed[x - 1][y] && grid[x - 1][y] != 0) {queue.offer(new int[]{x - 1, y});viewed[x - 1][y] = true;if (grid[x - 1][y] >= low && grid[x - 1][y] <= high) {priorityQueue.add(new int[]{x - 1, y});}}if (x + 1 < grid_x && !viewed[x + 1][y] && grid[x + 1][y] != 0) {queue.offer(new int[]{x + 1, y});viewed[x + 1][y] = true;if (grid[x + 1][y] >= low && grid[x + 1][y] <= high) {priorityQueue.add(new int[]{x + 1, y});}}if (y - 1 >= 0 && !viewed[x][y - 1] && grid[x][y - 1] != 0) {queue.offer(new int[]{x, y - 1});viewed[x][y - 1] = true;if (grid[x][y - 1] >= low && grid[x][y - 1] <= high) {priorityQueue.add(new int[]{x, y - 1});}}if (y + 1 < grid_y && !viewed[x][y + 1] && grid[x][y + 1] != 0) {queue.offer(new int[]{x, y + 1});viewed[x][y + 1] = true;if (grid[x][y + 1] >= low && grid[x][y + 1] <= high) {priorityQueue.add(new int[]{x, y + 1});}}}//从优先队列中取数字while (!priorityQueue.isEmpty()) {int[] r = priorityQueue.poll();ArrayList<Integer> arrayList = new ArrayList<>();arrayList.add(r[0]);arrayList.add(r[1]);res.add(arrayList);if (res.size() == k) {return res;}}}return res;}}

两个方法的区别就是在判断点的时机

方法一是在点的出队的时候，方法二是在点入队之前。

解题结果