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完整代码如下:
packagemain
import"fmt"
funccountQuadruplets1(nums[]int)int64{
n:=len(nums)
varansint64
dp:=make([]int64,n)
forl:=1;lcnt:=0
forj:=0;jifnums[j]ans+=dp[j]
}
}
cnt=0
forj:=0;jifnums[j]cnt++
}else{
dp[j]+=int64(cnt)
}
}
}
returnans
}
funccountQuadruplets2(nums[]int)int64{
n:=len(nums)
varansint64
dp:=make([]int64,n)
forl:=1;lcnt:=0
forj:=0;jifnums[j]ans+=dp[j]
cnt++
}else{
dp[j]+=int64(cnt)
}
}
}
returnans
}
funcmain(){
nums:=[]int{1,3,2,4,5}
fmt.Println(countQuadruplets1(nums))
fmt.Println(countQuadruplets2(nums))
}
rust完整代码如下:
fncount_quadruplets1(nums:Vec)->i64{
letn=nums.len();
letmutans=0;
letmutdp=vec![0;n];
forlin1..n{
letmutcnt=0;
forjin0..l{
ifnums[j]ans+=dp[j];
cnt+=1;
}else{
dp[j]+=cnt;
}
}
}
ansasi64
}
fncount_quadruplets2(nums:Vec)->i64{
letn=nums.len();
letmutans=0;
letmutdp=vec![0;n];
forlin1..n{
letmutcnt=0;
forjin0..l{
ifnums[j]ans+=dp[j];
cnt+=1;
}else{
dp[j]+=cnt;
}
}
}
ansasi64
}
fnmain(){
letnums=vec![1,3,2,4,5];
println!("count_quadruplets1:{}",count_quadruplets1(nums));
letnums=vec![1,3,2,4,5];
println!("count_quadruplets2:{}",count_quadruplets2(nums));
}
c++完整代码如下:
#include
#include
usingnamespacestd;
longlongcountQuadruplets1(vector&nums){
intn=nums.size();
longlongans=0;
vectordp(n,0);
for(intl=1;lfor(intj=0;jif(nums[j]ans+=dp[j];
}
}
intcnt=0;
for(intj=0;jif(nums[j]cnt++;
}
else{
dp[j]+=cnt;
break;
}
}
}
returnans;
}
longlongcountQuadruplets2(vector&nums){
intn=nums.size();
longlongans=0;
vectordp(n,0);
for(intl=1;lintcnt=0;
for(intj=0;jif(nums[j]ans+=dp[j];
cnt++;
}
else{
dp[j]+=cnt;
}
}
}
returnans;
}
intmain(){
vectornums={1,3,2,4,5};
cout<cout<return0;
}
特别声明:以上内容(如有图片或视频亦包括在内)为自媒体平台“网易号”用户上传并发布,本平台仅提供信息存储服务。
Notice: The content above (including the pictures and videos if any) is uploaded and posted by a user of NetEase Hao, which is a social media platform and only provides information storage services.