Huahua's Tech Road

花花酱 LeetCode 973. K Closest Points to Origin

By zxi on January 13, 2019

We have a list of points on the plane. Find the K closest points to the origin (0, 0).

(Here, the distance between two points on a plane is the Euclidean distance.)

You may return the answer in any order. The answer is guaranteed to be unique (except for the order that it is in.)

Example 1:

Input: points = [[1,3],[-2,2]], K = 1 
Output: [[-2,2]] 
Explanation:  The distance between (1, 3) and the origin is sqrt(10). The distance between (-2, 2) and the origin is sqrt(8). Since sqrt(8) < sqrt(10), (-2, 2) is closer to the origin. We only want the closest K = 1 points from the origin, so the answer is just [[-2,2]].

Example 2:

Input: points = [[3,3],[5,-1],[-2,4]], K = 2 
Output: [[3,3],[-2,4]] (The answer [[-2,4],[3,3]] would also be accepted.)

Note:

1 <= K <= points.length <= 10000
-10000 < points[i][0] < 10000
-10000 < points[i][1] < 10000

Solution: Sort

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

C++

// Author: Huahua, Running time: 180 ms

class Solution {

public:

vector<vector<int>> kClosest(vector<vector<int>>& points, int K) {

vector<long> s(points.size());

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

s[i] = (static_cast<long>(points[i][0] * points[i][0] +

points[i][1] * points[i][1]) << 32) | i;

std::sort(begin(s), end(s));

vector<vector<int>> ans(K);

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

ans[i] = points[static_cast<int>(s[i])];

return ans;

}

};

Python3

# Author: Huahua, running time: 528 ms

class Solution:

def kClosest(self, points, K):

return sorted(points, key = lambda p: p[0]**2 + p[1]**2)[0:K]

Multithreading and Multiprocessing – Parallel Computing 1

By zxi on January 8, 2019

Multithreading

C++

#include <stdio.h>

#include <thread>

int a = 1;

void run(int s) {

a += s;

}

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

std::thread thread1(run, 2);

std::thread thread2(run, 5);

thread1.join();

thread2.join();

printf("%d\n", a);

return 0;

}

// Output:

// 8

Multiprocessing

C++

#include <stdio.h>

#include <sys/types.h>

#include <unistd.h>

int a = 1;

void run(bool child) {

a += child ? 2 : 1;

}

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

a += 1;

pid_t pid = fork();

run(pid == 0);

printf("%d\n", a);

return 0;

}

// Output:

// 3

// 4

花花酱 LeetCode 972. Equal Rational Numbers

By zxi on January 5, 2019

Given two strings S and T, each of which represents a non-negative rational number, return True if and only if they represent the same number. The strings may use parentheses to denote the repeating part of the rational number.

In general a rational number can be represented using up to three parts: an integer part, a non-repeating part, and a repeating part. The number will be represented in one of the following three ways:

<IntegerPart> (e.g. 0, 12, 123)
<IntegerPart><.><NonRepeatingPart> (e.g. 0.5, 1., 2.12, 2.0001)
<IntegerPart><.><NonRepeatingPart><(><RepeatingPart><)> (e.g. 0.1(6), 0.9(9), 0.00(1212))

The repeating portion of a decimal expansion is conventionally denoted within a pair of round brackets. For example:

1 / 6 = 0.16666666… = 0.1(6) = 0.1666(6) = 0.166(66)

Both 0.1(6) or 0.1666(6) or 0.166(66) are correct representations of 1 / 6.

Example 1:

Input: S = "0.(52)", T = "0.5(25)"
Output: true
Explanation:
Because "0.(52)" represents 0.52525252..., and "0.5(25)" represents 0.52525252525..... , the strings represent the same number.

Example 2:

Input: S = "0.1666(6)", T = "0.166(66)"
Output: true

Example 3:

Input: S = "0.9(9)", T = "1."
Output: true
Explanation: 
"0.9(9)" represents 0.999999999... repeated forever, which equals 1.  [See this link for an explanation.]
"1." represents the number 1, which is formed correctly: (IntegerPart) = "1" and (NonRepeatingPart) = "".

Note:

Each part consists only of digits.
The <IntegerPart> will not begin with 2 or more zeros. (There is no other restriction on the digits of each part.)
1 <= <IntegerPart>.length <= 4
0 <= <NonRepeatingPart>.length <= 4
1 <= <RepeatingPart>.length <= 4

Solution1: Expend the string

Extend the string to 16+ more digits and covert it to double.

0.9(9) => 0.99999999999999
0.(52) => 0.525252525252525
0.5(25) => 0.5252525252525

C++

// Author: Huahua, running time: 4 ms

class Solution {

public:

bool isRationalEqual(string S, string T) {

auto convert = [](string s) {

// 0.1234(567)

// 01234567890

// i = 1, p = 6

auto i = s.find('.');

auto p = s.find('(');

if (p != string::npos) {

string r = s.substr(p + 1, s.length() - p - 2);

s = s.substr(0, p);

while (s.length() < 16)

s += r;

}

return stod(s);

};

return abs(convert(S) - convert(T)) < 1e-10;

}

};

Python3

class Solution:

def isRationalEqual(self, S, T):

def convert(s):

i = s.find('.')

