Posts published in “Hashtable”

花花酱 LeetCode 594. Longest Harmonious Subsequence

By zxi on March 20, 2018

Problem

https://leetcode.com/problems/longest-harmonious-subsequence/description/

题目大意：找一个最长子序列，要求子序列中最大值和最小值的差是1。

We define a harmonious array is an array where the difference between its maximum value and its minimum value is exactly 1.

Now, given an integer array, you need to find the length of its longest harmonious subsequence among all its possible subsequences.

Example 1:

Input: [1,3,2,2,5,2,3,7]
Output: 5
Explanation: The longest harmonious subsequence is [3,2,2,2,3].

Note: The length of the input array will not exceed 20,000.

Solution1: HashTable

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

C++

// Author: Huahua

// Running time: 127 ms

class Solution {

public:

int findLHS(vector<int>& nums) {

unordered_map<int, int> counts;

int ans = 0;

for (int num : nums) {

++counts[num];

int l = counts[num - 1];

int h = counts[num + 1];

if (l || h)

ans = max(ans, counts[num] + max(l, h));

}

return ans;

}

};

// Running time: 109 ms

class Solution {

public:

int findLHS(vector<int>& nums) {

unordered_map<int, int> counts;

int ans = 0;

for (int num : nums) {

const int c = ++counts[num];

auto it1 = counts.find(num - 1);

auto it2 = counts.find(num + 1);

if (it1 != counts.end())

ans = max(ans, c + it1->second);

if (it2 != counts.end())

ans = max(ans, c + it2->second);

}

return ans;

}

};

// Author: Huahua

// Running time: 102 ms

class Solution {

public:

int findLHS(vector<int>& nums) {

unordered_map<int, int> counts;

int ans = 0;

for (int num : nums)

++counts[num];

for (const auto& p : counts) {

auto it1 = counts.find(p.first - 1);

auto it2 = counts.find(p.first + 1);

if (it1 != counts.end())

ans = max(ans, p.second + it1->second);

if (it2 != counts.end())

ans = max(ans, p.second + it2->second);

}

return ans;

}

};

花花酱 LeetCode 383. Ransom Note

By zxi on March 15, 2018

题目大意：给你一个字符串，问能否用它其中的字符组成另外一个字符串，每个字符只能使用一次。

Problem:

Given an arbitrary ransom note string and another string containing letters from all the magazines, write a function that will return true if the ransom note can be constructed from the magazines ; otherwise, it will return false.

Each letter in the magazine string can only be used once in your ransom note.

Note:
You may assume that both strings contain only lowercase letters.

canConstruct("a", "b") -> false
canConstruct("aa", "ab") -> false
canConstruct("aa", "aab") -> true

Solution: HashTable

Time complexity: O(n + m)

Space complexity: O(128)

C++

// Author: Huahua

// Running time: 24 ms

class Solution {

public:

bool canConstruct(string ransomNote, string magazine) {

vector<int> counts(128, 0);

for (const char c : magazine)

++counts[c];

for (const char c : ransomNote)

if (--counts[c] < 0) return false;

return true;

}

};

// Author: Huahua

// Running time: 9 ms (beats 100%)

static int x=[](){

std::ios::sync_with_stdio(false);

cin.tie(NULL);

return 0;

}();

class Solution {

public:

bool canConstruct(const string& ransomNote, const string& magazine) {

vector<int> counts(128, 0);

for (const char c : magazine)

++counts[c];

for (const char c : ransomNote)

if (--counts[c] < 0) return false;

return true;

}

};

Python3

"""

Author: Huahua

Running time: 64 ms

"""

class Solution:

def canConstruct(self, ransomNote, magazine):

return not collections.Counter(ransomNote) - collections.Counter(magazine);

花花酱 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;

}

};