Posts tagged as “easy”

花花酱 LeetCode 1748. Sum of Unique Elements

By zxi on February 6, 2021

You are given an integer array nums. The unique elements of an array are the elements that appear exactly once in the array.

Return the sum of all the unique elements of nums.

Example 1:

Input: nums = [1,2,3,2]
Output: 4
Explanation: The unique elements are [1,3], and the sum is 4.

Example 2:

Input: nums = [1,1,1,1,1]
Output: 0
Explanation: There are no unique elements, and the sum is 0.

Example 3:

Input: nums = [1,2,3,4,5]
Output: 15
Explanation: The unique elements are [1,2,3,4,5], and the sum is 15.

Constraints:

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

Solution: Hashtable

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

C++

// Author: Huahua

class Solution {

public:

int sumOfUnique(vector<int>& nums) {

vector<int> seen(101);

int ans = 0;

for (int x : nums)

++seen[x];

for (int x : nums)

if (seen[x] == 1) ans += x;

return ans;

}

};

花花酱 LeetCode 1736. Latest Time by Replacing Hidden Digits

By zxi on January 23, 2021

You are given a string time in the form of hh:mm, where some of the digits in the string are hidden (represented by ?).

The valid times are those inclusively between 00:00 and 23:59.

Return the latest valid time you can get from time by replacing the hidden digits.

Example 1:

Input: time = "2?:?0"
Output: "23:50"
Explanation: The latest hour beginning with the digit '2' is 23 and the latest minute ending with the digit '0' is 50.

Example 2:

Input: time = "0?:3?"
Output: "09:39"

Example 3:

Input: time = "1?:22"
Output: "19:22"

Constraints:

time is in the format hh:mm.
It is guaranteed that you can produce a valid time from the given string.

Solution 1: Brute Force

Enumerate all possible clock in reverse order and find the first matching one.

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

C++

// Author: Huahua

class Solution {

public:

string maximumTime(string time) {

for (int m = 60 * 24 - 1; m >= 0; --m) {

int hh = m / 60;

int mm = m % 60;

if (time[0] != '?' && time[0] - '0' != hh / 10) continue;

if (time[1] != '?' && time[1] - '0' != hh % 10) continue;

if (time[3] != '?' && time[3] - '0' != mm / 10) continue;

if (time[4] != '?' && time[4] - '0' != mm % 10) continue;

time[0] = (hh / 10) + '0';

time[1] = (hh % 10) + '0';

time[3] = (mm / 10) + '0';

time[4] = (mm % 10) + '0';

break;

}

return time;

}

};

Solution 2: Rules

Using rules, fill from left to right.

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

C++

// Author: Huahua

class Solution {

public:

string maximumTime(string time) {

if (time[0] == '?') time[0] = time[1] >= '4' && time[1] <= '9' ? '1' : '2';

if (time[1] == '?') time[1] = time[0] == '2' ? '3' : '9';

if (time[3] == '?') time[3] = '5';

if (time[4] == '?') time[4] = '9';

return time;

}

};

花花酱 LeetCode1732. Find the Highest Altitude

By zxi on January 23, 2021

There is a biker going on a road trip. The road trip consists of n + 1 points at different altitudes. The biker starts his trip on point 0 with altitude equal 0.

You are given an integer array gain of length n where gain[i] is the net gain in altitude between points i and i + 1 for all (0 <= i < n). Return the highest altitude of a point.

Example 1:

Input: gain = [-5,1,5,0,-7]
Output: 1
Explanation: The altitudes are [0,-5,-4,1,1,-6]. The highest is 1.

Example 2:

Input: gain = [-4,-3,-2,-1,4,3,2]
Output: 0
Explanation: The altitudes are [0,-4,-7,-9,-10,-6,-3,-1]. The highest is 0.

Constraints:

n == gain.length
1 <= n <= 100
-100 <= gain[i] <= 100

Solution: Running Max

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

C++

// Author: Huahua

class Solution {

public:

int largestAltitude(vector<int>& gain) {

int ans = 0;

int cur = 0;

for (int diff : gain)

ans = max(ans, cur += diff);

return ans;

}

};

花花酱 LeetCode 1725. Number Of Rectangles That Can Form The Largest Square

By zxi on January 17, 2021

You are given an array rectangles where rectangles[i] = [l_i, w_i] represents the i^th rectangle of length l_i and width w_i.

You can cut the i^th rectangle to form a square with a side length of k if both k <= l_i and k <= w_i. For example, if you have a rectangle [4,6], you can cut it to get a square with a side length of at most 4.

Let maxLen be the side length of the largest square you can obtain from any of the given rectangles.

Return the number of rectangles that can make a square with a side length of maxLen.

Example 1:

Input: rectangles = [[5,8],[3,9],[5,12],[16,5]]
Output: 3
Explanation: The largest squares you can get from each rectangle are of lengths [5,3,5,5].
The largest possible square is of length 5, and you can get it out of 3 rectangles.

Example 2:

Input: rectangles = [[2,3],[3,7],[4,3],[3,7]]
Output: 3

Constraints:

1 <= rectangles.length <= 1000
rectangles[i].length == 2
1 <= l_i, w_i <= 10⁹
l_i != w_i

Solution: Running Max of Shortest Edge

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

C++

// Author: Huahua

class Solution {

public:

int countGoodRectangles(vector<vector<int>>& rectangles) {

int cur = 0;

int ans = 0;

for (const auto& r : rectangles) {

if (min(r[0], r[1]) > cur) {

cur = min(r[0], r[1]);

ans = 0;

}

if (min(r[0], r[1]) == cur) ++ans;

}

return ans;

}

};

花花酱 LeetCode 1720. Decode XORed Array

By zxi on January 10, 2021

There is a hidden integer array arr that consists of n non-negative integers.

It was encoded into another integer array encoded of length n - 1, such that encoded[i] = arr[i] XOR arr[i + 1]. For example, if arr = [1,0,2,1], then encoded = [1,2,3].

You are given the encoded array. You are also given an integer first, that is the first element of arr, i.e. arr[0].

Return the original array arr. It can be proved that the answer exists and is unique.

Example 1:

Input: encoded = [1,2,3], first = 1
Output: [1,0,2,1]
Explanation: If arr = [1,0,2,1], then first = 1 and encoded = [1 XOR 0, 0 XOR 2, 2 XOR 1] = [1,2,3]

Example 2:

Input: encoded = [6,2,7,3], first = 4
Output: [4,2,0,7,4]

Constraints:

2 <= n <= 10⁴
encoded.length == n - 1
0 <= encoded[i] <= 10⁵
0 <= first <= 10⁵

Solution: XOR

encoded[i] = arr[i] ^ arr[i + 1]
encoded[i] ^ arr[i] = arr[i] ^ arr[i] ^ arr[i + 1]
arr[i+1] = encoded[i]^arr[i]

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

C++

class Solution {

public:

vector<int> decode(vector<int>& encoded, int first) {

const int n = encoded.size() + 1;

vector<int> ans(n, first);

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

ans[i + 1] = ans[i] ^ encoded[i];

return ans;

}

};