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
}
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
}
Description
Given a list of strings words and a string pattern, return a list ofwords[i]that matchpattern. 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
}
