花花酱 LeetCode 22. Generate Parentheses

By zxi on July 26, 2018

Problem

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

Solution: DFS

Time complexity: O(2^n)

Space complexity: O(k + n)

C++

// Author: Huahua

// Running time: 0 ms

class Solution {

public:

vector<string> generateParenthesis(int n) {

vector<string> ans;

string cur;

if (n > 0) dfs(n, n, cur, ans);

return ans;

}

private:

void dfs(int l, int r, string& s, vector<string>& ans) {

if (l + r == 0) {

ans.push_back(s);

return;

}

if (r < l) return;

if (l > 0) {

dfs(l - 1, r, s += "(", ans);

s.pop_back();

}

if (r > 0) {

dfs(l, r - 1, s += ")", ans);

s.pop_back();

}

};

Problem

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.

Example 1:

Input: num1 = "2", num2 = "3"
Output: "6"

Example 2:

Input: num1 = "123", num2 = "456"
Output: "56088"

Note:

The length of both num1 and num2 is < 110.
Both num1 and num2 contain only digits 0-9.
Both num1 and num2 do not contain any leading zero, except the number 0 itself.
You must not use any built-in BigInteger library or convert the inputs to integer directly.

Solution: Simulation

Simulate multiplication one digit at a time.

Time complexity: O(l1*l2)

Space complexity: O(l1 + l2)

C++

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

string multiply(string num1, string num2) {

const int l1 = num1.length();

const int l2 = num2.length();

string ans(l1 + l2, '0');

for (int i = l1 - 1; i >= 0; --i)

for (int j = l2 - 1; j >= 0; --j) {

int sum = (ans[i + j + 1] - '0') + (num1[i] - '0') * (num2[j] - '0');

ans[i + j + 1] = (sum % 10) + '0';

ans[i + j] += sum / 10;

}

for (int i = 0; i < ans.length(); ++i)

if (ans[i] != '0' || i == ans.length() - 1) return ans.substr(i);

return "";

}

};

花花酱 LeetCode 2. Add Two Numbers

By zxi on July 25, 2018

Problem

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

Solution: Simulation

Simulate the addition, draw two numbers (one each) from l1, l2, if list is empty draw 0.

Using a dummy head makes things easier.

Time complexity: O(max(l1,l2))

Space complexity: O(max(l1,l2))

C++

// Author: Huahua

// Running time: 28 ms

class Solution {

public:

ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {

ListNode dummy(0);

ListNode* tail = &dummy;

int sum = 0;

while (l1 || l2 || sum) {

sum += (l1 ? l1->val : 0) + (l2 ? l2->val : 0);

l1 = l1 ? l1->next : nullptr;

l2 = l2 ? l2->next : nullptr;

tail->next = new ListNode(sum % 10);

sum /= 10;

tail = tail->next;

}

return dummy.next;

}

};

Java

// Author: Huahua

// Running time: 30 ms

class Solution {

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {

int sum = 0;

ListNode dummy = new ListNode(0);

ListNode tail = dummy;

while (l1 != null || l2 != null || sum != 0) {

if (l1 != null) {

sum += l1.val;

l1 = l1.next;

}

if (l2 != null) {

sum += l2.val;

l2 = l2.next;

}

tail.next = new ListNode(sum % 10);

sum /= 10;

tail = tail.next;

}

return dummy.next;

}

Python3

"""

Author: Huahua

Running time: 112 ms

"""

class Solution:

def addTwoNumbers(self, l1, l2):

s = 0

dummy = ListNode(0)

tail = dummy

while l1 or l2 or s > 0:

s += (l1.val if l1 else 0) + (l2.val if l2 else 0)

l1 = l1.next if l1 else None

l2 = l2.next if l2 else None

tail.next = ListNode(s % 10)

s //= 10

tail = tail.next

return dummy.next

Problem

https://leetcode.com/problems/is-graph-bipartite/

Given an undirected graph, return true if and only if it is bipartite.

Recall that a graph is bipartite if we can split it’s set of nodes into two independent subsets A and B such that every edge in the graph has one node in A and another node in B.

The graph is given in the following form: graph[i] is a list of indexes j for which the edge between nodes i and j exists. Each node is an integer between 0 and graph.length - 1. There are no self edges or parallel edges: graph[i] does not contain i, and it doesn’t contain any element twice.

Example 1:
Input: [[1,3], [0,2], [1,3], [0,2]]
Output: true
Explanation: 
The graph looks like this:
0----1
|    |
|    |
3----2
We can divide the vertices into two groups: {0, 2} and {1, 3}.

Example 2:
Input: [[1,2,3], [0,2], [0,1,3], [0,2]]
Output: false
Explanation: 
The graph looks like this:
0----1
| \  |
|  \ |
3----2
We cannot find a way to divide the set of nodes into two independent subsets.

Note:

graph will have length in range [1, 100].
graph[i] will contain integers in range [0, graph.length - 1].
graph[i] will not contain i or duplicate values.
The graph is undirected: if any element j is in graph[i], then i will be in graph[j].

Solution: Graph Coloring

For each node

If has not been colored, color it to RED(1).
Color its neighbors with a different color RED(1) to BLUE(-1) or BLUE(-1) to RED(-1).

If we can finish the coloring then the graph is bipartite. All red nodes on the left no connections between them and all blues nodes on the right, again no connections between them. red and blue nodes are neighbors.

Time complexity: O(V+E)

Space complexity: O(V)

C++ / DFS

// Author: Huahua

// Running time: 12 ms

class Solution {

public:

bool isBipartite(vector<vector<int>>& graph) {

const int n = graph.size();

vector<int> colors(n);

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

if (!colors[i] && !coloring(graph, colors, 1, i))

return false;

return true;

}

private:

bool coloring(const vector<vector<int>>& graph, vector<int>& colors, int color, int node) {

if (colors[node]) return colors[node] == color;

colors[node] = color;

for (int nxt : graph[node])

if (!coloring(graph, colors, -color, nxt)) return false;

return true;

}

};

Posts published in July 2018

花花酱 LeetCode 22. Generate Parentheses

Problem

Solution: DFS

Related Problems

花花酱 LeetCode 43. Multiply Strings

Problem

Solution: Simulation

花花酱 LeetCode 785. Is Graph Bipartite?

Problem

Solution: Graph Coloring

Related Problem

LeetCode Weekly Contest 94