Posts tagged as “easy”

花花酱 LeetCode 1624. Largest Substring Between Two Equal Characters

By zxi on October 18, 2020

Given a string s, return the length of the longest substring between two equal characters, excluding the two characters. If there is no such substring return -1.

A substring is a contiguous sequence of characters within a string.

Example 1:

Input: s = "aa"
Output: 0
Explanation: The optimal substring here is an empty substring between the two 'a's.

Example 2:

Input: s = "abca"
Output: 2
Explanation: The optimal substring here is "bc".

Example 3:

Input: s = "cbzxy"
Output: -1
Explanation: There are no characters that appear twice in s.

Example 4:

Input: s = "cabbac"
Output: 4
Explanation: The optimal substring here is "abba". Other non-optimal substrings include "bb" and "".

Constraints:

1 <= s.length <= 300
s contains only lowercase English letters.

Solution: Hashtable

Remember the first position each letter occurs.

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

C++

class Solution {

public:

int maxLengthBetweenEqualCharacters(string s) {

vector<int> first(26, -1);

int ans = -1;

for (int i = 0; i < s.length(); ++i) {

int& p = first[s[i] - 'a'];

if (p != -1) {

ans = max(ans, i - p - 1);

} else {

p = i;

}

return ans;

}

};

花花酱 LeetCode 1619. Mean of Array After Removing Some Elements

By zxi on October 17, 2020

Given an integer array arr, return the mean of the remaining integers after removing the smallest 5% and the largest 5% of the elements.

Answers within 10^-5 of the actual answer will be considered accepted.

Example 1:

Input: arr = [1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3]
Output: 2.00000
Explanation: After erasing the minimum and the maximum values of this array, all elements are equal to 2, so the mean is 2.

Example 2:

Input: arr = [6,2,7,5,1,2,0,3,10,2,5,0,5,5,0,8,7,6,8,0]
Output: 4.00000

Example 3:

Input: arr = [6,0,7,0,7,5,7,8,3,4,0,7,8,1,6,8,1,1,2,4,8,1,9,5,4,3,8,5,10,8,6,6,1,0,6,10,8,2,3,4]
Output: 4.77778

Example 4:

Input: arr = [9,7,8,7,7,8,4,4,6,8,8,7,6,8,8,9,2,6,0,0,1,10,8,6,3,3,5,1,10,9,0,7,10,0,10,4,1,10,6,9,3,6,0,0,2,7,0,6,7,2,9,7,7,3,0,1,6,1,10,3]
Output: 5.27778

Example 5:

Input: arr = [4,8,4,10,0,7,1,3,7,8,8,3,4,1,6,2,1,1,8,0,9,8,0,3,9,10,3,10,1,10,7,3,2,1,4,9,10,7,6,4,0,8,5,1,2,1,6,2,5,0,7,10,9,10,3,7,10,5,8,5,7,6,7,6,10,9,5,10,5,5,7,2,10,7,7,8,2,0,1,1]
Output: 5.29167

Constraints:

20 <= arr.length <= 1000
arr.lengthis a multiple of 20.
0 <= arr[i] <= 10⁵

Solution: Sorting

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

C++

// Author: Huahua

class Solution {

public:

double trimMean(vector<int>& arr) {

sort(begin(arr), end(arr));

const int offset = arr.size() / 20;

const int sum = accumulate(begin(arr) + offset, end(arr) - offset, 0);

return static_cast<double>(sum) / (arr.size() - 2 * offset);

}

};

花花酱 LeetCode 1614. Maximum Nesting Depth of the Parentheses

By zxi on October 10, 2020

A string is a valid parentheses string (denoted VPS) if it meets one of the following:

It is an empty string "", or a single character not equal to "(" or ")",
It can be written as AB (A concatenated with B), where A and B are VPS‘s, or
It can be written as (A), where A is a VPS.

We can similarly define the nesting depth depth(S) of any VPS S as follows:

depth("") = 0
depth(A + B) = max(depth(A), depth(B)), where A and B are VPS‘s
depth("(" + A + ")") = 1 + depth(A), where A is a VPS.

For example, "", "()()", and "()(()())" are VPS‘s (with nesting depths 0, 1, and 2), and ")(" and "(()" are not VPS‘s.

Given a VPS represented as string s, return the nesting depth of s.

Example 1:

Input: s = "(1+(2*3)+((8)/4))+1"
Output: 3
Explanation: Digit 8 is inside of 3 nested parentheses in the string.

Example 2:

Input: s = "(1)+((2))+(((3)))"
Output: 3

Example 3:

Input: s = "1+(2*3)/(2-1)"
Output: 1

Example 4:

Input: s = "1"
Output: 0

Constraints:

1 <= s.length <= 100
s consists of digits 0-9 and characters '+', '-', '*', '/', '(', and ')'.
It is guaranteed that parentheses expression s is a VPS.

Solution: Stack

We only need to deal with ‘(‘ and ‘)’

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

C++

// Author: Huahua

class Solution {

public:

int maxDepth(string s) {

int ans = 0;

int d = 0;

for (char c : s) {

if (c == '(') ans = max(ans, ++d);

else if (c == ')') --d;

}

return ans;

}

};

花花酱 LeetCode 1608. Special Array With X Elements Greater Than or Equal X

By zxi on October 4, 2020

You are given an array nums of non-negative integers. nums is considered special if there exists a number x such that there are exactly x numbers in nums that are greater than or equal to x.

Notice that x does not have to be an element in nums.

Return x if the array is special, otherwise, return -1. It can be proven that if nums is special, the value for x is unique.

Example 1:

Input: nums = [3,5]
Output: 2
Explanation: There are 2 values (3 and 5) that are greater than or equal to 2.

Example 2:

Input: nums = [0,0]
Output: -1
Explanation: No numbers fit the criteria for x.
If x = 0, there should be 0 numbers >= x, but there are 2.
If x = 1, there should be 1 number >= x, but there are 0.
If x = 2, there should be 2 numbers >= x, but there are 0.
x cannot be greater since there are only 2 numbers in nums.

Example 3:

Input: nums = [0,4,3,0,4]
Output: 3
Explanation: There are 3 values that are greater than or equal to 3.

Example 4:

Input: nums = [3,6,7,7,0]
Output: -1

Constraints:

1 <= nums.length <= 100
0 <= nums[i] <= 1000

Solution 1: Brute Force

Try all possible x from 0 to n.

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

C++

// Author: Huahua

class Solution {

public:

int specialArray(vector<int>& nums) {

for (int x = 0; x <= nums.size(); ++x)

if (x == count_if(begin(nums), end(nums), [x](int num) {

return num >= x; }))

return x;

return -1;

}

};

Python3

# Author: Huahua

class Solution:

def specialArray(self, nums: List[int]) -> int:

for x in range(len(nums) + 1):

if x == sum([n >= x for n in nums]): return x

return -1

Solution 2: Counting Sort

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

f[i] := sum(nums >= i)

C++

// Author: Huahua

class Solution {

public:

int specialArray(vector<int>& nums) {

const int n = nums.size();

vector<int> f(n + 2);

for (int v : nums) ++f[min(v, n)];

for (int i = n; i >= 0; --i)

if ((f[i] += f[i + 1]) == i) return i;

return -1;

}

};

花花酱 LeetCode 1603. Design Parking System

By zxi on October 3, 2020

Design a parking system for a parking lot. The parking lot has three kinds of parking spaces: big, medium, and small, with a fixed number of slots for each size.

Implement the ParkingSystem class:

ParkingSystem(int big, int medium, int small) Initializes object of the ParkingSystem class. The number of slots for each parking space are given as part of the constructor.
bool addCar(int carType) Checks whether there is a parking space of carType for the car that wants to get into the parking lot. carType can be of three kinds: big, medium, or small, which are represented by 1, 2, and 3 respectively. A car can only park in a parking space of its carType. If there is no space available, return false, else park the car in that size space and return true.

Example 1:

Input
["ParkingSystem", "addCar", "addCar", "addCar", "addCar"]
[[1, 1, 0], [1], [2], [3], [1]]
Output
[null, true, true, false, false]

Explanation ParkingSystem parkingSystem = new ParkingSystem(1, 1, 0); parkingSystem.addCar(1); // return true because there is 1 available slot for a big car parkingSystem.addCar(2); // return true because there is 1 available slot for a medium car parkingSystem.addCar(3); // return false because there is no available slot for a small car parkingSystem.addCar(1); // return false because there is no available slot for a big car. It is already occupied.

Constraints:

0 <= big, medium, small <= 1000
carType is 1, 2, or 3
At most 1000 calls will be made to addCar

Solution: Simulation

Time complexity: O(1) per addCar call
Space complexity: O(1)

C++

// Author: Huahua

class ParkingSystem {

public:

ParkingSystem(int big, int medium, int small):

slots_{{big, medium, small}} {}

bool addCar(int carType) {

return slots_[carType - 1]-- > 0;

}

private:

vector<int> slots_;

};

Python3

# Author: Huahua

class ParkingSystem:

def __init__(self, big: int, medium: int, small: int):

self.slots = {1: big, 2: medium, 3: small}

def addCar(self, carType: int) -> bool:

if self.slots[carType] == 0: return False

self.slots[carType] -= 1

return True