Posts published in “Hashtable”

花花酱 LeetCode 349. Intersection of Two Arrays

By zxi on March 8, 2018

题目大意：求2个数组的交集。

Problem:

https://leetcode.com/problems/intersection-of-two-arrays/description/

Given two arrays, write a function to compute their intersection.

Example:
Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2].

Note:

Each element in the result must be unique.
The result can be in any order.

C++ using std::set_intersection

// Author: Huahua

// Running time: 8 ms

class Solution {

public:

vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {

vector<int> intersection(max(nums1.size(), nums2.size()));

std::sort(nums1.begin(), nums1.end());

std::sort(nums2.begin(), nums2.end());

// Inputs must be in ascending order

auto it = std::set_intersection(nums1.begin(), nums1.end(), nums2.begin(), nums2.end(), intersection.begin());

intersection.resize(it - intersection.begin());

std::set<int> s(intersection.begin(), intersection.end());

return vector<int>(s.begin(), s.end());

}

};

C++ hashtable

// Author: Huahua

// Running time: 7 ms

class Solution {

public:

vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {

unordered_set<int> m(nums1.begin(), nums1.end());

vector<int> ans;

for (int num : nums2) {

if (!m.count(num)) continue;

ans.push_back(num);

m.erase(num);

}

return ans;

}

};

花花酱 LeetCode 454. 4Sum II

By zxi on March 5, 2018

题目大意：给你4个组数：A, B, C, D。问有多少组组合的A[i] + B[j] + C[k] + D[l] 的和为0。

Given four lists A, B, C, D of integer values, compute how many tuples (i, j, k, l) there are such that A[i] + B[j] + C[k] + D[l]is zero.

To make problem a bit easier, all A, B, C, D have same length of N where 0 ≤ N ≤ 500. All integers are in the range of -2²⁸ to 2²⁸ – 1 and the result is guaranteed to be at most 2³¹ – 1.

Example:

Input:

A = [ 1, 2]

B = [-2,-1]

C = [-1, 2]

D = [ 0, 2]

Output:

Explanation:

The two tuples are:

