Huahua’s Tech Road

花花酱 LeetCode 1447. Simplified Fractions

By zxi on May 17, 2020

Given an integer n, return a list of all simplified fractions between 0 and 1 (exclusive) such that the denominator is less-than-or-equal-to n. The fractions can be in any order.

Example 1:

Input: n = 2
Output: ["1/2"]
Explanation: "1/2" is the only unique fraction with a denominator less-than-or-equal-to 2.

Example 2:

Input: n = 3
Output: ["1/2","1/3","2/3"]

Example 3:

Input: n = 4
Output: ["1/2","1/3","1/4","2/3","3/4"]
Explanation: "2/4" is not a simplified fraction because it can be simplified to "1/2".

Example 4:

Input: n = 1
Output: []

Constraints:

1 <= n <= 100

Solution: GCD

if gcd(a, b) == 1 then a/b is a simplified frication.

std::gcd is available since c++17.

Time complexity: O(n^2logn)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

vector<string> simplifiedFractions(int n) {

vector<string> ans;

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

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

if (gcd(i, j) == 1)

ans.push_back(to_string(i) + "/" + to_string(j));

return ans;

}

};

花花酱 LeetCode 1446. Consecutive Characters

By zxi on May 17, 2020

Given a string s, the power of the string is the maximum length of a non-empty substring that contains only one unique character.

Return the power of the string.

Example 1:

Input: s = "leetcode"
Output: 2
Explanation: The substring "ee" is of length 2 with the character 'e' only.

Example 2:

Input: s = "abbcccddddeeeeedcba"
Output: 5
Explanation: The substring "eeeee" is of length 5 with the character 'e' only.

Example 3:

Input: s = "triplepillooooow"
Output: 5

Example 4:

Input: s = "hooraaaaaaaaaaay"
Output: 11

Example 5:

Input: s = "tourist"
Output: 1

Constraints:

1 <= s.length <= 500
s contains only lowercase English letters.

Solution: Run length encoding?

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

C++

// Author: Huahua

class Solution {

public:

int maxPower(string s) {

char p = '?';

int ans = 0;

int cur = 0;

for (char c : s) {

if (c != p) cur = 0;

p = c;

ans = max(ans, ++cur);

}

return ans;

}

};

Python-Like enumerate() In C++17 – C++ Weekly EP1

By zxi on May 17, 2020

C++

// Author: Huahua

#include <iostream>

#include <string>

#include <vector>

#include <list>

#include <tuple>

using namespace std;

// Python-Like enumerate() In C++17

// http://reedbeta.com/blog/python-like-enumerate-in-cpp17/

template <typename T,

typename TIter = decltype(std::begin(std::declval<T>())),

typename = decltype(std::end(std::declval<T>()))>

constexpr auto enumerate(T && iterable) {

struct iterator {

int i;

TIter iter;

bool operator != (const iterator & other) const { return iter != other.iter; }

void operator ++ () { ++i; ++iter; }

auto operator * () const { return std::tie(i, *iter); }

};

struct iterable_wrapper {

T iterable;

auto begin() { return iterator{ 0, std::begin(iterable) }; }

auto end() { return iterator{ 0, std::end(iterable) }; }

};

// return iterable_wrapper{ iterable }; // this makes a copy if iterable is a rvalue.

return iterable_wrapper{ std::forward<T>(iterable) };

}

struct A {

int val;

A(int val): val(val) { cout << "A(int)" << endl; }

A(const A& a): val(a.val) { cout << "A(A&)" << endl; }

A(A&& a): val(a.val) { cout << "A(A&&)" << endl; }

};

