April 2019 - Page 2 of 5 - Huahua's Tech Road

花花酱 LeetCode 50. Pow(x, n)

By zxi on April 24, 2019

Implement pow(x, n), which calculates x raised to the power n (xⁿ).

Example 1:

Input: 2.00000, 10
Output: 1024.00000

Example 2:

Input: 2.10000, 3
Output: 9.26100

Example 3:

Input: 2.00000, -2
Output: 0.25000
Explanation: 2^-2 = 1/2² = 1/4 = 0.25

Note:

-100.0 < x < 100.0
n is a 32-bit signed integer, within the range [−2³¹, 2³¹− 1]

Solution: Recursion

square x and cut n in half.
if n is negative, compute 1.0 / pow(x, |n|)

pow(x, n) := pow(x * x, n / 2) * (x if n % 2 else 1)
pow(x, 0) := 1

Example:
pow(x, 5) = pow(x^2, 2) * x 
          = pow(x^4, 1) * x 
          = pow(x^8, 0) * x^4 * x
          = 1 * x^4 * x = x^5

Time complexity: O(logn)
Space complexity: O(logn)

C++

// Author: Huahua

class Solution {

public:

double myPow(double x, int n) {

return n >= 0 ? myPowImp(x, n) : 1.0 / myPowImp(x, n);

}

private:

double myPowImp(double x, int n) {

if (n == 0) return 1;

return myPowImp(x * x, n / 2) * (n % 2 ? x : 1);

}

};

花花酱 LeetCode Weekly Contest 133

By zxi on April 20, 2019

LeetCode 1029 Two City Scheduling

Solution1: DP

dp[i][j] := min cost to put j people into city A for the first i people
dp[0][0] = 0
dp[i][0] = dp[i -1][0] + cost_b
dp[i][j] = min(dp[i – 1][j] + cost_b, dp[i – 1][j – 1] + cost_a)
ans := dp[n][n/2]

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

C++

// Author: Huahua, running time: 8 ms

class Solution {

public:

int twoCitySchedCost(vector<vector<int>>& costs) {

int n = costs.size();

vector<vector<int>> dp(n + 1, vector<int>(n + 1, INT_MAX / 2));

dp[0][0] = 0;

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

dp[i][0] = dp[i - 1][0] + costs[i - 1][1];

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

dp[i][j] = min(dp[i - 1][j - 1] + costs[i - 1][0],

dp[i - 1][j] + costs[i - 1][1]);

}

return dp[n][n / 2];

}

};

Solution 2: Greedy

Sort by cost_a – cost_b

Choose the first n/2 people for A, rest for B

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

C++

// Author: Huahua, running time: 8 ms

class Solution {

public:

int twoCitySchedCost(vector<vector<int>>& costs) {

int n = costs.size();

sort(begin(costs), end(costs), [](const auto& c1, const auto& c2){

return c1[0] - c1[1] < c2[0] - c2[1];

});

int ans = 0;

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

ans += i < n/2 ? costs[i][0] : costs[i][1];

return ans;

}

};

1030. Matrix Cells in Distance Order

Solution: Sorting

Time complexity: O(RC*log(RC))
Space complexity: O(RC)

C++

// Author: Huahua

class Solution {

public:

vector<vector<int>> allCellsDistOrder(int R, int C, int r0, int c0) {

vector<vector<int>> ans;

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

for (int j = 0; j < C; ++j)

ans.push_back({i, j});

std::sort(begin(ans), end(ans), [r0, c0](const vector<int>& a, const vector<int>& b){

return (abs(a[0] - r0) + abs(a[1] - c0)) < (abs(b[0] - r0) + abs(b[1] - c0));

});

return ans;

}

};

1031. Maximum Sum of Two Non-Overlapping Subarrays

Solution: Prefix sum

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

C++

// Author: Huahua

class Solution {

public:

int maxSumTwoNoOverlap(vector<int>& A, int L, int M) {

const int n = A.size();

vector<int> s(n + 1, 0);

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

s[i + 1] = s[i] + A[i];

int ans = 0;

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

int ls = s[i + L] - s[i];

int ms = max(maxSum(s, 0, i - M - 1, M),

maxSum(s, i + L, n - M, M));

ans = max(ans, ls + ms);

}

return ans;

}

private:

int maxSum(const vector<int>& s, int start, int end, int l) {

int ans = INT_MIN;

for (int i = start; i <= end; ++i)

ans = max(ans, s[i + l] - s[i]);

return ans;

}

};

1032. Stream of Characters

Solution: Trie

Time complexity:

