Posts tagged as “distance”

花花酱 LeetCode 1437. Check If All 1’s Are at Least Length K Places Away

By zxi on May 3, 2020

Given an array nums of 0s and 1s and an integer k, return True if all 1’s are at least k places away from each other, otherwise return False.

Example 1:

Input: nums = [1,0,0,0,1,0,0,1], k = 2
Output: true
Explanation: Each of the 1s are at least 2 places away from each other.

Example 2:

Input: nums = [1,0,0,1,0,1], k = 2
Output: false
Explanation: The second 1 and third 1 are only one apart from each other.

Example 3:

Input: nums = [1,1,1,1,1], k = 0
Output: true

Example 4:

Input: nums = [0,1,0,1], k = 1
Output: true

Constraints:

1 <= nums.length <= 10^5
0 <= k <= nums.length
nums[i] is 0 or 1

Solution: Scan the array

Only need to check adjacent ones. This problem should be easy instead of medium.

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

C++

// Author: Huahua

class Solution {

public:

bool kLengthApart(vector<int>& nums, int k) {

int d = k + 1; // distant enough

for (int n : nums) {

if (n == 0) {

++d;

} else {

if (d < k) return false;

d = 0;

}

return true;

}

};

花花酱 LeetCode 821. Shortest Distance to a Character

By zxi on April 22, 2018

Problem

题目大意：输出字符串的每个字符到一个指定字符的对短距离。

https://leetcode.com/problems/shortest-distance-to-a-character/description/

Given a string S and a character C, return an array of integers representing the shortest distance from the character C in the string.

Example 1:

Input: S = "loveleetcode", C = 'e'
Output: [3, 2, 1, 0, 1, 0, 0, 1, 2, 2, 1, 0]

Note:

S string length is in [1, 10000].
C is a single character, and guaranteed to be in string S.
All letters in S and C are lowercase.

Solution: Two Pass

Time complexity: O(n)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 14 ms

class Solution {

public:

vector<int> shortestToChar(string S, char C) {

const int n = S.length();

vector<int> ans(n, INT_MAX);

int index = -1;

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

if (S[i] == C) index = i;

if (index < 0) continue;

ans[i] = abs(i - index);

}

index = -1;

for (int i = n - 1; i >= 0; --i) {

if (S[i] == C) index = i;

if (index < 0) continue;

ans[i] = min(ans[i], abs(i - index));

}

return ans;

}

};

// Author: Huahua

// Running time: 14 ms

class Solution {

public:

vector<int> shortestToChar(string S, char C) {

const int n = S.length();

vector<int> indices(2 * n); // 0, 1, ..., n - 1, n - 1, n - 2, ..., 0

std::iota(indices.begin(), indices.begin() + n, 0);

std::iota(indices.rbegin(), indices.rbegin() + n, 0);

vector<int> ans(n, INT_MAX);

int index = -n;

for (int i : indices) {

if (S[i] == C) index = i;

ans[i] = min(ans[i], abs(i - index));

}

return ans;

}

};

花花酱 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 477. Total Hamming Distance

By zxi on December 14, 2017

Problem:

The Hamming distance between two integers is the number of positions at which the corresponding bits are different.

Now your job is to find the total Hamming distance between all pairs of the given numbers.

Example:

Input: 4, 14, 2

Output: 6

Explanation: In binary representation, the 4 is 0100, 14 is 1110, and 2 is 0010 (just

showing the four bits relevant in this case). So the answer will be:

HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.

Note:

Elements of the given array are in the range of 0 to 10^9
Length of the array will not exceed 10^4.

题目大意：给你一堆数，让你求所有数对的HammingDistance的总和。

Idea:

Brute force, compute HammingDistance for all pairs. O(n^2) TLE
Count how many ones on i-th bit, assuming k. Distance += k * (n – k). O(n)

Solution:

C++ / O(n)

// Author: Huahua

// Runtime: 59 ms

class Solution {

public:

int totalHammingDistance(vector<int>& nums) {

int ans = 0;

int mask = 1;

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

int count = 0;

for (const int num : nums)

if (num & mask) ++count;

ans += (nums.size() - count) * count;

mask <<= 1;

}

return ans;

}

};

花花酱 LeetCode 719. Find K-th Smallest Pair Distance

By zxi on October 29, 2017

题目大意：给你一个数组，返回所有数对中，绝对值差第k小的值。

Problem:

Given an integer array, return the k-th smallest distance among all the pairs. The distance of a pair (A, B) is defined as the absolute difference between A and B.

Example 1:

Input:

nums = [1,3,1]

k = 1

Output: 0

Explanation:

Here are all the pairs:

(1,3) -> 2

(1,1) -> 0

(3,1) -> 2

Then the 1st smallest distance pair is (1,1), and its distance is 0.

Note:

2 <= len(nums) <= 10000.
0 <= nums[i] < 1000000.
1 <= k <= len(nums) * (len(nums) - 1) / 2.

Idea

Bucket sort

Binary search / dp

Solution

C++ / binary search

// Author: Huahua

// Runtime: 9 ms

class Solution {

public:

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

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

int n = nums.size();

int l = 0;

int r = nums.back() - nums.front();

while (l <= r) {

int cnt = 0;

int j = 0;

int m = l + (r - l) / 2;

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

while (j < n && nums[j] - nums[i] <= m) ++j;

cnt += j - i - 1;

}

cnt >= k ? r = m - 1 : l = m + 1;

}

return l;

}

};

C++ / bucket sort w/ vector O(n^2)

// Author: Huahua

// Runtime: 549 ms

class Solution {

public:

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

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

const int N = nums.back();

vector<int> count(N + 1, 0);

const int n = nums.size();

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

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

++count[nums[j] - nums[i]];

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

k -= count[i];

if (k <= 0) return i;

}

return 0;

}

};

Related Problems: