Press "Enter" to skip to content

Posts tagged as “frequency”

花花酱 LeetCode 748. Shortest Completing Word

题目大意: 给你一个由字母和数字组成车牌。另外给你一些单词,让你找一个最短的单词能够覆盖住车牌中的字母(不考虑大小写)。如果有多个解,输出第一个解。

Problem:

Find the minimum length word from a given dictionary words, which has all the letters from the string licensePlate. Such a word is said to complete the given string licensePlate

Here, for letters we ignore case. For example, "P" on the licensePlate still matches "p" on the word.

It is guaranteed an answer exists. If there are multiple answers, return the one that occurs first in the array.

The license plate might have the same letter occurring multiple times. For example, given a licensePlate of "PP", the word "pair" does not complete the licensePlate, but the word "supper" does.

Example 1:

Example 2:

Note:

  1. licensePlate will be a string with length in range [1, 7].
  2. licensePlate will contain digits, spaces, or letters (uppercase or lowercase).
  3. words will have a length in the range [10, 1000].
  4. Every words[i] will consist of lowercase letters, and have length in range [1, 15].

Idea:

Hashtable

Solution:

C++

Time complexity: 时间复杂度 O(N*26), N is number of words.

Space complexity: 空间复杂度 O(26) = O(1)

 

花花酱 LeetCode 347. Top K Frequent Elements

Problem:

Given a non-empty array of integers, return the k most frequent elements.

For example,
Given [1,1,1,2,2,3] and k = 2, return [1,2].

Note:
You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
Your algorithm’s time complexity must be better than O(n log n), where n is the array’s size.



Idea:

 

Solution 2: Priority queue / max heap

Time complexity: O(n) + O(nlogk)

Space complexity: O(n)

C++

Java

Python

Solution 3: Bucket Sort

Time complexity: O(n)

Space complexity: O(n)

C++/hashmap

C++/array

Java

Python

Related Problems

花花酱 LeetCode 692. Top K Frequent Words

Problem:

Given a non-empty list of words, return the k most frequent elements.

Your answer should be sorted by frequency from highest to lowest. If two words have the same frequency, then the word with the lower alphabetical order comes first.

Example 1:

Example 2:

Note:

  1. You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
  2. Input words contain only lowercase letters.

Follow up:

  1. Try to solve it in O(n log k) time and O(n) extra space.



Idea:

Priority queue / min heap

Solution

C++ / priority_queue O(n log k) / O(n)

Related Problems

花花酱 LeetCode 409. Longest Palindrome

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:

Idea:

Greedy + Counting



Solution:

C++

 

Java

 

 

Python

 

花花酱 LeetCode 451. Sort Characters By Frequency

Given a string, sort it in decreasing order based on the frequency of characters.

Example 1:

Example 2:

Example 3:

Solution: