Press "Enter" to skip to content

Posts published in “Greedy”

花花酱 LeetCode 575. Distribute Candies

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

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:

Example 2:

Note:

  1. The length of the given array is in range [2, 10,000], and will be even.
  2. 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

C++ Bitset

 

 

花花酱 LeetCode 214. Shortest Palindrome

题目大意:给你一个字符串你可以在它的前面添加一些字符,返回最短的回文字符串。

Given a string S, you are allowed to convert it to a palindrome by adding characters in front of it. Find and return the shortest palindrome you can find by performing this transformation.

For example:

Given "aacecaaa", return "aaacecaaa".

Given "abcd", return "dcbabcd".

 

Solution 1: Brute Force

Time complexity: O(n^2)

Space complexity: O(n)

C++ w/ copy

 

C++ w/o copy

 

 

花花酱 LeetCode 763. Partition Labels

题目大意:把字符串分割成尽量多的不重叠子串,输出子串的长度数组。要求相同字符只能出现在一个子串中。

Problem:

A string S of lowercase letters is given. We want to partition this string into as many parts as possible so that each letter appears in at most one part, and return a list of integers representing the size of these parts.

Example 1:

Solution 0: Brute Force

Time complexity: O(n^2)

Space complexity: O(1)

C++

Python

 

Solution 1: Greedy

Time complexity: O(n)

Space complexity: O(26/128)

C++

Java

Python3

 

花花酱 LeetCode 321. Create Maximum Number

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++

Java

花花酱 LeetCode 621. Task Scheduler

题目大意:给你一些用字母表示的任务,执行每个任务需要单位时间的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:

Note:

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

Idea:

Counting

Time complexity: O(n)

Space complexity: O(1)