Huahua’s Tech Road

花花酱 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;

}

};

花花酱 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;

}

};

Huahua's Tech Road

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

花花酱 LeetCode 1451. Rearrange Words in a Sentence

Solution: Stable sort

C++