Posts published in “Hashtable”

花花酱 LeetCode 438. Find All Anagrams in a String

By zxi on May 28, 2018

Problem

题目大意：在s中找出所有p的Anagrams。

https://leetcode.com/problems/find-all-anagrams-in-a-string/description/

Given a string s and a non-empty string p, find all the start indices of p‘s anagrams in s.

Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.

The order of output does not matter.

Example 1:

Input:
s: "cbaebabacd" p: "abc"

Output:
[0, 6]

Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".

Example 2:

Input:
s: "abab" p: "ab"

Output:
[0, 1, 2]

Explanation:
The substring with start index = 0 is "ab", which is an anagram of "ab".
The substring with start index = 1 is "ba", which is an anagram of "ab".
The substring with start index = 2 is "ab", which is an anagram of "ab".

Solution: HashTable + Sliding Window

Time complexity: O(n)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 35 ms

class Solution {

public:

vector<int> findAnagrams(string s, string p) {

int n = s.length();

int l = p.length();

vector<int> ans;

vector<int> vp(26, 0);

vector<int> vs(26, 0);

for (char c : p) ++vp[c - 'a'];

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

if (i >= l) --vs[s[i - l] - 'a'];

++vs[s[i] - 'a'];

if (vs == vp) ans.push_back(i + 1 - l);

}

return ans;

}

};

花花酱 LeetCode 825. Friends Of Appropriate Ages

By zxi on April 29, 2018

Problem

Some people will make friend requests. The list of their ages is given and ages[i] is the age of the ith person.

Person A will NOT friend request person B (B != A) if any of the following conditions are true:

age[B] <= 0.5 * age[A] + 7
age[B] > age[A]
age[B] > 100 && age[A] < 100

Otherwise, A will friend request B.

Note that if A requests B, B does not necessarily request A. Also, people will not friend request themselves.

How many total friend requests are made?

Example 1:

Input: [16,16]
Output: 2
Explanation: 2 people friend request each other.

Example 2:

Input: [16,17,18]
Output: 2
Explanation: Friend requests are made 17 -> 16, 18 -> 17.

Example 3:

Input: [20,30,100,110,120]
Output: 
Explanation: Friend requests are made 110 -> 100, 120 -> 110, 120 -> 100.

Notes:

1 <= ages.length <= 20000.
1 <= ages[i] <= 120.

Solution: Hashtable

Count how many people at each age i.

Time complexity: O(n)

Space complexity: O(120)

C++

// Author: Huahua

// Running time: 39 ms

class Solution {

public:

int numFriendRequests(vector<int>& ages) {

const int kMaxAge = 120;

vector<int> counts(kMaxAge + 1, 0);

for (const int age : ages)

++counts[age];

int ans = 0;

for (int A = 1; A <= kMaxAge; ++A) {

for (int B = 0.5 * A + 7 + 1; B <= A; ++B)

ans += counts[A] * (counts[B] - (A == B));

}

return ans;

}

};

花花酱 LeetCode 822. Card Flipping Game

By zxi on April 29, 2018

Problem

题目大意：每张牌的正反面各印着一个数，你可以随便翻牌。找出一个最小的数使得其他牌当前正面的数值都不和它相等。

On a table are N cards, with a positive integer printed on the front and back of each card (possibly different).

We flip any number of cards, and after we choose one card.

If the number X on the back of the chosen card is not on the front of any card, then this number X is good.

What is the smallest number that is good? If no number is good, output 0.

Here, fronts[i] and backs[i] represent the number on the front and back of card i.

A flip swaps the front and back numbers, so the value on the front is now on the back and vice versa.

Example:

Input: fronts = [1,2,4,4,7], backs = [1,3,4,1,3]
Output: 2
Explanation: If we flip the second card, the fronts are [1,3,4,4,7] and the backs are [1,2,4,1,3]. We choose the second card, which has number 2 on the back, and it isn't on the front of any card, so 2 is good.

Note:

