Posts published in “Hashtable”

花花酱 LeetCode 561. Array Partition I

By zxi on August 16, 2018

Problem

Given an array of 2n integers, your task is to group these integers into n pairs of integer, say (a₁, b₁), (a₂, b₂), …, (a_n, b_n) which makes sum of min(a_i, b_i) for all i from 1 to n as large as possible.

Example 1:

Input: [1,4,3,2]

Output: 4
Explanation: n is 2, and the maximum sum of pairs is 4 = min(1, 2) + min(3, 4).

Note:

n is a positive integer, which is in the range of [1, 10000].
All the integers in the array will be in the range of [-10000, 10000].

Solution 1: Sorting

Time complexity: O(nlogn)

Space complexity: O(1)

// Author: Huahua

// Running time: 52 ms

class Solution {

public:

int arrayPairSum(vector<int>& nums) {

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

int ans = 0;

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

ans += nums[i];

return ans;

}

};

Solution 2: HashTable

Time complexity: O(n + max(nums) – min(nums))

Space complexity: O(max(nums) – min(nums))

// Author: Huahua

// Running time: 39 ms

class Solution {

public:

int arrayPairSum(vector<int>& nums) {

const int max_val = *max_element(begin(nums), end(nums));

const int min_val = *min_element(begin(nums), end(nums));

const int offset = -min_val;

vector<int> c(max_val - min_val + 1);

for (int num : nums)

++c[num + offset];

int ans = 0;

int index = 0;

int n = min_val;

while (n <= max_val) {

if (c[n + offset] == 0) {

++n;

continue;

}

ans += (++index & 1) ? n : 0;

--c[n + offset];

}

return ans;

}

};

花花酱 LeetCode 888. Uncommon Words from Two Sentences

By zxi on August 12, 2018

Problem

We are given two sentences A and B. (A sentence is a string of space separated words. Each word consists only of lowercase letters.)

A word is uncommon if it appears exactly once in one of the sentences, and does not appear in the other sentence.

Return a list of all uncommon words.

You may return the list in any order.

Example 1:

Input: A = "this apple is sweet", B = "this apple is sour"
Output: ["sweet","sour"]

Example 2:

Input: A = "apple apple", B = "banana"
Output: ["banana"]

Note:

0 <= A.length <= 200
0 <= B.length <= 200
A and B both contain only spaces and lowercase letters.

Solution: HashTable

Time complexity: O(m+n)

Space complexity: O(m+n)

C++

class Solution {

public:

vector<string> uncommonFromSentences(string A, string B) {

istringstream ss(A + " " + B);

unordered_map<string, int> counts;

string s;

while (ss >> s) ++counts[s];

vector<string> ans;

for (const auto& p : counts)

if (p.second == 1)

ans.push_back(p.first);

return ans;

}

};

花花酱 LeetCode 874. Walking Robot Simulation

By zxi on July 22, 2018

Problem

A robot on an infinite grid starts at point (0, 0) and faces north. The robot can receive one of three possible types of commands:

-2: turn left 90 degrees
-1: turn right 90 degrees
1 <= x <= 9: move forward x units

Some of the grid squares are obstacles.

The i-th obstacle is at grid point (obstacles[i][0], obstacles[i][1])

If the robot would try to move onto them, the robot stays on the previous grid square instead (but still continues following the rest of the route.)

Return the square of the maximum Euclidean distance that the robot will be from the origin.

Example 1:

Input: commands = [4,-1,3], obstacles = []
Output: 25
Explanation: robot will go to (3, 4)

Example 2:

Input: commands = [4,-1,4,-2,4], obstacles = [[2,4]]
Output: 65
Explanation: robot will be stuck at (1, 4) before turning left and going to (1, 8)

Note:

0 <= commands.length <= 10000
0 <= obstacles.length <= 10000
-30000 <= obstacle[i][0] <= 30000
-30000 <= obstacle[i][1] <= 30000
The answer is guaranteed to be less than 2 ^ 31.

Solution: Simulation

Time complexity: O(n + sum(x)) = O(n)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 60 ms

