Posts tagged as “hashtable”

花花酱 LeetCode 447. Number of Boomerangs

By zxi on March 24, 2018

Problem

Given n points in the plane that are all pairwise distinct, a “boomerang” is a tuple of points (i, j, k) such that the distance between i and j equals the distance between i and k (the order of the tuple matters).

Find the number of boomerangs. You may assume that n will be at most 500 and coordinates of points are all in the range [-10000, 10000] (inclusive).

Example:

Input:
[[0,0],[1,0],[2,0]]

Output:
2

Explanation:
The two boomerangs are [[1,0],[0,0],[2,0]] and [[1,0],[2,0],[0,0]]

Solution: HashTable

For each point, compute the distance to the rest of the points and count.

if there are k points that have the same distance to current point, then there are P(k,2) = k*k-1 Boomerangs.

for example, p1, p2, p3 have the same distance to p0, then there are P(3,2) = 3 * (3-1) = 6 Boomerangs

(p1, p0, p2), (p1, p0, p3)

(p2, p0, p1), (p2, p0, p3)

(p3, p0, p1), (p3, p0, p2)

C++

// Author: Huahua

// Running time: 210 ms (beats 83.33%)

class Solution {

public:

int numberOfBoomerangs(vector<pair<int, int>>& points) {

int ans = 0;

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

unordered_map<int, int> dist(points.size());

for (int j = 0; j < points.size(); ++j) {

const int dx = points[i].first - points[j].first;

const int dy = points[i].second - points[j].second;

++dist[dx * dx + dy * dy];

}

for (const auto& kv : dist)

ans += kv.second * (kv.second - 1);

}

return ans;

}

};

Solution 2: Sorting

dist = [1, 2, 1, 2, 1, 5]

sorted_dist = [1, 1, 1, 2, 2, 5], 1*3, 2*2, 5*1

ans = 3*(3-1) + 2 * (2 – 1) * 1 * (1 – 1) = 8

Time complexity: O(n*nlogn)

Space complexity: O(n)

// Author: Huahua

// Running time: 150 ms (beats 98.52%)

class Solution {

public:

int numberOfBoomerangs(vector<pair<int, int>>& points) {

const int n = points.size();

int ans = 0;

vector<int> dist(points.size());

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

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

const int dx = points[i].first - points[j].first;

const int dy = points[i].second - points[j].second;

dist[j] = dx * dx + dy * dy;

}

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

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

int k = 1;

while (j < n && dist[j] == dist[j - 1]) { ++j; ++k; }

ans += k * (k - 1);

}

return ans;

}

};

花花酱 LeetCode 560. Subarray Sum Equals K

By zxi on March 22, 2018

Problem

题目大意：给你一个数组，问有多少子数组的和为k。

https://leetcode.com/problems/subarray-sum-equals-k/description/

Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k.

Example 1:

Input:nums = [1,1,1], k = 2
Output: 2

Note:

The length of the array is in range [1, 20,000].
The range of numbers in the array is [-1000, 1000] and the range of the integer k is [-1e7, 1e7].

Solution -1: Brute Force

For every pair of i,j, check sum(nums[i:j]) in O(j-i) = O(n)

Time complexity: O(n^3) TLE

Space complexity: O(1)

Solution 0: Brute Force + Prefix sun

Precompute the prefix sum and check sum of nums[i:j] in O(1)

Time complexity: O(n^2)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 490 ms

class Solution {

public:

int subarraySum(vector<int>& nums, int k) {

const int n = nums.size();

vector<int> sums(n + 1, 0);

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

sums[i] = sums[i - 1] + nums[i - 1];

int ans = 0;

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

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

if (sums[j + 1] - sums[i] == k) ++ans;

return ans;

}

};

Solution 1: Running Prefix sum

Keep tracking the prefix sums and their counts.

s -> count: how many arrays nums[0:j] (j < i) that has sum of s

cur_sum = sum(nums[0:i])

check how many arrays nums[0:j] (j < i) that has sum (cur_sum – k)

then there are the same number of arrays nums[j+1: i] that have sum k.

Time complexity: O(n)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 36 ms

class Solution {

public:

int subarraySum(vector<int>& nums, int k) {

if (nums.empty()) return 0;

unordered_map<int, int> counts{{0,1}};

int cur_sum = 0;

int ans = 0;

for (const int num : nums) {

cur_sum += num;

ans += counts[cur_sum - k];

++counts[cur_sum];

}

return ans;

}

};

