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

}

};

花花酱 LeetCode 812. Largest Triangle Area

By zxi on April 8, 2018

Problem

题目大意：给你一些点，求用这些点能够成的最大的三角形面积是多少？

https://leetcode.com/problems/largest-triangle-area/description/

You have a list of points in the plane. Return the area of the largest triangle that can be formed by any 3 of the points.

Example:
Input: points = [[0,0],[0,1],[1,0],[0,2],[2,0]]
Output: 2
Explanation: 
The five points are show in the figure below. The red triangle is the largest.

Notes:

3 <= points.length <= 50.
No points will be duplicated.
-50 <= points[i][j] <= 50.
Answers within 10^-6 of the true value will be accepted as correct.

Solution: Brute Force

Time complexity: O(n^3)

Space complexity: O(1)

// Author: Huahua

// Running time: 11 ms

class Solution {

public:

double largestTriangleArea(vector<vector<int>>& points) {

const int n = points.size();

double best = 0.0;

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

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

for (int k = j + 1; k < n; ++k) {

const double a = dist(points[i], points[j]);

const double b = dist(points[i], points[k]);

const double c = dist(points[j], points[k]);

const double s = (a + b + c) / 2;

const double area = sqrt(s * (s - a) * (s - b) * (s - c));

best = max(best, area);

}

return best;

}

private:

static inline double dist(const vector<int>& p1, const vector<int>& p2) {

return sqrt((p1[0] - p2[0]) * (p1[0] - p2[0]) + (p1[1] - p2[1]) * (p1[1] - p2[1]));

}

};

花花酱 LeetCode 814. Binary Tree Pruning

By zxi on April 7, 2018

Problem:

题目大意：把不含有1的节点的子树全部删除。

https://leetcode.com/problems/binary-tree-pruning/description/

We are given the head node root of a binary tree, where additionally every node’s value is either a 0 or a 1.

Return the same tree where every subtree (of the given tree) not containing a 1 has been removed.

(Recall that the subtree of a node X is X, plus every node that is a descendant of X.)

Example 1:
Input: [1,null,0,0,1]
Output: [1,null,0,null,1]
 
Explanation: 
Only the red nodes satisfy the property "every subtree not containing a 1".
The diagram on the right represents the answer.

Example 2:
Input: [1,0,1,0,0,0,1]
Output: [1,null,1,null,1]

Example 3:
Input: [1,1,0,1,1,0,1,0]
Output: [1,1,0,1,1,null,1]

Note:

The binary tree will have at most 100 nodes.
The value of each node will only be 0 or 1.

Solution: Recursion

Time complexity: O(n)

Space complexity: O(h)

C++

// Author: Huahua

// Running time: 6 ms

class Solution {

public:

TreeNode* pruneTree(TreeNode* root) {

if (!root) return root;

root->left = pruneTree(root->left);

root->right = pruneTree(root->right);

if (root->val == 1 || root->left || root->right)

return root;

delete root;

return nullptr;

}

};

Java

// Author: Huahua

// Running time: 2 ms

class Solution {

public TreeNode pruneTree(TreeNode root) {

if (root == null) return root;

root.left = pruneTree(root.left);

root.right = pruneTree(root.right);

return (root.val == 1 || root.left != null || root.right != null) ? root : null;

}

Python3

// Author: Huahua

// Running time: 36 ms

class Solution:

def pruneTree(self, root):

if not root: return root

root.left = self.pruneTree(root.left)

root.right = self.pruneTree(root.right)

return root if root.val == 1 or root.left or root.right else None

Huahua's Tech Road

花花酱 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++

花花酱 LeetCode 812. Largest Triangle Area

Problem

Solution: Brute Force

花花酱 LeetCode 814. Binary Tree Pruning

Problem:

Solution: Recursion