Algorithms Archives - Page 38 of 43

花花酱 LeetCode 278. First Bad Version

By zxi on March 15, 2018

题目大意：给你一个API查询版本是否坏了，让你找出第一个坏掉的版本。

Problem:

https://leetcode.com/problems/first-bad-version/description/

You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API bool isBadVersion(version) which will return whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

Solution 1: Brute Force

Time Complexity: O(n) TLE

Space Complexity: O(1)

Solution 2: Binary Search

Time Complexity: O(logn)

Space Complexity: O(1)

// Forward declaration of isBadVersion API.

bool isBadVersion(int version);

// Author: Huahua

// Running time: 2 ms

class Solution {

public:

int firstBadVersion(int n) {

int l = 1;

int r = n;

while (l < r) {

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

if (isBadVersion(m))

r = m;

else

l = m + 1;

}

return l;

}

};

花花酱 LeetCode 697. Degree of an Array

By zxi on March 8, 2018

题目大意：求”度”相同的最短子数组的长度。

Problem:

https://leetcode.com/problems/degree-of-an-array/description/

Given a non-empty array of non-negative integers nums, the degree of this array is defined as the maximum frequency of any one of its elements.

Your task is to find the smallest possible length of a (contiguous) subarray of nums, that has the same degree as nums.

Example 1:

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

Output: 2

Explanation:

The input array has a degree of 2 because both elements 1 and 2 appear twice.

Of the subarrays that have the same degree:

[1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2]

The shortest length is 2. So return 2.

Example 2:

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

Solution 1: Hashtable

Time complexity: O(n)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 33 ms (beats 90.96%)

class Solution {

public:

int findShortestSubArray(vector<int>& nums) {

unordered_map<int, vector<int>> indices;

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

indices[nums[i]].push_back(i);

size_t degree = 0;

for (const auto& p : indices)

degree = max(degree, p.second.size());

int ans = nums.size();

for (const auto& p : indices) {

if (p.second.size() != degree) continue;

ans = min(ans, p.second.back() - p.second.front() + 1);

}

return ans;

}

};

花花酱 LeetCode 349. Intersection of Two Arrays

By zxi on March 8, 2018

题目大意：求2个数组的交集。

Problem:

https://leetcode.com/problems/intersection-of-two-arrays/description/

Given two arrays, write a function to compute their intersection.

Example:
Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2].

Note:

Each element in the result must be unique.
The result can be in any order.

C++ using std::set_intersection

// Author: Huahua

// Running time: 8 ms

class Solution {

public:

vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {

vector<int> intersection(max(nums1.size(), nums2.size()));

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

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

// Inputs must be in ascending order

auto it = std::set_intersection(nums1.begin(), nums1.end(), nums2.begin(), nums2.end(), intersection.begin());

intersection.resize(it - intersection.begin());

std::set<int> s(intersection.begin(), intersection.end());

return vector<int>(s.begin(), s.end());

}

};

C++ hashtable

// Author: Huahua

// Running time: 7 ms

class Solution {

public:

vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {

unordered_set<int> m(nums1.begin(), nums1.end());

vector<int> ans;

for (int num : nums2) {

if (!m.count(num)) continue;

ans.push_back(num);

m.erase(num);

}

return ans;

}

};

花花酱 LeetCode 506. Relative Ranks

By zxi on March 8, 2018

题目大意：给你一些人的分数，让你输出他们的排名，前三名输出金银铜牌。

Problem:

Given scores of N athletes, find their relative ranks and the people with the top three highest scores, who will be awarded medals: “Gold Medal”, “Silver Medal” and “Bronze Medal”.

Example 1:

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

Output: ["Gold Medal", "Silver Medal", "Bronze Medal", "4", "5"]

Explanation: The first three athletes got the top three highest scores, so they got "Gold Medal", "Silver Medal" and "Bronze Medal".

For the left two athletes, you just need to output their relative ranks according to their scores.

Note:

N is a positive integer and won’t exceed 10,000.
All the scores of athletes are guaranteed to be unique.

Solution 1: Sorting ( + Binary Search)

C++