int main(int argc, char** argv) {

vector<int> arr{1, 2, 4};

for (size_t i = 0; i < arr.size(); ++i)

cout << i << " " << arr[i] << endl;

size_t idx = 0;

for (int v : arr)

cout << idx++ << " " << v << endl;

for (auto it = begin(arr); it != end(arr); ++it)

cout << distance(begin(arr), it) << " " << *it << endl;

for (const auto& [i, v] : enumerate(arr))

cout << i << " " << v << endl;

list<string> lst{"hello", "world!"};

for (const auto& [i, v] : enumerate(lst))

cout << i << " " << v << endl;

for (const auto& [i, v] : enumerate(string("abcde")))

cout << i << " " << v << endl;

vector<A> vec;

vec.reserve(3);

vec.emplace_back(1);

vec.emplace_back(2);

vec.emplace_back(4);

for (const auto& [i, v] : enumerate(vec))

cout << i << " " << v.val << endl;

for (const auto& [i, v] : enumerate(vector<A>{A(1), A(2), A(4)}))

cout << i << " " << v.val << endl;

return 0;

}

花花酱 LeetCode 1453. Maximum Number of Darts Inside of a Circular Dartboard

By zxi on May 16, 2020

You have a very large square wall and a circular dartboard placed on the wall. You have been challenged to throw darts into the board blindfolded. Darts thrown at the wall are represented as an array of points on a 2D plane.

Return the maximum number of points that are within or lie on any circular dartboard of radius r.

Example 1:

Input: points = [[-2,0],[2,0],[0,2],[0,-2]], r = 2
Output: 4
Explanation: Circle dartboard with center in (0,0) and radius = 2 contain all points.

Example 2:

Input: points = [[-3,0],[3,0],[2,6],[5,4],[0,9],[7,8]], r = 5
Output: 5
Explanation: Circle dartboard with center in (0,4) and radius = 5 contain all points except the point (7,8).

Example 3:

Input: points = [[-2,0],[2,0],[0,2],[0,-2]], r = 1
Output: 1

Example 4:

Input: points = [[1,2],[3,5],[1,-1],[2,3],[4,1],[1,3]], r = 2
Output: 4

Constraints:

1 <= points.length <= 100
points[i].length == 2
-10^4 <= points[i][0], points[i][1] <= 10^4
1 <= r <= 5000

Solution 1: Angular Sweep

See for more details: https://www.geeksforgeeks.org/angular-sweep-maximum-points-can-enclosed-circle-given-radius/

Time complexity: O(n^2*logn)
Space complexity: O(n^2)

C++

// Author: Huahua

// Python-Like enumerate() In C++17

// http://reedbeta.com/blog/python-like-enumerate-in-cpp17/

template <typename T,

typename TIter = decltype(std::begin(std::declval<T>())),

typename = decltype(std::end(std::declval<T>()))>

constexpr auto enumerate(T && iterable) {

struct iterator {

size_t i;

TIter iter;

bool operator != (const iterator & other) const { return iter != other.iter; }

void operator ++ () { ++i; ++iter; }

auto operator * () const { return std::tie(i, *iter); }

};

struct iterable_wrapper {

T iterable;

auto begin() { return iterator{ 0, std::begin(iterable) }; }

auto end() { return iterator{ 0, std::end(iterable) }; }

};

return iterable_wrapper{ std::forward<T>(iterable) };

}

