花花酱 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++] == '#';

}

};

花花酱 LeetCode 328. Odd Even Linked List

By zxi on April 12, 2018

Problem

题目大意：给你一个链表，把所有奇数位置的节点串在一起，后面跟着所有串在一起的偶数位置的节点。

Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes.

You should try to do it in place. The program should run in O(1) space complexity and O(nodes) time complexity.

Example:
Given 1->2->3->4->5->NULL,
return 1->3->5->2->4->NULL.

Note:
The relative order inside both the even and odd groups should remain as it was in the input.
The first node is considered odd, the second node even and so on …

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

Solution

Time complexity: O(n)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 21 ms

class Solution {

public:

ListNode* oddEvenList(ListNode* head) {

if (head == nullptr) return head;

ListNode dummy_odd(0);

ListNode dummy_even(0);

ListNode* prev_odd = &dummy_odd;

ListNode* prev_even = &dummy_even;

int index = 0;

while (head) {

auto next = head->next;

head->next = nullptr; // important

if (index++ & 1) {

prev_even->next = head;

prev_even = head;

} else {

prev_odd->next = head;

prev_odd = head;

}

head = next;

}

prev_odd->next = dummy_even.next;

return dummy_odd.next;

}

};

// Author: Huahua

// Running time: 18 ms

class Solution {

public:

ListNode* oddEvenList(ListNode* head) {

if (head == nullptr) return head;

vector<ListNode> heads(2, ListNode(0));

vector<ListNode*> prevs{&heads[0], &heads[1]};

int index = 0;

while (head) {

auto next = head->next;

head->next = nullptr; // important

prevs[index]->next = head;

prevs[index] = head;

head = next;

index ^= 1;

}

prevs[0]->next = heads[1].next;

return heads[0].next;

}

};

Java

// Author: Huahua

// Running time: 1 ms

