Posts published in “Hashtable”

花花酱 LeetCode 409. Longest Palindrome

By zxi on September 19, 2017

https://leetcode.com/problems/longest-palindrome/description/

Problem:

Given a string which consists of lowercase or uppercase letters, find the length of the longest palindromes that can be built with those letters.

This is case sensitive, for example "Aa" is not considered a palindrome here.

Note:
Assume the length of given string will not exceed 1,010.

Example:

Input:

"abccccdd"

Output:

Explanation:

One longest palindrome that can be built is "dccaccd", whose length is 7.

Idea:

Greedy + Counting

Solution:

C++

// Author: Huahua

// Time complexity: O(n)

// Space complexity: O(128) = O(1)

// Running time: 3 ms 9/2017

class Solution {

public:

int longestPalindrome(const string& s) {

vector<int> freqs(128, 0);

for (const char c : s)

++freqs[c];

int ans = 0;

int odd = 0;

for (const int freq : freqs) {

// same as: ans += freq % 2 == 0 ? freq : freq - 1;

// same as: ans += freq / 2 * 2;

// same as: ans += ((freq >> 1) << 1);

// same as: ans += freq & (INT_MAX - 1);

ans += freq & (~1); // clear the last bit

odd |= freq & 1;

}

ans += odd;

return ans;

}

};

Java

// Author: Huahua

// Running time: 11 ms

