Posts published in April 2018

花花酱 LeetCode 823. Binary Trees With Factors

By zxi on April 29, 2018

Problem

题目大意：给你一些可以重复使用的数字问能够构成多少种不同的特殊二叉树（根结点的值需为子节点值的乘积）。

https://leetcode.com/problems/binary-trees-with-factors/description/

Given an array of unique integers, each integer is strictly greater than 1.

We make a binary tree using these integers and each number may be used for any number of times.

Each non-leaf node’s value should be equal to the product of the values of it’s children.

How many binary trees can we make? Return the answer modulo 10 ** 9 + 7.

Example 1:

Input: A = [2, 4]
Output: 3 Explanation: We can make these trees: [2], [4], [4, 2, 2]

Example 2:

Input: A = [2, 4, 5, 10]
Output: 7
Explanation: We can make these trees: [2], [4], [5], [10], [4, 2, 2], [10, 2, 5], [10, 5, 2].

Note:

1 <= A.length <= 1000.
2 <= A[i] <= 10 ^ 9.

Solution: DP

Use dp[i] to denote the number of valid binary trees using the first i + 1 smallest elements and roots at A[i].

dp[i] = sum(dp[j] * dp[i/j]), 0 <= j < i, A[i] is a factor of A[j] and A[i] / A[j] also in A.

      A[i]
     /    \
 A[j]  (A[i]/A[j])
  / \     / \
 .....   .....

ans = sum(dp[i]), for all possible i.

Time complexity: O(n^2)

Space complexity: O(n^2)

C++

// Author: Huahua

// Running time: 53 ms

class Solution {

public:

int numFactoredBinaryTrees(vector<int>& A) {

constexpr long kMod = 1000000007;

std::sort(A.begin(), A.end());

unordered_map<int, long> dp;

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

dp[A[i]] = 1;

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

if (A[i] % A[j] == 0 && dp.count(A[i] / A[j]))

dp[A[i]] += (dp[A[j]] * dp[A[i] / A[j]]) % kMod;

}

long ans = 0;

for (const auto& kv : dp)

ans += kv.second;

return ans % kMod;

}

};

花花酱 LeetCode 820. Short Encoding of Words

By zxi on April 24, 2018

Problem

Given a list of words, we may encode it by writing a reference string S and a list of indexes A.

For example, if the list of words is ["time", "me", "bell"], we can write it as S = "time#bell#" and indexes = [0, 2, 5].

Then for each index, we will recover the word by reading from the reference string from that index until we reach a “#” character.

What is the length of the shortest reference string S possible that encodes the given words?

Example:

Input: words = ["time", "me", "bell"] Output: 10 Explanation: S = "time#bell#" and indexes = [0, 2, 5].

Note:

1 <= words.length <= 2000.
1 <= words[i].length <= 7.
Each word has only lowercase letters.

Idea

Remove all the words that are suffix of other words.

Solution

Time complexity: O(n*l^2)

Space complexity: O(n*l)

// Author: Huahua

// Running time: 43 ms

class Solution {

public:

int minimumLengthEncoding(vector<string>& words) {

unordered_set<string> s(words.begin(), words.end());

for (const string& w : words) {

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

s.erase(w.substr(i));

}

int ans = 0;

for (const string& w : s)

ans += w.length() + 1;

return ans;

}

};

花花酱 LeetCode 821. Shortest Distance to a Character

By zxi on April 22, 2018

Problem

题目大意：输出字符串的每个字符到一个指定字符的对短距离。

https://leetcode.com/problems/shortest-distance-to-a-character/description/

Given a string S and a character C, return an array of integers representing the shortest distance from the character C in the string.

Example 1:

Input: S = "loveleetcode", C = 'e'
Output: [3, 2, 1, 0, 1, 0, 0, 1, 2, 2, 1, 0]

Note:

S string length is in [1, 10000].
C is a single character, and guaranteed to be in string S.
All letters in S and C are lowercase.

Solution: Two Pass

Time complexity: O(n)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 14 ms

class Solution {

public:

vector<int> shortestToChar(string S, char C) {

const int n = S.length();

vector<int> ans(n, INT_MAX);

int index = -1;

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

if (S[i] == C) index = i;

if (index < 0) continue;

ans[i] = abs(i - index);

}

index = -1;

for (int i = n - 1; i >= 0; --i) {

if (S[i] == C) index = i;

if (index < 0) continue;

ans[i] = min(ans[i], abs(i - index));

}

return ans;

}

};

// Author: Huahua

// Running time: 14 ms