class Solution {

public:

int robotSim(vector<int>& commands, vector<vector<int>>& obstacles) {

int x = 0;

int y = 0;

int dirs[][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; // WNES

int d = 1;

unordered_map<int, unordered_set<int>> o;

for (const auto obstacle : obstacles)

o[obstacle[0]].insert(obstacle[1]);

int ans = 0;

for (int c : commands) {

if (c == -2)

d = (d - 1 + 4) % 4;

else if (c == -1)

d = (d + 1) % 4;

else {

while (c--) {

int tx = x + dirs[d][0];

int ty = y + dirs[d][1];

if (o.count(tx) && o.at(tx).count(ty))

break;

x = tx;

y = ty;

ans = max(ans, x * x + y * y);

}

return ans;

}

};

花花酱 LeetCode 873. Length of Longest Fibonacci Subsequence

By zxi on July 22, 2018

Problem

A sequence X_1, X_2, ..., X_n is fibonacci-like if:

n >= 3
X_i + X_{i+1} = X_{i+2} for all i + 2 <= n

Given a strictly increasing array A of positive integers forming a sequence, find the length of the longest fibonacci-like subsequence of A. If one does not exist, return 0.

(Recall that a subsequence is derived from another sequence A by deleting any number of elements (including none) from A, without changing the order of the remaining elements. For example, [3, 5, 8] is a subsequence of [3, 4, 5, 6, 7, 8].)

Example 1:

Input: [1,2,3,4,5,6,7,8]
Output: 5
Explanation:
The longest subsequence that is fibonacci-like: [1,2,3,5,8].

Example 2:

Input: [1,3,7,11,12,14,18]
Output: 3
Explanation:
The longest subsequence that is fibonacci-like:
[1,11,12], [3,11,14] or [7,11,18].

Note:

3 <= A.length <= 1000
1 <= A[0] < A[1] < ... < A[A.length - 1] <= 10^9
(The time limit has been reduced by 50% for submissions in Java, C, and C++.)

Solution 1: DP

C++

// Author: Huahua

// Running time: 68 ms

// w/ Hashtable

// Time complexity: O(n^2)

// Space complexity: O(n^2)

class Solution {

public:

int lenLongestFibSubseq(vector<int>& A) {

const int n = A.size();

unordered_map<int, int> m;

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

m[A[i]] = i;

vector<vector<int>> dp(n, vector<int>(n, 2));

int ans = 0;

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

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

int a_i = A[k] - A[j];

if (a_i >= A[j]) break; // pruning 168 ms -> 68 ms

auto it = m.find(a_i);

if (it == end(m)) continue;

int i = it->second;

dp[j][k] = dp[i][j] + 1;

ans = max(ans, dp[j][k]);

}

return ans;

}

};

C++ V2

// Author: Huahua

// Running time: 96 ms

// w / Binary Search

// Time complexity: O(n^2logn)

// Space complexity: O(n)

class Solution {

public:

int lenLongestFibSubseq(vector<int>& A) {

const int n = A.size();

vector<vector<int>> dp(n, vector<int>(n, 2));

int ans = 0;

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

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

int a_i = A[k] - A[j];

if (a_i >= A[j]) break;

auto it = lower_bound(begin(A), begin(A) + j, a_i);

int i = it - begin(A);

if (A[i] != a_i) continue;

dp[j][k] = dp[i][j] + 1;

ans = max(ans, dp[j][k]);

}

return ans;

}

};

Solution 2: HashTable

Time complexity: O(n^3)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 172 ms

class Solution {

public:

int lenLongestFibSubseq(vector<int>& A) {

const int n = A.size();

unordered_set<int> m(begin(A), end(A));

int ans = 0;

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

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

int a = A[i];

int b = A[j];

int c = a + b;

int l = 2;

while (m.count(c)) {

a = b;

b = c;

c = a + b;

ans = max(ans, ++l);

}

return ans;

}

};

花花酱 LeetCode 869. Reordered Power of 2

By zxi on July 14, 2018

Problem

Starting with a positive integer N, we reorder the digits in any order (including the original order) such that the leading digit is not zero.

Return true if and only if we can do this in a way such that the resulting number is a power of 2.

Example 1:

Input: 1
Output: true

Example 2:

Input: 10
Output: false

Example 3:

Input: 16
Output: true

Example 4:

Input: 24
Output: false

Example 5:

1 2	<strong>Input: </strong><span id="example-input-5-1">46</span> <strong>Output: </strong><span id="example-output-5">true</span>

Note:

1 <= N <= 10^9

Solution: HashTable

Compare the counter of digit string with that of all power of 2s.

e.g. 64 -> {4: 1, 6: 1} == 46 {4:1, 6: 1}

Time complexity: O(1)

Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

bool reorderedPowerOf2(int N) {

auto m = countMap(N);

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

if (m == countMap(1 << i)) return true;

return false;

}

private:

map<int, int> countMap(int n) {

map<int, int> m;

while (n) {

++m[n % 10];

n /= 10;

}

return m;

}

};

Posts published in “Hashtable”

花花酱 LeetCode 561. Array Partition I

Problem

Solution 1: Sorting

Solution 2: HashTable

花花酱 LeetCode 888. Uncommon Words from Two Sentences

Problem

Solution: HashTable

花花酱 LeetCode 874. Walking Robot Simulation

Problem

Solution: Simulation

花花酱 LeetCode 873. Length of Longest Fibonacci Subsequence

Problem

<img class="alignnone size-full wp-image-3274" src="http://zxi.mytechroad.com/blog/wp-content/uploads/2018/07/873-ep210.png" alt="" width="960" height="540"/>

Solution 1: DP

C++

C++ V2

Solution 2: HashTable

C++

花花酱 LeetCode 869. Reordered Power of 2

Problem

Solution: HashTable