花花酱 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 621. Task Scheduler

By zxi on October 28, 2017

题目大意：给你一些用字母表示的任务，执行每个任务需要单位时间的CPU。对于相同的任务，CPU需要n个单位时间的冷却时间，期间可以执行其他不相同的任务。问最少多少时间可以完成所有任务。

Given a char array representing tasks CPU need to do. It contains capital letters A to Z where different letters represent different tasks.Tasks could be done without original order. Each task could be done in one interval. For each interval, CPU could finish one task or just be idle.

However, there is a non-negative cooling interval n that means between two same tasks, there must be at least n intervals that CPU are doing different tasks or just be idle.

You need to return the least number of intervals the CPU will take to finish all the given tasks.

Example 1:

Input: tasks = ["A","A","A","B","B","B"], n = 2

Output: 8

Explanation: A -> B -> idle -> A -> B -> idle -> A -> B.

Note:

The number of tasks is in the range [1, 10000].
The integer n is in the range [0, 100].

Idea:

Counting

Time complexity: O(n)

Space complexity: O(1)

// Author: Huahua

// Runtime: 56 ms

class Solution {

public:

int leastInterval(vector<char>& tasks, int n) {

vector<int> count(26, 0);

for (const char task : tasks)

++count[task - 'A'];

const int max_count = *max_element(count.begin(), count.end());

size_t ans = (max_count - 1) * (n + 1);

ans += count_if(count.begin(), count.end(),

[max_count](int c){ return c == max_count; });

return max(tasks.size(), ans);

}

};

花花酱 LeetCode 409. Longest Palindrome

By zxi on September 19, 2017

https://leetcode.com/problems/longest-palindrome/description/

Problem:

Given a string which consists of lowercase or uppercase letters, find the length of the longest palindromes that can be built with those letters.

This is case sensitive, for example "Aa" is not considered a palindrome here.

Note:
Assume the length of given string will not exceed 1,010.

Example:

Input:

"abccccdd"

Output:

Explanation:

One longest palindrome that can be built is "dccaccd", whose length is 7.

Idea:

Greedy + Counting

Solution:

C++

// Author: Huahua

// Time complexity: O(n)

// Space complexity: O(128) = O(1)

// Running time: 3 ms 9/2017

class Solution {

public:

int longestPalindrome(const string& s) {

vector<int> freqs(128, 0);

for (const char c : s)

++freqs[c];

int ans = 0;

int odd = 0;

for (const int freq : freqs) {

// same as: ans += freq % 2 == 0 ? freq : freq - 1;

// same as: ans += freq / 2 * 2;

// same as: ans += ((freq >> 1) << 1);

// same as: ans += freq & (INT_MAX - 1);

ans += freq & (~1); // clear the last bit

odd |= freq & 1;

}

ans += odd;

return ans;

}

};

Java

// Author: Huahua

// Running time: 11 ms

class Solution {

public int longestPalindrome(String s) {

int[] freqs = new int[128];

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

++freqs[s.charAt(i)];

int ans = 0;

int odd = 0;

for (int freq: freqs) {

ans += freq & (~1);

odd |= freq & 1;

}

return ans + odd;

}

Python

"""

Author: Huahua

Running time: 39 ms

"""

class Solution(object):

def longestPalindrome(self, s):

"""

:type s: str

:rtype: int

"""

freqs = [0] * 128

for c in s:

freqs[ord(c)] += 1

ans, odd = 0, 0

for freq in freqs:

ans += freq & (~1)

odd |= freq & 1

return ans + odd

花花酱 LeetCode 611. Valid Triangle Number

By zxi on September 9, 2017

Problem:

Given an array consists of non-negative integers, your task is to count the number of triplets chosen from the array that can make triangles if we take them as side lengths of a triangle.

Example 1:

Input: [2,2,3,4]
Output: 3
Explanation:
Valid combinations are: 
2,3,4 (using the first 2)
2,3,4 (using the second 2)
2,2,3

Note:

The length of the given array won’t exceed 1000.
The integers in the given array are in the range of [0, 1000].

Idea:

Greedy

Time Complexity:

O(n^2)

Solution:

// Author: Huahua

class Solution {

public:

int triangleNumber(vector<int>& nums) {

if (nums.size() < 3) return 0;

std::sort(nums.rbegin(), nums.rend());

int n = nums.size();

int ans = 0;

for (int c = 0; c < n-2; ++c) {

int b = c + 1;

int a = n - 1;

while (b < a) {

if (nums[a] + nums[b] > nums[c]) {

ans += (a - b);

++b;

} else {

--a;

}

return ans;

}

};

Posts published in “Greedy”

花花酱 LeetCode 321. Create Maximum Number

Idea: Greedy + DP

Solution:

C++

Java

花花酱 LeetCode 621. Task Scheduler

花花酱 LeetCode 409. Longest Palindrome

花花酱 LeetCode 611. Valid Triangle Number

Problem:

Idea:

Solution: