Posts tagged as “medium”

花花酱 LeetCode 1409. Queries on a Permutation With Key

By zxi on April 11, 2020

Given the array queries of positive integers between 1 and m, you have to process all queries[i] (from i=0 to i=queries.length-1) according to the following rules:

In the beginning, you have the permutation P=[1,2,3,...,m].
For the current i, find the position of queries[i] in the permutation P (indexing from 0) and then move this at the beginning of the permutation P. Notice that the position of queries[i] in P is the result for queries[i].

Return an array containing the result for the given queries.

Example 1:

Input: queries = [3,1,2,1], m = 5
Output: [2,1,2,1] 
Explanation: The queries are processed as follow: 
For i=0: queries[i]=3, P=[1,2,3,4,5], position of 3 in P is 2, then we move 3 to the beginning of P resulting in P=[3,1,2,4,5]. 
For i=1: queries[i]=1, P=[3,1,2,4,5], position of 1 in P is 1, then we move 1 to the beginning of P resulting in P=[1,3,2,4,5]. 
For i=2: queries[i]=2, P=[1,3,2,4,5], position of 2 in P is 2, then we move 2 to the beginning of P resulting in P=[2,1,3,4,5]. 
For i=3: queries[i]=1, P=[2,1,3,4,5], position of 1 in P is 1, then we move 1 to the beginning of P resulting in P=[1,2,3,4,5]. 
Therefore, the array containing the result is [2,1,2,1].

Example 2:

Input: queries = [4,1,2,2], m = 4
Output: [3,1,2,0]

Example 3:

Input: queries = [7,5,5,8,3], m = 8
Output: [6,5,0,7,5]

Constraints:

1 <= m <= 10^3
1 <= queries.length <= m
1 <= queries[i] <= m

Solution1: Simulation + Hashtable

Use a hashtable to store the location of each key.
For each query q, use h[q] to get the index of q, for each key, if its current index is less than q, increase their indices by 1. (move right). Set h[q] to 0.

Time complexity: O(q*m)
Space complexity: O(m)

C++

class Solution {

public:

vector<int> processQueries(vector<int>& queries, int m) {

vector<int> p(m + 1);

iota(begin(p), end(p), -1);

vector<int> ans;

for (int q : queries) {

ans.push_back(p[q]);

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

if (p[i] < p[q]) ++p[i];

p[q] = 0;

}

return ans;

}

};

Solution 2: Fenwick Tree + HashTable

Time complexity: O(qlogm)
Space complexity: O(m)

C++

// Author: Huahua

