Posts published in “Hashtable”

花花酱 LeetCode 355. Design Twitter

By zxi on March 10, 2020

Design a simplified version of Twitter where users can post tweets, follow/unfollow another user and is able to see the 10 most recent tweets in the user’s news feed. Your design should support the following methods:

postTweet(userId, tweetId): Compose a new tweet.
getNewsFeed(userId): Retrieve the 10 most recent tweet ids in the user’s news feed. Each item in the news feed must be posted by users who the user followed or by the user herself. Tweets must be ordered from most recent to least recent.
follow(followerId, followeeId): Follower follows a followee.
unfollow(followerId, followeeId): Follower unfollows a followee.

Example:

Twitter twitter = new Twitter();

// User 1 posts a new tweet (id = 5).
twitter.postTweet(1, 5);

// User 1's news feed should return a list with 1 tweet id -> [5].
twitter.getNewsFeed(1);

// User 1 follows user 2.
twitter.follow(1, 2);

// User 2 posts a new tweet (id = 6).
twitter.postTweet(2, 6);

// User 1's news feed should return a list with 2 tweet ids -> [6, 5].
// Tweet id 6 should precede tweet id 5 because it is posted after tweet id 5.
twitter.getNewsFeed(1);

// User 1 unfollows user 2.
twitter.unfollow(1, 2);

// User 1's news feed should return a list with 1 tweet id -> [5],
// since user 1 is no longer following user 2.
twitter.getNewsFeed(1);

Solution: hashtables

Time complexity:
postTweet O(1)
follow O(1)
unfollow O(1)
getNewsFeed O(nlogn)

Space complexity: O(n)

C++

// Author: Huahua

constexpr size_t kMaxTweets = 10;

class Twitter {

public:

/** Initialize your data structure here. */

Twitter() {}

/** Compose a new tweet. */

void postTweet(int userId, int tweetId) {

auto& tweets = user_tweets_[userId];

if (tweets.size() == kMaxTweets)

tweets.pop_front();

tweets.emplace_back(++time_, tweetId);

}

/** Retrieve the 10 most recent tweet ids in the user's news feed. Each item in the news feed must be posted by users who the user followed or by the user herself. Tweets must be ordered from most recent to least recent. */

vector<int> getNewsFeed(int userId) {

vector<pair<int, int>> feed(begin(user_tweets_[userId]),

end(user_tweets_[userId]));

for (int uid : user_followers_[userId])

feed.insert(end(feed),

begin(user_tweets_[uid]),

end(user_tweets_[uid]));

sort(rbegin(feed), rend(feed));

vector<int> ans;

for (int i = 0; i < min(kMaxTweets, feed.size()); ++i)

ans.push_back(feed[i].second);

return ans;

}

/** Follower follows a followee. If the operation is invalid, it should be a no-op. */

void follow(int followerId, int followeeId) {

if (followerId == followeeId) return;

user_followers_[followerId].insert(followeeId);

}

/** Follower unfollows a followee. If the operation is invalid, it should be a no-op. */

void unfollow(int followerId, int followeeId) {

if (followerId == followeeId) return;

user_followers_[followerId].erase(followeeId);

}

private:

int time_;

unordered_map<int, deque<pair<int, int>>> user_tweets_;

unordered_map<int, set<int>> user_followers_;

};