1. (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0

2. (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0

Solution 1: HashTable

Split the arrays into two groups: (A, B), (C, D)

Create the Minkowski sum of two groups and count the occurrence of each element.

e.g. A = [1, 2, 3], B = [0, -1, 1]

Minkowski sum(A, B) SAB= [0, 1, 2, 3, 4] => [0:1, 1:2, 2:3, 3:2, 4:1]

for each element s in SAB, check whether -s is in Minkowski sum(C, D) SCD

ans = sum(SAB[s] * SCD[-s]), for all s, that s in SAB and -s in SCD

Time complexity: O(n^2)

Space complexity: O(n^2)

C++

// Author: Huahua

// Running time: 217 ms

class Solution {

public:

int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {

unordered_map<int, int> sums;

for (int a : A)

for (int b : B)

++sums[a + b];

int ans = 0;

for (int c : C)

for (int d : D) {

auto it = sums.find(- c - d);

if (it != sums.end()) ans += it->second;

}

return ans;

}

};

Python3

"""

Author: Huahua

Running time: 672 ms

"""

class Solution:

def fourSumCount(self, A, B, C, D):

s = collections.Counter([a + b for a in A for b in B])

return sum(s[-c - d] for c in C for d in D)

Related Problems:

[解题报告] LeetCode 1. Two Sum – 花花酱

花花酱 LeetCode 791. Custom Sort String

By zxi on February 24, 2018

题目大意：给你字符的顺序，让你排序一个字符串。

S and T are strings composed of lowercase letters. In S, no letter occurs more than once.

S was sorted in some custom order previously. We want to permute the characters of T so that they match the order that S was sorted. More specifically, if x occurs before y in S, then x should occur before y in the returned string.

Return any permutation of T (as a string) that satisfies this property.

Example :

Input:

S = "cba"

T = "abcd"

Output: "cbad"

Explanation:

"a", "b", "c" appear in S, so the order of "a", "b", "c" should be "c", "b", and "a".

Since "d" does not appear in S, it can be at any position in T. "dcba", "cdba", "cbda" are also valid outputs.

Note:

S has length at most 26, and no character is repeated in S.
T has length at most 200.
S and T consist of lowercase letters only.

Solution 1: HashTable + Sorting

Store the order of char in a hashtable
Sort the string based on the order

Time complexity: O(nlogn)

Space complexity: O(128)

// Author: Huahua

// Running time: 2 ms

class Solution {

public:

string customSortString(string S, string T) {

vector<int> order(128, INT_MAX);

int i = 0;

for (char c: S)

if (order[c] == INT_MAX) order[c] = ++i;

std::sort(T.begin(), T.end(), [&order](const char c1, const char c2){

return order[c1] < order[c2];

});

return T;

}

};

花花酱 LeetCode 771. Jewels and Stones

By zxi on February 2, 2018

题目大意：给你宝石的类型，再给你一堆石头，返回里面宝石的数量。

Problem:

You’re given strings J representing the types of stones that are jewels, and S representing the stones you have. Each character in S is a type of stone you have. You want to know how many of the stones you have are also jewels.

The letters in J are guaranteed distinct, and all characters in J and S are letters. Letters are case sensitive, so "a" is considered a different type of stone from "A".

Example 1:

Input: J = "aA", S = "aAAbbbb"
Output: 3

Example 2:

Input: J = "z", S = "ZZ"
Output: 0

Note:

S and J will consist of letters and have length at most 50.
The characters in J are distinct.

Solution 1: HashTable

Time complexity: O(|J| + |S|)

Space complexity: O(128) / O(|J|)

C++

// Author: Huahua

// Running time: 9 ms

class Solution {

public:

int numJewelsInStones(string J, string S) {

std::vector<int> f(128, 0);

int ans = 0;

for (const char j : J)

f[j] = 1;

for (const char s : S)

ans += f[s] & 1;

return ans;

}

};

C++ v2

// Author: Huahua

// Running time: 10 ms

class Solution {

public:

int numJewelsInStones(const string& J, const string& S) {

std::set<char> f(J.begin(), J.end());

return std::count_if(S.begin(), S.end(),

[&f](const char c) { return f.count(c); });

}

};

Java

// Author: Huahua

// Running time: 18 ms

class Solution {

public int numJewelsInStones(String J, String S) {

int[] f = new int[128];

for (final char c : J.toCharArray())

f[c] = 1;

int ans = 0;

for (final char c : S.toCharArray())

ans += f[c];

return ans;

}

Python

"""

Author: Huahua

Running time: 43 ms

"""

class Solution(object):

def numJewelsInStones(self, J, S):

f = set(J)

return sum([s in f for s in S])

花花酱 LeetCode 758. Bold Words in String

By zxi on January 8, 2018

题目大意：给你一个字符串和一些要加粗的单词，返回加粗后的HTML代码。

Problem:

Given a set of keywords words and a string S, make all appearances of all keywords in S bold. Any letters between  and  tags become bold.

The returned string should use the least number of tags possible, and of course the tags should form a valid combination.

For example, given that words = ["ab", "bc"] and S = "aabcd", we should return "aabcd". Note that returning "aabcd" would use more tags, so it is incorrect.

Note:

words has length in range [0, 50].
words[i] has length in range [1, 10].
S has length in range [0, 500].
All characters in words[i] and S are lowercase letters.

Solution:

C++

Time complexity: O(nL^2)

Space complexity: O(n + d)

d: size of dictionary

L: max length of the word which is 10.

// Author: Huahua

// Running time: 13 ms

class Solution {

public:

string boldWords(vector<string>& words, string S) {

const int kMaxWordLen = 10;

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

int n = S.length();

vector<int> bolded(n, 0);

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

for (int l = 1; l <= min(n - i, kMaxWordLen); ++l)

if (dict.count(S.substr(i, l)))

std::fill(bolded.begin() + i, bolded.begin() + i + l, 1);

string ans;

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

if (bolded[i] && (i == 0 || !bolded[i - 1])) ans += "";

ans += S[i];

if (bolded[i] && (i == n - 1 || !bolded[i + 1])) ans += "";

}

return ans;

}

};