build O(sum(len(w))
query O(max(len(w))

Space complexity: O(sum(len(w))

C++

// Author: Huahua, 320 ms, 95 MB

class TrieNode {

public:

~TrieNode() {

for (auto node : next_)

delete node;

}

void reverse_build(const string& s, int i) {

if (i == -1) {

is_word_ = true;

return;

}

const int idx = s[i] - 'a';

if (!next_[idx]) next_[idx] = new TrieNode();

next_[idx]->reverse_build(s, i - 1);

}

bool reverse_search(const string& s, int i) {

if (i == -1 || is_word_) return is_word_;

const int idx = s[i] - 'a';

if (!next_[idx]) return false;

return next_[idx]->reverse_search(s, i - 1);

}

private:

bool is_word_ = false;

TrieNode* next_[26] = {0};

};

class StreamChecker {

public:

StreamChecker(vector<string>& words) {

root_ = std::make_unique<TrieNode>();

for (const string& w : words)

root_->reverse_build(w, w.length() - 1);

}

bool query(char letter) {

s_ += letter;

return root_->reverse_search(s_, s_.length() - 1);

}

private:

string s_;

unique_ptr<TrieNode> root_;

};

Java

// Author: Huahua, running time: 133 ms

class StreamChecker {

class TrieNode {

public TrieNode() {

isWord = false;

next = new TrieNode[26];

}

public boolean isWord;

public TrieNode next[];

}

private TrieNode root;

private StringBuilder sb;

public StreamChecker(String[] words) {

root = new TrieNode();

sb = new StringBuilder();

for (String word : words) {

TrieNode node = root;

char[] w = word.toCharArray();

for (int i = w.length - 1; i >= 0; --i) {

int idx = w[i] - 'a';

if (node.next[idx] == null) node.next[idx] = new TrieNode();

node = node.next[idx];

}

node.isWord = true;

}

public boolean query(char letter) {

sb.append(letter);

TrieNode node = root;

for (int i = sb.length() - 1; i >= 0; --i) {

int idx = sb.charAt(i) - 'a';

if (node.next[idx] == null) return false;

if (node.next[idx].isWord) return true;

node = node.next[idx];

}

return false;

}

花花酱 Binary Search II SP17

By zxi on April 20, 2019

Binary Search I SP5

For the given function g(x) and a range [l, r] find the smallest int number m such that g(m) is True, if not found, return r + 1.

花花酱 LeetCode 38. Count and Say

By zxi on April 17, 2019

Problem

https://leetcode.com/problems/count-and-say/

The count-and-say sequence is the sequence of integers with the first five terms as following:

1.     1
2.     11
3.     21
4.     1211
5.     111221

1 is read off as "one 1" or 11.
11 is read off as "two 1s" or 21.
21 is read off as "one 2, then one 1" or 1211.

Given an integer n where 1 ≤ n ≤ 30, generate the n^th term of the count-and-say sequence.

Note: Each term of the sequence of integers will be represented as a string.

Example 1:

Input: 1
Output: "1"

Example 2:

Input: 4
Output: "1211"

Solution: Recursion + Simulation

C++

// Author: Huahua, 4 ms, 8.6 MB

class Solution {

public:

string countAndSay(int n) {

string ans = "1";

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

ans = say(ans);

return ans;

}

private:

string say(const string& n){

string ans;

int s = 0, l = n.length();

for (int e = 1; e <= l; ++e)

if (e == l || n[s] != n[e]) {

int count = e - s;

ans += '0' + count;

ans += n[s];

s = e;

}

return ans;

}

};

花花酱 LeetCode 279. Perfect Squares

By zxi on April 17, 2019

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.

Example 1:

Input: n = 12
Output: 3 
Explanation: 12 = 4 + 4 + 4.

Example 2:

Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.

Solution 1: DP

dp[i] := ans
dp[0] = 0
dp[i] = min{dp[i – j * j] + 1} 1 <= j * j <= i

dp[5] = min{
dp[5 – 2 * 2] + 1 = dp[1] + 1 = (dp[1 – 1 * 1] + 1) + 1 = dp[0] + 1 + 1 = 2,
dp[5 – 1 * 1] + 1 = dp[3] + 1 = (dp[3 – 1 * 1] + 1) + 1 = dp[1] + 2 = dp[1 – 1*1] + 1 + 2 = dp[0] + 3 = 3
};

dp[5] = 2

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

C++

// Author: Huahua, running time: 104 ms

class Solution {

public:

int numSquares(int n) {

vector<int> dp(n + 1, INT_MAX >> 1);

dp[0] = 0;

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

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

dp[i] = min(dp[i], dp[i - j * j] + 1);

return dp[n];

}

};

Posts published in April 2019

花花酱 LeetCode 50. Pow(x, n)

Solution: Recursion

C++

花花酱 LeetCode Weekly Contest 133

LeetCode 1029 Two City Scheduling

C++

C++

1030. Matrix Cells in Distance Order

C++

1031. Maximum Sum of Two Non-Overlapping Subarrays

C++

1032. Stream of Characters

C++

Java

花花酱 Binary Search II SP17

花花酱 LeetCode 38. Count and Say

Problem

C++

花花酱 LeetCode 279. Perfect Squares

Solution 1: DP

C++