p = s.find('(')

if p >= 0:

r = s[p+1:-1]

s = s[0:p]

while len(s) < 16:

s += r

return float(s)

return abs(convert(S) - convert(T)) < 1e-10

Solution 2: Convert to a friction number

C++

// Author: Huahua, running time: 24 ms.

class Friction {

public:

Friction(long n = 0, long d = 1) {

long g = __gcd(n, d);

n_ = n / g;

d_ = d / g;

}

Friction operator+(const Friction& o) const {

return Friction(n_ * o.d_ + d_ * o.n_, d_ * o.d_);

}

bool operator==(const Friction& o) const {

return this->n_ * o.d_ == this->d_ * o.n_;

}

private:

long n_;

long d_;

};

class Solution {

public:

bool isRationalEqual(string S, string T) {

auto convert = [](string s) {

std::regex re("(\\d+)\\.?(\\d+)?(\\((\\d+)\\))?");

std::smatch matches;

std::regex_match(s, matches, re);

string int_part = matches[1].str();

string nr_part = matches[2].str();

string r_part = matches[4].str();

Friction f(stoi(int_part), 1);

const int base = pow(10, nr_part.length());

if (nr_part.length())

f = f + Friction(stoi(nr_part), base);

if (r_part.length())

f = f + Friction(stoi(r_part), (pow(10, r_part.length()) - 1) * base);

return f;

};

return convert(S) == convert(T);

}

};

花花酱 LeetCode 971. Flip Binary Tree To Match Preorder Traversal

By zxi on January 5, 2019

Given a binary tree with N nodes, each node has a different value from {1, ..., N}.

A node in this binary tree can be flipped by swapping the left child and the right child of that node.

Consider the sequence of N values reported by a preorder traversal starting from the root. Call such a sequence of N values the voyage of the tree.

(Recall that a preorder traversal of a node means we report the current node’s value, then preorder-traverse the left child, then preorder-traverse the right child.)

Our goal is to flip the least number of nodes in the tree so that the voyage of the tree matches the voyagewe are given.

If we can do so, then return a list of the values of all nodes flipped. You may return the answer in any order.

If we cannot do so, then return the list [-1].

Example 1:

Input: root = [1,2], voyage = [2,1]
Output: [-1]

Example 2:

Input: root = [1,2,3], voyage = [1,3,2]
Output: [1]

Example 3:

Input: root = [1,2,3], voyage = [1,2,3]
Output: []

Note:

1 <= N <= 100

Solution: Pre-order traversal

if root->val != v[pos] return [-1]
if root->left?->val != v[pos + 1], swap the nodes

c++

class Solution {

public:

vector<int> flipMatchVoyage(TreeNode* root, vector<int>& voyage) {

vector<int> flips;

int pos = 0;

solve(root, voyage, pos, flips);

return flips;

}

private:

void solve(TreeNode* root, const vector<int>& voyage, int& pos, vector<int>& flips) {

if (!root) return;

if (root->val != voyage.at(pos)) {

flips.clear();

flips.push_back(-1);

return;

}

if (root->left && root->left->val != voyage.at(pos + 1)) {

swap(root->left, root->right);

flips.push_back(root->val);

}

++pos;

solve(root->left, voyage, pos, flips);

solve(root->right, voyage, pos, flips);

}

};

Python3

# Author: Huahua, 60 ms

class Solution:

def flipMatchVoyage(self, root, voyage):

self.pos = 0

self.flips = []

def solve(root):

if not root: return

if root.val != voyage[self.pos]:

self.flips = [-1]

return

if root.left and root.left.val != voyage[self.pos + 1]:

root.left, root.right = root.right, root.left

self.flips.append(root.val)

self.pos += 1

solve(root.left)

solve(root.right)

solve(root)

return self.flips

花花酱 LeetCode 970. Powerful Integers

By zxi on January 5, 2019

Given two non-negative integers x and y, an integer is powerful if it is equal to x^i + y^j for some integers i >= 0 and j >= 0.

Return a list of all powerful integers that have value less than or equal to bound.

You may return the answer in any order. In your answer, each value should occur at most once.

Example 1:

Input: x = 2, y = 3, bound = 10
Output: [2,3,4,5,7,9,10]
Explanation: 
2 = 2^0 + 3^0
3 = 2^1 + 3^0
4 = 2^0 + 3^1
5 = 2^1 + 3^1
7 = 2^2 + 3^1
9 = 2^3 + 3^0
10 = 2^0 + 3^2

Example 2:

Input: x = 3, y = 5, bound = 15
Output: [2,4,6,8,10,14]

Note:

1 <= x <= 100
1 <= y <= 100
0 <= bound <= 10^6

Solution: Brute Force

Time complexity: O(log(bound) / log(x) * log(bound) / log(y))
Space complexity: O(log(bound) / log(x) * log(bound) / log(y))

C++

// Author: Huahua, running time: 4 ms

class Solution {

public:

vector<int> powerfulIntegers(int x, int y, int bound) {

unordered_set<int> ans;

for (int a = 1; a < bound; a *= x) {

for (int b = 1; a + b <= bound; b *= y) {

ans.insert(a + b);

if (y == 1) break;

}

if (x == 1) break;

}

return {begin(ans), end(ans)};

}

};