Press "Enter" to skip to content

Posts published in November 2018

花花酱 LeetCode 944. Delete Columns to Make Sorted

By zxi on November 18, 2018

Problem

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 a stringĀ "abcdef"Ā and deletion indicesĀ {0, 2, 3}, then the final string after deletionĀ isĀ "bef".

Suppose we chose a set of deletion indicesĀ DĀ such that after deletions, each remaining column in A is inĀ non-decreasingĀ sorted order.

Formally, theĀ c-th column isĀ [A[0][c], A[1][c], ..., A[A.length-1][c]]

Return the minimum possible value ofĀ D.length.

Example 1:

Input: ["cba","daf","ghi"]
Output: 1

Example 2:

Input: ["a","b"]
Output: 0

Example 3:

Input: ["zyx","wvu","tsr"]
Output: 3

Note:

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

Solution: Simulation

Check descending case column by column.

Time complexity: O(NL)

Space complexity: O(1)

C++

花花酱 LeetCode 942. DI String Match

By zxi on November 18, 2018

Problem

Given a stringĀ SĀ thatĀ onlyĀ contains “I” (increase) or “D” (decrease), letĀ N = S.length.

ReturnĀ anyĀ permutationĀ AĀ ofĀ [0, 1, ..., N]Ā such that for allĀ i = 0,Ā ..., N-1:

  • IfĀ S[i] == "I", thenĀ A[i] < A[i+1]
  • IfĀ S[i] == "D", thenĀ A[i] > A[i+1]

Example 1:

Input: "IDID"
Output: [0,4,1,3,2]

Example 2:

Input: "III"
Output: [0,1,2,3]

Example 3:

Input: "DDI"
Output: [3,2,0,1]

Note:

  1. 1 <= S.length <= 10000
  2. SĀ only contains charactersĀ "I"Ā orĀ "D".

Solution: Greedy

“I” -> use the smallest possible number

“D” -> use the largest possible number

Time complexity: O(n)

Space complexity: O(n)

C++

花花酱 LeetCode 941. Valid Mountain Array

By zxi on November 18, 2018

Problem

Given an arrayĀ AĀ of integers, returnĀ trueĀ if and only if it is aĀ valid mountain array.

Recall that A is a mountain array if and only if:

  • A.length >= 3
  • There exists someĀ iĀ withĀ 0 < iĀ < A.length - 1Ā such that:
    • A[0] < A[1] < ... A[i-1] < A[i]
    • A[i] > A[i+1] > ... > A[B.length - 1]

Example 1:

Input: [2,1]
Output: false

Example 2:

Input: [3,5,5]
Output: false

Example 3:

Input: [0,3,2,1]
Output: true

Note:

  1. 0 <= A.length <= 10000
  2. 0 <= A[i] <= 10000Ā 

Solution

Use has_up and has_down to track whether we have A[i] > A[i – 1] and A[i] < A[i – 1] receptively.

return false if any of the following happened:

  1. size(A) < 3
  2. has_down happened before has_up
  3. not has_down or not has_up
  4. A[i – 1] < A[i] after has_down
  5. A[i – 1] > A[i] before has_up

Time complexity: O(n)

Space complexity: O(n)

C++

花花酱 LeetCode 55. Jump Game

By zxi on November 15, 2018

Problem

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

Example 1:

Input: [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum
Ā             jump length is 0, which makes it impossible to reach the last index.

Solution: Greedy

If you can jump to i, then you can jump to at least i + nums[i].

Always jump as far as you can.

Keep tracking the farthest index you can jump to.

Init far = nums[0].

far = max(far, i + nums[i])

check far >= n – 1

ex 1 [2,3,1,1,4]

ex 2Ā [3,2,1,0,4]

C++

花花酱 LeetCode 940. Distinct Subsequences II

By zxi on November 14, 2018

Problem

Given a stringĀ S, count the number of distinct, non-empty subsequences ofĀ SĀ .

Since the result may be large,Ā return the answer moduloĀ 10^9 + 7.

Example 1:

Input: "abc"
Output: 7
Explanation: The 7 distinct subsequences are "a", "b", "c", "ab", "ac", "bc", and "abc".

Example 2:

Input: "aba"
Output: 6
Explanation: The 6 distinct subsequences are "a", "b", "ab", "ba", "aa" and "aba".

Example 3:

Input: "aaa"
Output: 3
Explanation: The 3 distinct subsequences are "a", "aa" and "aaa".

Note:

  1. SĀ contains only lowercase letters.
  2. 1 <= S.length <= 2000

Solution: DP

counts[i][j] := # of distinct sub sequences of s[1->i] and ends with letter j. (‘a'<= j <= ‘z’)

Initialization:

counts[*][*] = 0

Transition:

counts[i][j] = sum(counts[i-1]) + 1 if s[i] == jĀ  else counts[i-1][j]

ans = sum(counts[n])

e.g. S = “abc”

counts[1] = {‘a’ : 1}
counts[2] = {‘a’ : 1, ‘b’ : 1 + 1 = 2}
counts[3] = {‘a’ : 1, ‘b’ : 2, ‘c’: 1 + 2 + 1 = 4}
ans = sum(counts[3]) = 1 + 2 + 4 = 7

Time complexity: O(N*26)

Space complexity: O(N*26) -> O(26)

C++

Python3