1 <= fronts.length == backs.length <= 1000.
1 <= fronts[i] <= 2000.
1 <= backs[i] <= 2000.

Solution: Hashset

C++

// Author: Huahua

// Running time: 23 ms

class Solution {

public:

int flipgame(vector<int>& fronts, vector<int>& backs) {

unordered_set<int> same;

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

if (fronts[i] == backs[i])

same.insert(fronts[i]);

int ans = INT_MAX;

for (int v : fronts)

if (v < ans && !same.count(v)) ans = v;

for (int v : backs)

if (v < ans && !same.count(v)) ans = v;

return ans == INT_MAX ? 0 : ans;

}

};

花花酱 LeetCode 820. Short Encoding of Words

By zxi on April 24, 2018

Problem

Given a list of words, we may encode it by writing a reference string S and a list of indexes A.

For example, if the list of words is ["time", "me", "bell"], we can write it as S = "time#bell#" and indexes = [0, 2, 5].

Then for each index, we will recover the word by reading from the reference string from that index until we reach a “#” character.

What is the length of the shortest reference string S possible that encodes the given words?

Example:

Input: words = ["time", "me", "bell"] Output: 10 Explanation: S = "time#bell#" and indexes = [0, 2, 5].

Note:

1 <= words.length <= 2000.
1 <= words[i].length <= 7.
Each word has only lowercase letters.

Idea

Remove all the words that are suffix of other words.

Solution

Time complexity: O(n*l^2)

Space complexity: O(n*l)

// Author: Huahua

// Running time: 43 ms

class Solution {

public:

int minimumLengthEncoding(vector<string>& words) {

unordered_set<string> s(words.begin(), words.end());

for (const string& w : words) {

for (int i = w.length() - 1; i > 0; --i)

s.erase(w.substr(i));

}

int ans = 0;

for (const string& w : s)

ans += w.length() + 1;

return ans;

}

};

花花酱 LeetCode 819. Most Common Word

By zxi on April 14, 2018

Problem

题目大意：找出一个段落中出现次数最多的单词。

https://leetcode.com/problems/most-common-word/description/

Given a paragraph and a list of banned words, return the most frequent word that is not in the list of banned words. It is guaranteed there is at least one word that isn’t banned, and that the answer is unique.

Words in the list of banned words are given in lowercase, and free of punctuation. Words in the paragraph are not case sensitive. The answer is in lowercase.

Example:
Input: 
paragraph = "Bob hit a ball, the hit BALL flew far after it was hit."
banned = ["hit"]
Output: "ball"
Explanation: 
"hit" occurs 3 times, but it is a banned word.
"ball" occurs twice (and no other word does), so it is the most frequent non-banned word in the paragraph. 
Note that words in the paragraph are not case sensitive,
that punctuation is ignored (even if adjacent to words, such as "ball,"), 
and that "hit" isn't the answer even though it occurs more because it is banned.

Note:

1 <= paragraph.length <= 1000.
1 <= banned.length <= 100.
1 <= banned[i].length <= 10.
The answer is unique, and written in lowercase (even if its occurrences in paragraph may have uppercase symbols, and even if it is a proper noun.)
paragraph only consists of letters, spaces, or the punctuation symbols !?',;.
Different words in paragraph are always separated by a space.
There are no hyphens or hyphenated words.
Words only consist of letters, never apostrophes or other punctuation symbols.

Solution: Hashtable

// Author: Huahua

// Running time: 8 ms

class Solution {

public:

string mostCommonWord(string paragraph, vector<string>& banned) {

unordered_set<string> b(banned.begin(), banned.end());

unordered_map<string, int> counts;

const string pattern = "!?',;. ";

int best = 0;

string ans;

const int n = paragraph.size();

string word;

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

if (i == n || pattern.find(paragraph[i]) != string::npos) {

if (++counts[word] > best && !b.count(word) && word.size() > 0) {

best = counts[word];

ans = word;

}

word.clear();

} else {

word += tolower(paragraph[i]);

}

return ans;

}

};