hashtable – Page 24 – Huahua’s Tech Road

花花酱 LeetCode 106. Construct Binary Tree from Inorder and Postorder Traversal

By zxi on October 3, 2019

Given inorder and postorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

For example, given

inorder = [9,3,15,20,7]
postorder = [9,15,7,20,3]

Return the following binary tree:

Solution: Recursion

Similar to LC 105

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

C++

// Author: Huahua

class Solution {

public:

TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {

unordered_map<int, int> pos;

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

pos[inorder[i]] = i;

function<TreeNode*(int, int, int, int)> buildTree = [&](int is, int ie, int ps, int pe) {

if (ps > pe) return (TreeNode*)nullptr;

int im = pos[postorder[pe]];

int pm = ps + (im - is) - 1;

auto root = new TreeNode(postorder[pe]);

root->left = buildTree(is, im - 1, ps, pm);

root->right = buildTree(im + 1, ie, pm + 1, pe - 1);

return root;

};

return buildTree(0, inorder.size() - 1, 0, postorder.size() - 1);

}

};

花花酱 LeetCode 105. Construct Binary Tree from Preorder and Inorder Traversal

By zxi on October 3, 2019

Given preorder and inorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

For example, given

preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]

Return the following binary tree:

Solution: Recursion

Preprocessing: use a hashtable to store the index of element in preorder array.

For an element in inorder array, find the pos of it in preorder array in O(1), anything to the left will be the leftchild and anything to the right will be the right child.

e.g.
buildTree([9, 3, 15, 20, 7], [3, 9, 20, 15, 7]):
root = TreeNode(9) # inorder[0] = 9
root.left = buildTree([3], [3])
root.right = buildTree([15, 20, 7], [20, 15, 7])
return root

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

C++

// Author: Huahua

class Solution {

public:

TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {

unordered_map<int, int> pos;

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

pos[inorder[i]] = i;

function<TreeNode*(int, int, int, int)> buildTree = [&](int is, int ie, int ps, int pe) {

if (ps > pe) return (TreeNode*)nullptr;

int im = pos[preorder[ps]];

int pm = ps + (im - is);

auto root = new TreeNode(preorder[ps]);

root->left = buildTree(is, im - 1, ps + 1, pm);

root->right = buildTree(im + 1, ie, pm + 1, pe);

return root;

};

return buildTree(0, inorder.size() - 1, 0, preorder.size() - 1);

}

};

花花酱 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 tagged as “hashtable”

花花酱 LeetCode 106. Construct Binary Tree from Inorder and Postorder Traversal

Solution: Recursion

C++

Related Problems

花花酱 LeetCode 105. Construct Binary Tree from Preorder and Inorder Traversal

Solution: Recursion

C++

Related Problems

花花酱 LeetCode 49. Group Anagrams

Solution: HashTable

C++

花花酱 LeeCode 1207. Unique Number of Occurrences

Solution: HashTable

C++

花花酱 LeetCode 1189. Maximum Number of Balloons

C++