Posts tagged as “medium”

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

}

};