Posts tagged as “hashtable”

花花酱 LeetCode 963. Minimum Area Rectangle II

By zxi on December 26, 2018

Given a set of points in the xy-plane, determine the minimum area of any rectangle formed from these points, with sides not necessarily parallel to the x and y axes.

If there isn’t any rectangle, return 0.

Example 1:

Input: [[1,2],[2,1],[1,0],[0,1]]
Output: 2.00000
Explanation: The minimum area rectangle occurs at [1,2],[2,1],[1,0],[0,1], with an area of 2.

Example 2:

Input: [[0,1],[2,1],[1,1],[1,0],[2,0]]
Output: 1.00000
Explanation: The minimum area rectangle occurs at [1,0],[1,1],[2,1],[2,0], with an area of 1.

Example 3:

Input: [[0,3],[1,2],[3,1],[1,3],[2,1]]
Output: 0
Explanation: There is no possible rectangle to form from these points.

Example 4:

Input: [[3,1],[1,1],[0,1],[2,1],[3,3],[3,2],[0,2],[2,3]]
Output: 2.00000
Explanation: The minimum area rectangle occurs at [2,1],[2,3],[3,3],[3,1], with an area of 2.

Note:

1 <= points.length <= 50
0 <= points[i][0] <= 40000
0 <= points[i][1] <= 40000
All points are distinct.
Answers within 10^-5 of the actual value will be accepted as correct.

Solution: HashTable

Iterate all possible triangles and check the opposite points that creating a quadrilateral.

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

C++

class Solution {

public:

double minAreaFreeRect(vector<vector<int>>& points) {

constexpr double INF_AREA = 1e100;

const auto n = points.size();

unordered_set<int> s;

for (const auto& p : points)

s.insert(p[0] << 16 | p[1]);

double min_area = INF_AREA;

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

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

if (i == j) continue;

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

if (i == k || j == k) continue;

const auto& p1 = points[i];

const auto& p2 = points[j];

const auto& p3 = points[k];

int dot = (p2[0] - p1[0]) * (p3[0] - p1[0]) +

(p2[1] - p1[1]) * (p3[1] - p1[1]);

if (dot != 0) continue;

int p4_x = p2[0] + p3[0] - p1[0];

int p4_y = p2[1] + p3[1] - p1[1];

if (!s.count(p4_x << 16 | p4_y)) continue;

double a = pow(p2[0] - p1[0], 2) + pow(p2[1] - p1[1], 2);

double b = pow(p3[0] - p1[0], 2) + pow(p3[1] - p1[1], 2);

double area = a * b;

min_area = min(min_area, area);

}

return min_area < INF_AREA ? sqrt(min_area) : 0;

}

};

花花酱 LeetCode 954. Array of Doubled Pairs

By zxi on December 9, 2018

Problem

Given an array of integers A with even length, return true if and only if it is possible to reorder it such that A[2 * i + 1] = 2 * A[2 * i] for every 0 <= i < len(A) / 2.

Example 1:

Input: [3,1,3,6]
Output: false

Example 2:

Input: [2,1,2,6]
Output: false

Example 3:

Input: [4,-2,2,-4]
Output: true
Explanation: We can take two groups, [-2,-4] and [2,4] to form [-2,-4,2,4] or [2,4,-2,-4].

Example 4:

Input: [1,2,4,16,8,4]
Output: false

Note:

0 <= A.length <= 30000
A.length is even
-100000 <= A[i] <= 100000

Solution 1:

Time complexity: O(N + 100000 * 2)

Space complexity: O(100000 * 2)

C++

// Author: Huahua, 108 ms

class Solution {

public:

bool canReorderDoubled(vector<int>& A) {

const int kMaxN = 100000;

vector<int> p(kMaxN + 1);

vector<int> n(kMaxN + 1);

for (int a : A) {

if (a >= 0) ++p[a];

else ++n[-a];

}

for (int i = 0; i <= kMaxN / 2; ++i) {

if (p[i] && (p[i * 2] -= p[i]) < 0) return false;

if (n[i] && (n[i * 2] -= n[i]) < 0) return false;

}

return true;

}

};

