前两天刷leetcode的时候,突发奇想,leetcode中最难的一道题是什么样子的呢?

于是,我就将所有题目(https://leetcode-cn.com/problemset/all/ )按照通过率排了个序(中英文网站题目不同),找到了它(截止到目前

2021年4月5日,它的通过率依然是最低的):

经过努力+作弊,我终于完成了leetcode通过率最低的一道题-LMLPHP

题目描述如下:

具体描述,请参考: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;
    }
}

执行一下...

然后,报错了...

经过努力+作弊,我终于完成了leetcode通过率最低的一道题-LMLPHP

得到的结果居然有负值?肯定是溢出了,再次调整代码,计算的时候,将运算数与结果设置为 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);
    }
}

再次运行,嗯,很好,不报错了,但是...超时了:

经过努力+作弊,我终于完成了leetcode通过率最低的一道题-LMLPHP

这,还能怎么办?经过一晚上的思考,也没有得到一个完美的答案,怎么办?第二天,突然有了新想法,既然每次调用 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);
}

运行,然后,就通过了:

经过努力+作弊,我终于完成了leetcode通过率最低的一道题-LMLPHP

终于通过了,终于可以看答案了,又涨知识,原来这个是有算法上的解决方法的,也贴到下面吧:

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)
// 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

至于具体的说明,就请移步leetcode查看吧经过努力+作弊,我终于完成了leetcode通过率最低的一道题-LMLPHP

经过努力+作弊,我终于完成了leetcode通过率最低的一道题-LMLPHP

04-05 13:11