Huahua’s Tech Road

花花酱 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])])

花花酱 LeetCode 521. Longest Uncommon Subsequence I

By zxi on March 7, 2018

题目大意：求2个字符串最长的不同子序列的长度。

Problem:

https://leetcode.com/problems/longest-uncommon-subsequence-i/description/

Given a group of two strings, you need to find the longest uncommon subsequence of this group of two strings. The longest uncommon subsequence is defined as the longest subsequence of one of these strings and this subsequence should not be any subsequence of the other strings.

A subsequence is a sequence that can be derived from one sequence by deleting some characters without changing the order of the remaining elements. Trivially, any string is a subsequence of itself and an empty string is a subsequence of any string.

The input will be two strings, and the output needs to be the length of the longest uncommon subsequence. If the longest uncommon subsequence doesn’t exist, return -1.

Example 1:

Input: "aba", "cdc"

Output: 3

Explanation: The longest uncommon subsequence is "aba" (or "cdc"),

because "aba" is a subsequence of "aba",

but not a subsequence of any other strings in the group of two strings.

Note:

Both strings’ lengths will not exceed 100.
Only letters from a ~ z will appear in input strings.

Idea:

If two strings are the same, then the longest uncommon sequence does not exist, return -1.

e.g. aaa vs aaa, return -1

Otherwise, the longer string is always a uncommon sequence of the shorter one.

e.g. aaab vs aaa, return 4

Solution 1:

Time complexity: O(n)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 3 ms

class Solution {

public:

int findLUSlength(string a, string b) {

return a == b ? -1 : max(a.length(), b.length());

}

};

Java

// Author: Huahua

// Running time: 3 ms

class Solution {

public int findLUSlength(String a, String b) {

return a.equals(b) ? -1 : Math.max(a.length(), b.length());

}

Python3

"""

Author: Huahua

Running time: 40 ms (beats 100%)

Website: http://zxi.mytechroad.com/blog/string/leetcode-521-longest-uncommon-subsequence-i/

"""

class Solution:

def findLUSlength(self, a, b):

la, lb = len(a), len(b)

if la != lb: return max(la, lb)

return -1 if a == b else la

Huahua's Tech Road

花花酱 LeetCode 697. Degree of an Array

花花酱 LeetCode 349. Intersection of Two Arrays

花花酱 LeetCode 506. Relative Ranks

花花酱 LeetCode 495. Teemo Attacking

花花酱 LeetCode 521. Longest Uncommon Subsequence I