LEETCODE 1333. Filter Restaurants by Vegan-Friendly, Price and Distance 解题思路分析

题目大意:

餐厅过滤器

给你一个餐馆信息数组 restaurants,其中  restaurants[i] = [idi, ratingi, veganFriendlyi, pricei, distancei]。你必须使用以下三个过滤器来过滤这些餐馆信息。

其中素食者友好过滤器 veganFriendly 的值可以为 true 或者 false,如果为 true 就意味着你应该只包括 veganFriendlyi 为 true 的餐馆,为 false 则意味着可以包括任何餐馆。此外,我们还有最大价格 maxPrice 和最大距离 maxDistance 两个过滤器,它们分别考虑餐厅的价格因素和距离因素的最大值。

过滤后返回餐馆的 id,按照 rating 从高到低排序。如果 rating 相同,那么按 id 从高到低排序。简单起见, veganFriendlyi 和 veganFriendly 为 true 时取值为 1,为 false 时,取值为 0 。

示例 1:

输入:restaurants = [[1,4,1,40,10],[2,8,0,50,5],[3,8,1,30,4],[4,10,0,10,3],[5,1,1,15,1]], veganFriendly = 1, maxPrice = 50, maxDistance = 10
输出:[3,1,5] 
解释: 
 这些餐馆为:
 餐馆 1 [id=1, rating=4, veganFriendly=1, price=40, distance=10]
 餐馆 2 [id=2, rating=8, veganFriendly=0, price=50, distance=5]
 餐馆 3 [id=3, rating=8, veganFriendly=1, price=30, distance=4]
 餐馆 4 [id=4, rating=10, veganFriendly=0, price=10, distance=3]
 餐馆 5 [id=5, rating=1, veganFriendly=1, price=15, distance=1] 
 在按照 veganFriendly = 1, maxPrice = 50 和 maxDistance = 10 进行过滤后,我们得到了餐馆 3, 餐馆 1 和 餐馆 5(按评分从高到低排序)。 

示例 2:

输入:restaurants = [[1,4,1,40,10],[2,8,0,50,5],[3,8,1,30,4],[4,10,0,10,3],[5,1,1,15,1]], veganFriendly = 0, maxPrice = 50, maxDistance = 10
输出:[4,3,2,1,5]
解释:餐馆与示例 1 相同,但在 veganFriendly = 0 的过滤条件下,应该考虑所有餐馆。

示例 3:

输入:restaurants = [[1,4,1,40,10],[2,8,0,50,5],[3,8,1,30,4],[4,10,0,10,3],[5,1,1,15,1]], veganFriendly = 0, maxPrice = 30, maxDistance = 3
输出:[4,5]

提示:

  • 1 <= restaurants.length <= 10^4
  • restaurants[i].length == 5
  • 1 <= idi, ratingi, pricei, distancei <= 10^5
  • 1 <= maxPrice, maxDistance <= 10^5
  • veganFriendlyi 和 veganFriendly 的值为 0 或 1 。
  • 所有 idi 各不相同。

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1333

解题思路分析:

本题难度不大,按照题目给出的veganFriendly,maxPrice以及maxDistance三个参数,从数组中将符合条件的数据列出,然后再根据 rating 和id进行排序即可。本题的关键考察点在于排序,java语言中我们可以使用PriorityQueue来存储符合要求的数据,存储时,按照优先rating降序,rating相同时id降序的顺序存储。存储后,PriorityQueue会按照给定的排序规则对数据进行排序,最后再将排序好的数据输出即可。

实现代码:

public List<Integer> filterRestaurants(int[][] restaurants, int veganFriendly, int maxPrice, int maxDistance) {
    // 使用PriorityQueue存储符合条件的数据
    // PriorityQueue的排序规则为优先rating降序,rating相同时id降序
    PriorityQueue<int[]> q =
            new PriorityQueue<>((a,b)->b[1]-a[1]==0?b[0]-a[0]:b[1]-a[1]);
    // 循环每一个餐厅信息
    for(int[] r :restaurants){
        // 将符合条件的加入到Queue
        if((veganFriendly==0||r[2]==1)
           && r[3]<=maxPrice
           && r[4]<=maxDistance){
            q.offer(new int[]{r[0],r[1]});
        }
    }
    // 返回结果
    List<Integer> res = new ArrayList<>();
    // 将queue中排序好的餐厅id加入返回结果
    while(q.size()>0) res.add(q.poll()[0]);
    return res;
}

本题解法执行时间为4ms。

Runtime: 4 ms, faster than 99.69% of Java online submissions for Filter Restaurants by Vegan-Friendly, Price and Distance.

Memory Usage: 50.3 MB, less than 100.00% of Java online submissions for Filter Restaurants by Vegan-Friendly, Price and Distance.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-1333-filter-restaurants-by-vegan-friendly-price-and-distance-解题思路分析/
此条目发表在leetcode分类目录,贴了, , , , 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。