Posts published in March 2018

花花酱 LeetCode 454. 4Sum II

By zxi on March 5, 2018

题目大意：给你4个组数：A, B, C, D。问有多少组组合的A[i] + B[j] + C[k] + D[l] 的和为0。

Given four lists A, B, C, D of integer values, compute how many tuples (i, j, k, l) there are such that A[i] + B[j] + C[k] + D[l]is zero.

To make problem a bit easier, all A, B, C, D have same length of N where 0 ≤ N ≤ 500. All integers are in the range of -2²⁸ to 2²⁸ – 1 and the result is guaranteed to be at most 2³¹ – 1.

Example:

Input:

A = [ 1, 2]

B = [-2,-1]

C = [-1, 2]

D = [ 0, 2]

Output:

Explanation:

The two tuples are:

1. (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0

2. (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0

Solution 1: HashTable

Split the arrays into two groups: (A, B), (C, D)

Create the Minkowski sum of two groups and count the occurrence of each element.

e.g. A = [1, 2, 3], B = [0, -1, 1]

Minkowski sum(A, B) SAB= [0, 1, 2, 3, 4] => [0:1, 1:2, 2:3, 3:2, 4:1]

for each element s in SAB, check whether -s is in Minkowski sum(C, D) SCD

ans = sum(SAB[s] * SCD[-s]), for all s, that s in SAB and -s in SCD

Time complexity: O(n^2)

Space complexity: O(n^2)

C++

// Author: Huahua

// Running time: 217 ms

class Solution {

public:

int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {

unordered_map<int, int> sums;

for (int a : A)

for (int b : B)

++sums[a + b];

int ans = 0;

for (int c : C)

for (int d : D) {

auto it = sums.find(- c - d);

if (it != sums.end()) ans += it->second;

}

return ans;

}

};

Python3

"""

Author: Huahua

Running time: 672 ms

"""

class Solution:

def fourSumCount(self, A, B, C, D):

s = collections.Counter([a + b for a in A for b in B])

return sum(s[-c - d] for c in C for d in D)

Related Problems:

[解题报告] LeetCode 1. Two Sum – 花花酱

花花酱 LeetCode 515. Find Largest Value in Each Tree Row

By zxi on March 5, 2018

题目大意：给你一棵树，返回每一层最大的元素的值。

You need to find the largest value in each row of a binary tree.

Example:

<b>Input:</b>

/ \

3 2

/ \ \

5 3 9

<b>Output:</b> [1, 3, 9]

Solution 1: Inorder traversal + depth info

C++

// Author: Huahua

// Running time: 15 ms

class Solution {

public:

vector<int> largestValues(TreeNode* root) {

vector<int> ans;

inorder(root, 0, ans);

return ans;

}

private:

void inorder(TreeNode* root, int d, vector<int>& ans) {

if (root == nullptr) return;

while (ans.size() <= d) ans.push_back(INT_MIN);

inorder(root->left, d + 1, ans);

ans[d] = max(ans[d], root->val);

inorder(root->right, d + 1, ans);

}

};

Python3

"""

Author: Huahua

Running time: 72 ms (beats 100%)

"""

class Solution:

def largestValues(self, root):

def inorder(root, d, ans):

if not root: return ans

if len(ans) <= d: ans += [float('-inf')]

inorder(root.left, d + 1, ans)

if root.val > ans[d]: ans[d] = root.val

inorder(root.right, d + 1, ans)

return ans

return inorder(root, 0, [])

花花酱 LeetCode 513. Find Bottom Left Tree Value

By zxi on March 5, 2018

题目大意：给你一棵树，返回左下角（最后一行最左面）的节点的值。

https://leetcode.com/problems/find-bottom-left-tree-value/description/

Problem:

Given a binary tree, find the leftmost value in the last row of the tree.

Example 1:

Input:

/ \

1 3

Output:

Example 2:

Input:

/ \

2 3

/ / \

4 5 6

Output:

Note: You may assume the tree (i.e., the given root node) is not NULL.

Solution 1: Inorder traversal with depth info

The first node visited in the deepest row is the answer.

// Author: Huahua

// Running time: 12 ms

class Solution {

public:

int findBottomLeftValue(TreeNode* root) {

int max_row = -1;

int ans;

dfs(root, 0, max_row, ans);

return ans;

}

private:

void inorder(TreeNode* root, int row, int& max_row, int& ans) {

if (root == nullptr) return;

inorder(root->left, row + 1, max_row, ans);

if (row > max_row) {

ans = root->val;

max_row = row;

}

inorder(root->right, row + 1, max_row, ans);

}

};

Python3

"""

Author: Huahua

Running time: 92 ms

"""

class Solution:

def inorder(self, root, row):

if not root: return

self.inorder(root.left, row + 1)

if row > self.max_row:

self.max_row, self.ans = row, root.val

self.inorder(root.right, row + 1)

def findBottomLeftValue(self, root):

self.ans, self.max_row = 0, -1

self.inorder(root, 0)

return self.ans

花花酱 LeetCode 496. Next Greater Element I

By zxi on March 5, 2018

题目大意：给你一个组数A里面每个元素都不相同。再给你一个数组B，元素是A的子集，问对于B中的每个元素，在A数组中相同元素之后第一个比它的元素是多少。

Problem:

You are given two arrays (without duplicates) nums1 and nums2 where nums1’s elements are subset of nums2. Find all the next greater numbers for nums1‘s elements in the corresponding places of nums2.

The Next Greater Number of a number x in nums1 is the first greater number to its right in nums2. If it does not exist, output -1 for this number.

Example 1:

Input: nums1 = [4,1,2], nums2 = [1,3,4,2].

Output: [-1,3,-1]

Explanation:

For number 4 in the first array, you cannot find the next greater number for it in the second array, so output -1.

For number 1 in the first array, the next greater number for it in the second array is 3.

For number 2 in the first array, there is no next greater number for it in the second array, so output -1.

Example 2:

Input: nums1 = [2,4], nums2 = [1,2,3,4].

Output: [3,-1]

Explanation:

For number 2 in the first array, the next greater number for it in the second array is 3.

For number 4 in the first array, there is no next greater number for it in the second array, so output -1.

Note:

All elements in nums1 and nums2 are unique.
The length of both nums1 and nums2 would not exceed 1000.

Solution 1: Brute Force

Time complexity: O(n^2)

Space complexity: O(1)

// Author: Huahua

// Running time: 13 ms

class Solution {

public:

vector<int> nextGreaterElement(vector<int>& findNums, vector<int>& nums) {

vector<int> ans;

for (int num : findNums) {

ans.push_back(-1);

int index = std::find(nums.begin(), nums.end(), num) - nums.begin();

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

if (nums[i] > num) {

ans.back() = nums[i];

break;

}

return ans;

}

};

Solution 2: HashTable + Brute Force

Time complexity: O(n^2)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 15 ms

class Solution {

public:

vector<int> nextGreaterElement(vector<int>& findNums, vector<int>& nums) {

unordered_map<int, int> indices;

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

indices[nums[i]] = i;

vector<int> ans;

for (int num : findNums) {

ans.push_back(-1);

for (int i = indices[num]; i < nums.size(); ++i)

if (nums[i] > num) {

ans.back() = nums[i];

break;

}

return ans;

}

};

Solution 3: Stack + HashTable

Using a stack to store the nums whose next greater isn’t found yet.

// Author: Huahua

// Running time: 11 ms

class Solution {

public:

vector<int> nextGreaterElement(vector<int>& findNums, vector<int>& nums) {

stack<int> s;

unordered_map<int, int> next;

for (int num : nums) {

while (!s.empty() && num > s.top()) {

next[s.top()] = num;

s.pop();

}

s.push(num);

}

vector<int> ans;

for (int num : findNums)

ans.push_back(next.count(num) ? next[num] : -1);

return ans;

}

};

花花酱 LeetCode 575. Distribute Candies

By zxi on March 5, 2018

题目大意：有一些不同种类的糖果，男生女生各得一半数量的糖果，问女生最多可能得到多少种不同种类的糖果。

Given an integer array with even length, where different numbers in this array represent different kinds of candies. Each number means one candy of the corresponding kind. You need to distribute these candies equally in number to brother and sister. Return the maximum number of kinds of candies the sister could gain.

Example 1:

Input: candies = [1,1,2,2,3,3]

Output: 3

Explanation:

There are three different kinds of candies (1, 2 and 3), and two candies for each kind.

Optimal distribution: The sister has candies [1,2,3] and the brother has candies [1,2,3], too.

The sister has three different kinds of candies.

Example 2:

Input: candies = [1,1,2,3]

Output: 2

Explanation: For example, the sister has candies [2,3] and the brother has candies [1,1].

The sister has two different kinds of candies, the brother has only one kind of candies.

Note:

The length of the given array is in range [2, 10,000], and will be even.
The number in given array is in range [-100,000, 100,000].

Solution 1: Greedy

Give all unique candies to sisters until they have n/2 candies.

Time complexity: O(n)

Space complexity: O(n)

C++ Hashset

// Author: Huahua

// Running time: 258 ms

class Solution {

public:

int distributeCandies(vector<int>& candies) {

unordered_set<int> kinds(candies.begin(), candies.end());

return min(kinds.size(), candies.size() / 2);

}

};

C++ Bitset

// Author: Huahua

// Running time: 195 ms (beats 97.61%)

class Solution {

public:

int distributeCandies(vector<int>& candies) {

constexpr int kMaxKinds = 200001;

constexpr int kOffset = 100000;

bitset<kMaxKinds> s;

for (int candy : candies)

if (!s.test(candy + kOffset))

s.set(candy + kOffset);

return std::min(s.count(), candies.size() / 2);

}

};