/**

* Your Twitter object will be instantiated and called as such:

* Twitter* obj = new Twitter();

* obj->postTweet(userId,tweetId);

* vector<int> param_2 = obj->getNewsFeed(userId);

* obj->follow(followerId,followeeId);

* obj->unfollow(followerId,followeeId);

花花酱 LeetCode 1371. Find the Longest Substring Containing Vowels in Even Counts

By zxi on March 8, 2020

Given the string s, return the size of the longest substring containing each vowel an even number of times. That is, ‘a’, ‘e’, ‘i’, ‘o’, and ‘u’ must appear an even number of times.

Example 1:

Input: s = "eleetminicoworoep"
Output: 13
Explanation: The longest substring is "leetminicowor" which contains two each of the vowels: e, i and o and zero of the vowels: a and u.

Example 2:

Input: s = "leetcodeisgreat"
Output: 5
Explanation: The longest substring is "leetc" which contains two e's.

Example 3:

Input: s = "bcbcbc"
Output: 6
Explanation: In this case, the given string "bcbcbc" is the longest because all vowels: a, e, i, o and u appear zero times.

Constraints:

1 <= s.length <= 5 x 10^5
s contains only lowercase English letters.

Solution: HashTable

Record the first index when a state occurs. index – last_index is the length of the all-even-vowel substring.

State: {a: odd|even, e: odd|even, …, u:odd|even}.

There are total 2^5 = 32 states that can be represented as a binary string.

whenever a vowel occurs, we flip the bit, e.g. odd->even, even->odd using XOR.

Time complexity: O(5*n)
Space complexity: O(32)

C++

// Author: Huahua

class Solution {

public:

int findTheLongestSubstring(string s) {

const char vowels[] = "aeiou";

vector<int> idx(1 << 5, INT_MAX); // state -> first_index

idx[0] = -1;

int state = 0;

int ans = 0;

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

for (int j = 0; j < 5; ++j)

if (s[i] == vowels[j]) state ^= 1 << j;

if (idx[state] == INT_MAX) idx[state] = i;

ans = max(ans, i - idx[state]);

}

return ans;

}

};

Python3

# Author: Huahua

class Solution:

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

idx = {0 : -1}

vowels = "aeiou"

state = 0

ans = 0

for i in range(len(s)):

j = vowels.find(s[i])

if j >= 0: state ^= 1 << j

if state not in idx:

idx[state] = i

ans = max(ans, i - idx[state])

return ans

花花酱 LeetCode 138. Copy List with Random Pointer

By zxi on January 29, 2020

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

The Linked List is represented in the input/output as a list of n nodes. Each node is represented as a pair of [val, random_index] where:

val: an integer representing Node.val
random_index: the index of the node (range from 0 to n-1) where random pointer points to, or null if it does not point to any node.

Example 1:

Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]

Example 2:

Input: head = [[1,1],[2,1]]
Output: [[1,1],[2,1]]

Example 3:

Input: head = [[3,null],[3,0],[3,null]]
Output: [[3,null],[3,0],[3,null]]

Example 4:

Input: head = []
Output: []
Explanation: Given linked list is empty (null pointer), so return null.

Constraints:

-10000 <= Node.val <= 10000
Node.random is null or pointing to a node in the linked list.
Number of Nodes will not exceed 1000.

Solution: Hashtable

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

C++

// Author: Huahua

class Solution {

public:

Node* copyRandomList(Node* head) {

if (!head) return head;

unordered_map<Node*, Node*> m;

Node* cur = m[head] = new Node(head->val);

Node* ans = cur;

while (head) {

if (head->random) {

auto it = m.find(head->random);

if (it == end(m))

it = m.emplace(head->random, new Node(head->random->val)).first;

cur->random = it->second;

}

if (head->next) {

auto it = m.find(head->next);

if (it == end(m))

it = m.emplace(head->next, new Node(head->next->val)).first;

cur->next = it->second;

}

head = head->next;

cur = cur->next;

}

return ans;

}

};

花花酱 LeetCode 1331. Rank Transform of an Array

By zxi on January 26, 2020

Given an array of integers arr, replace each element with its rank.

The rank represents how large the element is. The rank has the following rules:

Rank is an integer starting from 1.
The larger the element, the larger the rank. If two elements are equal, their rank must be the same.
Rank should be as small as possible.

Example 1:

Input: arr = [40,10,20,30]
Output: [4,1,2,3]
Explanation: 40 is the largest element. 10 is the smallest. 20 is the second smallest. 30 is the third smallest.

Example 2:

Input: arr = [100,100,100]
Output: [1,1,1]
Explanation: Same elements share the same rank.

Example 3:

Input: arr = [37,12,28,9,100,56,80,5,12]
Output: [5,3,4,2,8,6,7,1,3]

Constraints:

0 <= arr.length <= 10⁵
-10⁹ <= arr[i] <= 10⁹

Solution: Sorting + HashTable

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

C++

// Author: Huahua

class Solution {

public:

vector<int> arrayRankTransform(vector<int>& arr) {

set<int> s(begin(arr), end(arr));

unordered_map<int, int> m;

int r = 0;

for (const int v : s) m[v] = ++r;

vector<int> ans(arr.size());

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

ans[i] = m[arr[i]];

return ans;

}

};

花花酱 LeetCode 1329. Sort the Matrix Diagonally

By zxi on January 26, 2020

Given a m * n matrix mat of integers, sort it diagonally in ascending order from the top-left to the bottom-right then return the sorted array.

Example 1:

Input: mat = [[3,3,1,1],[2,2,1,2],[1,1,1,2]]
Output: [[1,1,1,1],[1,2,2,2],[1,2,3,3]]

Constraints:

m == mat.length
n == mat[i].length
1 <= m, n <= 100
1 <= mat[i][j] <= 100

Solution: HashTable

Collect each diagonal’s (keyed by i – j) elements into an array and sort it separately.
If we offset the key by n, e.g. i – j + n, we can use an array instead of a hashtable.

Time complexity: O(m*n + (m+n) * (m+n) * log(m + n))) = (n^2*logn)
Space complexity: O(m*n)

C++

// Author: Huahua

class Solution {

public:

vector<vector<int>> diagonalSort(vector<vector<int>>& mat) {

const int m = mat.size();

const int n = mat[0].size();

vector<deque<int>> qs(m + n);

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

for (int j = 0; j < n; ++j)

qs[i - j + n].push_back(mat[i][j]);

for (auto& q : qs)

sort(begin(q), end(q));

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

for (int j = 0; j < n; ++j) {

mat[i][j] = qs[i - j + n].front();

qs[i - j + n].pop_front();

}

return mat;

}

};