前两天刷leetcode的时候，突发奇想，leetcode中最难的一道题是什么样子的呢？
于是，我就将所有题目（https://leetcode-cn.com/problemset/all/ ）按照通过率排了个序（中英文网站题目不同），找到了它（截止到目前
2021年4月5日，它的通过率依然是最低的）：
image.png
题目描述如下：
请你实现三个 API append，addAll 和 multAll 来实现奇妙序列。
请实现 Fancy 类 ：
- Fancy() 初始化一个空序列对象。
- void append(val) 将整数 val 添加在序列末尾。
- void addAll(inc) 将所有序列中的现有数值都增加 inc 。
- void multAll(m) 将序列中的所有现有数值都乘以整数 m 。
- int getIndex(idx) 得到下标为 idx 处的数值（下标从 0 开始），并将结果对 109 + 7 取余。
- 如果下标大于等于序列的长度，请返回 -1 。
力扣（LeetCode）
具体描述，请参考：https://leetcode-cn.com/problems/fancy-sequence/
这里，我们从题目给定的模板开始：
public class Fancy {
public Fancy() {
}
public void Append(int val) {
}
public void AddAll(int inc) {
}
public void MultAll(int m) {
}
public int GetIndex(int idx) {
}
}
/**
* Your Fancy object will be instantiated and called as such:
* Fancy obj = new Fancy();
* obj.Append(val);
* obj.AddAll(inc);
* obj.MultAll(m);
* int param_4 = obj.GetIndex(idx);
*/
我们可以看到，最后的注释说明了代码的使用方法，以下再次引用代码时，我们将忽略它们。
看题目描述，需要我们提供一个类似于链表/数组的功能，可以向集合末尾添加一个整数，可以对集合中所有元素执行加上一个属或乘上一个数的操作，最后还能通过索引获取到对应索引处的值。
嗯。。。
听起来不是很难嘛，代码改成下面试试？
public class Fancy {
private List<int> list = new List<int>();
public Fancy() {
}
public void Append(int val) {
list.Add(val);
}
public void AddAll(int inc) {
int cnt = this.list.Count;
for(int i = 0; i < cnt; i++) {
this.list[i] += inc;
}
}
public void MultAll(int m) {
int cnt = this.list.Count;
for(int i = 0; i < cnt; i++) {
this.list[i] *= m;
}
}
public int GetIndex(int idx) {
if(idx < 0 || idx >= this.list.Count) {
return -1;
}
return this.list[idx] % 1000000007;
}
}
执行一下...
然后，报错了...
image.png
得到的结果居然有负值？肯定是溢出了，再次调整代码，计算的时候，将运算数与结果设置为 long，改成如下形式：
public class Fancy {
private List<int> list = new List<int>();
public Fancy() {
}
public void Append(int val) {
list.Add(val);
}
public void AddAll(int inc) {
int cnt = this.list.Count;
for(int i = 0; i < cnt; i++) {
long val = this.list[i] + (long)inc;
this.list[i] = (int)(val % 1000000007);
}
}
public void MultAll(int m) {
int cnt = this.list.Count;
for(int i = 0; i < cnt; i++) {
long val = this.list[i] * (long)m;
this.list[i] = (int)(val % 1000000007);
}
}
public int GetIndex(int idx) {
if(idx < 0 || idx >= this.list.Count) {
return -1;
}
return (this.list[idx] % 1000000007);
}
}
再次运行，嗯，很好，不报错了，但是...超时了：
image.png
这，还能怎么办？经过一晚上的思考，也没有得到一个完美的答案，怎么办？第二天，突然有了新想法，既然每次调用 AddAll 或者 MultAll 的时候，都要计算所有元素，性能瓶颈会不会在这里？
是不是只有在 GetIndex 的时候再计算可以避免执行不必要的计算？但，怎么做呢？咱有闭包啊，只要记录所有的AddAll, MultAll 的调用，并使用闭包记录其参数，这样就可以只在调用 AddAll 或 MultAll 的时候创建闭包就好了。
于是，代码就变成了下面这个样子：
public class Fancy
{
private List<Entry> list = new List<Entry>();
private List<Func<int, int>> funcs = new List<Func<int, int>>();
public Fancy() { }
public void Append(int val)
{
// 在这里，我们只要将节点直接添加到
// 数据列表中即可。
// 由于在本节点添加之前的所有AddAll/MultAll
// 调用，均不应该计算，所以这里我们将需要调用
// 的索引指向调用函数列表最后一个元素的后面。
this.list.Add(new Entry
{
Val = val,
StartIndex = funcs.Count
});
}
public void AddAll(int inc)
{
// 由于可能在调用Append之前调用本方法，
// 但是由于此时列表中没有任何元素，所以
// 应忽略调用。
if (this.list.Count <= 0)
{
return;
}
// 这里并不执行计算操作，只是创建了一个
// 闭包，并将其添加到函数列表中。
this.funcs.Add(val =>
{
long v = val + (long)inc;
return (int)(v % 1000000007);
});
}
public void MultAll(int m)
{
// 由于可能在调用Append之前调用本方法，
// 但是由于此时列表中没有任何元素，所以
// 应忽略调用。
if (this.list.Count <= 0)
{
return;
}
// 这里并不执行计算操作，只是创建了一个
// 闭包，并将其添加到函数列表中。
this.funcs.Add(val =>
{
long v = val * (long)m;
return (int)(v % 1000000007);
});
}
public int GetIndex(int idx)
{
// 如果没有任何元素，直接返回 -1。
if (idx < 0 || idx >= this.list.Count)
{
return -1;
}
// 这里，我们获取到了要找的目标节点，但是由于
// 节点保存的值为计算之前的值，所以这里需要从
// StartIndex 索引处开始计算值，并获取到结果。
Entry entry = this.list[idx];
int val = entry.Val;
int cnt = this.funcs.Count;
for (int i = entry.StartIndex; i < cnt; i++)
{
val = this.funcs[i](val);
}
return val;
}
private struct Entry
{
public int Val { get; set; }
public int StartIndex { get; set; }
}
}
努力了这么久，再执行一下试试：
没天理啊，还是超时...
但题目还是要做的，继续修改代码，我们这里虽然进行了延迟求值，但是终归每次 GetIndex 都要计算的，能不能减少这里的运算呢？
于是，每次计算之后，我都更新了StartIndex值，代码改成了这样：
public class Fancy
{
private List<Entry> list = new List<Entry>(10000);
private List<Func<long, long>> funcs =
new List<Func<long, long>>(10000);
public Fancy() { }
public void Append(int val)
{
this.list.Add(new Entry
{
Value = val,
LastIndex = funcs.Count
});
}
public void AddAll(int inc)
{
if (this.list.Count <= 0)
{
return;
}
this.funcs.Add(val =>
{
long v = val + inc;
if (v > 1000000007)
{
return v % 1000000007;
}
return v;
});
}
public void MultAll(int m)
{
if (this.list.Count <= 0)
{
return;
}
this.funcs.Add(val =>
{
long v = val * m;
if (v > 1000000007)
{
return v % 1000000007;
}
return v;
});
}
public int GetIndex(int idx)
{
if (idx >= this.list.Count || idx < 0)
{
return -1;
}
Entry entry = this.list[idx];
// 这里我们判断最后执行函数的索引，如果已经
// 执行了所有要执行的函数，那么 entry.Value
// 存放的就是目标值，直接返回。
if (entry.LastIndex >= this.funcs.Count)
{
return entry.Value;
}
// 如果需要计算，就执行所有计算，然后返回最后计算的值。
long val = entry.Value;
for (int i = entry.LastIndex; i < funcs.Count; i++)
{
val = funcs[i](val);
}
entry.LastIndex = funcs.Count;
entry.Value = (int)val;
return entry.Value;
}
private struct Entry
{
public int Value { get; set; }
public int LastIndex { get; set; }
}
}
经过多次修改，满怀希望的再次运行，但是结果再次让我失望，再一次的超时了。
真是让人绝望...
好在，我想到了一个作弊的方法，把代码从C#改成了C语言...
typedef long (*fun)(long, long);
typedef struct {
int size;
int funSize;
int indexes[100000];
int vals[100000];
fun funcs[100000];
int ps[100000];
} Fancy;
Fancy* fancyCreate() {
Fancy* fancy = (Fancy*)malloc(sizeof(Fancy));
if (fancy) {
memset(fancy, 0, sizeof(Fancy));
}
return fancy;
}
void fancyAppend(Fancy* obj, int val) {
obj->vals[obj->size] = val;
obj->indexes[obj->size] = obj->funSize;
obj->size++;
}
long add(long val, long inc) {
val += inc;
if (val < 1000000007) {
return val;
}
return val % 1000000007;
}
long mult(long val, long m) {
val *= m;
if (val < 1000000007) {
return val;
}
return val % 1000000007;
}
void fancyAddAll(Fancy* obj, int inc) {
obj->funcs[obj->funSize] = add;
obj->ps[obj->funSize] = inc;
obj->funSize++;
}
void fancyMultAll(Fancy* obj, int m) {
obj->funcs[obj->funSize] = mult;
obj->ps[obj->funSize] = m;
obj->funSize++;
}
int fancyGetIndex(Fancy* obj, int idx) {
if (idx >= obj->size) {
return -1;
}
int last = obj->indexes[idx];
long val = obj->vals[idx];
if (last >= obj->funSize) {
return (int)val;
}
while (last < obj->funSize) {
val = obj->funcs[last](val, obj->ps[last]);
last++;
}
obj->vals[idx] = val;
obj->indexes[idx] = obj->funSize;
return (int)val;
}
void fancyFree(Fancy* obj) {
free(obj);
}
运行，然后，就通过了：
image.png
终于通过了，终于可以看答案了，又涨知识，原来这个是有算法上的解决方法的，也贴到下面吧：
class Fancy {
private:
static constexpr int mod = 1000000007;
vector<int> v, a, b;
public:
Fancy() {
a.push_back(1);
b.push_back(0);
}
// 快速幂
int quickmul(int x, int y) {
int ret = 1;
int cur = x;
while (y) {
if (y & 1) {
ret = (long long)ret * cur % mod;
}
cur = (long long)cur * cur % mod;
y >>= 1;
}
return ret;
}
// 乘法逆元
int inv(int x) {
return quickmul(x, mod - 2);
}
void append(int val) {
v.push_back(val);
a.push_back(a.back());
b.push_back(b.back());
}
void addAll(int inc) {
b.back() = (b.back() + inc) % mod;
}
void multAll(int m) {
a.back() = (long long)a.back() * m % mod;
b.back() = (long long)b.back() * m % mod;
}
int getIndex(int idx) {
if (idx >= v.size()) {
return -1;
}
int ao = (long long)inv(a[idx]) * a.back() % mod;
int bo = (b.back() - (long long)b[idx] * ao % mod + mod) % mod;
int ans = ((long long)ao * v[idx] % mod + bo) % mod;
return ans;
}
};
// 作者：zerotrac2
// 链接：https://leetcode-cn.com/problems/fancy-sequence/solution/qi-miao-xu-lie-by-zerotrac2/
// 来源：力扣（LeetCode）
// 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
image.png