class Solution {

public ListNode oddEvenList(ListNode head) {

ListNode[] heads = new ListNode[]{new ListNode(0), new ListNode(0)};

ListNode[] prevs = new ListNode[]{heads[0], heads[1]};

int index = 0;

while (head != null) {

ListNode next = head.next;

head.next = null;

prevs[index].next = head;

prevs[index] = prevs[index].next;

head = next;

index ^= 1;

}

prevs[0].next = heads[1].next;

return heads[0].next;

}

Python3

"""

Author: Huahua

Running time: 56 ms

"""

class Solution:

def oddEvenList(self, head):

heads = [ListNode(0), ListNode(0)]

prevs = [heads[0], heads[1]]

index = 0

while head:

nxt = head.next

head.next = None

prevs[index].next = head

prevs[index] = prevs[index].next

head = nxt

index ^= 1

prevs[0].next = heads[1].next

return heads[0].next

花花酱 LeetCode 815. Bus Routes

By zxi on April 9, 2018

Problem

题目大意：给你每辆公交车的环形路线，问最少需要坐多少辆公交车才能送S到达T。

https://leetcode.com/problems/bus-routes/description/

We have a list of bus routes. Each routes[i] is a bus route that the i-th bus repeats forever. For example if routes[0] = [1, 5, 7], this means that the first bus (0-th indexed) travels in the sequence 1->5->7->1->5->7->1->… forever.

We start at bus stop S (initially not on a bus), and we want to go to bus stop T. Travelling by buses only, what is the least number of buses we must take to reach our destination? Return -1 if it is not possible.

Example:
Input: 
routes = [[1, 2, 7], [3, 6, 7]]
S = 1
T = 6
Output: 2
Explanation: 
The best strategy is take the first bus to the bus stop 7, then take the second bus to the bus stop 6.

Note:

1 <= routes.length <= 500.
1 <= routes[i].length <= 500.
0 <= routes[i][j] < 10 ^ 6.

Solution: BFS

Time Complexity: O(m*n) m: # of buses, n: # of routes

Space complexity: O(m*n + m)

C++

// Author: Huahua

// Running time: 89 ms

class Solution {

public:

int numBusesToDestination(vector<vector<int>>& routes, int S, int T) {

if (S == T) return 0;

unordered_map<int, vector<int>> m;

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

for (const int stop : routes[i])

m[stop].push_back(i);

vector<int> visited(routes.size(), 0);

queue<int> q;

q.push(S);

int buses = 0;

while (!q.empty()) {

int size = q.size();

++buses;

while (size--) {

int curr = q.front(); q.pop();

for (const int bus : m[curr]) {

if (visited[bus]) continue;

visited[bus] = 1;

for (int stop : routes[bus]) {

if (stop == T) return buses;

q.push(stop);

}

return -1;

}

};

花花酱 LeetCode 813. Largest Sum of Averages

By zxi on April 9, 2018

Problem

题目大意：把一个数组分成k个段，求每段平均值和的最大值。

https://leetcode.com/problems/largest-sum-of-averages/description/

We partition a row of numbers A into at most K adjacent (non-empty) groups, then our score is the sum of the average of each group. What is the largest score we can achieve?

Note that our partition must use every number in A, and that scores are not necessarily integers.

Example:
Input: 
A = [9,1,2,3,9]
K = 3
Output: 20
Explanation: 
The best choice is to partition A into [9], [1, 2, 3], [9]. The answer is 9 + (1 + 2 + 3) / 3 + 9 = 20.
We could have also partitioned A into [9, 1], [2], [3, 9], for example.
That partition would lead to a score of 5 + 2 + 6 = 13, which is worse.

Note:

1 <= A.length <= 100.
1 <= A[i] <= 10000.
1 <= K <= A.length.
Answers within 10^-6 of the correct answer will be accepted as correct.

Idea

DP, use dp[k][i] to denote the largest average sum of partitioning first i elements into k groups.

Init

dp[1][i] = sum(a[0] ~ a[i – 1]) / i, for i in 1, 2, … , n.

Transition

dp[k][i] = max(dp[k – 1][j] + sum(a[j] ~ a[i – 1]) / (i – j)) for j in k – 1,…,i-1.

that is find the best j such that maximize dp[k][i]

largest sum of partitioning first j elements (a[0] ~ a[j – 1]) into k – 1 groups (already computed)

+ average of a[j] ~ a[i – 1] (partition a[j] ~ a[i – 1] into 1 group).

Answer

dp[K][n]

Solution 1: DP

Time complexity: O(kn^2)

Space complexity: O(kn)

C++

// Author: Huahua

// Running time: 9 ms

class Solution {

public:

double largestSumOfAverages(vector<int>& A, int K) {

const int n = A.size();

vector<vector<double>> dp(K + 1, vector<double>(n + 1, 0.0));

vector<double> sums(n + 1, 0.0);

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

sums[i] = sums[i - 1] + A[i - 1];

dp[1][i] = static_cast<double>(sums[i]) / i;

}

for (int k = 2; k <= K; ++k)

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

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

dp[k][i] = max(dp[k][i], dp[k - 1][j] + (sums[i] - sums[j]) / (i - j));

return dp[K][n];

}

};

C++ O(n) space

// Author: Huahua

// Running time: 8 ms

class Solution {

public:

double largestSumOfAverages(vector<int>& A, int K) {

const int n = A.size();

vector<double> dp(n + 1, 0.0);

vector<double> sums(n + 1, 0.0);

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

sums[i] = sums[i - 1] + A[i - 1];

dp[i] = static_cast<double>(sums[i]) / i;

}

for (int k = 2; k <= K; ++k) {

vector<double> tmp(n + 1, 0.0);

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

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

tmp[i] = max(tmp[i], dp[j] + (sums[i] - sums[j]) / (i - j));

dp.swap(tmp);

}

return dp[n];

}

};

Solution 2: DFS + memoriation

C++

// Author: Huahua

// Running time: 10 ms

class Solution {

public:

double largestSumOfAverages(vector<int>& A, int K) {

const int n = A.size();

m_ = vector<vector<double>>(K + 1, vector<double>(n + 1, 0.0));

sums_ = vector<double>(n + 1, 0.0);

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

sums_[i] = sums_[i - 1] + A[i - 1];

return LSA(A, n, K);

}

private:

vector<vector<double>> m_;

vector<double> sums_;

// Largest sum of averages for first n elements in A paritioned into k groups

double LSA(const vector<int>& A, int n, int k) {

if (m_[k][n] > 0) return m_[k][n];

if (k == 1) return sums_[n] / n;

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

m_[k][n] = max(m_[k][n], LSA(A, i, k - 1) + (sums_[n] - sums_[i]) / (n - i));

return m_[k][n];

}

};

Huahua's Tech Road

花花酱 LeetCode 816. Ambiguous Coordinates

Problem

Solution: Brute Force

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

Problem

Solution: Recursion

花花酱 LeetCode 328. Odd Even Linked List

Problem

Solution

花花酱 LeetCode 815. Bus Routes

Problem

Solution: BFS

花花酱 LeetCode 813. Largest Sum of Averages

Problem

Idea

Init

Transition

Answer

Solution 1: DP

C++

C++ O(n) space

Solution 2: DFS + memoriation

C++