Huahua’s Tech Road

花花酱 LeetCode 1448. Count Good Nodes in Binary Tree

By zxi on May 17, 2020

Given a binary tree root, a node X in the tree is named good if in the path from root to X there are no nodes with a value greater than X.

Return the number of good nodes in the binary tree.

Example 1:

Input: root = [3,1,4,3,null,1,5]
Output: 4
Explanation: Nodes in blue are good.
Root Node (3) is always a good node.
Node 4 -> (3,4) is the maximum value in the path starting from the root.
Node 5 -> (3,4,5) is the maximum value in the path
Node 3 -> (3,1,3) is the maximum value in the path.

Example 2:

Input: root = [3,3,null,4,2]
Output: 3
Explanation: Node 2 -> (3, 3, 2) is not good, because "3" is higher than it.

Example 3:

Input: root = [1]
Output: 1
Explanation: Root is considered as good.

Constraints:

The number of nodes in the binary tree is in the range [1, 10^5].
Each node’s value is between [-10^4, 10^4].

Solution: Recursion

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

C++

// Author: Huahua

class Solution {

public:

int goodNodes(TreeNode* root, int max_val = INT_MIN) {

if (!root) return 0;

return goodNodes(root->left, max(max_val, root->val))

+ goodNodes(root->right, max(max_val, root->val))

+ (root->val >= max_val ? 1 : 0);

}

};

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

}

};

Huahua's Tech Road

花花酱 LeetCode 1448. Count Good Nodes in Binary Tree

Solution: Recursion

C++

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