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

}

花花酱 LeetCode 817. Linked List Components

By zxi on April 14, 2018

Problem

题目大意：给你一个链表，再给你一些合法的节点，问你链表中有多少个连通分量（所有节点必须合法）。

https://leetcode.com/problems/linked-list-components/description/

We are given head, the head node of a linked list containing unique integer values.

We are also given the list G, a subset of the values in the linked list.

Return the number of connected components in G, where two values are connected if they appear consecutively in the linked list.

Example 1:

Input: 
head: 0->1->2->3
G = [0, 1, 3]
Output: 2
Explanation: 
0 and 1 are connected, so [0, 1] and [3] are the two connected components.

Example 2:

Input: 
head: 0->1->2->3->4
G = [0, 3, 1, 4]
Output: 2
Explanation: 
0 and 1 are connected, 3 and 4 are connected, so [0, 1] and [3, 4] are the two connected components.

Note:

If N is the length of the linked list given by head, 1 <= N <= 10000.
The value of each node in the linked list will be in the range [0, N - 1].
1 <= G.length <= 10000.
G is a subset of all values in the linked list.

Solution1: Graph Traversal using DFS

// Author: Huahua

// Running time: 76 ms

class Solution {

public:

int numComponents(ListNode* head, vector<int>& G) {

unordered_set<int> f(G.begin(), G.end());

unordered_map<int, vector<int>> g;

int u = head->val;

while (head->next) {

head = head->next;

int v = head->val;

if (f.count(v) && f.count(u)) {

g[u].push_back(v);

g[v].push_back(u);

}

u = v;

}

int ans = 0;

unordered_set<int> visited;

for (int u : G) {

if (visited.count(u)) continue;

++ans;

dfs(u, g, visited);

}

return ans;

}

private:

void dfs(int cur, unordered_map<int, vector<int>>& g, unordered_set<int>& visited) {

if (visited.count(cur)) return;

visited.insert(cur);

for (const int next : g[cur])

dfs(next, g, visited);

}

};

Solution 2: Count tail node in sub graph

// Author: Huahua

// Running time: 35 ms

class Solution {

public:

int numComponents(ListNode* head, vector<int>& G) {

unordered_set<int> g(G.begin(), G.end());

int ans = 0;

while (head) {

if (g.count(head->val) && (!head->next || !g.count(head->next->val)))

++ans;

head = head->next;

}

return ans;

}

};

花花酱 LeetCode 819. Most Common Word

By zxi on April 14, 2018

Problem

题目大意：找出一个段落中出现次数最多的单词。

https://leetcode.com/problems/most-common-word/description/

Given a paragraph and a list of banned words, return the most frequent word that is not in the list of banned words. It is guaranteed there is at least one word that isn’t banned, and that the answer is unique.

Words in the list of banned words are given in lowercase, and free of punctuation. Words in the paragraph are not case sensitive. The answer is in lowercase.

Example:
Input: 
paragraph = "Bob hit a ball, the hit BALL flew far after it was hit."
banned = ["hit"]
Output: "ball"
Explanation: 
"hit" occurs 3 times, but it is a banned word.
"ball" occurs twice (and no other word does), so it is the most frequent non-banned word in the paragraph. 
Note that words in the paragraph are not case sensitive,
that punctuation is ignored (even if adjacent to words, such as "ball,"), 
and that "hit" isn't the answer even though it occurs more because it is banned.

Note:

1 <= paragraph.length <= 1000.
1 <= banned.length <= 100.
1 <= banned[i].length <= 10.
The answer is unique, and written in lowercase (even if its occurrences in paragraph may have uppercase symbols, and even if it is a proper noun.)
paragraph only consists of letters, spaces, or the punctuation symbols !?',;.
Different words in paragraph are always separated by a space.
There are no hyphens or hyphenated words.
Words only consist of letters, never apostrophes or other punctuation symbols.

Solution: Hashtable

// Author: Huahua

// Running time: 8 ms

class Solution {

public:

string mostCommonWord(string paragraph, vector<string>& banned) {

unordered_set<string> b(banned.begin(), banned.end());

unordered_map<string, int> counts;

const string pattern = "!?',;. ";

int best = 0;

string ans;

const int n = paragraph.size();

string word;

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

if (i == n || pattern.find(paragraph[i]) != string::npos) {

if (++counts[word] > best && !b.count(word) && word.size() > 0) {

best = counts[word];

ans = word;

}

word.clear();

} else {

word += tolower(paragraph[i]);

}

return ans;

}

};

花花酱 LeetCode 816. Ambiguous Coordinates

By zxi on April 14, 2018

Problem

题目大意：把一串数字分成两段，输出所有合法的分法（可以加小数点）。

https://leetcode.com/problems/ambiguous-coordinates/description/

We had some 2-dimensional coordinates, like "(1, 3)" or "(2, 0.5)". Then, we removed all commas, decimal points, and spaces, and ended up with the string S. Return a list of strings representing all possibilities for what our original coordinates could have been.

