写点什么

文心一言 VS 讯飞星火 VS chatgpt (208)-- 算法导论 15.4 5 题

  • 2024-03-05
    北京
  • 本文字数:5975 字

    阅读完需:约 20 分钟

五、设计一个 O() 时间的算法,求一个 n 个数的序列的最长单调递增子序列。要写代码的时候,请用 go 语言。

文心一言,抛 panic:

在 Go 语言中设计一个 O(n^2) 时间复杂度的算法来求一个 n 个数的序列的最长单调递增子序列(Longest Increasing Subsequence, LIS)可以使用动态规划的方法。以下是一个实现示例:


package main    import (    "fmt"  )    // LIS 使用动态规划来求一个序列的最长单调递增子序列  func LIS(nums []int) []int {    n := len(nums)    if n == 0 {      return []int{}    }      // dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度    dp := make([]int, n)    // 初始化 dp 数组,每个元素自身构成一个长度为 1 的递增子序列    for i := 0; i < n; i++ {      dp[i] = 1    }      // 初始化最长递增子序列的末尾元素数组    lis := make([]int, n)    // 最长递增子序列的长度    maxLen := 1    // 最长递增子序列的末尾元素索引    maxIndex := 0      for i := 1; i < n; i++ {      for j := 0; j < i; j++ {        // 如果 nums[i] 大于 nums[j],则考虑将 nums[i] 添加到以 nums[j] 结尾的递增子序列        if nums[i] > nums[j] && dp[i] < dp[j]+1 {          dp[i] = dp[j] + 1          lis[i] = j // 记录状态转移路径        }      }      // 更新最长递增子序列的长度和末尾元素索引      if dp[i] > maxLen {        maxLen = dp[i]        maxIndex = i      }    }      // 根据状态转移路径反向构建最长递增子序列    result := make([]int, maxLen)    for i := maxIndex; i >= 0; i = lis[i] {      result[maxLen-1-i] = nums[i]    }      return result  }    func main() {    nums := []int{10, 9, 2, 5, 3, 7, 101, 18}    lis := LIS(nums)    fmt.Println("The longest increasing subsequence is:", lis)  }
复制代码


这个算法的时间复杂度是 O(n^2),其中 n 是序列的长度。我们创建了一个 dp 数组来存储以每个元素结尾的最长递增子序列的长度,并通过比较每个元素和它之前的元素来更新 dp 数组。我们也创建了一个 lis 数组来记录状态转移的路径,以便在算法结束时反向构建出最长递增子序列。


当 dp[i] 的值更新时,我们记录下是哪个 dp[j] 转移过来的,即 lis[i] = j。这样,在构建最长递增子序列时,我们可以从 maxIndex(最长递增子序列的末尾元素索引)开始,根据 lis 数组反向追溯,得到整个子序列。


在 main 函数中,我们调用 LIS 函数并打印出最长递增子序列。




讯飞星火,代码正常运行:

在 Go 语言中,我们可以使用动态规划来解决这个问题。以下是实现最长单调递增子序列的代码:


package mainimport "fmt"
func max(a, b int) int { if a > b { return a } return b}
func longestIncreasingSubsequence(nums []int) int { n := len(nums) dp := make([]int, n) for i := range dp { dp[i] = 1 } for i := 1; i < n; i++ { for j := 0; j < i; j++ { if nums[i] > nums[j] { dp[i] = max(dp[i], dp[j]+1) } } } maxLen := 0 for _, v := range dp { maxLen = max(maxLen, v) } return maxLen}
func main() { nums := []int{10, 9, 2, 5, 3, 7, 101, 18} fmt.Println("Length of Longest Increasing Subsequence is", longestIncreasingSubsequence(nums))}
复制代码