花花酱 LeetCode 554. Brick Wall

By zxi on March 22, 2018

Problem

https://leetcode.com/problems/brick-wall/description/

题目大意：从小到下切一刀，最少会切到多少块砖。

There is a brick wall in front of you. The wall is rectangular and has several rows of bricks. The bricks have the same height but different width. You want to draw a vertical line from the top to the bottom and cross the least bricks.

The brick wall is represented by a list of rows. Each row is a list of integers representing the width of each brick in this row from left to right.

If your line go through the edge of a brick, then the brick is not considered as crossed. You need to find out how to draw the line to cross the least bricks and return the number of crossed bricks.

You cannot draw a line just along one of the two vertical edges of the wall, in which case the line will obviously cross no bricks.

Example:

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

Note:

The width sum of bricks in different rows are the same and won’t exceed INT_MAX.
The number of bricks in each row is in range [1,10,000]. The height of wall is in range [1,10,000]. Total number of bricks of the wall won’t exceed 20,000.

Solution: HashTable

Count boundaries, cut at the location with most common boundaries.

Time complexity: O(|bricks|)

Space complexity: O(|bricks|)

C++

// Author: Huahua

// Running time: 42 ms

class Solution {

public:

int leastBricks(vector<vector<int>>& wall) {

unordered_map<int, int> count;

int max_count = 0;

for (const auto& bricks : wall) {

int s = 0;

for (int i = 0; i < bricks.size() - 1; ++i) {

s += bricks[i];

max_count = max(max_count, ++count[s]);

}

return wall.size() - max_count;

}

};

花花酱 LeetCode 609. Find Duplicate File in System

By zxi on March 20, 2018

Problem

https://leetcode.com/problems/find-duplicate-file-in-system/description/

题目大意：输出系统中文件内容相同的文件名。

Given a list of directory info including directory path, and all the files with contents in this directory, you need to find out all the groups of duplicate files in the file system in terms of their paths.

A group of duplicate files consists of at least two files that have exactly the same content.

A single directory info string in the input list has the following format:

"root/d1/d2/.../dm f1.txt(f1_content) f2.txt(f2_content) ... fn.txt(fn_content)"

It means there are n files (f1.txt, f2.txt … fn.txt with content f1_content, f2_content … fn_content, respectively) in directory root/d1/d2/.../dm. Note that n >= 1 and m >= 0. If m = 0, it means the directory is just the root directory.

The output is a list of group of duplicate file paths. For each group, it contains all the file paths of the files that have the same content. A file path is a string that has the following format:

"directory_path/file_name.txt"

Example 1:

Input:
["root/a 1.txt(abcd) 2.txt(efgh)", "root/c 3.txt(abcd)", "root/c/d 4.txt(efgh)", "root 4.txt(efgh)"]
Output:  
[["root/a/2.txt","root/c/d/4.txt","root/4.txt"],["root/a/1.txt","root/c/3.txt"]]

Note:

No order is required for the final output.
You may assume the directory name, file name and file content only has letters and digits, and the length of file content is in the range of [1,50].
The number of files given is in the range of [1,20000].
You may assume no files or directories share the same name in the same directory.
You may assume each given directory info represents a unique directory. Directory path and file info are separated by a single blank space.

Follow-up beyond contest:

Imagine you are given a real file system, how will you search files? DFS or BFS?
If the file content is very large (GB level), how will you modify your solution?
If you can only read the file by 1kb each time, how will you modify your solution?
What is the time complexity of your modified solution? What is the most time-consuming part and memory consuming part of it? How to optimize?
How to make sure the duplicated files you find are not false positive?

Solution: HashTable

Key: content, Value: Array of filenames

Time complexity: O(n)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 80ms (beats 94.68%)

class Solution {

public:

vector<vector<string>> findDuplicate(vector<string>& paths) {

unordered_map<string, vector<string>> files; // content -> filenames

for (const string& path : paths) {

string folder;

int i = 0;

while (path[i] != ' ') folder += path[i++];

while (i < path.length()) {

string filename;

string content;

++i; // ' '

while (path[i] != '(') filename += path[i++];

++i; // '('

while (path[i] != ')') content += path[i++];

++i; // ')'

files[content].push_back(folder + "/" + filename);

}

vector<vector<string>> ans;

for (auto& kv : files)

if (kv.second.size() > 1)

ans.push_back(std::move(kv.second));

return ans;

}

};

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

}

};