Golang每日一练(leetDay0101) 最长递增子序列I\II\个数

目录

300. 最长递增子序列 Longest Increasing Subsequence  🌟🌟

2407. 最长递增子序列 II Longest Increasing Subsequence ii  🌟🌟🌟

673. 最长递增子序列的个数 Number of Longest Increasing Subsequence  🌟🌟

🌟 每日一练刷题专栏 🌟

Rust每日一练 专栏

Golang每日一练 专栏

Python每日一练 专栏

C/C 每日一练 专栏

Java每日一练 专栏

---

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)

1.  
   package main
2.  
    
3.  
   import "fmt"
4.  
    
5.  
   func lengthOfLIS(nums []int) int {
6.  
   n := len(nums)
7.  
   if n == 0 {
8.  
   return 0
9.  
   }
10.  
    d := make([]int, n 1)
11.  
    d[1] = nums[0]
12.  
    len := 1
13.  
    for i := 1; i < n; i {
14.  
    if nums[i] > d[len] {
15.  
    len
16.  
    d[len] = nums[i]
17.  
    } else {
18.  
    l, r := 1, len
19.  
    pos := 0
20.  
    for l <= r {
21.  
    mid := l (r-l)/2
22.  
    if d[mid] < nums[i] {
23.  
    pos = mid
24.  
    l = mid 1
25.  
    } else {
26.  
    r = mid - 1
27.  
    }
28.  
    }
29.  
    d[pos 1] = nums[i]
30.  
    }
31.  
    }
32.  
    return len
33.  
    }
34.  
     
35.  
    func main() {
36.  
    nums := []int{10, 9, 2, 5, 3, 7, 101, 18}
37.  
    fmt.Println(lengthOfLIS(nums))
38.  
     
39.  
    nums = []int{0, 1, 0, 3, 2, 3}
40.  
    fmt.Println(lengthOfLIS(nums))
41.  
     
42.  
    nums = []int{7, 7, 7, 7, 7, 7, 7}
43.  
    fmt.Println(lengthOfLIS(nums))
44.  
    }

输出：

4
4
1

代码2：动态规划，时间复杂度：O(n^2)

1.  
   package main
2.  
    
3.  
   import "fmt"
4.  
    
5.  
   func lengthOfLIS(nums []int) int {
6.  
   n := len(nums)
7.  
   dp := make([]int, n)
8.  
   // 初始化 dp 数组
9.  
   for i := 0; i < n; i {
10.  
    dp[i] = 1
11.  
    }
12.  
    ans := 1
13.  
    // 开始 dp
14.  
    for i := 1; i < n; i {
15.  
    for j := 0; j < i; j {
16.  
    if nums[j] < nums[i] {
17.  
    dp[i] = max(dp[i], dp[j] 1)
18.  
    }
19.  
    }
20.  
    ans = max(ans, dp[i])
21.  
    }
22.  
    return ans
23.  
    }
24.  
     
25.  
    func max(x, y int) int {
26.  
    if x > y {
27.  
    return x
28.  
    }
29.  
    return y
30.  
    }
31.  
     
32.  
    func main() {
33.  
    nums := []int{10, 9, 2, 5, 3, 7, 101, 18}
34.  
    fmt.Println(lengthOfLIS(nums))
35.  
     
36.  
    nums = []int{0, 1, 0, 3, 2, 3}
37.  
    fmt.Println(lengthOfLIS(nums))
38.  
     
39.  
    nums = []int{7, 7, 7, 7, 7, 7, 7}
40.  
    fmt.Println(lengthOfLIS(nums))
41.  
    }

---

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

代码：二分查找

1.  
   package main
2.  
    
3.  
   import "fmt"
4.  
    
5.  
   var mx []int // 全局变量
6.  
    
7.  
   func updateTree(root, l, r, i, val int) {
8.  
   if l == r {
9.  
   mx[root] = val
10.  
    return
11.  
    }
12.  
    mid := (l r) / 2
13.  
    if i <= mid {
14.  
    updateTree(root*2, l, mid, i, val)
15.  
    } else {
16.  
    updateTree(root*2 1, mid 1, r, i, val)
17.  
    }
18.  
    mx[root] = max(mx[root*2], mx[root*2 1])
19.  
    }
