Press "Enter" to skip to content

Posts tagged as “increasing”

花花酱 LeetCode 960. Delete Columns to Make Sorted III

We are given an array A of N lowercase letter strings, all of the same length.

Now, we may choose any set of deletion indices, and for each string, we delete all the characters in those indices.

For example, if we have an array A = ["babca","bbazb"] and deletion indices {0, 1, 4}, then the final array after deletions is ["bc","az"].

Suppose we chose a set of deletion indices D such that after deletions, the final array has every element (row) in lexicographic order.

For clarity, A[0] is in lexicographic order (ie. A[0][0] <= A[0][1] <= ... <= A[0][A[0].length - 1]), A[1] is in lexicographic order (ie. A[1][0] <= A[1][1] <= ... <= A[1][A[1].length - 1]), and so on.

Return the minimum possible value of D.length.

Example 1:

Input: ["babca","bbazb"]
Output: 3
Explanation: After deleting columns 0, 1, and 4, the final array is A = ["bc", "az"].
Both these rows are individually in lexicographic order (ie. A[0][0] <= A[0][1] and A[1][0] <= A[1][1]).
Note that A[0] > A[1] - the array A isn't necessarily in lexicographic order.

Example 2:

Input: ["edcba"]
Output: 4
Explanation: If we delete less than 4 columns, the only row won't be lexicographically sorted.

Example 3:

Input: ["ghi","def","abc"]
Output: 0
Explanation: All rows are already lexicographically sorted.

Note:

  1. 1 <= A.length <= 100
  2. 1 <= A[i].length <= 100

Solution: DP

dp[i] := max length of increasing sub-sequence (of all strings) ends with i-th letter.
dp[i] = max(dp[j] + 1) if all A[*][j] <= A[*][i], j < i
Time complexity: (n*L^2)
Space complexity: O(L)

C++

Python3

花花酱 LeetCode 491. Increasing Subsequences

Problem

Given an integer array, your task is to find all the different possible increasing subsequences of the given array, and the length of an increasing subsequence should be at least 2 .

Example:

Input: [4, 6, 7, 7]
Output: [[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7,7], [4,7,7]]

Note:

  1. The length of the given array will not exceed 15.
  2. The range of integer in the given array is [-100,100].
  3. The given array may contain duplicates, and two equal integers should also be considered as a special case of increasing sequence.

Solution: DFS

Time complexity: O(2^n)

Space complexity: O(n)

C++

 

花花酱 LeetCode 334. Increasing Triplet Subsequence

Problem

题目大意:判断一个数组中是否存在长度为3的单调递增子序列。

Formally the function should:

Return true if there exists i, j, k 
such that arr[i] < arr[j] < arr[k] given 0 ≤ i < j < k ≤ n-1 else return false.

Your algorithm should run in O(n) time complexity and O(1) space complexity.

Examples:
Given [1, 2, 3, 4, 5],
return true.

Given [5, 4, 3, 2, 1],
return false.

Credits:
Special thanks to @DjangoUnchained for adding this problem and creating all test cases.

Solution: Greedy

Time complexity: O(n)

Space complexity: O(1)

C++