Huahua’s Tech Road

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;

}

};

花花酱 LeetCode 1451. Rearrange Words in a Sentence

By zxi on May 16, 2020

Given a sentence text (A sentence is a string of space-separated words) in the following format:

First letter is in upper case.
Each word in text are separated by a single space.

Your task is to rearrange the words in text such that all words are rearranged in an increasing order of their lengths. If two words have the same length, arrange them in their original order.

Return the new text following the format shown above.

Example 1:

Input: text = "Leetcode is cool"
Output: "Is cool leetcode"
Explanation: There are 3 words, "Leetcode" of length 8, "is" of length 2 and "cool" of length 4.
Output is ordered by length and the new first word starts with capital letter.

Example 2:

Input: text = "Keep calm and code on"
Output: "On and keep calm code"
Explanation: Output is ordered as follows:
"On" 2 letters.
"and" 3 letters.
"keep" 4 letters in case of tie order by position in original text.
"calm" 4 letters.
"code" 4 letters.

Example 3:

Input: text = "To be or not to be"
Output: "To be or to be not"

Constraints:

text begins with a capital letter and then contains lowercase letters and single space between words.
1 <= text.length <= 10^5

Solution: Stable sort

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

C++

// Author: Huahua

class Solution {

public:

string arrangeWords(string text) {

vector<string> words{""};

for (char c : text) {

if (c == ' ')

words.push_back("");

else

words.back() += c;

}

words[0][0] = tolower(words[0][0]);

stable_sort(begin(words), end(words), [](const auto& w1, const auto& w2){

return w1.length() < w2.length();

});

string ans;

for (const string& word : words) {

if (!ans.empty()) ans += ' ';

ans += word;

}

ans[0] = toupper(ans[0]);

return ans;

}

};

花花酱 LeetCode 1450. Number of Students Doing Homework at a Given Time

By zxi on May 16, 2020

Given two integer arrays startTime and endTime and given an integer queryTime.

The ith student started doing their homework at the time startTime[i] and finished it at time endTime[i].

Return the number of students doing their homework at time queryTime. More formally, return the number of students where queryTime lays in the interval [startTime[i], endTime[i]] inclusive.

Example 1:

Input: startTime = [1,2,3], endTime = [3,2,7], queryTime = 4
Output: 1
Explanation: We have 3 students where:
The first student started doing homework at time 1 and finished at time 3 and wasn't doing anything at time 4.
The second student started doing homework at time 2 and finished at time 2 and also wasn't doing anything at time 4.
The third student started doing homework at time 3 and finished at time 7 and was the only student doing homework at time 4.

Example 2:

Input: startTime = [4], endTime = [4], queryTime = 4
Output: 1
Explanation: The only student was doing their homework at the queryTime.

Example 3:

Input: startTime = [4], endTime = [4], queryTime = 5
Output: 0

Example 4:

Input: startTime = [1,1,1,1], endTime = [1,3,2,4], queryTime = 7
Output: 0

Example 5:

Input: startTime = [9,8,7,6,5,4,3,2,1], endTime = [10,10,10,10,10,10,10,10,10], queryTime = 5
Output: 5

Constraints:

startTime.length == endTime.length
1 <= startTime.length <= 100
1 <= startTime[i] <= endTime[i] <= 1000
1 <= queryTime <= 1000

Solution: Brute Force

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

C++

// Author: Huahua

class Solution {

public:

int busyStudent(vector<int>& startTime, vector<int>& endTime, int queryTime) {

int ans = 0;

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

if (startTime[i] <= queryTime && queryTime <= endTime[i]) ++ans;

return ans;

}

};

Python3

# Author: Huahua

class Solution:

def busyStudent(self, startTime: List[int], endTime: List[int], queryTime: int) -> int:

return sum(s <= queryTime <= e for s, e in zip(startTime, endTime))

Huahua's Tech Road

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++

花花酱 LeetCode 1451. Rearrange Words in a Sentence

Solution: Stable sort

C++

花花酱 LeetCode 1450. Number of Students Doing Homework at a Given Time

Solution: Brute Force

C++

Python3