2023-11-22：用go語言，給你一個(gè)長度為 n 下標(biāo)從 0 開始的整數(shù)數(shù)組 nums。

它包含 1 到 n 的所有數(shù)字，請你返回上升四元組的數(shù)目。

如果一個(gè)四元組 (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本來用起來還可以，但有次數(shù)限制，故放棄。

大體過程如下：

算法1：countQuadruplets1

1.初始化變量：n為數(shù)組長度，ans為結(jié)果計(jì)數(shù)器，dp為動(dòng)態(tài)規(guī)劃數(shù)組。

2.遍歷數(shù)組，從第二個(gè)元素開始（下標(biāo)為1）：

a.初始化計(jì)數(shù)器cnt為0。

b.遍歷當(dāng)前元素之前的所有元素（下標(biāo)小于當(dāng)前元素的下標(biāo)），如果當(dāng)前元素大于前一個(gè)元素，則將dp[j]加到ans上，并將cnt加1。

c.再次遍歷當(dāng)前元素之前的所有元素（下標(biāo)小于當(dāng)前元素的下標(biāo)），如果當(dāng)前元素大于前一個(gè)元素，則將cnt加到dp[j]上；否則，將dp[j]加上cnt的整數(shù)值。

3.返回ans作為結(jié)果。

算法2：countQuadruplets2

1.初始化變量：n為數(shù)組長度，ans為結(jié)果計(jì)數(shù)器，dp為動(dòng)態(tài)規(guī)劃數(shù)組。

2.遍歷數(shù)組，從第二個(gè)元素開始（下標(biāo)為1）：

a.初始化計(jì)數(shù)器cnt為0。

b.遍歷當(dāng)前元素之前的所有元素（下標(biāo)小于當(dāng)前元素的下標(biāo)），如果當(dāng)前元素大于前一個(gè)元素，則將dp[j]加到ans上，并將cnt加1；否則，將dp[j]加上cnt的整數(shù)值。

3.返回ans作為結(jié)果。

總的時(shí)間復(fù)雜度：兩種算法的時(shí)間復(fù)雜度都是O(n^2)，因?yàn)樾枰獌蓪友h(huán)遍歷數(shù)組。

總的額外空間復(fù)雜度：兩種算法的空間復(fù)雜度都是O(n)，因?yàn)樾枰褂靡粋€(gè)長度為n的動(dòng)態(tài)規(guī)劃數(shù)組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;
}

總結(jié)

以上是生活随笔為你收集整理的2023-11-22：用go语言，给你一个长度为 n 下标从 0 开始的整数数组 nums。 它包含 1 到 n 的所有数字，请你返回上升四元组的数目。 如果一个四元组 (i, j, k, l) 满足的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。