class Solution {

public:

int numPoints(vector<vector<int>>& points, int r) {

const int n = points.size();

vector<vector<double>> d(n, vector<double>(n));

for (const auto& [i, pi] : enumerate(points))

for (const auto& [j, pj] : enumerate(points))

d[i][j] = d[j][i] = sqrt((pi[0] - pj[0]) * (pi[0] - pj[0])

+ (pi[1] - pj[1]) * (pi[1] - pj[1]));

int ans = 1;

for (const auto& [i, pi] : enumerate(points)) {

vector<pair<double, int>> angles; // {angle, event_type}

for (const auto& [j, pj] : enumerate(points)) {

if (i != j && d[i][j] <= 2 * r) {

const double a = atan2(pj[1] - pi[1], pj[0] - pi[0]);

const double b = acos(d[i][j] / (2 * r));

angles.emplace_back(a - b, -1); // entering

angles.emplace_back(a + b, 1); // exiting

}

// If angles are the same, entering points go first.

sort(begin(angles), end(angles));

int pts = 1;

for (const auto& [_, event] : angles)

ans = max(ans, pts -= event);

}

return ans;

}

};

花花酱 LeetCode 1452. People Whose List of Favorite Companies Is Not a Subset of Another List

By zxi on May 16, 2020

Given the array favoriteCompanies where favoriteCompanies[i] is the list of favorites companies for the ith person (indexed from 0).

Return the indices of people whose list of favorite companies is not a subset of any other list of favorites companies. You must return the indices in increasing order.

Example 1:

Input: favoriteCompanies = [["leetcode","google","facebook"],["google","microsoft"],["google","facebook"],["google"],["amazon"]]
Output: [0,1,4] 
Explanation: 
Person with index=2 has favoriteCompanies[2]=["google","facebook"] which is a subset of favoriteCompanies[0]=["leetcode","google","facebook"] corresponding to the person with index 0. 
Person with index=3 has favoriteCompanies[3]=["google"] which is a subset of favoriteCompanies[0]=["leetcode","google","facebook"] and favoriteCompanies[1]=["google","microsoft"]. 
Other lists of favorite companies are not a subset of another list, therefore, the answer is [0,1,4].

Example 2:

Input: favoriteCompanies = [["leetcode","google","facebook"],["leetcode","amazon"],["facebook","google"]]
Output: [0,1] 
Explanation: In this case favoriteCompanies[2]=["facebook","google"] is a subset of favoriteCompanies[0]=["leetcode","google","facebook"], therefore, the answer is [0,1].

Example 3:

Input: favoriteCompanies = [["leetcode"],["google"],["facebook"],["amazon"]]
Output: [0,1,2,3]

Constraints:

1 <= favoriteCompanies.length <= 100
1 <= favoriteCompanies[i].length <= 500
1 <= favoriteCompanies[i][j].length <= 20
All strings in favoriteCompanies[i] are distinct.
All lists of favorite companies are distinct, that is, If we sort alphabetically each list then favoriteCompanies[i] != favoriteCompanies[j].
All strings consist of lowercase English letters only.

Solution: Hashtable

Time complexity: O(n*n*m)
Space complexity: O(n*m)
where n is the # of people, m is the # of companies

C++

// Author: Huahua, 664 ms 58.4 MB

class Solution {

public:

vector<int> peopleIndexes(vector<vector<string>>& favoriteCompanies) {

const int n = favoriteCompanies.size();

vector<unordered_set<string>> m;

for (const auto& c : favoriteCompanies)

m.emplace_back(begin(c), end(c));

vector<int> ans;

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

bool valid = true;

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

if (i == j) continue;

bool subset = true;

for (const auto& s : m[i])

if (!m[j].count(s)) {

subset = false;

break;

}

if (subset) {

valid = false;

break;

}

if (valid)

ans.push_back(i);

}

return ans;

}

};

Use int as key to make it faster.

C++

// Author: Huahua, 476 ms, 48.7 MB

class Solution {

public:

vector<int> peopleIndexes(vector<vector<string>>& favoriteCompanies) {

const int n = favoriteCompanies.size();

unordered_map<string, int> ids;

vector<unordered_set<int>> m;

for (const auto& companies : favoriteCompanies) {

m.push_back({});

for (const auto& c : companies) {

if (!ids.count(c))

ids[c] = ids.size();

m.back().insert(ids[c]);

}

vector<int> ans;

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

bool valid = true;

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

if (i == j) continue;

bool subset = true;

for (const auto& s : m[i])

if (!m[j].count(s)) {

subset = false;

break;

}

if (subset) {

valid = false;

break;

}

if (valid) ans.push_back(i);

}

return ans;

}

};

Huahua's Tech Road

花花酱 LeetCode 1447. Simplified Fractions

Solution: GCD

C++

花花酱 LeetCode 1446. Consecutive Characters

Solution: Run length encoding?

C++

Python-Like enumerate() In C++17 – C++ Weekly EP1

C++

花花酱 LeetCode 1453. Maximum Number of Darts Inside of a Circular Dartboard

Solution 1: Angular Sweep

C++

花花酱 LeetCode 1452. People Whose List of Favorite Companies Is Not a Subset of Another List

Solution: Hashtable

C++

C++