class Fenwick {

public:

explicit Fenwick(int n): vals_(n) {}

// sum(A[1~i])

int query(int i) const {

int s = 0;

while (i > 0) {

s += vals_[i];

i -= i & -i;

}

return s;

}

// A[i] += delta

void update(int i, int delta) {

while (i < vals_.size()) {

vals_[i] += delta;

i += i & -i;

}

private:

vector<int> vals_;

};

class Solution {

public:

vector<int> processQueries(vector<int>& queries, int m) {

Fenwick tree(m * 2 + 1);

vector<int> pos(m + 1);

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

tree.update(pos[i] = i + m, 1);

vector<int> ans;

for (int q : queries) {

ans.push_back(tree.query(pos[q] - 1));

tree.update(pos[q], -1); // set to 0.

tree.update(pos[q] = m--, 1); // move to the front.

}

return ans;

}

};

Python3

class Fenwick:

def __init__(self, n):

self.n = n

self.val = [0] * n

def query(self, i):

s = 0

while i > 0:

s += self.val[i]

i -= i & -i

return s

def update(self, i, delta):

while i < self.n:

self.val[i] += delta

i += i & -i

class Solution:

def processQueries(self, queries: List[int], m: int) -> List[int]:

pos = [i + m for i in range(m + 1)]

tree = Fenwick(2 * m + 1)

for i in range(1, m + 1): tree.update(i + m, 1)

ans = []

for q in queries:

ans.append(tree.query(pos[q] - 1))

tree.update(pos[q], -1)

pos[q] = m

m -= 1

tree.update(pos[q], 1)

return ans

花花酱 LeetCode 1405. Longest Happy String

By zxi on April 5, 2020

A string is called happy if it does not have any of the strings 'aaa', 'bbb' or 'ccc' as a substring.

Given three integers a, b and c, return any string s, which satisfies following conditions:

s is happy and longest possible.
s contains at most a occurrences of the letter 'a', at most b occurrences of the letter 'b' and at most c occurrences of the letter 'c'.
s will only contain 'a', 'b' and 'c' letters.

If there is no such string s return the empty string "".

Example 1:

Input: a = 1, b = 1, c = 7
Output: "ccaccbcc"
Explanation: "ccbccacc" would also be a correct answer.

Example 2:

Input: a = 2, b = 2, c = 1
Output: "aabbc"

Example 3:

Input: a = 7, b = 1, c = 0
Output: "aabaa"
Explanation: It's the only correct answer in this case.

Constraints:

0 <= a, b, c <= 100
a + b + c > 0

Solution: Greedy

Put the char with highest frequency first if its consecutive length of that char is < 2
or put one char if any of other two chars has consecutive length of 2.

increase the consecutive length of itself and reset that for other two chars.

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

C++

// Author: Huahua

class Solution {

public:

string longestDiverseString(int a, int b, int c) {

const int total = a + b + c;

vector<int> f{a, b, c};

vector<int> l{0, 0, 0};

string ans;

for (int _ = 0; _ < total; ++_)

for (int i = 0; i < 3; ++i) {

const int j = (i + 1) % 3;

const int k = (i + 2) % 3;

if ((f[i] >= f[j] && f[i] >= f[k] && l[i] != 2)

|| (f[i] > 0 && (l[j] == 2 || l[k] == 2))) {

ans += 'a' + i;

++l[i];

--f[i];

l[j] = l[k] = 0;

break;

}

return ans;

}

};

花花酱 LeetCode 1401. Circle and Rectangle Overlapping

By zxi on April 4, 2020

Given a circle represented as (radius, x_center, y_center) and an axis-aligned rectangle represented as (x1, y1, x2, y2), where (x1, y1) are the coordinates of the bottom-left corner, and (x2, y2) are the coordinates of the top-right corner of the rectangle.

Return True if the circle and rectangle are overlapped otherwise return False.

In other words, check if there are any point (xi, yi) such that belongs to the circle and the rectangle at the same time.

Example 1:

Input: radius = 1, x_center = 0, y_center = 0, x1 = 1, y1 = -1, x2 = 3, y2 = 1
Output: true
Explanation: Circle and rectangle share the point (1,0)

Example 2:

Input: radius = 1, x_center = 0, y_center = 0, x1 = -1, y1 = 0, x2 = 0, y2 = 1
Output: true

Example 3:

Input: radius = 1, x_center = 1, y_center = 1, x1 = -3, y1 = -3, x2 = 3, y2 = 3
Output: true

Example 4:

Input: radius = 1, x_center = 1, y_center = 1, x1 = 1, y1 = -3, x2 = 2, y2 = -1
Output: false

Constraints:

1 <= radius <= 2000
-10^4 <= x_center, y_center, x1, y1, x2, y2 <= 10^4
x1 < x2
y1 < y2

Solution: Geometry

Find the shortest distance from the center to the rectangle, return dist <= radius.

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

C++

// Author: Huahua

class Solution {

public:

bool checkOverlap(int radius, int x_center, int y_center, int x1, int y1, int x2, int y2) {

int dx = x_center - max(x1, min(x2, x_center));

int dy = y_center - max(y1, min(y2, y_center));

return dx * dx + dy * dy <= radius * radius;

}

};

花花酱 LeetCode 1395. Count Number of Teams

By zxi on March 28, 2020

There are n soldiers standing in a line. Each soldier is assigned a unique rating value.

You have to form a team of 3 soldiers amongst them under the following rules:

Choose 3 soldiers with index (i, j, k) with rating (rating[i], rating[j], rating[k]).
A team is valid if: (rating[i] < rating[j] < rating[k]) or (rating[i] > rating[j] > rating[k]) where (0 <= i < j < k < n).

Return the number of teams you can form given the conditions. (soldiers can be part of multiple teams).

Example 1:

Input: rating = [2,5,3,4,1]
Output: 3
Explanation: We can form three teams given the conditions. (2,3,4), (5,4,1), (5,3,1).

Example 2:

Input: rating = [2,1,3]
Output: 0
Explanation: We can't form any team given the conditions.

Example 3:

Input: rating = [1,2,3,4]
Output: 4

Constraints:

n == rating.length
1 <= n <= 200
1 <= rating[i] <= 10^5

Solution 1: Brute Force

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

C++

// Author: Huahua

class Solution {

public:

int numTeams(vector<int>& rating) {

int n = rating.size();

int ans = 0;

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

for (int j = i + 1; j < n; ++j)

for (int k = j + 1; k < n; ++k)

if (rating[i] < rating[j] && rating[j] < rating[k]

|| rating[i] > rating[j] && rating[j] > rating[k])

++ans;

return ans;

}

};

Solution 2: Math

For each soldier j, count how many soldiers on his left has smaller ratings as left[j], count how many soldiers his right side has larger ratings as right[j]

ans = sum(left[j] * right[j] + (j – left[j]) * (n – j – 1 * right[j])

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

C++

// Author: Huahua, 4 ms

class Solution {

public:

int numTeams(vector<int>& rating) {

int n = rating.size();

int ans = 0;

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

int l = 0;

int r = 0;

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

if (rating[i] < rating[j]) ++l;

for (int k = j + 1; k < n; ++k)

if (rating[j] < rating[k]) ++r;

ans += (l * r) + (j - l) * (n - j - 1 - r);

}

return ans;

}

};

花花酱 LeetCode 1396. Design Underground System

By zxi on March 28, 2020

Implement the class UndergroundSystem that supports three methods:

1. checkIn(int id, string stationName, int t)

A customer with id card equal to id, gets in the station stationName at time t.
A customer can only be checked into one place at a time.

2. checkOut(int id, string stationName, int t)

A customer with id card equal to id, gets out from the station stationName at time t.

3. getAverageTime(string startStation, string endStation)

Returns the average time to travel between the startStation and the endStation.
The average time is computed from all the previous traveling from startStation to endStation that happened directly.
Call to getAverageTime is always valid.

You can assume all calls to checkIn and checkOut methods are consistent. That is, if a customer gets in at time t₁ at some station, then it gets out at time t₂ with t₂ > t₁. All events happen in chronological order.

Example 1:

Input
["UndergroundSystem","checkIn","checkIn","checkIn","checkOut","checkOut","checkOut","getAverageTime","getAverageTime","checkIn","getAverageTime","checkOut","getAverageTime"]
[[],[45,"Leyton",3],[32,"Paradise",8],[27,"Leyton",10],[45,"Waterloo",15],[27,"Waterloo",20],[32,"Cambridge",22],["Paradise","Cambridge"],["Leyton","Waterloo"],[10,"Leyton",24],["Leyton","Waterloo"],[10,"Waterloo",38],["Leyton","Waterloo"]]

Output
[null,null,null,null,null,null,null,14.0,11.0,null,11.0,null,12.0]

Explanation
UndergroundSystem undergroundSystem = new UndergroundSystem();
undergroundSystem.checkIn(45, "Leyton", 3);
undergroundSystem.checkIn(32, "Paradise", 8);
undergroundSystem.checkIn(27, "Leyton", 10);
undergroundSystem.checkOut(45, "Waterloo", 15);
undergroundSystem.checkOut(27, "Waterloo", 20);
undergroundSystem.checkOut(32, "Cambridge", 22);
undergroundSystem.getAverageTime("Paradise", "Cambridge");       // return 14.0. There was only one travel from "Paradise" (at time 8) to "Cambridge" (at time 22)
undergroundSystem.getAverageTime("Leyton", "Waterloo");          // return 11.0. There were two travels from "Leyton" to "Waterloo", a customer with id=45 from time=3 to time=15 and a customer with id=27 from time=10 to time=20. So the average time is ( (15-3) + (20-10) ) / 2 = 11.0
undergroundSystem.checkIn(10, "Leyton", 24);
undergroundSystem.getAverageTime("Leyton", "Waterloo");          // return 11.0
undergroundSystem.checkOut(10, "Waterloo", 38);
undergroundSystem.getAverageTime("Leyton", "Waterloo");          // return 12.0

Constraints:

There will be at most 20000 operations.
1 <= id, t <= 10^6
All strings consist of uppercase, lowercase English letters and digits.
1 <= stationName.length <= 10
Answers within 10^-5 of the actual value will be accepted as correct.

Solution: Hashtable

For each user, store the checkin station and time.
For each trip (startStation + “_” + endStation), store the total time and counts.

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

C++

// Author: Huahua

class UndergroundSystem {

public:

UndergroundSystem() {}

void checkIn(int id, string stationName, int t) {

m_[id] = {stationName, t};

}

void checkOut(int id, string stationName, int t) {

const auto& [s0, t0] = m_[id];

string key = s0 + "_" + stationName;

times_[key].first += (t - t0);

++times_[key].second;

}

double getAverageTime(string startStation, string endStation) {

const auto& [sum, count] = times_[startStation + "_" + endStation];

return static_cast<double>(sum) / count;

}

private:

unordered_map<int, pair<string, int>> m_; // id -> {station, t}

unordered_map<string, pair<int, int>> times_; // trip -> {sum, count}

};