class Solution {

public:

vector<int> shortestToChar(string S, char C) {

const int n = S.length();

vector<int> indices(2 * n); // 0, 1, ..., n - 1, n - 1, n - 2, ..., 0

std::iota(indices.begin(), indices.begin() + n, 0);

std::iota(indices.rbegin(), indices.rbegin() + n, 0);

vector<int> ans(n, INT_MAX);

int index = -n;

for (int i : indices) {

if (S[i] == C) index = i;

ans[i] = min(ans[i], abs(i - index));

}

return ans;

}

};

花花酱 LeetCode 482. License Key Formatting

By zxi on April 16, 2018

Problem

题目大意：把序列号格式化，每组要求是K个字符（第一组 <= K），组和组之间用“-”分隔。

https://leetcode.com/problems/license-key-formatting/description/

You are given a license key represented as a string S which consists only alphanumeric character and dashes. The string is separated into N+1 groups by N dashes.

Given a number K, we would want to reformat the strings such that each group contains exactly K characters, except for the first group which could be shorter than K, but still must contain at least one character. Furthermore, there must be a dash inserted between two groups and all lowercase letters should be converted to uppercase.

Given a non-empty string S and a number K, format the string according to the rules described above.

Example 1:

Input: S = "5F3Z-2e-9-w", K = 4

Output: "5F3Z-2E9W"

Explanation: The string S has been split into two parts, each part has 4 characters.
Note that the two extra dashes are not needed and can be removed.

Example 2:

Input: S = "2-5g-3-J", K = 2

Output: "2-5G-3J"

Explanation: The string S has been split into three parts, each part has 2 characters except the first part as it could be shorter as mentioned above.

Note:

The length of string S will not exceed 12,000, and K is a positive integer.
String S consists only of alphanumerical characters (a-z and/or A-Z and/or 0-9) and dashes(-).
String S is non-empty.

Solution

Time complexity: O(n)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 16 ms

class Solution {

public:

string licenseKeyFormatting(string S, int K) {

string s;

for (char c : S)

if (c != '-') s.push_back(toupper(c));

int first = s.length() % K;

string ans = s.substr(0, first);

for (int i = 0; i < s.length() - first; ++i) {

if (i % K == 0 && (i + first)) ans += '-';

ans.push_back(s[i + first]);

}

return ans;

}

};

花花酱 LeetCode 818. Race Car

By zxi on April 15, 2018

Problem

题目大意：初始位置0速度+1，每次你可以加速（速度*2）或者倒车（速度变成-1*dir）。问最少需要执行多少步操作能够到达T。

https://leetcode.com/problems/race-car/description/

Your car starts at position 0 and speed +1 on an infinite number line. (Your car can go into negative positions.)

Your car drives automatically according to a sequence of instructions A (accelerate) and R (reverse).

When you get an instruction “A”, your car does the following: position += speed, speed *= 2.

When you get an instruction “R”, your car does the following: if your speed is positive then speed = -1 , otherwise speed = 1. (Your position stays the same.)

For example, after commands “AAR”, your car goes to positions 0->1->3->3, and your speed goes to 1->2->4->-1.

Now for some target position, say the length of the shortest sequence of instructions to get there.

Example 1:
Input: 
target = 3
Output: 2
Explanation: 
The shortest instruction sequence is "AA".
Your position goes from 0->1->3.

Example 2:
Input: 
target = 6
Output: 5
Explanation: 
The shortest instruction sequence is "AAARA".
Your position goes from 0->1->3->7->7->6.

Note:

1 <= target <= 10000.

Visualization of the Solution

Solution 1: BFS

C++/Str

// Author: Huahua

// Running time: 221 ms