Our original representation never had extraneous zeroes, so we never started with numbers like “00”, “0.0”, “0.00”, “1.0”, “001”, “00.01”, or any other number that can be represented with less digits. Also, a decimal point within a number never occurs without at least one digit occuring before it, so we never started with numbers like “.1”.

The final answer list can be returned in any order. Also note that all coordinates in the final answer have exactly one space between them (occurring after the comma.)

Example 1:
Input: "(123)"
Output: ["(1, 23)", "(12, 3)", "(1.2, 3)", "(1, 2.3)"]

Example 2:
Input: "(00011)"
Output:  ["(0.001, 1)", "(0, 0.011)"]
Explanation: 
0.0, 00, 0001 or 00.01 are not allowed.

Example 3:
Input: "(0123)"
Output: ["(0, 123)", "(0, 12.3)", "(0, 1.23)", "(0.1, 23)", "(0.1, 2.3)", "(0.12, 3)"]

Example 4:
Input: "(100)"
Output: [(10, 0)]
Explanation: 
1.0 is not allowed.

Solution: Brute Force

Time complexity: O(n^3)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 16 ms

class Solution {

public:

vector<string> ambiguousCoordinates(string S) {

vector<string> ans;

int n = S.length();

for (int l1 = 1; l1 <= n - 3; ++l1) {

int l2 = n - l1 - 2;

string s1 = S.substr(1, l1);

string s2 = S.substr(l1 + 1, l2);

if (valid(s1) && valid(s2))

ans.push_back("(" + s1 + ", " + s2 + ")");

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

string ts1 = s1;

if (i > 0) ts1.insert(i, ".");

if (!valid(ts1)) continue;

for (int j = 0; j < l2; ++j) {

if (i == 0 && j == 0) continue;

string ts2 = s2;

if (j > 0) ts2.insert(j, ".");

if (!valid(ts2)) continue;

ans.push_back("(" + ts1 + ", " + ts2 + ")");

}

return ans;

}

private:

bool valid(const string& s) {

bool p = false; // has "."

bool d = false; // has digits in front of "."

int zeros = 0; // leading zeros

int i = 0;

while (s[zeros] == '0' && zeros < s.length()) ++zeros;

for (int i = zeros; i < s.length(); ++i) {

if (!p && isdigit(s[i])) d = true;

if (s[i] == '.') p = true;

}

if (zeros == 1 && s != "0" && !p || zeros > 1) return false;

if (p && (s.back() == '0' || s.back() == '.' || zeros > 0 && d)) return false;

return true;

}

};

花花酱 LeetCode 331. Verify Preorder Serialization of a Binary Tree

By zxi on April 13, 2018

Problem

题目大意：验证二叉树前序遍历的序列化是否合法。

https://leetcode.com/problems/verify-preorder-serialization-of-a-binary-tree/description/

One way to serialize a binary tree is to use pre-order traversal. When we encounter a non-null node, we record the node’s value. If it is a null node, we record using a sentinel value such as #.

     _9_
    /   \
   3     2
  / \   / \
 4   1  #  6
/ \ / \   / \
# # # #   # #

For example, the above binary tree can be serialized to the string "9,3,4,#,#,1,#,#,2,#,6,#,#", where #represents a null node.

Given a string of comma separated values, verify whether it is a correct preorder traversal serialization of a binary tree. Find an algorithm without reconstructing the tree.

Each comma separated value in the string must be either an integer or a character '#' representing nullpointer.

You may assume that the input format is always valid, for example it could never contain two consecutive commas such as "1,,3".

Example 1:
"9,3,4,#,#,1,#,#,2,#,6,#,#"
Return true

Example 2:
"1,#"
Return false

Example 3:
"9,#,#,1"
Return false

Credits:
Special thanks to @dietpepsi for adding this problem and creating all test cases.

Solution: Recursion

If a node is not null, it must has two children, thus verify left subtree and right subtree recursively.
If a not is null, the current char must be ‘#’

Time complexity: O(n)

Space complexity: O(h)

C++

// Author: Huahua

// Running time: 5 ms

class Solution {

public:

bool isValidSerialization(string preorder) {

int pos = 0;

return isValid(preorder, pos) && pos == preorder.length();

}

private:

bool isValid(const string& s, int& pos) {

if (pos >= s.length()) return false;

if (isdigit(s[pos])) {

while (isdigit(s[pos])) ++pos;

return isValid(s, ++pos) && isValid(s, ++pos);

}

return s[pos++] == '#';

}

};

Huahua's Tech Road

花花酱 LeetCode 818. Race Car

Problem

Visualization of the Solution

Solution 1: BFS

C++/Str

C++/Int

Solution 2: DP O(TlogT)

C++

Solution 3: DP O(T^2)

C++

C++/opt

Java

花花酱 LeetCode 817. Linked List Components

Problem

Solution1: Graph Traversal using DFS

Solution 2: Count tail node in sub graph

花花酱 LeetCode 819. Most Common Word

Problem

Solution: Hashtable

花花酱 LeetCode 816. Ambiguous Coordinates

Problem

Solution: Brute Force

花花酱 LeetCode 331. Verify Preorder Serialization of a Binary Tree

Problem

Solution: Recursion