想问下 amazon oa 里面的triangle sum 那道题

来自APP · 2022-8-15 11:28:12

您需要登录才可以下载或查看附件。没有帐号？注册账号

x

力扣2221 那道题我写的是O(n^2), 想知道O(n) 的

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

ace 算O(n) 还是 O(1)?

Erikaze

https://en.wikipedia.org/wiki/Pa ... when%20a%20binomial,This%20is%20the%20binomial%20theorem.

这题本质上是数学题

匿名用户-NS5RZ *2022-8-16 01:04:31* · 2022-8-16 01:04:31

On的在lc上很容易overflow，不知道亚麻的数据量是多少

GamowK

本帖最后由 GamowK 于 2022-8-14 20:49 编辑

用组合数学的方法可以O(N)。杨辉三角第N行依次乘以数组每一项再求和再模10
你把三角每一行都拆成第一行数的和的形式就懂了

SMART_BOY

lc上有数学解法是O(N). 个人认为recursion算ON。可以用迭代优化

来自APP · 2022-8-17 11:00:32

SMART_BOY 发表于 2022-08-14 20:37:49
lc上有数学解法是O(N). 个人认为recursion算ON。可以用迭代优化

recursion 要是modify array in place 也是O(n) 吗就是因为多余的stack frame 吗