Posts published in July 2018

花花酱 LeetCode 135. Candy

By zxi on July 27, 2018

Problem

There are N children standing in a line. Each child is assigned a rating value.

You are giving candies to these children subjected to the following requirements:

Each child must have at least one candy.
Children with a higher rating get more candies than their neighbors.

What is the minimum candies you must give?

Example 1:

Input: [1,0,2]
Output: 5
Explanation: You can allocate to the first, second and third child with 2, 1, 2 candies respectively.

Example 2:

Input: [1,2,2]
Output: 4
Explanation: You can allocate to the first, second and third child with 1, 2, 1 candies respectively.
             The third child gets 1 candy because it satisfies the above two conditions.

Solution: Greedy

First pass: left to right, the right one will have one more candy than the left one if taller.

Second pass: right to left, the left one will be at least one more candy than the right one if taller.

Time Complexity: O(n)

Space Complexity: O(n)

C++

class Solution {

public:

int candy(vector<int>& ratings) {

const int n = ratings.size();

vector<int> ans(n, 1);

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

if (ratings[i] > ratings[i - 1]) ans[i] = ans[i - 1] + 1;

for (int i = n - 2; i >= 0; --i)

if (ratings[i] > ratings[i + 1]) ans[i] = max(ans[i], ans[i + 1] + 1);

return accumulate(begin(ans), end(ans), 0);

}

};

花花酱 LeetCode 148. Sort List

By zxi on July 26, 2018

Problem

Sort a linked list in O(n log n) time using constant space complexity.

Example 1:

Input: 4->2->1->3
Output: 1->2->3->4

Example 2:

Input: -1->5->3->4->0
Output: -1->0->3->4->5

Solution: Merge Sort

Top-down (recursion)

Time complexity: O(nlogn)

Space complexity: O(logn)

C++

// Author: Huahua

// Running time: 32 ms

/**

* Definition for singly-linked list.

* struct ListNode {

* int val;

* ListNode *next;

* ListNode(int x) : val(x), next(NULL) {}

* };

class Solution {

public:

ListNode* sortList(ListNode* head) {

// 0 or 1 element, we are done.

if (!head || !head->next) return head;

ListNode* slow = head;

ListNode* fast = head->next;

while (fast && fast->next) {

fast = fast->next->next;

slow = slow->next;

}

ListNode* mid = slow->next;

slow->next = nullptr; // Break the list.

return merge(sortList(head), sortList(mid));

}

private:

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

ListNode dummy(0);

ListNode* tail = &dummy;

while (l1 && l2) {

if (l1->val > l2->val) swap(l1, l2);

tail->next = l1;

l1 = l1->next;

tail = tail->next;

}

tail->next = l1 ? l1 : l2;

return dummy.next;

}

};

Java

// Author: Huahua

// Running time: 6 ms

class Solution {

public ListNode sortList(ListNode head) {

if (head == null || head.next == null) return head;

ListNode slow = head;

ListNode fast = head.next;

while (fast != null && fast.next != null) {

fast = fast.next.next;

slow = slow.next;

}

ListNode mid = slow.next;

slow.next = null;

return merge(sortList(head), sortList(mid));

}

private ListNode merge(ListNode l1, ListNode l2) {

ListNode dummy = new ListNode(0);

ListNode tail = dummy;

while (l1 != null && l2 != null) {

if (l1.val > l2.val) {

ListNode tmp = l1;

l1 = l2;

l2 = tmp;

}

tail.next = l1;

l1 = l1.next;

tail = tail.next;

}

tail.next = (l1 != null) ? l1 : l2;

return dummy.next;

}

Python3

# Author: Huahua, 232 ms

class Solution:

def sortList(self, head):

def merge(l1, l2):

dummy = ListNode(0)

tail = dummy

while l1 and l2:

if l1.val > l2.val: l1, l2 = l2, l1

tail.next = l1

l1 = l1.next

tail = tail.next

tail.next = l1 if l1 else l2

return dummy.next

if not head or not head.next: return head

slow = head

fast = head.next

while fast and fast.next:

fast = fast.next.next

slow = slow.next

mid = slow.next

slow.next = None

return merge(self.sortList(head), self.sortList(mid))

bottom up

Time complexity: O(nlogn)

Space complexity: O(1)

// Author: Huahua

// Running time: 32 ms

class Solution {

public:

ListNode* sortList(ListNode* head) {

// 0 or 1 element, we are done.

if (!head || !head->next) return head;

int len = 1;

ListNode* cur = head;

while (cur = cur->next) ++len;

ListNode dummy(0);

dummy.next = head;

ListNode* l;

ListNode* r;

ListNode* tail;

for (int n = 1; n < len; n <<= 1) {

cur = dummy.next; // partial sorted head

tail = &dummy;

while (cur) {

l = cur;

r = split(l, n);

cur = split(r, n);

auto merged = merge(l, r);

tail->next = merged.first;

tail = merged.second;

}

return dummy.next;

}

private:

// Splits the list into two parts, first n element and the rest.

// Returns the head of the rest.

ListNode* split(ListNode* head, int n) {

while (--n && head)

head = head->next;

ListNode* rest = head ? head->next : nullptr;

if (head) head->next = nullptr;

return rest;

}

// Merges two lists, returns the head and tail of the merged list.

pair<ListNode*, ListNode*> merge(ListNode* l1, ListNode* l2) {

ListNode dummy(0);

ListNode* tail = &dummy;

while (l1 && l2) {

if (l1->val > l2->val) swap(l1, l2);

tail->next = l1;

l1 = l1->next;

tail = tail->next;

}

tail->next = l1 ? l1 : l2;

while (tail->next) tail = tail->next;

return {dummy.next, tail};

}

};

花花酱 LeetCode 101. Symmetric Tree

By zxi on July 26, 2018

Problem

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

But the following [1,2,2,null,3,null,3] is not:

Note:
Bonus points if you could solve it both recursively and iteratively.

Solution: Recursion

Time complexity: O(n)

Space complexity: O(n)

C++

class Solution {

public:

bool isSymmetric(TreeNode* root) {

return isMirror(root, root);

}

private:

bool isMirror(TreeNode* root1, TreeNode* root2) {

if (!root1 && !root2) return true;

if (!root1 || !root2) return false;

return root1->val == root2->val

&& isMirror(root1->right, root2->left)

&& isMirror(root1->left, root2->right);

}

};

Python

"""

Author: Huahua

Running time: 48 ms

"""

class Solution:

def isSymmetric(self, root):

def isMirror(root1, root2):

if not root1 and not root2: return True

if not root1 or not root2: return False

return root1.val == root2.val \

and isMirror(root1.left, root2.right) \

and isMirror(root2.left, root1.right)

return isMirror(root, root)

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;

}

};

Posts published in July 2018

花花酱 LeetCode 135. Candy

Problem

Solution: Greedy

花花酱 LeetCode 101. Symmetric Tree

Problem

Solution: Recursion

C++

Python

Related Problems

花花酱 LeetCode 842. Split Array into Fibonacci Sequence

Problem

Solution: DFS

花花酱 LeetCode 47. Permutations II

Problem

Solution

Related Problems