class Solution {

public int longestPalindrome(String s) {

int[] freqs = new int[128];

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

++freqs[s.charAt(i)];

int ans = 0;

int odd = 0;

for (int freq: freqs) {

ans += freq & (~1);

odd |= freq & 1;

}

return ans + odd;

}

Python

"""

Author: Huahua

Running time: 39 ms

"""

class Solution(object):

def longestPalindrome(self, s):

"""

:type s: str

:rtype: int

"""

freqs = [0] * 128

for c in s:

freqs[ord(c)] += 1

ans, odd = 0, 0

for freq in freqs:

ans += freq & (~1)

odd |= freq & 1

return ans + odd

花花酱 LeetCode 381. Insert Delete GetRandom O(1) – Duplicates allowed

By zxi on September 17, 2017

https://leetcode.com/problems/insert-delete-getrandom-o1-duplicates-allowed/description/

Problem:

Design a data structure that supports all following operations in average O(1) time.

Note: Duplicate elements are allowed.

insert(val): Inserts an item val to the collection.
remove(val): Removes an item val from the collection if present.
getRandom: Returns a random element from current collection of elements. The probability of each element being returned is linearly related to the number of same value the collection contains.

Idea:

Hashtable + array

Solution:

// Author: Huahua

// Running time: 49 ms

class RandomizedCollection {

public:

/** Initialize your data structure here. */

RandomizedCollection() {}

/** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */

bool insert(int val) {

m_[val].push_back(vals_.size());

vals_.emplace_back(val, m_[val].size() - 1);

return m_[val].size() == 1u;

}

/** Removes a value from the collection. Returns true if the collection contained the specified element. */

bool remove(int val) {

if (!m_.count(val)) return false;

int index_to_evict = m_[val].back();

const auto& last_entry = vals_.back();

// Update index

m_[last_entry.first][last_entry.second] = index_to_evict;

// Swap vals

swap(vals_.back(), vals_[index_to_evict]);

// Clenup

vals_.pop_back();

m_[val].pop_back();

if (m_[val].empty()) m_.erase(val);

return true;

}

/** Get a random element from the collection. */

int getRandom() {

return vals_[rand() % vals_.size()].first;

}

private:

// val -> indices array: indices in vals_

unordered_map<int, vector<int>> m_;

// {val, index in the indices array}

vector<pair<int,int>> vals_;

};

Java

// Author: Huahua

// Running time: 122 ms (<94.53%)

class RandomizedCollection {

class Entry {

public int value;

public int index;

public Entry(int val, int idx) {

value = val;

index = idx;

}

private Map<Integer, List<Integer>> m;

private List<Entry> vals;

private Random rand;

/** Initialize your data structure here. */

public RandomizedCollection() {

m = new HashMap<>();

vals = new ArrayList<>();

rand = new Random();

}

/** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */

public boolean insert(int val) {

List<Integer> l = m.getOrDefault(val, new ArrayList<Integer>());

l.add(vals.size());

m.put(val, l);

vals.add(new Entry(val, l.size() - 1));

return l.size() == 1;

}

/** Removes a value from the collection. Returns true if the collection contained the specified element. */

public boolean remove(int val) {

if (!m.containsKey(val)) return false;

List<Integer> l = m.get(val);

int index_to_evict = l.get(l.size() - 1);

Entry last_entry = vals.get(vals.size() - 1);

// Update index

m.get(last_entry.value).set(last_entry.index, index_to_evict);

// Swap vals

vals.set(index_to_evict, last_entry);

// Cleanup

vals.remove(vals.size() - 1);

l.remove(l.size() - 1);

if (l.size() == 0) m.remove(val);

return true;

}

/** Get a random element from the collection. */

public int getRandom() {

return vals.get(rand.nextInt(vals.size())).value;

}

Related Problems:

花花酱 LeetCode 380. Insert Delete GetRandom O(1)

By zxi on September 16, 2017

Problem:

Design a data structure that supports all following operations in average O(1) time.

insert(val): Inserts an item val to the set if not already present.
remove(val): Removes an item val from the set if present.
getRandom: Returns a random element from current set of elements. Each element must have the same probability of being returned.

Idea:

Hashtable + array

Time complexity:

O(1)

Solution:

// Author: Huahua

// Running time: 49 ms

class RandomizedSet {

public:

/** Initialize your data structure here. */

RandomizedSet() {}

/** Inserts a value to the set. Returns true if the set did not already contain the specified element. */

bool insert(int val) {

if(m_.count(val)) return false;

m_[val] = vals_.size();

vals_.push_back(val);

return true;

}

/** Removes a value from the set. Returns true if the set contained the specified element. */

bool remove(int val) {

if(!m_.count(val)) return false;

int index = m_[val];

m_[vals_.back()] = index;

m_.erase(val);

std::swap(vals_[index], vals_.back());

vals_.pop_back();

return true;

}

/** Get a random element from the set. */

int getRandom() {

int index = rand() % vals_.size();

return vals_[index];

}

private:

// val -> index in the array

unordered_map<int, int> m_;

vector<int> vals_;

};

Related Problems:

花花酱 LeetCode 460. LFU Cache

By zxi on September 14, 2017

Problem:

Design and implement a data structure for Least Frequently Used (LFU) cache. It should support the following operations: get and put.

get(key) – Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
put(key, value) – Set or insert the value if the key is not already present. When the cache reaches its capacity, it should invalidate the least frequently used item before inserting a new item. For the purpose of this problem, when there is a tie (i.e., two or more keys that have the same frequency), the least recently used key would be evicted.

Follow up:
Could you do both operations in O(1) time complexity?

Example:

LFUCache cache = new LFUCache( 2 /* capacity */ );

cache.put(1, 1);

cache.put(2, 2);

cache.get(1); // returns 1

cache.put(3, 3); // evicts key 2

cache.get(2); // returns -1 (not found)

cache.get(3); // returns 3.

cache.put(4, 4); // evicts key 1.

cache.get(1); // returns -1 (not found)

cache.get(3); // returns 3

cache.get(4); // returns 4

Idea:

Hashtable + balanced search tree

Hashtable + double linked list

Solution 1: O(logc) c is the capacity

// Author: Huahua

// Running time: 99 ms

struct CacheNode {

int key;

int value;

int freq;

long tick;

// Defines the order, smaller one will be evicted first

bool operator <(const CacheNode& rhs) const {

if (freq < rhs.freq) return true;

if (freq == rhs.freq) return tick < rhs.tick;

return false;

}

};

class LFUCache {

public:

LFUCache(int capacity):capacity_(capacity), tick_(0) {}

int get(int key) {

auto it = m_.find(key);

if (it == m_.cend()) return -1;

int value = it->second.value;

touch(it->second);

return value;

}

void put(int key, int value) {

if (capacity_ == 0) return;

auto it = m_.find(key);

if (it != m_.cend()) {

// Key exists, update value and touch

it->second.value = value;

touch(it->second);

return;

}

if (m_.size() == capacity_) {

// Remove the first node in cache

const CacheNode& node = *cache_.cbegin();

m_.erase(node.key);

cache_.erase(node);

}

CacheNode node{key, value, 1, ++tick_};

m_[node.key] = node;

cache_.insert(node);

}

private:

void touch(CacheNode& node) {

cache_.erase(node); // log(capacity)

++node.freq;

node.tick = ++tick_;

cache_.insert(node); // log(capacity)

}

long tick_;

int capacity_;

unordered_map<int, CacheNode> m_;

set<CacheNode> cache_;

};

Solution 2: O(1)

// Author: Huahua

// Running time: 89 ms (beats 96.3%)

struct CacheNode {

int key;

int value;

int freq;

// pointer to the node in the list

list<int>::const_iterator it;

};

class LFUCache {

public:

LFUCache(int capacity): capacity_(capacity), min_freq_(0) {}

int get(int key) {

auto it = n_.find(key);

if (it == n_.cend()) return -1;

touch(it->second);

return it->second.value;

}

void put(int key, int value) {

if (capacity_ == 0) return;

auto it = n_.find(key);

if (it != n_.cend()) {

// Key already exists, update the value and touch it

it->second.value = value;

touch(it->second);

return;

}

if (n_.size() == capacity_) {

// No capacity, need to remove one entry that

// 1. has the lowest freq

// 2. least recently used if there are multiple ones

// Step 1: remove the element from min_freq_ list

const int key_to_evict = l_[min_freq_].back();

l_[min_freq_].pop_back();

// Step 2: remove the key from cache

n_.erase(key_to_evict);

}

// We know new item has freq of 1, thus set min_freq to 1

const int freq = 1;

min_freq_ = freq;

// Add the key to the freq list

l_[freq].push_front(key);

// Create a new node

n_[key] = {key, value, freq, l_[freq].cbegin()};

}

private:

void touch(CacheNode& node) {

// Step 1: update the frequency

const int prev_freq = node.freq;

const int freq = ++(node.freq);

// Step 2: remove the entry from old freq list

l_[prev_freq].erase(node.it);

if (l_[prev_freq].empty() && prev_freq == min_freq_) {

// Delete the list

l_.erase(prev_freq);

// Increase the min freq

++min_freq_;

}

// Step 4: insert the key into the front of the new freq list

l_[freq].push_front(node.key);

// Step 5: update the pointer

node.it = l_[freq].cbegin();

}

int capacity_;

int min_freq_;

// key -> CacheNode

unordered_map<int, CacheNode> n_;

// freq -> keys with freq

unordered_map<int, list<int>> l_;

};

花花酱 LeetCode 451. Sort Characters By Frequency

By zxi on September 13, 2017

Problem:

Given a string, sort it in decreasing order based on the frequency of characters.

Example 1:

Input:
“tree”

Output:
“eert”

Explanation:
‘e’ appears twice while ‘r’ and ‘t’ both appear once.
So ‘e’ must appear before both ‘r’ and ‘t’. Therefore “eetr” is also a valid answer.
Example 2:

Input:
“cccaaa”

Output:
“cccaaa”

Explanation:
Both ‘c’ and ‘a’ appear three times, so “aaaccc” is also a valid answer.
Note that “cacaca” is incorrect, as the same characters must be together.
Example 3:

Input:
“Aabb”

Output:
“bbAa”

Explanation:
“bbaA” is also a valid answer, but “Aabb” is incorrect.
Note that ‘A’ and ‘a’ are treated as two different characters.

Idea:

Counting sort

Solution 1:

Sort the string based on element frequency

// Author: Huahua

// Running time: 289 ms

class Solution {

public:

string frequencySort(string& s) {

array<int, 128> f{0};

for(char c:s) ++f[c];

sort(s.begin(), s.end(), [&f] (char a, char b) {

return f[a] > f[b] || (f[a] == f[b] && a > b);

});

return s;

}

};

// Author: Huahua

// Running time: 139 ms

class Solution {

public:

string frequencySort(string& s) {

map<char, int> f;

for(char c:s) ++f[c];

sort(s.begin(), s.end(), [&f] (char a, char b) {

return f[a] > f[b] || (f[a] == f[b] && a > b);

});

return s;

}

};

// Author: Huahua

// Running time: 29 ms

class Solution {

public:

string frequencySort(string& s) {

array<int, 128> f{0};

for(char c:s) ++f[c];

sort(s.begin(), s.end(), [&f] (char a, char b) {

return f[a] > f[b] || (f[a] == f[b] && a > b);

});

return s;

}

};

Solution 2:

Counting sort

// Author: Huahua

// Running time: 12 ms

class Solution {

public:

string frequencySort(const string& s) {

vector<int> f(128, 0);

for(char c:s) ++f[c];

vector<pair<int,char>> v;

for (int i = 0; i < 128; ++i) {

if (f[i] > 0) v.emplace_back(f[i], i);

}

sort(v.rbegin(), v.rend());

string ans;

for(const auto& kv : v) {

ans.append(kv.first, kv.second);

}

return ans;

}

};