Given the array restaurants where restaurants[i] = [idi, ratingi, veganFriendlyi, pricei, distancei]. You have to filter the restaurants using three filters.
The veganFriendly filter will be either true (meaning you should only include restaurants with veganFriendlyi set to true) or false (meaning you can include any restaurant). In addition, you have the filters maxPrice and maxDistance which are the maximum value for price and distance of restaurants you should consider respectively.
Return the array of restaurant IDs after filtering, ordered by rating from highest to lowest. For restaurants with the same rating, order them by id from highest to lowest. For simplicity veganFriendlyi and veganFriendly take value 1 when it is true, and 0 when it is false.
Example 1:
Input: 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
Output: [3,1,5]
Explanation: The restaurants are:
Restaurant 1 [id=1, rating=4, veganFriendly=1, price=40, distance=10]
Restaurant 2 [id=2, rating=8, veganFriendly=0, price=50, distance=5]
Restaurant 3 [id=3, rating=8, veganFriendly=1, price=30, distance=4]
Restaurant 4 [id=4, rating=10, veganFriendly=0, price=10, distance=3]
Restaurant 5 [id=5, rating=1, veganFriendly=1, price=15, distance=1]
After filter restaurants with veganFriendly = 1, maxPrice = 50 and maxDistance = 10 we have restaurant 3, restaurant 1 and restaurant 5 (ordered by rating from highest to lowest).
Example 2:
Input: 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
Output: [4,3,2,1,5]
Explanation: The restaurants are the same as in example 1, but in this case the filter veganFriendly = 0, therefore all restaurants are considered.
Example 3:
Input: 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
Output: [4,5]
Constraints:
1 <= restaurants.length <= 10^4restaurants[i].length == 51 <= idi, ratingi, pricei, distancei <= 10^51 <= maxPrice, maxDistance <= 10^5veganFriendlyiandveganFriendlyare 0 or 1.- All
idiare distinct.
这道题给了一个餐馆数组，每个餐馆包括一系列信息，id，rating，veganFriendly，price，distance。现在给了一些搜索条件，比如是否素食友好，最大价格，最大距离，然后返回符合要求的餐馆。这其实就是类似 Yelp 的功能啊，这里的素食友好的条件需要特别注意一下，即素食主义者不能去非素食餐馆，而非素食主义者可以去素食餐馆，所以不能简单的对比 veganFriendly。所以当餐馆的 veganFriendly 是1，给定的 veganFriendly 是0的话，就不能选择该餐馆。那么取个反，当餐馆的 veganFriendly 为1，或者给定的 veganFriendly 为0时可以选餐馆，另外餐馆的价格要小于等于最大价格，且餐馆的距离要小于等于最大距离，将符合要求的餐馆选出来放到一个新的数组中。之后就是给这个数组排序，排序的方法就是若 rating 不相等，把大的排前面，若 rating 相等，把 Id 大的放前面即可，参见代码如下：
class Solution {
public:
vector<int> filterRestaurants(vector<vector<int>>& restaurants, int veganFriendly, int maxPrice, int maxDistance) {
vector<int> res;
vector<vector<int>> filtered;
for (auto r : restaurants) {
if ((r[2] != 0 || veganFriendly != 1) && r[3] <= maxPrice && r[4] <= maxDistance) {
filtered.push_back(r);
}
}
sort(filtered.begin(), filtered.end(), [](vector<int>& a, vector<int>& b) {
return (a[1] != b[1]) ? (a[1] > b[1]) : (a[0] > b[0]);
});
for (auto r : filtered) {
res.push_back(r[0]);
}
return res;
}
};
Github 同步地址:
https://github.com/grandyang/leetcode/issues/1333
参考资料：
https://leetcode.com/problems/filter-restaurants-by-vegan-friendly-price-and-distance/
LeetCode All in One 题目讲解汇总(持续更新中...)
标签：Distance,rating,10,Price,veganFriendly,distance,Vegan,price,restaurants From： https://www.cnblogs.com/grandyang/p/17158526.html