花花酱 LeetCode 842. Split Array into Fibonacci Sequence

By zxi on July 26, 2018

Problem

Given a string S of digits, such as S = "123456579", we can split it into a Fibonacci-like sequence [123, 456, 579].

Formally, a Fibonacci-like sequence is a list F of non-negative integers such that:

0 <= F[i] <= 2^31 - 1, (that is, each integer fits a 32-bit signed integer type);
F.length >= 3;
and F[i] + F[i+1] = F[i+2] for all 0 <= i < F.length - 2.

Also, note that when splitting the string into pieces, each piece must not have extra leading zeroes, except if the piece is the number 0 itself.

Return any Fibonacci-like sequence split from S, or return [] if it cannot be done.

Example 1:

Input: "123456579"
Output: [123,456,579]

Example 2:

Input: "11235813"
Output: [1,1,2,3,5,8,13]

Example 3:

Input: "112358130"
Output: []
Explanation: The task is impossible.

Example 4:

Input: "0123"
Output: []
Explanation: Leading zeroes are not allowed, so "01", "2", "3" is not valid.

Example 5:

Input: "1101111"
Output: [110, 1, 111]
Explanation: The output [11, 0, 11, 11] would also be accepted.

Note:

1 <= S.length <= 200
S contains only digits.

Solution: DFS

Time complexity: O(2^n)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 0 ms

class Solution {

public:

vector<int> splitIntoFibonacci(string s) {

const int n = s.length();

vector<int> nums;

function<bool(int)> dfs = [&](int pos) {

if (pos == n) return nums.size() >= 3;

int max_len = s[pos] == '0' ? 1 : 10;

long num = 0;

for (int i = pos; i < min(pos + max_len, n); ++i) {

num = num * 10 + (s[i] - '0');

if (num > INT_MAX) break;

if (nums.size() >= 2) {

long sum = nums.rbegin()[0];

sum += nums.rbegin()[1];

if (num > sum) break;

else if (num < sum) continue;

// num must equaals to sum.

}

nums.push_back(num);

if (dfs(i + 1)) return true;

nums.pop_back();

}

return false;

};

dfs(0);

return nums;

}

};

花花酱 LeetCode 47. Permutations II

By zxi on July 26, 2018

Problem

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

Example:

Input: [1,1,2]
Output:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

Solution

Time complexity: O(n!)

Space complexity: O(n + k)

// Author: Huahua

// Running time: 20 ms

class Solution {

public:

vector<vector<int>> permuteUnique(vector<int>& nums) {

sort(begin(nums), end(nums));

vector<vector<int>> ans;

vector<int> used(nums.size());

vector<int> cur;

dfs(nums, cur, used, ans);

return ans;

}

private:

void dfs(const vector<int>& nums, vector<int>& cur, vector<int>& used, vector<vector<int>>& ans) {

if (cur.size() == nums.size()) {

ans.push_back(cur);

return;

}

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

if (used[i]) continue;

// Same number can be only used once at each depth.

if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;

used[i] = 1;

cur.push_back(nums[i]);

dfs(nums, cur, used, ans);

cur.pop_back();

used[i] = 0;

}

};

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

花花酱 LeetCode 842. Split Array into Fibonacci Sequence

Problem

Solution: DFS

花花酱 LeetCode 47. Permutations II

Problem

Solution

Related Problems

花花酱 LeetCode 22. Generate Parentheses

Problem

Solution: DFS

Related Problems

花花酱 LeetCode 43. Multiply Strings

Problem

Solution: Simulation

Huahua's Tech Road

花花酱 LeetCode 842. Split Array into Fibonacci Sequence

Problem

Solution: DFS

花花酱 LeetCode 47. Permutations II

Problem

Solution

Related Problems

花花酱 LeetCode 22. Generate Parentheses

Problem

Solution: DFS

Related Problems

花花酱 LeetCode 43. Multiply Strings

Problem

Solution: Simulation

花花酱 LeetCode 2. Add Two Numbers

Problem

Solution: Simulation

C++

Java

Python3

Related Problems