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
}