2023-07-04：給定一個數(shù)組A, 把它分成兩個數(shù)組B和C

對于數(shù)組A每個i位置的數(shù)來說，

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

也就是一個數(shù)字分成兩份，然后各自進入B和C

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

最終B數(shù)組要求從左到右不能降序

最終C數(shù)組要求從左到右不能升序

比如

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.定義一個遞歸函數(shù) process1，接受一個數(shù)組 arr，一個索引 i，前一個增加值 preIncrease 和前一個減少值 preDecrease。

2.如果 i 等于數(shù)組的長度（即 i == arr.size()），返回 1。

3.將 ans 初始化為 0。

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

5.如果前一個增加值 preIncrease 小于等于當前增加值，并且前一個減少值 preDecrease 大于等于當前減少值，遞歸調用 process1，并將結果加到 ans 上。

6.返回 ans。

7.在 ways1 函數(shù)中，將 ans 初始化為 0。

8.遍歷第一個元素 arr 的可能增加值和減少值。

9.對于每對可能的增加值和減少值，調用更新參數(shù)后的 process1，并將結果加到 ans 上。

10.返回 ans。

算法二：

1.定義一個函數(shù) pascalTriangleModulus，使用給定的公式計算 Pascal's 三角形中元素的模值。

2.定義一個函數(shù) power，使用模冪運算計算 x 的 n 次方。

3.在 ways2 函數(shù)中，將變量 n 設置為 arr 的大小，將變量 k 設置為 arr[0]-1。

4.從第二個元素開始遍歷數(shù)組 arr，并根據(jù)前一個元素和當前元素之差來減小 k 的值（如果前一個元素大于當前元素）。

5.如果 k 小于等于 0，則返回 0，因為無法以有效方式對數(shù)組進行分割。

6.使用 pascalTriangleModulus 函數(shù)，參數(shù)為 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 函數(shù)的時間復雜度為常數(shù)時間。

總空間復雜度：

• ??算法一：空間復雜度為 O(n)，其中 n 是 arr 的大小，由于遞歸調用和函數(shù)棧的使用。

• ??算法二：空間復雜度為 O(1)，因為沒有使用額外的數(shù)據(jù)結構。

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?<<?"隨機生成的數(shù)據(jù)測試?:?"?<<?endl;
????cout?<<?"數(shù)組長度?:?"?<<?n?<<?endl;
????cout?<<?"數(shù)值范圍?:?["?<<?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?<<?"運行最慢的數(shù)據(jù)測試?:?"?<<?endl;
????cout?<<?"數(shù)組長度?:?"?<<?n?<<?endl;
????cout?<<?"數(shù)值都是?:?"?<<?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("隨機生成的數(shù)據(jù)測試?:?")
????fmt.Println("數(shù)組長度?:?",?n)
????fmt.Println("數(shù)值范圍?:?[",?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("運行最慢的數(shù)據(jù)測試?:?")
????fmt.Println("數(shù)組長度?:?",?n)
????fmt.Println("數(shù)值都是?:?",?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("性能測試結束")
}