class Solution {

public:

vector<string> findRelativeRanks(vector<int>& nums) {

vector<string> ans;

vector<int> s(nums);

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

vector<string> medals{"Gold", "Silver", "Bronze"};

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

int rank = s.end() - std::lower_bound(s.begin(), s.end(), nums[i]);

if (rank <= 3)

ans.push_back(medals[rank - 1] + " Medal");

else

ans.push_back(std::to_string(rank));

}

return ans;

}

};

// Author: Huahua

// Running time: 13 ms

class Solution {

public:

vector<string> findRelativeRanks(vector<int>& nums) {

vector<pair<int, int>> s;

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

s.emplace_back(nums[i], i);

vector<string> medals{"Gold", "Silver", "Bronze"};

std::sort(s.rbegin(), s.rend());

vector<string> ans(nums.size());

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

ans[s[i].second] = i < 3 ? (medals[i] + " Medal") : std::to_string(i + 1);

return ans;

}

};

花花酱 LeetCode 495. Teemo Attacking

By zxi on March 8, 2018

题目大意：给你攻击的时间序列以及中毒的时长，求总共的中毒时间。

Problem:

https://leetcode.com/problems/teemo-attacking/description/

In LOL world, there is a hero called Teemo and his attacking can make his enemy Ashe be in poisoned condition. Now, given the Teemo’s attacking ascending time series towards Ashe and the poisoning time duration per Teemo’s attacking, you need to output the total time that Ashe is in poisoned condition.

You may assume that Teemo attacks at the very beginning of a specific time point, and makes Ashe be in poisoned condition immediately.

Example 1:

Input: [1,4], 2
Output: 4
Explanation: At time point 1, Teemo starts attacking Ashe and makes Ashe be poisoned immediately. 
This poisoned status will last 2 seconds until the end of time point 2. 
And at time point 4, Teemo attacks Ashe again, and causes Ashe to be in poisoned status for another 2 seconds. 
So you finally need to output 4.

Example 2:

Input: [1,2], 2
Output: 3
Explanation: At time point 1, Teemo starts attacking Ashe and makes Ashe be poisoned. 
This poisoned status will last 2 seconds until the end of time point 2. 
However, at the beginning of time point 2, Teemo attacks Ashe again who is already in poisoned status. 
Since the poisoned status won't add up together, though the second poisoning attack will still work at time point 2, it will stop at the end of time point 3. 
So you finally need to output 3.

Note:

You may assume the length of given time series array won’t exceed 10000.
You may assume the numbers in the Teemo’s attacking time series and his poisoning time duration per attacking are non-negative integers, which won’t exceed 10,000,000.

Idea: Running Process

Compare the current attack time with the last one, if span is more than duration, add duration to total, otherwise add (curr – last).

C++

// Author: Huahua

// Running time: 66 ms

class Solution {

public:

int findPoisonedDuration(vector<int>& t, int duration) {

if (t.empty()) return 0;

int total = 0;

for (int i = 1; i < t.size(); ++ i)

total += (t[i] > t[i - 1] + duration ? duration : t[i] - t[i - 1]);

return total + duration;

}

};

Java

// Author: Huahua

// Running time: 9 ms

class Solution {

public int findPoisonedDuration(int[] t, int duration) {

if (t.length == 0) return 0;

int total = 0;

for (int i = 1; i < t.length; ++ i)

total += (t[i] > t[i - 1] + duration ? duration : t[i] - t[i - 1]);

return total + duration;

}

Python3

"""

Author: Huahua

Running time: 64 ms (beats 100%)

"""

class Solution:

def findPoisonedDuration(self, timeSeries, duration):

if not timeSeries: return 0

l = timeSeries[0]

total = 0

for t in timeSeries:

total += duration if t - l > duration else t - l

l = t

return total + duration

import numpy as np

class Solution:

def findPoisonedDuration(self, timeSeries, duration):

if not timeSeries: return 0

d = np.diff(timeSeries)

d = np.clip(d, 0, duration)

return int(np.sum(d) + duration)

class Solution:

def findPoisonedDuration(self, t, duration):

return sum([min(c - l, duration) for l, c in zip(t, t[1:] + [1e9])])

Posts published in “Algorithms”

花花酱 LeetCode 278. First Bad Version

花花酱 LeetCode 697. Degree of an Array

花花酱 LeetCode 349. Intersection of Two Arrays

花花酱 LeetCode 506. Relative Ranks

花花酱 LeetCode 495. Teemo Attacking