Solution 2:

Time complexity: O(NlogN)

Space complexity: O(N)

C++

// Author: Huahua, 108 ms

class Solution {

public:

bool canReorderDoubled(vector<int>& A) {

unordered_map<int, int> c;

for (int a : A) ++c[a];

vector<int> keys;

for (const auto &kv : c) keys.push_back(kv.first);

sort(begin(keys), end(keys), [](int a, int b) { return abs(a) < abs(b); });

for (int key : keys)

if (c[key] && (c[key * 2] -= c[key]) < 0) return false;

return true;

}

};

花花酱 LeetCode 953. Verifying an Alien Dictionary

By zxi on December 9, 2018

Problem

In an alien language, surprisingly they also use english lowercase letters, but possibly in a different order. The order of the alphabet is some permutation of lowercase letters.

Given a sequence of words written in the alien language, and the order of the alphabet, return true if and only if the given words are sorted lexicographicaly in this alien language.

Example 1:

Input: words = ["hello","leetcode"], order = "hlabcdefgijkmnopqrstuvwxyz"
Output: true
Explanation: As 'h' comes before 'l' in this language, then the sequence is sorted.

Example 2:

Input: words = ["word","world","row"], order = "worldabcefghijkmnpqstuvxyz"
Output: false
Explanation: As 'd' comes after 'l' in this language, then words[0] > words[1], hence the sequence is unsorted.

Example 3:

Input: words = ["apple","app"], order = "abcdefghijklmnopqrstuvwxyz"
Output: false
Explanation: The first three characters "app" match, and the second string is shorter (in size.) According to lexicographical rules "apple" > "app", because 'l' > '∅', where '∅' is defined as the blank character which is less than any other character (More info).

Note:

1 <= words.length <= 100
1 <= words[i].length <= 20
order.length == 26
All characters in words[i] and order are english lowercase letters.

Solution: Hashtable

Time complexity: O(sum(len(words[i])))

Space complexity: O(26)

C++

// Author: Huahua, 8 ms

class Solution {

public:

bool isAlienSorted(vector<string>& words, string order) {

vector<char> m(26);

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

m[order[i] - 'a'] = 'a' + i;

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

for (int j = 0; j < words[i].length(); ++j)

words[i][j] = m[words[i][j] - 'a'];

if (i > 0 && words[i] < words[i - 1]) return false;

}

return true;

}

};

花花酱 LeetCode 939. Minimum Area Rectangle

By zxi on November 11, 2018

Problem

Given a set of points in the xy-plane, determine the minimum area of a rectangle formed from these points, with sides parallel to the x and y axes.

If there isn’t any rectangle, return 0.

Example 1:

Input: [[1,1],[1,3],[3,1],[3,3],[2,2]]
Output: 4

Example 2:

Input: [[1,1],[1,3],[3,1],[3,3],[4,1],[4,3]]
Output: 2

Note:

1 <= points.length <= 500
0 <= points[i][0] <= 40000
0 <= points[i][1] <= 40000
All points are distinct.

Solution 1: HashTable + Brute Force

Try all pairs of points to form a diagonal and see whether pointers of another diagonal exist or not.

Assume two points are (x0, y0), (x1, y1) x0 != x1 and y0 != y1. The other two points will be (x0, y1), (x1, y0)

Time complexity: O(n^2)

Space complexity: O(n)

C++

// Author: Huahua, running time: 96 ms

