首页 > 资讯 > 正文

聚焦:2023-07-04:给定一个数组A, 把它分成两个数组B和C 对于数组A每个i位置的数来说, A[i] = B[i] + C[i] 也就是一个数字分成两份,然后各自进入B和C 要求B[i], C[i

来源:博客园 2023-07-04 22:42:58

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 #include #define MOD 1000000007using namespace std;int process1(vector& arr, int i, int preIncrease, int preDecrease);int ways1(vector& 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& 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& 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 randomArray(int n, int v) {    vector 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 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 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 mainimport ("fmt""math/big""math/rand""time")func ways1(arr []int) int {ans := 0for 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 := 0for 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] - 1for 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) % modn >>= 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 := 10V := 20testTimes := 20000fmt.Println("功能测试开始")for i := 0; i < testTimes; i++ {n := rand.Intn(N) + 1arr := randomArray(n, V)ans1 := ways1(arr)ans2 := ways2(arr)if ans1 != ans2 {fmt.Println("出错了!")}}fmt.Println("功能测试结束")fmt.Println("性能测试开始")n := 10000000v := 10000000fmt.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 -= 5v -= 5fmt.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("性能测试结束")}

标签:

编辑:

最近更新

热点

2023全球数字经济大会经国务院批准,由北京市人民政府、国家发展和改革委员会、工业和信息化部、商务部、国家互联网信息办公室、中国科学技

详细>>

微信小号购买网址:http: www zxh123 vip Index asp?page=3今天与

详细>>

近日,《关于促进职业教育提质升级赋能绿色低碳高质量发展先行区建设的实施意见》发布,总体要求构建省域现代职业教育体系新模式为落脚点,

详细>>

团队的凝聚力,是企业迈向辉煌的基石。优秀团队的背后,是大局意识、协作精神和服务精神的集中体现,是个体利益和整体利益的高度统一。为进

详细>>

一年一度的618电商大促进入白热化冲刺阶段,很多网友憋足劲准备在618这波大促中购买一部心仪的智能手机。在今年的618换机大潮中,酷派COOL3

详细>>

世界名表一比一高仿手表精仿名表。 支持货到付款批发市场一手货源专营各大精仿品牌大厂货:C厂,VS厂,JF厂,MKS厂,KW厂,HBBv6厂,JF厂

详细>>