Golang每日一练(leetDay0101) 最长递增子序列I\II\个数
目录
300. 最长递增子序列 Longest Increasing Subsequence 🌟🌟
2407. 最长递增子序列 II Longest Increasing Subsequence ii 🌟🌟🌟
673. 最长递增子序列的个数 Number of Longest Increasing Subsequence 🌟🌟
300. 最长递增子序列 Longest Increasing Subsequence
给你一个整数数组 nums
,找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7]
是数组 [0,3,1,6,2,2,7]
的子序列。
示例 1:
输入:nums = [10,9,2,5,3,7,101,18]
输出:4
解释:最长递增子序列是 [2,3,7,101],因此长度为 4 。
示例 2:
输入:nums = [0,1,0,3,2,3]
输出:4
示例 3:
输入:nums = [7,7,7,7,7,7,7]
输出:1
提示:
1 <= nums.length <= 2500
-10^4 <= nums[i] <= 10^4
进阶:
- 你能将算法的时间复杂度降低到
O(n log(n))
吗?
代码1:二分查找,时间复杂度 O(n log n)
-
package main
-
-
import "fmt"
-
-
func lengthOfLIS(nums []int) int {
-
n := len(nums)
-
if n == 0 {
-
return 0
-
}
-
d := make([]int, n 1)
-
d[1] = nums[0]
-
len := 1
-
for i := 1; i < n; i {
-
if nums[i] > d[len] {
-
len
-
d[len] = nums[i]
-
} else {
-
l, r := 1, len
-
pos := 0
-
for l <= r {
-
mid := l (r-l)/2
-
if d[mid] < nums[i] {
-
pos = mid
-
l = mid 1
-
} else {
-
r = mid - 1
-
}
-
}
-
d[pos 1] = nums[i]
-
}
-
}
-
return len
-
}
-
-
func main() {
-
nums := []int{10, 9, 2, 5, 3, 7, 101, 18}
-
fmt.Println(lengthOfLIS(nums))
-
-
nums = []int{0, 1, 0, 3, 2, 3}
-
fmt.Println(lengthOfLIS(nums))
-
-
nums = []int{7, 7, 7, 7, 7, 7, 7}
-
fmt.Println(lengthOfLIS(nums))
-
}
输出:
4
4
1
代码2:动态规划,时间复杂度:O(n^2)
-
package main
-
-
import "fmt"
-
-
func lengthOfLIS(nums []int) int {
-
n := len(nums)
-
dp := make([]int, n)
-
// 初始化 dp 数组
-
for i := 0; i < n; i {
-
dp[i] = 1
-
}
-
ans := 1
-
// 开始 dp
-
for i := 1; i < n; i {
-
for j := 0; j < i; j {
-
if nums[j] < nums[i] {
-
dp[i] = max(dp[i], dp[j] 1)
-
}
-
}
-
ans = max(ans, dp[i])
-
}
-
return ans
-
}
-
-
func max(x, y int) int {
-
if x > y {
-
return x
-
}
-
return y
-
}
-
-
func main() {
-
nums := []int{10, 9, 2, 5, 3, 7, 101, 18}
-
fmt.Println(lengthOfLIS(nums))
-
-
nums = []int{0, 1, 0, 3, 2, 3}
-
fmt.Println(lengthOfLIS(nums))
-
-
nums = []int{7, 7, 7, 7, 7, 7, 7}
-
fmt.Println(lengthOfLIS(nums))
-
}
2407. 最长递增子序列 II Longest Increasing Subsequence ii
给你一个整数数组 nums
和一个整数 k
。
找到 nums
中满足以下要求的最长子序列:
- 子序列 严格递增
- 子序列中相邻元素的差值 不超过
k
。
请你返回满足上述要求的 最长子序列 的长度。
子序列 是从一个数组中删除部分元素后,剩余元素不改变顺序得到的数组。
示例 1:
输入:nums = [4,2,1,4,3,4,5,8,15], k = 3
输出:5
解释:
满足要求的最长子序列是 [1,3,4,5,8] 。
子序列长度为 5 ,所以我们返回 5 。
注意子序列 [1,3,4,5,8,15] 不满足要求,因为 15 - 8 = 7 大于 3 。
示例 2:
输入:nums = [7,4,5,1,8,12,4,7], k = 5
输出:4
解释:
满足要求的最长子序列是 [4,5,8,12] 。
子序列长度为 4 ,所以我们返回 4 。
示例 3:
输入:nums = [1,5], k = 1
输出:1
解释:
满足要求的最长子序列是 [1] 。
子序列长度为 1 ,所以我们返回 1 。
提示:
1 <= nums.length <= 10^5
1 <= nums[i], k <= 10^5
代码:二分查找
-
package main
-
-
import "fmt"
-
-
var mx []int // 全局变量
-
-
func updateTree(root, l, r, i, val int) {
-
if l == r {
-
mx[root] = val
-
return
-
}
-
mid := (l r) / 2
-
if i <= mid {
-
updateTree(root*2, l, mid, i, val)
-
} else {
-
updateTree(root*2 1, mid 1, r, i, val)
-
}
-
mx[root] = max(mx[root*2], mx[root*2 1])
-
}
-
-
func query(root, l, r, L, R int) int {
-
if L <= l && r <= R {
-
return mx[root]
-
}
-
ret := 0
-
mid := (l r) / 2
-
if L <= mid {
-
ret = query(root*2, l, mid, L, R)
-
}
-
if R > mid {
-
ret = max(query(root*2 1, mid 1, r, L, R), ret)
-
}
-
return ret
-
}
-
-
func lengthOfLIS(nums []int, k int) int {
-
up := 0
-
for _, x := range nums {
-
if x > up {
-
up = x
-
}
-
}
-
mx = make([]int, 4*up)
-
for _, x := range nums {
-
if x == 1 {
-
updateTree(1, 1, up, 1, 1)
-
} else {
-
L := x - k
-
if L < 1 {
-
L = 1
-
}
-
ret := 1 query(1, 1, up, L, x-1)
-
updateTree(1, 1, up, x, ret)
-
}
-
}
-
return mx[1]
-
}
-
-
func max(a, b int) int {
-
if a > b {
-
return a
-
}
-
return b
-
}
-
-
func main() {
-
nums1 := []int{4, 2, 1, 4, 3, 4, 5, 8, 15}
-
k1 := 3
-
fmt.Println(lengthOfLIS(nums1, k1))
-
nums2 := []int{7, 4, 5, 1, 8, 12, 4, 7}
-
k2 := 5
-
fmt.Println(lengthOfLIS(nums2, k2))
-
nums3 := []int{1, 5}
-
k3 := 1
-
fmt.Println(lengthOfLIS(nums3, k3))
-
}
输出:
5
4
1
673. 最长递增子序列的个数 Number of Longest Increasing Subsequence
给定一个未排序的整数数组 nums
, 返回最长递增子序列的个数 。
注意 这个数列必须是 严格 递增的。
示例 1:
输入: [1,3,5,4,7]
输出: 2
解释: 有两个最长递增子序列,分别是 [1, 3, 4, 7] 和[1, 3, 5, 7]。
示例 2:
输入: [2,2,2,2,2]
输出: 5
解释: 最长递增子序列的长度是1,并且存在5个子序列的长度为1,因此输出5。
提示:
1 <= nums.length <= 2000
-10^6 <= nums[i] <= 10^6
代码:
-
package main
-
-
import "fmt"
-
-
func findNumberOfLIS(nums []int) int {
-
n := len(nums)
-
if n <= 1 {
-
return n
-
}
-
dp := make([]int, n)
-
cnt := make([]int, n)
-
for i := range dp {
-
dp[i], cnt[i] = 1, 1
-
}
-
maxLen, ans := 1, 0
-
for i := 1; i < n; i {
-
for j := 0; j < i; j {
-
if nums[j] < nums[i] {
-
if dp[j] 1 > dp[i] {
-
dp[i], cnt[i] = dp[j] 1, cnt[j]
-
} else if dp[j] 1 == dp[i] {
-
cnt[i] = cnt[j]
-
}
-
}
-
}
-
maxLen = max(maxLen, dp[i])
-
}
-
for i := range cnt {
-
if dp[i] == maxLen {
-
ans = cnt[i]
-
}
-
}
-
return ans
-
}
-
-
func max(x, y int) int {
-
if x > y {
-
return x
-
}
-
return y
-
}
-
-
func main() {
-
fmt.Println(findNumberOfLIS([]int{1, 3, 5, 4, 7}))
-
fmt.Println(findNumberOfLIS([]int{2, 2, 2, 2, 2}))
-
}
输出:
2
5
🌟 每日一练刷题专栏 🌟
✨ 持续,努力奋斗做强刷题搬运工!
👍 点赞,你的认可是我坚持的动力!
🌟 收藏,你的青睐是我努力的方向!
✎ 评论,你的意见是我进步的财富!
☸ 主页:https://hannyang.blog.csdn.net/
Rust每日一练 专栏(2023.5.16~)更新中... |
|
Golang每日一练 专栏(2023.3.11~)更新中... |
|
Python每日一练 专栏(2023.2.18~2023.5.18)暂停更 |
|
C/C 每日一练 专栏(2023.2.18~2023.5.18)暂停更 |
|
Java每日一练 专栏(2023.3.11~2023.5.18)暂停更 |
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhfiaagf
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
excel下划线不显示怎么办
PHP中文网 06-23 -
怎样阻止微信小程序自动打开
PHP中文网 06-13 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
photoshop蒙版画笔没反应怎么办
PHP中文网 06-24