Posts tagged as “easy”

花花酱 LeetCode 812. Largest Triangle Area

By zxi on April 8, 2018

Problem

题目大意：给你一些点，求用这些点能够成的最大的三角形面积是多少？

https://leetcode.com/problems/largest-triangle-area/description/

You have a list of points in the plane. Return the area of the largest triangle that can be formed by any 3 of the points.

Example:
Input: points = [[0,0],[0,1],[1,0],[0,2],[2,0]]
Output: 2
Explanation: 
The five points are show in the figure below. The red triangle is the largest.

Notes:

3 <= points.length <= 50.
No points will be duplicated.
-50 <= points[i][j] <= 50.
Answers within 10^-6 of the true value will be accepted as correct.

Solution: Brute Force

Time complexity: O(n^3)

Space complexity: O(1)

// Author: Huahua

// Running time: 11 ms

class Solution {

public:

double largestTriangleArea(vector<vector<int>>& points) {

const int n = points.size();

double best = 0.0;

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

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

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

const double a = dist(points[i], points[j]);

const double b = dist(points[i], points[k]);

const double c = dist(points[j], points[k]);

const double s = (a + b + c) / 2;

const double area = sqrt(s * (s - a) * (s - b) * (s - c));

best = max(best, area);

}

return best;

}

private:

static inline double dist(const vector<int>& p1, const vector<int>& p2) {

return sqrt((p1[0] - p2[0]) * (p1[0] - p2[0]) + (p1[1] - p2[1]) * (p1[1] - p2[1]));

}

};

花花酱 LeetCode 453. Minimum Moves to Equal Array Elements

By zxi on April 5, 2018

Problem

题目大意：给你一个数组，每次可以把其中n-1个数加1，问最少需要多少次操作可以使得数组中的元素都相等。

https://leetcode.com/problems/minimum-moves-to-equal-array-elements/description/

Given a non-empty integer array of size n, find the minimum number of moves required to make all array elements equal, where a move is incrementing n – 1 elements by 1.

Example:

Input:
[1,2,3]

Output:
3

Explanation:
Only three moves are needed (remember each move increments two elements):

[1,2,3]  =>  [2,3,3]  =>  [3,4,3]  =>  [4,4,4]

Idea

Assuming the sum of array is S, the minimum element of the array is min and minimum number of moves is m.

Each move will increase the sum of array by n – 1. Finally, every element becomes x. So we have:

S + (n – 1) * m = x * n
min + m = x

We got: m = S – n * min

Solution: Math

Time complexity: O(n)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 51 ms

class Solution {

public:

int minMoves(const vector<int>& a) {

return accumulate(a.begin(), a.end(), 0L) - a.size() * *min_element(a.begin(), a.end());

}

};

Python

"""

Author: Huahua

Running time: 104 ms

"""

class Solution:

def minMoves(self, nums):

return sum(nums) - len(nums) * min(nums)

花花酱 LeetCode 599. Minimum Index Sum of Two Lists

By zxi on April 2, 2018

Problem

Suppose Andy and Doris want to choose a restaurant for dinner, and they both have a list of favorite restaurants represented by strings.

You need to help them find out their common interest with the least list index sum. If there is a choice tie between answers, output all of them with no order requirement. You could assume there always exists an answer.

Example 1:

Input:
["Shogun", "Tapioca Express", "Burger King", "KFC"]
["Piatti", "The Grill at Torrey Pines", "Hungry Hunter Steakhouse", "Shogun"]
Output: ["Shogun"]
Explanation: The only restaurant they both like is "Shogun".

Example 2:

Input:
["Shogun", "Tapioca Express", "Burger King", "KFC"]
["KFC", "Shogun", "Burger King"]
Output: ["Shogun"]
Explanation: The restaurant they both like and have the least index sum is "Shogun" with index sum 1 (0+1).

Note:

The length of both lists will be in the range of [1, 1000].
The length of strings in both lists will be in the range of [1, 30].
The index is starting from 0 to the list length minus 1.
No duplicates in both lists.

Solution

Time complexity: O(n+m)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 103 ms

class Solution {

public:

vector<string> findRestaurant(vector<string>& list1, vector<string>& list2) {

unordered_map<string, int> indices;

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

indices[list1[i]] = i;

vector<string> ans;

int best_index = INT_MAX;

string best;

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

if (!indices.count(list2[i])) continue;

int index = indices[list2[i]] + i;

if (index < best_index) ans.clear();

if (index <= best_index) {

best_index = index;

ans.push_back(list2[i]);

}

return ans;

}

};

