Posts published in April 2018

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

}

};

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