2023-07-04：给定一个数组A, 把它分成两个数组B和C

对于数组A每个i位置的数来说，

A[i] = B[i] + C[i]

也就是一个数字分成两份，然后各自进入B和C

要求B[i], C[i] >= 1

最终B数组要求从左到右不能降序

最终C数组要求从左到右不能升序

比如

A = { 5, 4, 5 }

可以分成

B = { 2, 2, 3 }

C = { 3, 2, 2 }

这是一种有效的划分

返回有多少种有效的划分方式

1 <= A的长度 <= 10^7

1 <= A[i] <= 10^7

最终结果可能很大，请返回对1000000007取余的结果。

国外算法面经帖子上的题。

答案2023-07-04：

大体步骤如下：

算法一：

1.定义一个递归函数 process1，接受一个数组 arr，一个索引 i，前一个增加值 preIncrease 和前一个减少值 preDecrease。

2.如果 i 等于数组的长度（即 i == arr.size()），返回 1。

3.将 ans 初始化为 0。

4.遍历 arr[i] 可能的增加值和减少值。

5.如果前一个增加值 preIncrease 小于等于当前增加值，并且前一个减少值 preDecrease 大于等于当前减少值，递归调用 process1，并将结果加到 ans 上。

6.返回 ans。

7.在 ways1 函数中，将 ans 初始化为 0。

8.遍历第一个元素 arr 的可能增加值和减少值。

9.对于每对可能的增加值和减少值，调用更新参数后的 process1，并将结果加到 ans 上。

10.返回 ans。

算法二：

1.定义一个函数 pascalTriangleModulus，使用给定的公式计算 Pascal’s 三角形中元素的模值。

2.定义一个函数 power，使用模幂运算计算 x 的 n 次方。

3.在 ways2 函数中，将变量 n 设置为 arr 的大小，将变量 k 设置为 arr[0]-1。

4.从第二个元素开始遍历数组 arr，并根据前一个元素和当前元素之差来减小 k 的值（如果前一个元素大于当前元素）。

5.如果 k 小于等于 0，则返回 0，因为无法以有效方式对数组进行分割。

6.使用 pascalTriangleModulus 函数，参数为 k-1+n 和 n，计算结果。

7.返回结果。

总时间复杂度：

• 算法一：process1 的时间复杂度为 $O(2^n)$ ，其中 n 是 arr 的大小。在 ways1 中，我们遍历第一个元素 arr 的每个可能的增加值和减少值，时间复杂度为 O(arr[0])。因此，总时间复杂度为 $O(arr[0] * 2^n)$。

• 算法二：ways2 的时间复杂度为 O(n)，其中 n 是 arr 的大小。pascalTriangleModulus 函数的时间复杂度为常数时间。

总空间复杂度：

• 算法一：空间复杂度为 O(n)，其中 n 是 arr 的大小，由于递归调用和函数栈的使用。

• 算法二：空间复杂度为 O(1)，因为没有使用额外的数据结构。

c++完整代码如下：

#include <iostream>
#include <vector>
#define MOD 1000000007

using namespace std;

int process1(vector<int>& arr, int i, int preIncrease, int preDecrease);

int ways1(vector<int>& arr) {
    int ans = 0;
    for (int increase = 1, decrease = arr[0] - 1; increase < arr[0]; increase++, decrease--) {
        ans += process1(arr, 1, increase, decrease);
    }
    return ans;
}

int process1(vector<int>& arr, int i, int preIncrease, int preDecrease) {
    if (i == arr.size()) {
        return 1;
    }
    int ans = 0;
    for (int increase = 1, decrease = arr[i] - 1; increase < arr[i]; increase++, decrease--) {
        if (preIncrease <= increase && preDecrease >= decrease) {
            ans += process1(arr, i + 1, increase, decrease);
        }
    }
    return ans;
}

long long power(long long x, int n);

int pascalTriangleModulus(int n, int r) {
    long long up = 1;
    long long inv1 = 1;
    long long inv2 = 1;
    for (int i = 1; i <= n; i++) {
        up = (up * i) % MOD;
        if (i == r) {
            inv1 = power(up, MOD - 2);
        }
        if (i == n - r) {
            inv2 = power(up, MOD - 2);
        }
    }
    return (((up * inv1) % MOD) * inv2) % MOD;
}

long long power(long long x, int n) {
    long long ans = 1;
    while (n > 0) {
        if ((n & 1) == 1) {
            ans = (ans * x) % MOD;
        }
        x = (x * x) % MOD;
        n >>= 1;
    }
    return ans;
}

int ways2(vector<int>& arr) {
    int n = arr.size();
    int k = arr[0] - 1;
    for (int i = 1; i < n && k > 0; i++) {
        if (arr[i - 1] > arr[i]) {
            k -= arr[i - 1] - arr[i];
        }
    }
    if (k <= 0) {
        return 0;
    }
    return pascalTriangleModulus(k - 1 + n, n);
}

vector<int> randomArray(int n, int v) {
    vector<int> arr(n);
    for (int i = 0; i < n; i++) {
        arr[i] = rand() % v + 1;
    }
    return arr;
}