20.  
     
21.  
    func query(root, l, r, L, R int) int {
22.  
    if L <= l && r <= R {
23.  
    return mx[root]
24.  
    }
25.  
    ret := 0
26.  
    mid := (l r) / 2
27.  
    if L <= mid {
28.  
    ret = query(root*2, l, mid, L, R)
29.  
    }
30.  
    if R > mid {
31.  
    ret = max(query(root*2 1, mid 1, r, L, R), ret)
32.  
    }
33.  
    return ret
34.  
    }
35.  
     
36.  
    func lengthOfLIS(nums []int, k int) int {
37.  
    up := 0
38.  
    for _, x := range nums {
39.  
    if x > up {
40.  
    up = x
41.  
    }
42.  
    }
43.  
    mx = make([]int, 4*up)
44.  
    for _, x := range nums {
45.  
    if x == 1 {
46.  
    updateTree(1, 1, up, 1, 1)
47.  
    } else {
48.  
    L := x - k
49.  
    if L < 1 {
50.  
    L = 1
51.  
    }
52.  
    ret := 1 query(1, 1, up, L, x-1)
53.  
    updateTree(1, 1, up, x, ret)
54.  
    }
55.  
    }
56.  
    return mx[1]
57.  
    }
58.  
     
59.  
    func max(a, b int) int {
60.  
    if a > b {
61.  
    return a
62.  
    }
63.  
    return b
64.  
    }
65.  
     
66.  
    func main() {
67.  
    nums1 := []int{4, 2, 1, 4, 3, 4, 5, 8, 15}
68.  
    k1 := 3
69.  
    fmt.Println(lengthOfLIS(nums1, k1))
70.  
    nums2 := []int{7, 4, 5, 1, 8, 12, 4, 7}
71.  
    k2 := 5
72.  
    fmt.Println(lengthOfLIS(nums2, k2))
73.  
    nums3 := []int{1, 5}
74.  
    k3 := 1
75.  
    fmt.Println(lengthOfLIS(nums3, k3))
76.  
    }

输出：

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

代码：

1.  
   package main
2.  
    
3.  
   import "fmt"
4.  
    
5.  
   func findNumberOfLIS(nums []int) int {
6.  
   n := len(nums)
7.  
   if n <= 1 {
8.  
   return n
9.  
   }
10.  
    dp := make([]int, n)
11.  
    cnt := make([]int, n)
12.  
    for i := range dp {
13.  
    dp[i], cnt[i] = 1, 1
14.  
    }
15.  
    maxLen, ans := 1, 0
16.  
    for i := 1; i < n; i {
17.  
    for j := 0; j < i; j {
18.  
    if nums[j] < nums[i] {
19.  
    if dp[j] 1 > dp[i] {
20.  
    dp[i], cnt[i] = dp[j] 1, cnt[j]
21.  
    } else if dp[j] 1 == dp[i] {
22.  
    cnt[i] = cnt[j]
23.  
    }
24.  
    }
25.  
    }
26.  
    maxLen = max(maxLen, dp[i])
27.  
    }
28.  
    for i := range cnt {
29.  
    if dp[i] == maxLen {
30.  
    ans = cnt[i]
31.  
    }
32.  
    }
33.  
    return ans
34.  
    }
35.  
     
36.  
    func max(x, y int) int {
37.  
    if x > y {
38.  
    return x
39.  
    }
40.  
    return y
41.  
    }
42.  
     
43.  
    func main() {
44.  
    fmt.Println(findNumberOfLIS([]int{1, 3, 5, 4, 7}))
45.  
    fmt.Println(findNumberOfLIS([]int{2, 2, 2, 2, 2}))
46.  
    }

输出：

2
5

---

🌟 每日一练刷题专栏 🌟

✨ 持续，努力奋斗做强刷题搬运工！

👍 点赞，你的认可是我坚持的动力！ 

🌟 收藏，你的青睐是我努力的方向！ 

✎ 评论，你的意见是我进步的财富！  

☸ 主页：https://hannyang.blog.csdn.net/ 

这篇好文章是转载于：学新通技术网