花花酱 LeetCode 811. Subdomain Visit Count

By zxi on April 1, 2018

Problem

A website domain like “discuss.leetcode.com” consists of various subdomains. At the top level, we have “com”, at the next level, we have “leetcode.com”, and at the lowest level, “discuss.leetcode.com”. When we visit a domain like “discuss.leetcode.com”, we will also visit the parent domains “leetcode.com” and “com” implicitly.

Now, call a “count-paired domain” to be a count (representing the number of visits this domain received), followed by a space, followed by the address. An example of a count-paired domain might be “9001 discuss.leetcode.com”.

We are given a list cpdomains of count-paired domains. We would like a list of count-paired domains, (in the same format as the input, and in any order), that explicitly counts the number of visits to each subdomain.

Example 1:
Input: 
["9001 discuss.leetcode.com"]
Output: 
["9001 discuss.leetcode.com", "9001 leetcode.com", "9001 com"]
Explanation: 
We only have one website domain: "discuss.leetcode.com". As discussed above, the subdomain "leetcode.com" and "com" will also be visited. So they will all be visited 9001 times.

Example 2:
Input: 
["900 google.mail.com", "50 yahoo.com", "1 intel.mail.com", "5 wiki.org"]
Output: 
["901 mail.com","50 yahoo.com","900 google.mail.com","5 wiki.org","5 org","1 intel.mail.com","951 com"]
Explanation: 
We will visit "google.mail.com" 900 times, "yahoo.com" 50 times, "intel.mail.com" once and "wiki.org" 5 times. For the subdomains, we will visit "mail.com" 900 + 1 = 901 times, "com" 900 + 50 + 1 = 951 times, and "org" 5 times.

Notes:

The length of cpdomains will not exceed 100.
The length of each domain name will not exceed 100.
Each address will have either 1 or 2 “.” characters.
The input count in any count-paired domain will not exceed 10000.

Solution: HashTable

Time complexity: O(n)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 16 ms

class Solution {

public:

vector<string> subdomainVisits(vector<string>& cpdomains) {

unordered_map<string, int> counts;

for (const string& cpdomain : cpdomains) {

size_t index = cpdomain.find(' ');

int count = std::stoi(cpdomain.substr(0, index));

string domain = cpdomain.substr(index + 1);

while (true) {

counts[domain] += count;

size_t i = domain.find('.');

if (i == string::npos) break;

domain = domain.substr(i + 1);

}

vector<string> ans;

for (const auto& kv : counts)

ans.push_back(std::to_string(kv.second) + " " + kv.first);

return ans;

}

};

花花酱 LeetCode 806. Number of Lines To Write String

By zxi on March 24, 2018

Problem

题目大意：给你每个字母的宽度，以及一个字符串。问一共需要多少行和多少列才能把这个字符串打印出来。将设每行的宽度是100。

We are to write the letters of a given string S, from left to right into lines. Each line has maximum width 100 units, and if writing a letter would cause the width of the line to exceed 100 units, it is written on the next line. We are given an array widths, an array where widths[0] is the width of ‘a’, widths[1] is the width of ‘b’, …, and widths[25] is the width of ‘z’.

Now answer two questions: how many lines have at least one character from S, and what is the width used by the last such line? Return your answer as an integer list of length 2.

Example :
Input: 
widths = [10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10]
S = "abcdefghijklmnopqrstuvwxyz"
Output: [3, 60]
Explanation: 
All letters have the same length of 10. To write all 26 letters,
we need two full lines and one line with 60 units.

Example :
Input: 
widths = [4,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10]
S = "bbbcccdddaaa"
Output: [2, 4]
Explanation: 
All letters except 'a' have the same length of 10, and 
"bbbcccdddaa" will cover 9 * 10 + 2 * 4 = 98 units.
For the last 'a', it is written on the second line because
there is only 2 units left in the first line.
So the answer is 2 lines, plus 4 units in the second line.

Note:

The length of S will be in the range [1, 1000].
S will only contain lowercase letters.
widths is an array of length 26.
widths[i] will be in the range of [2, 10].

Solution: Simulation

Time Complexity: O(n)

Space Complexity: O(1)

// Author: Huahua

class Solution {

public:

vector<int> numberOfLines(vector<int>& widths, string S) {

int lines = 1;

int units = 0;

for (char c : S) {

if (units + widths[c - 'a'] > 100) {

++lines;

units = 0;

}

units += widths[c - 'a'];

}

return {lines, units};

}

};