2022-06-12

300. Longest Increasing Subsequence

Description

Given an integer array `nums`, return the length of the longest strictly increasing subsequence.

A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements. For example, `[3,6,2,7]` is a subsequence of the array `[0,3,1,6,2,2,7]`.

Example 1:

``````Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.``````

Example 2:

``````Input: nums = [0,1,0,3,2,3]
Output: 4``````

Example 3:

``````Input: nums = [7,7,7,7,7,7,7]
Output: 1``````

Constraints:

• `1 <= nums.length <= 2500`

• `-10^4 <= nums[i] <= 10^4`

Follow up: Can you come up with an algorithm that runs in `O(n log(n))` time complexity?

Solution

Approach #0

``````func lengthOfLIS(nums []int) (ans int) {
n := len(nums)
dp := make([]int, n)
dp[0] = 1
ans = 1
for i := 1; i < n; i++ {
dp[i] = 1
for j := 0; j < i; j++ {
if nums[i] > nums[j] {
dp[i] = max(dp[i], dp[j]+1)
}
}
ans = max(ans, dp[i])
}
return
}

func max(a, b int) int {
if a > b {
return a
}
return b
}``````

673. Number of Longest Increasing Subsequence

Description

Given an integer array `nums`, return the number of longest increasing subsequences.

Notice that the sequence has to be strictly increasing.

Example 1:

``````Input: nums = [1,3,5,4,7]
Output: 2
Explanation: The two longest increasing subsequences are [1, 3, 4, 7] and [1, 3, 5, 7].``````

Example 2:

``````Input: nums = [2,2,2,2,2]
Output: 5
Explanation: The length of longest continuous increasing subsequence is 1, and there are 5 subsequences' length is 1, so output 5.``````

Constraints:

• `1 <= nums.length <= 2000`

• `-10^6 <= nums[i] <= 10^6`

Solution

Approach #0

``````func findNumberOfLIS(nums []int) (ans int) {
n := len(nums)
dp := make([]int, n)
cnt := make([]int, n)
maxLen := 0
for i := 0; i < n; i++ {
dp[i] = 1
cnt[i] = 1
for j := 0; j < i; j++ {
if nums[i] > nums[j] {
if dp[j]+1 == dp[i] {
cnt[i] += cnt[j]
}
if dp[j]+1 > dp[i] {
dp[i] = dp[j] + 1
cnt[i] = cnt[j]
}
}
}
if dp[i] > maxLen {
maxLen = dp[i]
ans = cnt[i]
} else if dp[i] == maxLen {
ans += cnt[i]
}
}
return
}``````

890. Find and Replace Pattern

Description

Given a list of strings `words` and a string `pattern`, return a list of `words[i]` that match `pattern`. You may return the answer in any order.

A word matches the pattern if there exists a permutation of letters `p` so that after replacing every letter `x` in the pattern with `p(x)`, we get the desired word.

Recall that a permutation of letters is a bijection from letters to letters: every letter maps to another letter, and no two letters map to the same letter.

Example 1:

``````Input: words = ["abc","deq","mee","aqq","dkd","ccc"], pattern = "abb"
Output: ["mee","aqq"]
Explanation: "mee" matches the pattern because there is a permutation {a -> m, b -> e, ...}.
"ccc" does not match the pattern because {a -> c, b -> c, ...} is not a permutation, since a and b map to the same letter.``````

Example 2:

``````Input: words = ["a","b","c"], pattern = "a"
Output: ["a","b","c"] ``````

Constraints:

• `1 <= pattern.length <= 20`

• `1 <= words.length <= 50`

• `words[i].length == pattern.length`

• `pattern` and `words[i]` are lowercase English letters.

Solution

Approach #0

``````func findAndReplacePattern(words []string, pattern string) (ans []string) {
if len(pattern) == 1 {
return words
}
for _, word := range words {
if match(word, pattern) && match(pattern, word) {
ans = append(ans, word)
}
}
return
}

func match(word, pattern string) bool {
m := make(map[rune]byte)
for i, a := range word {
b := pattern[i]
if m[a] == 0 {
m[a] = b
} else {
if m[a] != b {
return false
}
}
}
return true
}``````

Last updated