Press "Enter" to skip to content

Posts tagged as “sequence”

花花酱 LeetCode 128. Longest Consecutive Sequence

 

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

 

Solution 2: C++ / offline

 

花花酱 LeetCode 664. Strange Printer

Problem:

There is a strange printer with the following two special requirements:

  1. The printer can only print a sequence of the same character each time.
  2. At each turn, the printer can print new characters starting from and ending at any places, and will cover the original existing characters.

Given a string consists of lower English letters only, your job is to count the minimum number of turns the printer needed in order to print it.

Example 1:

Example 2:

Hint: Length of the given string will not exceed 100.

Idea:

Dynamic programming



Time Complexity: 

O(n^3)

Space Complexity:

O(n^2)

Solution:

C++

Java

Python3