Posts tagged as “hard”

花花酱 LeetCode 321. Create Maximum Number

By zxi on November 14, 2017

Problem:

Given two arrays of length m and n with digits 0-9 representing two numbers. Create the maximum number of length k <= m + n from digits of the two. The relative order of the digits from the same array must be preserved. Return an array of the k digits. You should try to optimize your time and space complexity.

Example 1:

nums1 = [3, 4, 6, 5]
nums2 = [9, 1, 2, 5, 8, 3]
k = 5
return [9, 8, 6, 5, 3]

Example 2:

nums1 = [6, 7]
nums2 = [6, 0, 4]
k = 5
return [6, 7, 6, 0, 4]

Example 3:

nums1 = [3, 9]
nums2 = [8, 9]
k = 3
return [9, 8, 9]

题目大意：给你两个数字数组和k，返回从两个数组中选取k个数字能够组成的最大值。

Idea: Greedy + DP

Solution:

Time complexity: O(k * (n1+n2)^2)

Space complexity: O(n1+n2)

C++

// Author: Huahua

// Runtime: 26 ms

class Solution {

public:

vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {

vector<int> ans;

const int n1 = nums1.size();

const int n2 = nums2.size();

for (int i = max(0, k - n2); i <= min(k, n1); ++i)

ans = max(ans, maxNumber(maxNumber(nums1, i),

maxNumber(nums2, k - i)));

return ans;

}

private:

vector<int> maxNumber(const vector<int>& nums, int k) {

vector<int> ans(k);

int j = 0;

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

while (j > 0 && nums[i] > ans[j - 1]

&& nums.size() - i > k - j) --j;

if (j < k) ans[j++] = nums[i];

}

return ans;

}

vector<int> maxNumber(const vector<int>& nums1, const vector<int>& nums2) {

vector<int> ans(nums1.size() + nums2.size());

auto s1 = nums1.cbegin();

auto e1 = nums1.cend();

auto s2 = nums2.cbegin();

auto e2 = nums2.cend();

int index = 0;

while (s1 != e1 || s2 != e2)

ans[index++] =

lexicographical_compare(s1, e1, s2, e2) ? *s2++ : *s1++;

return ans;

}

};

Java

// Author: Huahua

// Runtime: 18 ms

class Solution {

public int[] maxNumber(int[] nums1, int[] nums2, int k) {

int[] best = new int[0];

for (int i = Math.max(0, k - nums2.length);

i <= Math.min(k, nums1.length); ++i)

best = max(best, 0,

maxNumber(maxNumber(nums1, i),

maxNumber(nums2, k - i)), 0);

return best;

}

private int[] maxNumber(int[] nums, int k) {

int[] ans = new int[k];

int j = 0;

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

while (j > 0 && nums[i] > ans[j - 1]

&& nums.length - i > k - j) --j;

if (j < k)

ans[j++] = nums[i];

}

return ans;

}

private int[] maxNumber(int[] nums1, int[] nums2) {

int[] ans = new int[nums1.length + nums2.length];

int s1 = 0;

int s2 = 0;

int index = 0;

while (s1 != nums1.length || s2 != nums2.length)

ans[index++] = max(nums1, s1, nums2, s2) == nums1 ?

nums1[s1++] : nums2[s2++];

return ans;

}

private int[] max(int[] nums1, int s1, int[] nums2, int s2) {

for (int i = s1; i < nums1.length; ++i) {

int j = s2 + i - s1;

if (j >= nums2.length) return nums1;

if (nums1[i] < nums2[j]) return nums2;

if (nums1[i] > nums2[j]) return nums1;

}

return nums2;

}

花花酱 LeetCode 4. Median of Two Sorted Arrays

By zxi on November 8, 2017

题目大意：求两个已经排序的数组的中位数（如果合并后）。

Problem:

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

Example 1:

nums1 = [1, 3]

nums2 = [2]

The median is 2.0

Example 2:

nums1 = [1, 2]

nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

Idea:

Binary Search

Time complexity: O(log(min(n1,n2)))

Space complexity: O(1)

Solution: Binary Search

C++

// Author: Huahua

// Runtime: 52 ms

class Solution {

public:

double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {

const int n1 = nums1.size();

const int n2 = nums2.size();

// Make sure n1 <= n2

if (n1 > n2) return findMedianSortedArrays(nums2, nums1);

const int k = (n1 + n2 + 1) / 2;

int l = 0;

int r = n1;

while (l < r) {

const int m1 = l + (r - l) / 2;

const int m2 = k - m1;

if (nums1[m1] < nums2[m2 - 1])

l = m1 + 1;

else

r = m1;

}

const int m1 = l;

const int m2 = k - l;

const int c1 = max(m1 <= 0 ? INT_MIN : nums1[m1 - 1],

m2 <= 0 ? INT_MIN : nums2[m2 - 1]);

if ((n1 + n2) % 2 == 1)

return c1;

const int c2 = min(m1 >= n1 ? INT_MAX : nums1[m1],

m2 >= n2 ? INT_MAX : nums2[m2]);

return (c1 + c2) * 0.5;

}

};

Java

// Author: Huahua

// Runtime: 66 ms

