Hashtable Archives - Page 19 of 34

花花酱 LeetCode 1233. Remove Sub-Folders from the Filesystem

By zxi on October 21, 2019

Given a list of folders, remove all sub-folders in those folders and return in any order the folders after removing.

If a folder[i] is located within another folder[j], it is called a sub-folder of it.

The format of a path is one or more concatenated strings of the form: / followed by one or more lowercase English letters. For example, /leetcode and /leetcode/problems are valid paths while an empty string and / are not.

Example 1:

Input: folder = ["/a","/a/b","/c/d","/c/d/e","/c/f"]
Output: ["/a","/c/d","/c/f"]
Explanation: Folders "/a/b/" is a subfolder of "/a" and "/c/d/e" is inside of folder "/c/d" in our filesystem.

Example 2:

Input: folder = ["/a","/a/b/c","/a/b/d"]
Output: ["/a"]
Explanation: Folders "/a/b/c" and "/a/b/d/" will be removed because they are subfolders of "/a".

Example 3:

Input: folder = ["/a/b/c","/a/b/ca","/a/b/d"]
Output: ["/a/b/c","/a/b/ca","/a/b/d"]

Constraints:

1 <= folder.length <= 4 * 10^4
2 <= folder[i].length <= 100
folder[i] contains only lowercase letters and ‘/’
folder[i] always starts with character ‘/’
Each folder name is unique.

Solution: HashTable

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

C++

// Author: Huahua

class Solution {

public:

vector<string> removeSubfolders(vector<string>& folder) {

unordered_set<string> s(begin(folder), end(folder));

vector<string> ans;

for (const auto& cur : folder) {

string f = cur;

bool valid = true;

while (!f.empty() && valid) {

while (f.back() != '/') f.pop_back();

f.pop_back();

if (s.count(f)) valid = false;

}

if (valid) ans.push_back(cur);

}

return ans;

}

};

花花酱 LeetCode 49. Group Anagrams

By zxi on October 2, 2019

Given an array of strings, group anagrams together.

Example:

Input: ["eat", "tea", "tan", "ate", "nat", "bat"],
Output:
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]

Note:

All inputs will be in lowercase.
The order of your output does not matter.

Solution: HashTable

The sorted word will be the key of each group

Time complexity: O(sum(l*log(l)))
Space complexity: O(sum(l))

C++

// Author: Huahua

class Solution {

public:

vector<vector<string>> groupAnagrams(vector<string>& strs) {

vector<vector<string>> ans;

unordered_map<string, vector<int>> m;

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

string c = strs[i];

sort(begin(c), end(c));

m[c].push_back(i);

}

for (const auto& kv : m) {

ans.push_back({});

for (int i : kv.second)

ans.back().push_back(strs[i]);

}

return ans;

}

};

花花酱 LeeCode 1207. Unique Number of Occurrences

By zxi on September 29, 2019

Given an array of integers arr, write a function that returns true if and only if the number of occurrences of each value in the array is unique.

Example 1:

Input: arr = [1,2,2,1,1,3]
Output: true
Explanation: The value 1 has 3 occurrences, 2 has 2 and 3 has 1. No two values have the same number of occurrences.

Example 2:

Input: arr = [1,2]
Output: false

Example 3:

Input: arr = [-3,0,1,-3,1,1,1,-3,10,0]
Output: true

Constraints:

1 <= arr.length <= 1000
-1000 <= arr[i] <= 1000

Solution: HashTable

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

C++

// Author: Huahua

class Solution {

public:

bool uniqueOccurrences(vector<int>& arr) {

unordered_map<int, int> c;

for (int a : arr) ++c[a];

unordered_set<int> s;

for (const auto& kv : c)

if (!s.insert(kv.second).second)

return false;

return true;

}

};

花花酱 LeetCode 1189. Maximum Number of Balloons

By zxi on September 15, 2019

Given a string text, you want to use the characters of text to form as many instances of the word “balloon” as possible.

You can use each character in text at most once. Return the maximum number of instances that can be formed.

Example 1:

Input: text = "nlaebolko"
Output: 1

Example 2:

Input: text = "loonbalxballpoon"
Output: 2

Example 3:

Input: text = "leetcode"
Output: 0

Constraints:

1 <= text.length <= 10^4
text consists of lower case English letters only.

Solution: HashTable

Use a hashtable to count the occurrence of each letter and find the bottleneck one.

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

C++

// Author: Huahua

class Solution {

public:

int maxNumberOfBalloons(string text) {

map<char, int> c;

for (char t : text) ++c[t];

return min({c['b'], c['a'], c['l'] / 2, c['o'] / 2, c['n']});

}

};

Posts published in “Hashtable”

花花酱 LeetCode 1282. Group the People Given the Group Size They Belong To

Solution: HashMap + Greedy

C++

花花酱 LeetCode 1233. Remove Sub-Folders from the Filesystem

Solution: HashTable

C++

花花酱 LeetCode 49. Group Anagrams

Solution: HashTable

C++

花花酱 LeeCode 1207. Unique Number of Occurrences

Solution: HashTable

C++

花花酱 LeetCode 1189. Maximum Number of Balloons

C++