Huahua’s Tech Road

花花酱 LeetCode 1333. Filter Restaurants by Vegan-Friendly, Price and Distance

By zxi on January 26, 2020

Given the array restaurants where restaurants[i] = [id_i, rating_i, veganFriendly_i, price_i, distance_i]. You have to filter the restaurants using three filters.

The veganFriendly filter will be either true (meaning you should only include restaurants with veganFriendly_i 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 veganFriendly_i 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^4
restaurants[i].length == 5
1 <= id_i, rating_i, price_i, distance_i<= 10^5
1 <= maxPrice, maxDistance <= 10^5
veganFriendly_i and veganFriendly are 0 or 1.
All id_i are distinct.

Solution

Time complexity: O(nlogn)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

vector<int> filterRestaurants(vector<vector<int>>& restaurants, int veganFriendly, int maxPrice, int maxDistance) {

vector<pair<int, int>> rs; // <rating, id>

for (auto& r : restaurants)

if ((!veganFriendly || veganFriendly && r[2]) && r[3] <= maxPrice && r[4] <= maxDistance)

rs.emplace_back(r[1], r[0]);

sort(rbegin(rs), rend(rs));

vector<int> ans;

for (const auto& r : rs) ans.push_back(r.second);

return ans;

}

};

花花酱 LeetCode 1332. Remove Palindromic Subsequences

By zxi on January 26, 2020

Given a string s consisting only of letters 'a' and 'b'. In a single step you can remove one palindromic subsequence from s.

Return the minimum number of steps to make the given string empty.

A string is a subsequence of a given string, if it is generated by deleting some characters of a given string without changing its order.

A string is called palindrome if is one that reads the same backward as well as forward.

Example 1:

Input: s = "ababa"
Output: 1
Explanation: String is already palindrome

Example 2:

Input: s = "abb"
Output: 2
Explanation: "abb" -> "bb" -> "". 
Remove palindromic subsequence "a" then "bb".

Example 3:

Input: s = "baabb"
Output: 2
Explanation: "baabb" -> "b" -> "". 
Remove palindromic subsequence "baab" then "b".

Example 4:

Input: s = ""
Output: 0

Constraints:

0 <= s.length <= 1000
s only consists of letters ‘a’ and ‘b’

Solution: Math

if s is empty => 0 step
if s is a palindrome => 1 step
Otherwise, 2 steps…
1. delete all the as
2. delete all the bs

Time complexity: O(n)
Space complexity: O(n) / O(1)

C++

// Author: Huahua

class Solution {

public:

int removePalindromeSub(string s) {

if (s.empty()) return 0;

if (s == string(rbegin(s), rend(s))) return 1;

return 2;

}

};

花花酱 LeetCode 1331. Rank Transform of an Array

By zxi on January 26, 2020

Given an array of integers arr, replace each element with its rank.

The rank represents how large the element is. The rank has the following rules:

Rank is an integer starting from 1.
The larger the element, the larger the rank. If two elements are equal, their rank must be the same.
Rank should be as small as possible.

Example 1:

Input: arr = [40,10,20,30]
Output: [4,1,2,3]
Explanation: 40 is the largest element. 10 is the smallest. 20 is the second smallest. 30 is the third smallest.

Example 2:

Input: arr = [100,100,100]
Output: [1,1,1]
Explanation: Same elements share the same rank.

Example 3:

Input: arr = [37,12,28,9,100,56,80,5,12]
Output: [5,3,4,2,8,6,7,1,3]

Constraints:

0 <= arr.length <= 10⁵
-10⁹ <= arr[i] <= 10⁹

Solution: Sorting + HashTable

Time complexity: O(nlogn)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

vector<int> arrayRankTransform(vector<int>& arr) {

set<int> s(begin(arr), end(arr));

unordered_map<int, int> m;

int r = 0;

for (const int v : s) m[v] = ++r;

vector<int> ans(arr.size());

for (int i = 0; i < arr.size(); ++i)

ans[i] = m[arr[i]];

return ans;

}

};

花花酱 LeetCode 1330. Reverse Subarray To Maximize Array Value

By zxi on January 26, 2020

You are given an integer array nums. The value of this array is defined as the sum of |nums[i]-nums[i+1]| for all 0 <= i < nums.length-1.

You are allowed to select any subarray of the given array and reverse it. You can perform this operation only once.

Find maximum possible value of the final array.

Example 1:

Input: nums = [2,3,1,5,4]
Output: 10
Explanation: By reversing the subarray [3,1,5] the array becomes [2,5,1,3,4] whose value is 10.

Example 2:

Input: nums = [2,4,9,24,2,1,10]
Output: 68

Constraints:

1 <= nums.length <= 3*10^4
-10^5 <= nums[i] <= 10^5

Solution: Greedy

Time complexity: O(n)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int maxValueAfterReverse(vector<int>& nums) {

const int n = nums.size();

int sum = 0;

int gain = 0;

int hi = INT_MIN;

int lo = INT_MAX;

for (int i = 0; i < n - 1; ++i) {

int n1 = nums[i];

int n2 = nums[i + 1];

sum += abs(n1 - n2);

gain = max({gain,

abs(nums[0] - n2) - abs(n1 - n2),

abs(nums[n - 1] - n1) - abs(n1 - n2)});

hi = max(hi, min(n1, n2));

lo = min(lo, max(n1, n2));

}

return sum + max(gain, (hi - lo) * 2);

}

};

花花酱 LeetCode 1329. Sort the Matrix Diagonally

By zxi on January 26, 2020

Given a m * n matrix mat of integers, sort it diagonally in ascending order from the top-left to the bottom-right then return the sorted array.

Example 1:

Input: mat = [[3,3,1,1],[2,2,1,2],[1,1,1,2]]
Output: [[1,1,1,1],[1,2,2,2],[1,2,3,3]]

Constraints:

m == mat.length
n == mat[i].length
1 <= m, n <= 100
1 <= mat[i][j] <= 100

Solution: HashTable

Collect each diagonal’s (keyed by i – j) elements into an array and sort it separately.
If we offset the key by n, e.g. i – j + n, we can use an array instead of a hashtable.

Time complexity: O(m*n + (m+n) * (m+n) * log(m + n))) = (n^2*logn)
Space complexity: O(m*n)

C++

// Author: Huahua

class Solution {

public:

vector<vector<int>> diagonalSort(vector<vector<int>>& mat) {

const int m = mat.size();

const int n = mat[0].size();

vector<deque<int>> qs(m + n);

for (int i = 0; i < m; ++i)

for (int j = 0; j < n; ++j)

qs[i - j + n].push_back(mat[i][j]);

for (auto& q : qs)

sort(begin(q), end(q));

for (int i = 0; i < m; ++i)

for (int j = 0; j < n; ++j) {

mat[i][j] = qs[i - j + n].front();

qs[i - j + n].pop_front();

}

return mat;

}

};

Huahua's Tech Road

花花酱 LeetCode 1333. Filter Restaurants by Vegan-Friendly, Price and Distance

Solution

C++

花花酱 LeetCode 1332. Remove Palindromic Subsequences

Solution: Math

C++

花花酱 LeetCode 1331. Rank Transform of an Array

Solution: Sorting + HashTable

C++

花花酱 LeetCode 1330. Reverse Subarray To Maximize Array Value

Solution: Greedy

C++

花花酱 LeetCode 1329. Sort the Matrix Diagonally

Solution: HashTable

C++