class Solution {

public double findMedianSortedArrays(int[] nums1, int[] nums2) {

int n1 = nums1.length;

int n2 = nums2.length;

if (n1 > n2)

return findMedianSortedArrays(nums2, nums1);

int k = (n1 + n2 + 1) / 2;

int l = 0;

int r = n1;

while (l < r) {

int m1 = l + (r - l) / 2;

int m2 = k - m1;

if (nums1[m1] < nums2[m2 - 1])

l = m1 + 1;

else

r = m1;

}

int m1 = l;

int m2 = k - l;

int c1 = Math.max(m1 <= 0 ? Integer.MIN_VALUE : nums1[m1 - 1],

m2 <= 0 ? Integer.MIN_VALUE : nums2[m2 - 1]);

if ((n1 + n2) % 2 == 1)

return c1;

int c2 = Math.min(m1 >= n1 ? Integer.MAX_VALUE : nums1[m1],

m2 >= n2 ? Integer.MAX_VALUE : nums2[m2]);

return (c1 + c2) * 0.5;

}

Solution:

C++ / pair

// Author: Huahua

// Running time: 6 ms

class Solution {

public:

int maxPoints(vector<Point>& points) {

int n = points.size();

int ans = 0;

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

std::map<std::pair<int,int>, int> count;

int same_points = 1;

int max_points = 0;

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

const Point& p1 = points[i];

const Point& p2 = points[j];

if (p1.x == p2.x && p1.y == p2.y)

++same_points;

else

max_points = max(max_points, ++count[getSlope(p1, p2)]);

}

ans = max(ans, same_points + max_points);

}

return ans;

}

private:

// slope dy/dx : <dy, dx>

std::pair<int, int> getSlope(const Point& p1, const Point& p2) {

const int dx = p2.x - p1.x;

const int dy = p2.y - p1.y;

// horizontal line

if (dy == 0) return { p1.y, 0 };

// vertical line

if (dx == 0) return { 0, p1.x };

const int d = gcd(dx, dy);

return { dy / d, dx / d };

}

int gcd(int m, int n) {

return n == 0 ? m : gcd(n, m % n);

}

};

C++ / long

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

int maxPoints(vector<Point>& points) {

int n = points.size();

int ans = 0;

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

unordered_map<long, int> count;

int same_points = 1;

int max_points = 0;

const Point& p1 = points[i];

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

const Point& p2 = points[j];

if (p1.x == p2.x && p1.y == p2.y)

++same_points;

else

max_points = max(max_points, ++count[getSlope(p1, p2)]);

}

ans = max(ans, same_points + max_points);

}

return ans;

}

private:

// slope dy/dx : dy << 32 | dx

long getSlope(const Point& p1, const Point& p2) {

const int dx = p2.x - p1.x;

const int dy = p2.y - p1.y;

// horizontal line

if (dy == 0) return static_cast<long>(p1.y) << 32 | 0;

// vertical line

if (dx == 0) return static_cast<long>(0)<< 32 | p1.x;

const int d = __gcd(dx, dy);

return static_cast<long>(dy / d) << 32 | (dx / d);

}

};

花花酱 LeetCode 124. Binary Tree Maximum Path Sum

By zxi on October 17, 2017

Problem:

Given a binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

For example:
Given the below binary tree,

/ \

2 3

Return 6.

Idea:

Recursion

Time complexity O(n)

Space complexity O(h)

Solution: Recursion

C++

// Author: Huahua

// Runtime: 19 ms

class Solution {

public:

int maxPathSum(TreeNode* root) {

if (!root) return 0;

int ans = INT_MIN;

maxPathSum(root, ans);

return ans;

}

private:

int maxPathSum(TreeNode* root, int& ans) {

if (!root) return 0;

int l = max(0, maxPathSum(root->left, ans));

int r = max(0, maxPathSum(root->right, ans));

int sum = l + r + root->val;

ans = max(ans, sum);

return max(l, r) + root->val;

}

};

Python3

"""

Author: Huahua

Runtime: 138 ms (< 90.38%)

"""

class Solution(object):

def _maxPathSum(self, root):

if not root: return -sys.maxint

l = max(0, self._maxPathSum(root.left))

r = max(0, self._maxPathSum(root.right))

self.ans = max(self.ans, root.val + l + r)

return root.val + max(l, r)

def maxPathSum(self, root):

self.ans = -sys.maxint

self._maxPathSum(root)

return self.ans

Related Problems:

花花酱 LeetCode 128. Longest Consecutive Sequence

By zxi on October 2, 2017

Problem:

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

Your algorithm should run in O(n) complexity.

Idea:

Hashtable / Hashset

Time complexity: O(n)

Space complexity: O(n)

Solution 1: C++ / online

class Solution {

public:

int longestConsecutive(vector<int>& nums) {

unordered_map<int, int> h;

int ans = 0;

for (int num : nums) {

if (h.count(num)) continue;

auto it_l = h.find(num - 1);

auto it_r = h.find(num + 1);

int l = it_l != h.end() ? it_l->second : 0;

int r = it_r != h.end() ? it_r->second : 0;

int t = l + r + 1;

h[num] = h[num - l] = h[num + r] = t;

ans = max(ans, t);

}

return ans;

}

};

Solution 2: C++ / offline

class Solution {

public:

int longestConsecutive(vector<int>& nums) {

unordered_set<int> h(nums.begin(), nums.end());

int ans = 0;

for (int num : nums)

if (!h.count(num - 1)) {

int l = 0;

while (h.count(num++)) ++l;

ans = max(ans, l);

}

return ans;

}

};

Posts tagged as “hard”

花花酱 LeetCode 321. Create Maximum Number

Idea: Greedy + DP

Solution:

C++

Java

花花酱 LeetCode 4. Median of Two Sorted Arrays

Solution: Binary Search

C++

Java

Related Problem:

花花酱 LeetCode 149. Max Points on a Line

Solution:

C++ / pair

C++ / long

花花酱 LeetCode 124. Binary Tree Maximum Path Sum

Solution: Recursion

C++

Python3

花花酱 LeetCode 128. Longest Consecutive Sequence