hashset Archives - Huahua's Tech Road

花花酱 LeetCode 2154. Keep Multiplying Found Values by Two

By zxi on February 4, 2022

You are given an array of integers nums. You are also given an integer original which is the first number that needs to be searched for in nums.

You then do the following steps:

If original is found in nums, multiply it by two (i.e., set original = 2 * original).
Otherwise, stop the process.
Repeat this process with the new number as long as you keep finding the number.

Return the final value of original.

Example 1:

Input: nums = [5,3,6,1,12], original = 3
Output: 24
Explanation: 
- 3 is found in nums. 3 is multiplied by 2 to obtain 6.
- 6 is found in nums. 6 is multiplied by 2 to obtain 12.
- 12 is found in nums. 12 is multiplied by 2 to obtain 24.
- 24 is not found in nums. Thus, 24 is returned.

Example 2:

Input: nums = [2,7,9], original = 4
Output: 4
Explanation:
- 4 is not found in nums. Thus, 4 is returned.

Constraints:

1 <= nums.length <= 1000
1 <= nums[i], original <= 1000

Solution: Hashset

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

C++

// Author: Huahua

class Solution {

public:

int findFinalValue(vector<int>& nums, int original) {

unordered_set<int> s(begin(nums), end(nums));

while (true) {

if (!s.count(original)) break;

original *= 2;

}

return original;

}

};

花花酱 LeetCode 2103. Rings and Rods

By zxi on December 12, 2021

Problem

Solution: Hashset

Use 10 hashsets to track the status of each rod, check whether it contains three unique elements (R,G,B).

Time complexity: O(n)
Space complexity: O(10*3)

C++

// Author: Huahua

class Solution {

public:

int countPoints(string rings) {

constexpr int kRods = 10;

vector<unordered_set<char>> s(kRods);

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

s[rings[i + 1] - '0'].insert(rings[i]);

int ans = 0;

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

if (s[i].size() == 3)

++ans;

return ans;

}

};

花花酱 LeetCode 1876. Substrings of Size Three with Distinct Characters

By zxi on August 6, 2021

A string is good if there are no repeated characters.

Given a string s, return the number of good substrings of length three in s.

Note that if there are multiple occurrences of the same substring, every occurrence should be counted.

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

Example 1:

Input: s = "xyzzaz"
Output: 1
Explanation: There are 4 substrings of size 3: "xyz", "yzz", "zza", and "zaz". 
The only good substring of length 3 is "xyz".

Example 2:

Input: s = "aababcabc"
Output: 4
Explanation: There are 7 substrings of size 3: "aab", "aba", "bab", "abc", "bca", "cab", and "abc".
The good substrings are "abc", "bca", "cab", and "abc".

Constraints:

1 <= s.length <= 100
s consists of lowercase English letters.

Solution: Brute Force w/ (Hash)Set

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

C++

class Solution {

public:

int countGoodSubstrings(string s) {

int ans = 0;

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

ans += set<char>(s.begin() + i, s.begin() + i + 3).size() == 3;

return ans;

}

};

Python3

class Solution:

def countGoodSubstrings(self, s: str) -> int:

return sum(len(set(s[i:i + 3])) == 3 for i in range(len(s) - 2))

花花酱 LeetCode 1817. Finding the Users Active Minutes

By zxi on April 6, 2021

You are given the logs for users’ actions on LeetCode, and an integer k. The logs are represented by a 2D integer array logs where each logs[i] = [ID_i, time_i] indicates that the user with ID_i performed an action at the minute time_i.

Multiple users can perform actions simultaneously, and a single user can perform multiple actions in the same minute.

The user active minutes (UAM) for a given user is defined as the number of unique minutes in which the user performed an action on LeetCode. A minute can only be counted once, even if multiple actions occur during it.

You are to calculate a 1-indexed array answer of size k such that, for each j (1 <= j <= k), answer[j] is the number of users whose UAM equals j.

Return the array answer as described above.

Example 1:

Input: logs = [[0,5],[1,2],[0,2],[0,5],[1,3]], k = 5
Output: [0,2,0,0,0]
Explanation:
The user with ID=0 performed actions at minutes 5, 2, and 5 again. Hence, they have a UAM of 2 (minute 5 is only counted once).
The user with ID=1 performed actions at minutes 2 and 3. Hence, they have a UAM of 2.
Since both users have a UAM of 2, answer[2] is 2, and the remaining answer[j] values are 0.

Example 2:

Input: logs = [[1,1],[2,2],[2,3]], k = 4
Output: [1,1,0,0]
Explanation:
The user with ID=1 performed a single action at minute 1. Hence, they have a UAM of 1.
The user with ID=2 performed actions at minutes 2 and 3. Hence, they have a UAM of 2.
There is one user with a UAM of 1 and one with a UAM of 2.
Hence, answer[1] = 1, answer[2] = 1, and the remaining values are 0.

Constraints:

1 <= logs.length <= 10⁴
0 <= ID_i <= 10⁹
1 <= time_i <= 10⁵
k is in the range [The maximum UAM for a user, 10⁵].

Solution: Hashsets in a Hashtable

key: user_id, value: set{time}

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

C++

class Solution {

public:

vector<int> findingUsersActiveMinutes(vector<vector<int>>& logs, int k) {

unordered_map<int, unordered_set<int>> m;

vector<int> ans(k);

for (const auto& log : logs)

m[log[0]].insert(log[1]);

for (const auto& [id, s] : m)

++ans[s.size() - 1];

return ans;

}

};

花花酱 LeetCode 1695. Maximum Erasure Value

By zxi on December 20, 2020

You are given an array of positive integers nums and want to erase a subarray containing unique elements. The score you get by erasing the subarray is equal to the sum of its elements.

Return the maximum score you can get by erasing exactly one subarray.

An array b is called to be a subarray of a if it forms a contiguous subsequence of a, that is, if it is equal to a[l],a[l+1],...,a[r] for some (l,r).

Example 1:

Input: nums = [4,2,4,5,6]
Output: 17
Explanation: The optimal subarray here is [2,4,5,6].

Example 2:

Input: nums = [5,2,1,2,5,2,1,2,5]
Output: 8
Explanation: The optimal subarray here is [5,2,1] or [1,2,5].

Constraints:

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁴

Solution: Sliding window + Hashset

Maintain a window that has no duplicate elements.

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

C++

// Author: Huahua

class Solution {

public:

int maximumUniqueSubarray(vector<int>& nums) {

const int n = nums.size();

unordered_set<int> t;

int ans = 0;

for (int l = 0, r = 0, s = 0; r < n; ++r) {

while (t.count(nums[r]) && l < r) {

s -= nums[l];

t.erase(nums[l++]);

}

t.insert(nums[r]);

ans = max(ans, s += nums[r]);

}

return ans;

}

};

Posts tagged as “hashset”

花花酱 LeetCode 2154. Keep Multiplying Found Values by Two

Solution: Hashset

C++

花花酱 LeetCode 2103. Rings and Rods

Solution: Hashset

C++

花花酱 LeetCode 1876. Substrings of Size Three with Distinct Characters

Solution: Brute Force w/ (Hash)Set

C++

Python3

花花酱 LeetCode 1817. Finding the Users Active Minutes

Solution: Hashsets in a Hashtable

C++

花花酱 LeetCode 1695. Maximum Erasure Value

Solution: Sliding window + Hashset

C++