int main() {
    cout << "打印部分杨辉三角形" << endl;
    for (int n = 0; n <= 10; n++) {
        for (int r = 0; r <= n; r++) {
            cout << pascalTriangleModulus(n, r) << " ";
        }
        cout << endl;
    }
    int N = 10;
    int V = 20;
    int testTimes = 20000;
    cout << "功能测试开始" << endl;
    for (int i = 0; i < testTimes; i++) {
        int n = rand() % N + 1;
        vector<int> arr = randomArray(n, V);
        int ans1 = ways1(arr);
        int ans2 = ways2(arr);
        if (ans1 != ans2) {
            cout << "出错了!" << endl;
        }
    }
    cout << "功能测试结束" << endl;

    cout << "性能测试开始" << endl;
    int n = 10000000;
    int v = 10000000;
    cout << "随机生成的数据测试 : " << endl;
    cout << "数组长度 : " << n << endl;
    cout << "数值范围 : [" << 1 << "," << v << "]" << endl;
    vector<int> arr(n);
    for (int i = 0; i < n; i++) {
        arr[i] = rand() % v + 1;
    }

    clock_t start, end;
    start = clock();
    ways2(arr);
    end = clock();
    cout << "运行时间 : " << (end - start) << " 毫秒" << endl;

    cout << "运行最慢的数据测试 : " << endl;
    cout << "数组长度 : " << n << endl;
    cout << "数值都是 : " << v << endl;
    cout << "这种情况其实是复杂度最高的情况" << endl;
    for (int i = 0; i < n; i++) {
        arr[i] = v;
    }
    start = clock();
    ways2(arr);
    end = clock();
    cout << "运行时间 : " << (end - start) << " 毫秒" << endl;
    cout << "性能测试结束" << endl;

    return 0;
}

go完整代码如下：

package main

import (
    "fmt"
    "math/big"
    "math/rand"
    "time"
)

func ways1(arr []int) int {
    ans := 0
    for increase, decrease := 1, arr[0]-1; increase < arr[0]; increase, decrease = increase+1, decrease-1 {
        ans += process1(arr, 1, increase, decrease)
    }
    return ans
}

func process1(arr []int, i, preIncrease, preDecrease int) int {
    if i == len(arr) {
        return 1
    }
    ans := 0
    for increase, decrease := 1, arr[i]-1; increase < arr[i]; increase, decrease = increase+1, decrease-1 {
        if preIncrease <= increase && preDecrease >= decrease {
            ans += process1(arr, i+1, increase, decrease)
        }
    }
    return ans
}

func ways2(arr []int) int {
    n := len(arr)
    k := arr[0] - 1
    for i := 1; i < n && k > 0; i++ {
        if arr[i-1] > arr[i] {
            k -= arr[i-1] - arr[i]
        }
    }
    if k <= 0 {
        return 0
    }
    return pascalTriangleModulus(k-1+n, n)
}

func pascalTriangleModulus(n, r int) int {
    mod := big.NewInt(1000000007)
    up := big.NewInt(1)
    inv1 := big.NewInt(1)
    inv2 := big.NewInt(1)
    for i := 1; i <= n; i++ {
        up.Mul(up, big.NewInt(int64(i)))
        if i == r {
            inv1.Exp(up, big.NewInt(int64(mod.Int64()-2)), mod)
        }
        if i == n-r {
            inv2.Exp(up, big.NewInt(int64(mod.Int64()-2)), mod)
        }
    }
    inv1.Mod(inv1, mod)
    inv2.Mod(inv2, mod)
    ans := new(big.Int)
    ans.Mul(up, inv1)
    ans.Mod(ans, mod)
    ans.Mul(ans, inv2)
    ans.Mod(ans, mod)
    return int(ans.Int64())
}

func power(x int64, n, mod int64) int64 {
    ans := int64(1)
    for n > 0 {
        if n&1 == 1 {
            ans = (ans * x) % mod
        }
        x = (x * x) % mod
        n >>= 1
    }
    return ans
}

func randomArray(n, v int) []int {
    arr := make([]int, n)
    rand.Seed(time.Now().UnixNano())
    for i := 0; i < n; i++ {
        arr[i] = rand.Intn(v) + 1
    }
    return arr
}

func main() {
    fmt.Println("打印部分杨辉三角形")
    for n := 0; n <= 10; n++ {
        for r := 0; r <= n; r++ {
            fmt.Print(pascalTriangleModulus(n, r), " ")
        }
        fmt.Println()
    }
    N := 10
    V := 20
    testTimes := 20000
    fmt.Println("功能测试开始")
    for i := 0; i < testTimes; i++ {
        n := rand.Intn(N) + 1
        arr := randomArray(n, V)
        ans1 := ways1(arr)
        ans2 := ways2(arr)
        if ans1 != ans2 {
            fmt.Println("出错了!")
        }
    }
    fmt.Println("功能测试结束")

    fmt.Println("性能测试开始")
    n := 10000000
    v := 10000000
    fmt.Println("随机生成的数据测试 : ")
    fmt.Println("数组长度 : ", n)
    fmt.Println("数值范围 : [", 1, ",", v, "]")
    arr := randomArray(n, v)

    start := time.Now()
    ways2(arr)
    end := time.Now()
    fmt.Println("运行时间 : ", end.Sub(start).Milliseconds(), " 毫秒")

    n -= 5
    v -= 5
    fmt.Println("运行最慢的数据测试 : ")
    fmt.Println("数组长度 : ", n)
    fmt.Println("数值都是 : ", v)
    fmt.Println("这种情况其实是复杂度最高的情况")
    for i := 0; i < n; i++ {
        arr[i] = v
    }
    start = time.Now()
    ways2(arr)
    end = time.Now()
    fmt.Println("运行时间 : ", end.Sub(start).Milliseconds(), " 毫秒")
    fmt.Println("性能测试结束")
}

本作品采用《CC 协议》，转载必须注明作者和本文链接