聚焦:2023-07-04:给定一个数组A, 把它分成两个数组B和C 对于数组A每个i位置的数来说, A[i] = B[i] + C[i] 也就是一个数字分成两份,然后各自进入B和C 要求B[i], C[i
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-07-04:给定一个数组A, 把
- 世界观速讯丨今夏热浪来袭 美国三分之
- 东湖评论:给予更多关爱让残障群体融入
- 中国石油北京项目管理公司:胡继勇被免
- 中国驻日本大使馆阐述中方立场!|环球
- iphone 13 pro max镜头信息(iphone
- 前沿资讯!自己做的猪肉馅丸子蒸,需要
- 每日时讯!甘肃路桥清忠二标项目“四岗
- 体型不胖,为什么也会血脂高?来看专家
- 今日热文:新app推广告话术(新app推广)
- 快报:寄快递怎么寄 第一次_寄快递怎
- 今日报丨人人喊打的黄牛:日入十万,已
- 两省省委副书记同日官宣进京履新-当前
- 快消息!喜剧学院快乐实习生全集(关于
- 怒了!泰山球迷会致信体育总局:彻查裁
- 笔记本电脑无线网络开关怎样打开_笔记
- 注意!上海瀚讯将于7月20日召开股东大会
- 当前通讯!他们,是到基层就业的高校毕
- 广本6月销量环比大涨11.4%,型格成销量
- 7月4日中燃舟山地区燃料油报价平稳
- 消息称京东零售云已并入京东科技|环球
- 今日快讯:为什么男朋友宁愿给我买8千
- 【歌词翻译】U149 - グッデイ・グッ
- 外媒:美国拟限制中国企业使用美国云计
- 环球播报:美媒:Meta公司想进中国市场
- 英飞凌XENSIV™ PAS CO2传感器符合国
- 北大兔展联合实验室发布中文法律大模型
- 河南长垣市推进碳达峰试点建设工作方案
- 【全球热闻】黑龙江省发布气象风险预警
- 全球头条:“庆党日”社会各界到施秉开
热点
2023全球数字经济大会经国务院批准,由北京市人民政府、国家发展和改革委员会、工业和信息化部、商务部、国家互联网信息办公室、中国科学技
详细>>微信小号购买网址:http: www zxh123 vip Index asp?page=3今天与
详细>>近日,《关于促进职业教育提质升级赋能绿色低碳高质量发展先行区建设的实施意见》发布,总体要求构建省域现代职业教育体系新模式为落脚点,
详细>>团队的凝聚力,是企业迈向辉煌的基石。优秀团队的背后,是大局意识、协作精神和服务精神的集中体现,是个体利益和整体利益的高度统一。为进
详细>>一年一度的618电商大促进入白热化冲刺阶段,很多网友憋足劲准备在618这波大促中购买一部心仪的智能手机。在今年的618换机大潮中,酷派COOL3
详细>>世界名表一比一高仿手表精仿名表。 支持货到付款批发市场一手货源专营各大精仿品牌大厂货:C厂,VS厂,JF厂,MKS厂,KW厂,HBBv6厂,JF厂
详细>>