Posts tagged as “hashtable”

花花酱 LeetCode 525. Contiguous Array

By zxi on June 30, 2018

Problem

题目大意：求最长子数组，要求其中0和1的数量相等。

Given a binary array, find the maximum length of a contiguous subarray with equal number of 0 and 1.

Example 1:

Input: [0,1]
Output: 2
Explanation: [0, 1] is the longest contiguous subarray with equal number of 0 and 1.

Example 2:

Input: [0,1,0]
Output: 2
Explanation: [0, 1] (or [1, 0]) is a longest contiguous subarray with equal number of 0 and 1.

Note: The length of the given binary array will not exceed 50,000.

Solution: HashTable

Prefix sum + hashtable

Time complexity: O(n)

Space complexity: O(n)

// Author: Huahua

// Running time: 143 ms

class Solution {

public:

int findMaxLength(vector<int>& nums) {

if (nums.empty()) return 0;

unordered_map<int, int> pos;

int sum = 0;

int ans = 0;

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

sum += nums[i] ? 1 : -1;

if (sum == 0) {

ans = i + 1;

} else if (pos.count(sum)) {

ans = max(ans, i - pos[sum]);

} else {

pos[sum] = i;

}

return ans;

}

};

V2: Using array instead of a hashtable

Time complexity: O(2*n + 1 + n)

Space complexity: O(2*n + 1)

// Author: Huahua

// Running time: 102 ms (<96.8 %)

class Solution {

public:

int findMaxLength(vector<int>& nums) {

if (nums.empty()) return 0;

const int n = nums.size();

vector<int> pos(2 * n + 1, INT_MIN);

int sum = 0;

int ans = 0;

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

sum += nums[i] ? 1 : -1;

if (sum == 0) {

ans = i + 1;

} else if (pos[sum + n] != INT_MIN) {

ans = max(ans, i - pos[sum + n]);

} else {

pos[sum + n] = i;

}

return ans;

}

};

花花酱 LeetCode 567. Permutation in String

By zxi on June 28, 2018

Problem

题目大意：给你s1, s2，问你s2的子串中是否存在s1的一个排列。

https://leetcode.com/problems/permutation-in-string/description/

Given two strings s1 and s2, write a function to return true if s2 contains the permutation of s1. In other words, one of the first string’s permutations is the substring of the second string.

Example 1:

Input:s1 = "ab" s2 = "eidbaooo"
Output:True
Explanation: s2 contains one permutation of s1 ("ba").

Example 2:

Input:s1= "ab" s2 = "eidboaoo"
Output: False

Note:

The input strings only contain lower case letters.
The length of both given strings is in range [1, 10,000].

Solution: Sliding Window

Time Complexity: O(l1 + l2 * 26) = O(l1 + l2)

Space Complexity: O(26 * 2) = O(1)

C++

// Author: Huahua

// Running time: 12 ms

class Solution {

public:

bool checkInclusion(string s1, string s2) {

int l1 = s1.length();

int l2 = s2.length();

vector<int> c1(26);

vector<int> c2(26);

for (const char c : s1)

++c1[c - 'a'];

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

if (i >= l1)

--c2[s2[i - l1] - 'a'];

++c2[s2[i] - 'a'];

if (c1 == c2) return true;

}

return false;

}

};

Problem

Given two strings A and B of lowercase letters, return true if and only if we can swap two letters in A so that the result equals B.

Example 1:

Input: A = "ab", B = "ba"
Output: true

Example 2:

Input: A = "ab", B = "ab"
Output: false

Example 3:

Input: A = "aa", B = "aa"
Output: true

Example 4:

Input: A = "aaaaaaabc", B = "aaaaaaacb"
Output: true

Example 5:

Input: A = "", B = "aa"
Output: false

Note:

0 <= A.length <= 20000
0 <= B.length <= 20000
A and B consist only of lowercase letters.

Solution: HashTable

Time complexity: O(n)

Space complexity: O(26)

// Author: Huahua

// Running time: 7 ms

class Solution {

public:

bool buddyStrings(string A, string B) {

if (A.length() != B.length()) return false;

vector<int> ca(26);

vector<int> cb(26);

int diff = 0;

for (int i = 0; i < A.length(); ++i) {

if (A[i] != B[i] && diff++ > 2) return false;

++ca[A[i]-'a'];

++cb[B[i]-'a'];

}

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

if (diff == 0 && ca[i] > 1) return true;

if (ca[i] != cb[i]) return false;

}

return diff == 2;

}

};

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

}

};

Posts tagged as “hashtable”

花花酱 LeetCode 525. Contiguous Array

Problem

Solution: HashTable

花花酱 LeetCode 567. Permutation in String

Problem

Solution: Sliding Window

Related Problems

花话酱 LeetCode 859. Buddy Strings

Problem

Solution: HashTable

花花酱 LeetCode 825. Friends Of Appropriate Ages

Problem

Solution: Hashtable

花花酱 LeetCode 822. Card Flipping Game

Problem

Solution: Hashset