class Solution {

public:

int minAreaRect(vector<vector<int>>& points) {

unordered_map<int, unordered_set<int>> s;

for (const auto& point : points)

s[point[0]].insert(point[1]);

const int n = points.size();

int min_area = INT_MAX;

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

for (int j = i + 1; j < n; ++j) {

int x0 = points[i][0];

int y0 = points[i][1];

int x1 = points[j][0];

int y1 = points[j][1];

if (x0 == x1 || y0 == y1) continue;

int area = abs(x0 - x1) * abs(y0 - y1);

if (area > min_area) continue;

if (!s[x1].count(y0) || !s[x0].count(y1)) continue;

min_area = area;

}

return min_area == INT_MAX ? 0 : min_area;

}

};

C++ / 1D hashtable

// Author: Huahua, 68 ms

class Solution {

public:

int minAreaRect(vector<vector<int>>& points) {

unordered_set<int> s;

for (const auto& point : points)

s.insert((point[0] << 16) | point[1]);

const int n = points.size();

int min_area = INT_MAX;

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

for (int j = i + 1; j < n; ++j) {

int x0 = points[i][0];

int y0 = points[i][1];

int x1 = points[j][0];

int y1 = points[j][1];

if (x0 == x1 || y0 == y1) continue;

int area = abs(x0 - x1) * abs(y0 - y1);

if (area > min_area) continue;

int p0 = (x1 << 16) | y0;

int p1 = (x0 << 16) | y1;

if (!s.count(p0) || !s.count(p1)) continue;

min_area = area;

}

return min_area == INT_MAX ? 0 : min_area;

}

};

花花酱 LeetCode 648. Replace Words

By zxi on November 8, 2018

Problem

https://leetcode.com/problems/replace-words/description/

In English, we have a concept called root, which can be followed by some other words to form another longer word – let’s call this word successor. For example, the root an, followed by other, which can form another word another.

Now, given a dictionary consisting of many roots and a sentence. You need to replace all the successor in the sentence with the root forming it. If a successor has many roots can form it, replace it with the root with the shortest length.

You need to output the sentence after the replacement.

Example 1:

Input: dict = ["cat", "bat", "rat"]
sentence = "the cattle was rattled by the battery"
Output: "the cat was rat by the bat"

Note:

The input will only have lower-case letters.
1 <= dict words number <= 1000
1 <= sentence words number <= 1000
1 <= root length <= 100
1 <= sentence words length <= 1000

Solution 1: HashTable

Time complexity: O(sum(w^2))

Space complexity: O(sum(l))

// Author: Huahua, Running time: 84 ms

class Solution {

public:

string replaceWords(vector<string>& dict, string sentence) {

unordered_set<string> d(begin(dict), end(dict));

sentence.push_back(' ');

string output;

string word;

bool found = false;

for (char c : sentence) {

if (c == ' ') {

if (!output.empty()) output += ' ';

output += word;

word = "";

found = false;

continue;

}

if (found) continue;

word += c;

if (d.count(word)) {

found = true;

}

return output;

}

};

Solution2: Trie

Time complexity: O(sum(l) + n)

Space complexity: O(sum(l) * 26)

// Author: Huahua, running time: 48 ms

class TrieNode {

public:

TrieNode(): children(26), is_word(false) {}

~TrieNode() {

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

if (children[i]) {

delete children[i];

children[i] = nullptr;

}

vector<TrieNode*> children;

bool is_word;

};

class Solution {

public:

string replaceWords(vector<string>& dict, string sentence) {

TrieNode root;

for (const string& word : dict) {

TrieNode* cur = &root;

for (char c : word) {

if (!cur->children[c - 'a']) cur->children[c - 'a'] = new TrieNode();

cur = cur->children[c - 'a'];

}

cur->is_word = true;

}

string ans;

stringstream ss(sentence);

string word;

while (ss >> word) {

TrieNode* cur = &root;

bool found = false;

int len = 0;

for (char c : word) {

cur = cur->children[c - 'a'];

if (!cur) break;

++len;

if (cur->is_word) {

found = true;

break;

}

if (!ans.empty()) ans += ' ';

ans += found ? word.substr(0, len) : word;

}

return ans;

}

};