在这个程序中,我们首先定义了一个一维数组 dp,其中 dp[i]表示以第 i 个元素结尾的最长递增子序列的长度。然后,我们遍历数组,对于每个元素,我们都检查它之前的所有元素,如果当前元素大于之前的某个元素,那么我们就更新 dp[i]的值。最后,我们返回 dp 数组中的最大值,这就是最长递增子序列的长度。



360 智脑,代码正常运行:

以下是一个使用 Go 语言实现的 O(n^2)时间的算法,用于求解一个 n 个数的序列的最长单调递增子序列:


package main  import "fmt" func longestMonotonicSubsequence(X []int, n int) int {    // 初始化dp数组     dp := make([]int, n+1)    for i := range dp {        dp[i] = 1     }     // 从第二个元素开始遍历     for i := 1; i < n; i++ {        for j := 0; j < i; j++ {            // 如果X[i]大于X[j],并且dp[i]小于dp[j]+1             if X[i] > X[j] && dp[i] < dp[j]+1 {                dp[i] = dp[j] + 1             }        }    }     // 找到dp数组中的最大值     max := 0     for _, v := range dp {        if v > max {            max = v         }    }     return max } func main() {    X := []int{10, 22, 9, 33, 21, 50, 41, 60}    n := len(X)    fmt.Println(longestMonotonicSubsequence(X, n))}
复制代码


在这个算法中,我们使用了一个动态规划的方法。我们首先初始化一个 dp 数组,其中 dp[i]表示序列 X 中以 X[i]结尾的最长单调递增子序列的长度。然后,我们从第二个元素开始遍历 X,对于每个元素 X[i],我们检查它是否大于之前的元素 X[j],并且 dp[i]是否小于 dp[j]+1。如果是,我们就更新 dp[i]为 dp[j]+1。最后,我们找到 dp 数组中的最大值,即为所求的最长单调递增子序列的长度。



智谱清言,代码正常运行:

在计算机科学中,最长单调递增子序列(Longest Monotonically Increasing Subsequence,简称 LIS)问题可以通过动态规划在 O()的时间内解决。下面是一个使用 Go 语言实现的 O(n^2) 动态规划算法来解决最长单调递增子序列问题:


package mainimport (  "fmt")// lis 函数计算最长单调递增子序列的长度func lis(nums []int) int {  if len(nums) == 0 {    return 0  }  // dp[i] 表示以 nums[i] 结尾的最长单调递增子序列的长度  dp := make([]int, len(nums))  // 初始化dp数组,每个元素的值都是1,因为每个数字本身都可以构成一个长度为1的递增子序列  for i := range dp {    dp[i] = 1  }  // 动态规划填表  for i := 1; i < len(nums); i++ {    for j := 0; j < i; j++ {      if nums[i] > nums[j] {        dp[i] = max(dp[i], dp[j]+1)      }    }  }  // 找出dp数组中的最大值,即为最长单调递增子序列的长度  maxLength := 0  for _, length := range dp {    maxLength = max(maxLength, length)  }  return maxLength}// max 函数返回两个整数中的最大值func max(a, b int) int {  if a > b {    return a  }  return b}func main() {  // 测试数据  nums := []int{10, 9, 2, 5, 3, 7, 101, 18}  fmt.Println("The length of the longest increasing subsequence is:", lis(nums))}
复制代码


这段代码首先初始化一个动态规划数组 dp,其中 dp[i] 表示以 nums[i] 结尾的最长单调递增子序列的长度。然后,它通过两层循环来填充这个数组,如果在 nums 中的某个较小的元素 nums[j] 之后有元素 nums[i],则 dp[i] 可以更新为 dp[j] + 1。最后,它遍历 dp 数组以找到最大的值,这个值就是最长单调递增子序列的长度。


请注意,尽管这个算法是 O(n^2) 的,但对于较大的数据集,它可能不是最优的。在实际应用中,可以考虑使用二分搜索优化算法,将时间复杂度降低到 O(nlogn)。



天工,代码正常运行:

以下是一个使用动态规划算法来找出一个包含 n 个元素的序列的最长单调递增子序列(LIS)的 Go 语言实现。这个算法的时间复杂度是 O(n^2)。


package main
import "fmt"
// findLISLength 使用动态规划找出给定数组的最长单调递增子序列的长度。func findLISLength(nums []int) int { if len(nums) == 0 { return 0 }
dp := make([]int, len(nums)) dp[0] = 1 // 初始化第一个元素的 LIS 为 1。
for i := 1; i < len(nums); i++ { for j := 0; j < i; j++ { if nums[i] > nums[j] { dp[i] = max(dp[i], dp[j]+1) } } }
// 找到最长 LIS 长度。 var maxLen int for _, length := range dp { if length > maxLen { maxLen = length } } return maxLen}
// max 返回两个整数中较大的一个。func max(a, b int) int { if a >= b { return a } return b}
func main() { nums := []int{10, 22, 9, 33, 21, 50, 30, 60, 80} length := findLISLength(nums) fmt.Printf("Length of LIS: %d\n", length)}
复制代码


这段代码定义了一个 findLISLength 函数,它接受一个整数切片作为输入,并返回该序列的最长单调递增子序列的长度。函数内部使用了一个名为 dp 的动态规划数组,用于存储每个元素在 LIS 中的可能最大长度。通过迭代和比较,逐步构建出整个数组在 LIS 中的长度,最后通过遍历 dp 数组来找到最长的 LIS 长度。


main 函数中,有一个示例数组 nums,调用 findLISLength 函数并打印结果。你可以替换 nums 中的值以测试不同的数组。



灵小智,代码正常运行:

Sure! 下面是一个使用Go语言实现的O($n^2$)时间复杂度的算法来求解一个n个数的序列的最长单调递增子序列。
复制代码


package main
import ( "fmt")
func longestIncreasingSubsequence(nums []int) []int { length := len(nums) dp := make([]int, length) for i := 0; i < length; i++ { dp[i] = 1 }
for i := 1; i < length; i++ { for j := 0; j < i; j++ { if nums[i] > nums[j] && dp[i] < dp[j]+1 { dp[i] = dp[j] + 1 } } }
maxLen := 0 endIndex := 0 for i := 0; i < length; i++ { if dp[i] > maxLen { maxLen = dp[i] endIndex = i } }
result := make([]int, maxLen) result[maxLen-1] = nums[endIndex] maxLen-- endIndex--
for i := endIndex; i >= 0; i-- { if nums[i] < nums[endIndex] && dp[i] == maxLen { result[maxLen-1] = nums[i] maxLen-- endIndex = i } }
return result}
func main() { nums := []int{10, 22, 9, 33, 21, 50, 41, 60} lis := longestIncreasingSubsequence(nums) fmt.Println("最长递增子序列为:", lis)}
复制代码


希望这个算法和代码对你有所帮助!



chatgpt,代码正常运行:

要设计一个 O(n^2)时间复杂度的算法来求一个 n 个数的序列的最长单调递增子序列,可以使用动态规划的思想。下面是用 Go 语言实现的代码:


package main
import ( "fmt")
func longestIncreasingSubsequence(nums []int) int { n := len(nums) if n == 0 { return 0 }
dp := make([]int, n) // dp[i]表示以nums[i]结尾的最长递增子序列长度 maxLen := 1 // 最长递增子序列的长度,默认为1
for i := 0; i < n; i++ { dp[i] = 1 // 初始化dp数组为1 for j := 0; j < i; j++ { if nums[j] < nums[i] && dp[j]+1 > dp[i] { dp[i] = dp[j] + 1 // 更新dp数组 } } if dp[i] > maxLen { maxLen = dp[i] } }
return maxLen}
func main() { nums := []int{10, 22, 9, 33, 21, 50, 41, 60} fmt.Println("最长递增子序列长度:", longestIncreasingSubsequence(nums))}
复制代码


该代码使用动态规划算法,定义 dp 数组表示以每个位置元素结尾的最长递增子序列长度。初始化 dp 数组为 1,并在遍历过程中更新 dp 值。最后返回 dp 数组中的最大值作为最长递增子序列的长度。


该算法的时间复杂度为 O(n^2),因为需要两层循环来遍历所有可能的子序列。



kimi,代码正常运行:

为了在 O(n^2) 时间内找到一个序列的最长单调递增子序列(LIS),我们可以使用一个经典的动态规划方法。这个算法的核心思想是维护一个数组 lis,其中 lis[i] 表示以第 i 个元素结尾的最长递增子序列的长度。对于每个元素,我们需要检查它之前的所有元素,如果当前元素大于之前的某个元素,我们更新 lis 数组。


以下是使用 Go 语言实现的 O(n^2) 时间复杂度的 LIS 算法:


package main
import ( "fmt")
// LIS 函数计算序列的最长单调递增子序列的长度func LIS(seq []int) int { n := len(seq) lis := make([]int, n) maxLIS := 0
// 初始化 lis 数组,每个元素的 LIS 长度初始为 1 for i := range lis { lis[i] = 1 }
// 遍历序列,更新 lis 数组 for i := 1; i < n; i++ { for j := 0; j < i; j++ { if seq[i] > seq[j] && lis[i] < lis[j]+1 { lis[i] = lis[j] + 1 } } // 更新最大 LIS 长度 if lis[i] > maxLIS { maxLIS = lis[i] } }
return maxLIS}
func main() { seq := []int{10, 9, 2, 5, 3, 7, 101, 18} lisLength := LIS(seq) fmt.Printf("Length of the Longest Increasing Subsequence is: %d\n", lisLength)}
复制代码


在这个实现中,我们首先初始化 lis 数组,使得每个元素的 LIS 长度初始为 1。然后,我们使用两层循环来更新 lis 数组。外层循环遍历序列中的每个元素,内层循环检查当前元素之前的所有元素。如果找到一个较小的元素,我们尝试更新当前元素的 LIS 长度。最后,我们记录并返回最大的 LIS 长度。


这个算法的时间复杂度是 O(n^2),因为我们需要对序列中的每个元素进行两次遍历。



混元,代码正常运行:

以下是使用 Go 语言实现的一个 O(n^2) 时间复杂度的算法,用于求一个 n 个数的序列的最长单调递增子序列:


package main
import ( "fmt")
func longestIncreasingSubsequence(arr []int) int { n := len(arr) dp := make([]int, n)
for i := range dp { dp[i] = 1 }
for i := 1; i < n; i++ { for j := 0; j < i; j++ { if arr[i] > arr[j] { dp[i] = max(dp[i], dp[j]+1) } } }
maxLength := 0 for _, val := range dp { maxLength = max(maxLength, val) }
return maxLength}
func max(a, b int) int { if a > b { return a } return b}
func main() { arr := []int{10, 22, 9, 33, 21, 50, 41, 60, 80} fmt.Printf("The length of the longest increasing subsequence is: %d\n", longestIncreasingSubsequence(arr))}
复制代码


这个实现使用动态规划方法。dp[i] 表示以 arr[i] 结尾的最长单调递增子序列的长度。对于每个元素 arr[i],我们遍历其之前的所有元素 arr[j],如果 arr[i] > arr[j],则更新 dp[i]max(dp[i], dp[j]+1)。最后,我们返回 dp 数组中的最大值,即为最长单调递增子序列的长度。




发布于: 44 分钟前阅读数: 5
用户头像

公众号:福大大架构师每日一题 2021-02-15 加入

公众号:福大大架构师每日一题

评论

发布
暂无评论
文心一言 VS 讯飞星火 VS chatgpt (208)-- 算法导论15.4 5题_福大大架构师每日一题_福大大架构师每日一题_InfoQ写作社区