2023-11-22：用 go 语言，给你一个长度为 n 下标从 0 开始的整数数组 nums。
它包含 1 到 n 的所有数字，请你返回上升四元组的数目。
如果一个四元组 (i, j, k, l) 满足以下条件，我们称它是上升的：
0 <= i < j < k < l < n 且
nums[i] < nums[k] < nums[j] < nums[l] 。
输入：nums = [1,3,2,4,5]。
输出：2。
来自左程云。
答案 2023-11-22：
go 代码用灵捷 3.5 编写。
rust 代码用讯飞星火编写。
c++的代码用天工编写。
灵捷 3.5 本来用起来还可以，但有次数限制，故放弃。
大体过程如下：
算法 1：countQuadruplets1
1.初始化变量：n 为数组长度，ans 为结果计数器，dp 为动态规划数组。
2.遍历数组，从第二个元素开始（下标为 1）：
a.初始化计数器 cnt 为 0。
b.遍历当前元素之前的所有元素（下标小于当前元素的下标），如果当前元素大于前一个元素，则将 dp[j]加到 ans 上，并将 cnt 加 1。
c.再次遍历当前元素之前的所有元素（下标小于当前元素的下标），如果当前元素大于前一个元素，则将 cnt 加到 dp[j]上；否则，将 dp[j]加上 cnt 的整数值。
3.返回 ans 作为结果。
算法 2：countQuadruplets2
1.初始化变量：n 为数组长度，ans 为结果计数器，dp 为动态规划数组。
2.遍历数组，从第二个元素开始（下标为 1）：
a.初始化计数器 cnt 为 0。
b.遍历当前元素之前的所有元素（下标小于当前元素的下标），如果当前元素大于前一个元素，则将 dp[j]加到 ans 上，并将 cnt 加 1；否则，将 dp[j]加上 cnt 的整数值。
3.返回 ans 作为结果。
总的时间复杂度：两种算法的时间复杂度都是 O(n^2)，因为需要两层循环遍历数组。
总的额外空间复杂度：两种算法的空间复杂度都是 O(n)，因为需要使用一个长度为 n 的动态规划数组 dp。
go 完整代码如下：
package main
import "fmt"
func countQuadruplets1(nums []int) int64 { n := len(nums) var ans int64 dp := make([]int64, n) for l := 1; l < n; l++ { cnt := 0 for j := 0; j < l; j++ { if nums[j] < nums[l] { ans += dp[j] } }
cnt = 0 for j := 0; j < l; j++ { if nums[j] < nums[l] { cnt++ } else { dp[j] += int64(cnt) } } } return ans}
func countQuadruplets2(nums []int) int64 { n := len(nums) var ans int64 dp := make([]int64, n) for l := 1; l < n; l++ { cnt := 0 for j := 0; j < l; j++ { if nums[j] < nums[l] { ans += dp[j] cnt++ } else { dp[j] += int64(cnt) } } } return ans}
func main() { nums := []int{1, 3, 2, 4, 5} fmt.Println(countQuadruplets1(nums)) fmt.Println(countQuadruplets2(nums))}
复制代码
rust 完整代码如下：
fn count_quadruplets1(nums: Vec<i32>) -> i64 { let n = nums.len(); let mut ans = 0; let mut dp = vec![0; n]; for l in 1..n { let mut cnt = 0; for j in 0..l { if nums[j] < nums[l] { ans += dp[j]; cnt += 1; } else { dp[j] += cnt; } } } ans as i64}
fn count_quadruplets2(nums: Vec<i32>) -> i64 { let n = nums.len(); let mut ans = 0; let mut dp = vec![0; n]; for l in 1..n { let mut cnt = 0; for j in 0..l { if nums[j] < nums[l] { ans += dp[j]; cnt += 1; } else { dp[j] += cnt; } } } ans as i64}
fn main() { let nums = vec![1, 3, 2, 4, 5]; println!("count_quadruplets1: {}", count_quadruplets1(nums)); let nums = vec![1, 3, 2, 4, 5]; println!("count_quadruplets2: {}", count_quadruplets2(nums));}
复制代码
c++完整代码如下：
#include <iostream>#include <vector>using namespace std;
long long countQuadruplets1(vector<int>& nums) { int n = nums.size(); long long ans = 0; vector<long long> dp(n, 0); for (int l = 1; l < n; l++) { for (int j = 0; j < l; j++) { if (nums[j] < nums[l]) { ans += dp[j]; } } int cnt = 0; for (int j = 0; j < l; j++) { if (nums[j] < nums[l]) { cnt++; } else { dp[j] += cnt; break; } } } return ans;}
long long countQuadruplets2(vector<int>& nums) { int n = nums.size(); long long ans = 0; vector<long long> dp(n, 0); for (int l = 1; l < n; l++) { int cnt = 0; for (int j = 0; j < l; j++) { if (nums[j] < nums[l]) { ans += dp[j]; cnt++; } else { dp[j] += cnt; } } } return ans;}
int main() { vector<int> nums = { 1, 3, 2, 4, 5 }; cout << countQuadruplets1(nums) << endl; cout << countQuadruplets2(nums) << endl; return 0;}
复制代码
评论