sequence Archives - Huahua's Tech Road

花花酱 LeetCode 2145. Count the Hidden Sequences

By zxi on January 31, 2022

You are given a 0-indexed array of n integers differences, which describes the differences between each pair of consecutive integers of a hidden sequence of length (n + 1). More formally, call the hidden sequence hidden, then we have that differences[i] = hidden[i + 1] - hidden[i].

You are further given two integers lower and upper that describe the inclusive range of values [lower, upper] that the hidden sequence can contain.

For example, given differences = [1, -3, 4], lower = 1, upper = 6, the hidden sequence is a sequence of length 4 whose elements are in between 1 and 6 (inclusive).
- [3, 4, 1, 5] and [4, 5, 2, 6] are possible hidden sequences.
- [5, 6, 3, 7] is not possible since it contains an element greater than 6.
- [1, 2, 3, 4] is not possible since the differences are not correct.

Return the number of possible hidden sequences there are. If there are no possible sequences, return 0.

Example 1:

Input: differences = [1,-3,4], lower = 1, upper = 6
Output: 2
Explanation: The possible hidden sequences are:
- [3, 4, 1, 5]
- [4, 5, 2, 6]
Thus, we return 2.

Example 2:

Input: differences = [3,-4,5,1,-2], lower = -4, upper = 5
Output: 4
Explanation: The possible hidden sequences are:
- [-3, 0, -4, 1, 2, 0]
- [-2, 1, -3, 2, 3, 1]
- [-1, 2, -2, 3, 4, 2]
- [0, 3, -1, 4, 5, 3]
Thus, we return 4.

Example 3:

Input: differences = [4,-7,2], lower = 3, upper = 6
Output: 0
Explanation: There are no possible hidden sequences. Thus, we return 0.

Constraints:

n == differences.length
1 <= n <= 10⁵
-10⁵ <= differences[i] <= 10⁵
-10⁵ <= lower <= upper <= 10⁵

Solution: Math

Find the min and max of the cumulative sum of the differences.

Ans = max(0, upper – lower – (hi – lo) + 1)

Time complexity: O(n)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int numberOfArrays(vector<int>& differences, int lower, int upper) {

long long s = 0;

long long hi = 0;

long long lo = 0;

for (int d : differences) {

s += d;

hi = max(hi, s);

lo = min(lo, s);

}

return max(0LL, upper - lower - (hi - lo) + 1);

}

};

花花酱 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;

}

};

花花酱 LeetCode 664. Strange Printer

By zxi on September 20, 2017

Problem:

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

The printer can only print a sequence of the same character each time.
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:

Input: "aaabbb"

Output: 2

Explanation: Print "aaa" first and then print "bbb".

Example 2:

Input: "aba"

Output: 2

Explanation: Print "aaa" first and then print "b" from the second place of the string, which will cover the existing character 'a'.

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

// Author: Huahua

// Time Complexity: O(n^3)

// Space Complexity: O(n^2)

// Running Time: 22 ms

class Solution {

public:

int strangePrinter(const string& s) {

int l = s.length();

t_ = vector<vector<int>>(l, vector<int>(l, 0));

return turn(s, 0, s.length() - 1);

}

private:

// Minimal turns to print s[i] to s[j]

int turn(const string& s, int i, int j) {

// Empty string

if (i > j) return 0;

// Solved

if (t_[i][j] > 0) return t_[i][j];

// Default behavior, print s[i] to s[j-1] and print s[j]

int ans = turn(s, i, j-1) + 1;

for (int k = i; k < j; ++k)

if (s[k] == s[j])

ans = min(ans, turn(s, i, k) + turn(s, k + 1, j - 1));

return t_[i][j] = ans;

}

vector<vector<int>> t_;

};

Java

// Author: Huahua

// Time Complexity: O(n^3)

// Space Complexity: O(n^2)

// Running Time: 31 ms (beat 99.25%) 9/2017

class Solution {

public int strangePrinter(String s) {

int l = s.length();

t_ = new int[l][l];

return turn(s.toCharArray(), 0, l - 1);

}

// Minimal turns to print s[i] to s[j]

private int turn(char[] s, int i, int j) {

// Empty string

if (i > j) return 0;

// Solved

if (t_[i][j] > 0) return t_[i][j];

// Default behavior, print s[i] to s[j-1] and print s[j]

int ans = turn(s, i, j-1) + 1;

for (int k = i; k < j; ++k)

if (s[k] == s[j])

ans = Math.min(ans, turn(s, i, k) + turn(s, k + 1, j - 1));

return t_[i][j] = ans;

}

private int[][] t_;

}

Python3

"""

Author: Huahua

Time Complexity: O(n^3)

Space Complexity: O(n^2)

Running Time: 895 ms (beat 66%) 9/2017

"""

class Solution(object):

def strangePrinter(self, s):

"""

:type s: str

:rtype: int

"""

l = len(s)

self._t = [[0 for _ in xrange(l)] for _ in xrange(l)]

return self._turns(s, 0, l - 1)

def _turns(self, s, i, j):

if i > j: return 0

if self._t[i][j] > 0: return self._t[i][j]

ans = self._turns(s, i, j - 1) + 1

for k in xrange(i, j):

if s[k] == s[j]:

ans = min(ans, self._turns(s, i, k)

+ self._turns(s, k + 1, j-1))

self._t[i][j] = ans

return self._t[i][j]

Posts tagged as “sequence”

花花酱 LeetCode 2145. Count the Hidden Sequences

Solution: Math

C++

花花酱 LeetCode 128. Longest Consecutive Sequence

花花酱 LeetCode 664. Strange Printer

C++

Java

Python3