class Solution {

public:

int racecar(int target) {

queue<pair<int, int>> q;

q.push({0, 1});

unordered_set<string> v;

v.insert("0_1");

v.insert("0_-1");

int steps = 0;

while (!q.empty()) {

int size = q.size();

while (size--) {

auto p = q.front(); q.pop();

int pos = p.first;

int speed = p.second;

{

int pos1 = pos + speed;

int speed1 = speed * 2;

pair<int, int> p1{pos1, speed1};

if (pos1 == target) return steps + 1;

if (p1.first > 0 && p1.first < 2 * target)

q.push(p1);

}

{

int speed2 = speed > 0 ? -1 : 1;

pair<int, int> p2{pos, speed2};

string key2 = to_string(pos) + "_" + to_string(speed2);

if (!v.count(key2)) {

q.push(p2);

v.insert(key2);

}

++steps;

}

return -1;

}

};

C++/Int

// Author: Huahua

// Running time: 16 ms

class Solution {

public:

int racecar(int target) {

queue<pair<int, int>> q;

q.push({0, 1});

unordered_set<int> v;

v.insert({0, 2});

int steps = 0;

while (!q.empty()) {

int size = q.size();

while (size--) {

auto p = q.front(); q.pop();

int pos = p.first;

int speed = p.second;

pair<int, int> p1 = {pos + speed, speed * 2};

if (p1.first == target) return steps + 1;

if (p1.first > 0 && p1.first + speed < 2 * target)

q.push(p1);

int speed2 = speed > 0 ? -1 : 1;

pair<int, int> p2 = {pos, speed2};

int key = (pos << 2) | (speed2 + 1);

if (!v.count(key) && p2.first >= target / 2) {

q.push(p2);

v.insert(key);

}

++steps;

}

return -1;

}

};

Solution 2: DP O(TlogT)

C++

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

int racecar(int target) {

m_ = vector<int>(target + 1, 0);

return dp(target);

}

private:

vector<int> m_;

int dp(int t) {

if (m_[t] > 0) return m_[t];

int n = ceil(log2(t + 1));

// AA...A (nA) best case

if (1 << n == t + 1) return m_[t] = n;

// AA...AR (nA + 1R) + dp(left)

m_[t] = n + 1 + dp((1 << n) - 1 - t);

for (int m = 0; m < n - 1; ++m) {

int cur = (1 << (n - 1)) - (1 << m);

//AA...ARA...AR (n-1A + 1R + mA + 1R) + dp(left)

m_[t] = min(m_[t], n + m + 1 + dp(t - cur));

}

return m_[t];

}

};

Solution 3: DP O(T^2)

m[t][d] : min steps to reach t and facing d (0 = right, 1 = left)

Time Complexity: O(n^2)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 469 ms

constexpr int kMaxT = 10000;

int m[kMaxT + 1][2]={0};

class Solution {

public:

int racecar(int target) {

if (m[1][0] == 0) {

for (int t = 1; t <= kMaxT; ++t) {

const int n = ceil(log2(t + 1));

if (1 << n == t + 1) {

m[t][0] = n;

m[t][1] = n + 1;

continue;

}

const int l = (1 << n) - 1 - t;

m[t][0] = n + 1 + min(m[l][1], m[l][0] + 1);

m[t][1] = n + 1 + min(m[l][0], m[l][1] + 1);

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

const int mi = min(m[i][0] + 2, m[i][1] + 1);

m[t][0] = min(m[t][0], m[t - i][0] + mi);

m[t][1] = min(m[t][1], m[t - i][1] + mi);

}

return min(m[target][0], m[target][1]);

}

};

C++/opt

// Author: Huahua

// Running time: 361 ms

typedef unsigned char uint8;

constexpr int kMaxT = 10000;

uint8 m[kMaxT + 1][2]={0};

inline uint8 MIN(uint8 a, uint8 b) {

return a < b ? a : b;

}

class Solution {

public:

int racecar(int target) {

if (m[1][0] == 0) {

for (int t = 1; t <= kMaxT; ++t) {

const int n = ceil(log2(t + 1));

if (1 << n == t + 1) {

m[t][0] = n;

m[t][1] = n + 1;

continue;

}

const int l = (1 << n) - 1 - t;

m[t][0] = n + 1 + MIN(m[l][1], (uint8)(m[l][0] + 1));

m[t][1] = n + 1 + MIN(m[l][0], (uint8)(m[l][1] + 1));

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

const int mi = MIN(m[i][0] + 2, m[i][1] + 1);

m[t][0] = MIN(m[t][0], (uint8)(m[t - i][0] + mi));

m[t][1] = MIN(m[t][1], (uint8)(m[t - i][1] + mi));

}

return min(m[target][0], m[target][1]);

}

};

Java

// Author: Huahua

// Running time: 562 ms

class Solution {

private static int[][] m;

public int racecar(int target) {

if (m == null) {

final int kMaxT = 10000;

m = new int[kMaxT + 1][2];

for (int t = 1; t <= kMaxT; ++t) {

int n = (int)Math.ceil(Math.log(t + 1) / Math.log(2));

if (1 << n == t + 1) {

m[t][0] = n;

m[t][1] = n + 1;

continue;

}

int l = (1 << n) - 1 - t;

m[t][0] = n + 1 + Math.min(m[l][1], m[l][0] + 1);

m[t][1] = n + 1 + Math.min(m[l][0], m[l][1] + 1);

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

for (int d = 0; d <= 1; d++)

m[t][d] = Math.min(m[t][d], Math.min(

m[i][0] + 2 + m[t - i][d],

m[i][1] + 1 + m[t - i][d]));

}

return Math.min(m[target][0], m[target][1]);

}