Leetcode70场双周赛-第三题2146. 价格范围内最高排名的 K 样物品

2146. 价格范围内最高排名的 K 样物品 - 力扣(LeetCode) (leetcode-cn.com)Leetcode70场双周赛-第三题2146. 价格范围内最高排名的 K 样物品https://leetcode-cn.com/problems/k-highest-ranked-items-within-a-price-range/

题目描述

 Leetcode70场双周赛-第三题2146. 价格范围内最高排名的 K 样物品

 Leetcode70场双周赛-第三题2146. 价格范围内最高排名的 K 样物品

 Leetcode70场双周赛-第三题2146. 价格范围内最高排名的 K 样物品

 解题思路

核心办法是: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[]>() {
            @Override
            public 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];
        // 定义queue
        LinkedList<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[]>() {
            @Override
            public 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;
    }

}

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

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

解题结果

Leetcode70场双周赛-第三题2146. 价格范围内最高排名的 K 样物品

上一篇:Android Studio出现Wait for build to finish解决办法


下一篇:10、CountDownLatch、CyclicBarrier