{"id":418,"date":"2020-12-01T14:50:29","date_gmt":"2020-12-01T06:50:29","guid":{"rendered":"https:\/\/blog.frost-s.tk\/?p=418"},"modified":"2021-12-17T11:41:41","modified_gmt":"2021-12-17T03:41:41","slug":"leetcode-%e8%ae%b0%e5%bd%95","status":"publish","type":"post","link":"https:\/\/blog.frost-s.com\/index.php\/2020\/12\/01\/leetcode-%e8%ae%b0%e5%bd%95\/","title":{"rendered":"leetcode \u8bb0\u5f55"},"content":{"rendered":"\n

\u9898\u76ee\uff1a\uff08\u9898\u53f71622\uff09<\/p>\n\n\n\n

\u8bf7\u4f60\u5b9e\u73b0\u4e09\u4e2a API append\uff0caddAll \u548c multAll \u6765\u5b9e\u73b0\u5947\u5999\u5e8f\u5217\u3002<\/p>\n\n\n\n

\u8bf7\u5b9e\u73b0 Fancy \u7c7b \uff1a<\/p>\n\n\n\n

Fancy() \u521d\u59cb\u5316\u4e00\u4e2a\u7a7a\u5e8f\u5217\u5bf9\u8c61\u3002
void append(val) \u5c06\u6574\u6570 val \u6dfb\u52a0\u5728\u5e8f\u5217\u672b\u5c3e\u3002
void addAll(inc) \u5c06\u6240\u6709\u5e8f\u5217\u4e2d\u7684\u73b0\u6709\u6570\u503c\u90fd\u589e\u52a0 inc \u3002
void multAll(m) \u5c06\u5e8f\u5217\u4e2d\u7684\u6240\u6709\u73b0\u6709\u6570\u503c\u90fd\u4e58\u4ee5\u6574\u6570 m \u3002
int getIndex(idx) \u5f97\u5230\u4e0b\u6807\u4e3a idx \u5904\u7684\u6570\u503c\uff08\u4e0b\u6807\u4ece 0 \u5f00\u59cb\uff09\uff0c\u5e76\u5c06\u7ed3\u679c\u5bf9 109 + 7 \u53d6\u4f59\u3002\u5982\u679c\u4e0b\u6807\u5927\u4e8e\u7b49\u4e8e\u5e8f\u5217\u7684\u957f\u5ea6\uff0c\u8bf7\u8fd4\u56de -1 \u3002
 <\/p>\n\n\n\n

\u793a\u4f8b\uff1a<\/p>\n\n\n\n

\u8f93\u5165\uff1a
[\"Fancy\", \"append\", \"addAll\", \"append\", \"multAll\", \"getIndex\", \"addAll\", \"append\", \"multAll\", \"getIndex\", \"getIndex\", \"getIndex\"]
[[], [2], [3], [7], [2], [0], [3], [10], [2], [0], [1], [2]]
\u8f93\u51fa\uff1a<\/p>\n\n\n\n

\n

[null, null, null, null, null, 10, null, null, null, 26, 34, 20]<\/p>\n<\/div><\/div>\n\n\n\n

\u89e3\u91ca\uff1a
Fancy fancy = new Fancy();
fancy.append(2); \/\/ \u5947\u5999\u5e8f\u5217\uff1a[2]
fancy.addAll(3); \/\/ \u5947\u5999\u5e8f\u5217\uff1a[2+3] -> [5]
fancy.append(7); \/\/ \u5947\u5999\u5e8f\u5217\uff1a[5, 7]
fancy.multAll(2); \/\/ \u5947\u5999\u5e8f\u5217\uff1a[52, 7<\/em>2] -> [10, 14]
fancy.getIndex(0); \/\/ \u8fd4\u56de 10
fancy.addAll(3); \/\/ \u5947\u5999\u5e8f\u5217\uff1a[10+3, 14+3] -> [13, 17]
fancy.append(10); \/\/ \u5947\u5999\u5e8f\u5217\uff1a[13, 17, 10]
fancy.multAll(2); \/\/ \u5947\u5999\u5e8f\u5217\uff1a[132, 17<\/em>2, 10*2] -> [26, 34, 20]
fancy.getIndex(0); \/\/ \u8fd4\u56de 26
fancy.getIndex(1); \/\/ \u8fd4\u56de 34
fancy.getIndex(2); \/\/ \u8fd4\u56de 20
 <\/p>\n\n\n\n

\u63d0\u793a\uff1a<\/p>\n\n\n\n

1 <= val, inc, m <= 100
0 <= idx <= 105
\u603b\u5171\u6700\u591a\u4f1a\u6709 105 \u6b21\u5bf9 append\uff0caddAll\uff0cmultAll \u548c getIndex \u7684\u8c03\u7528\u3002<\/p>\n\n\n\n

\u9898\u89e3\uff1a<\/p>\n\n\n\n

class Fancy {\n\n    private final long MOD = (long) 1e9 + 7;\n\n    private long mul, add;\n\n    private List nums;\n\n    private List addList, mulList;\n\n    public Fancy() {\n        nums = new ArrayList<>();\n        addList = new ArrayList<>();\n        mulList = new ArrayList<>();\n        mul = 1;\n        add = 0;\n    }\n\n    public void append(int val) {\n        nums.add(val);\n        addList.add(add);\n        mulList.add(mul);\n    }\n\n    public void addAll(int inc) {\n        add = (add + inc) % MOD;\n    }\n\n    public void multAll(int m) {\n        add = (add * m) % MOD;\n        mul = (mul * m) % MOD;\n    }\n\n    public int getIndex(int idx) {\n        if (idx >= nums.size()) return -1;\n        long ans = nums.get(idx);\n        long q = qpow(mulList.get(idx), MOD - 2L);\n        ans = ans * mul % MOD;\n        ans = ans * q % MOD;\n        ans = (ans + add) % MOD;\n        ans = (ans - addList.get(idx) * mul % MOD * q % MOD + MOD) % MOD;\n        return (int) ans;\n    }\n\n    private long qpow(long a, long p) {\n        long ans = 1;\n        while (p > 0) {\n            if ((p & 1) > 0) ans = ans * a % MOD;\n            a = a * a % MOD;\n            p >>= 1;\n        }\n        return ans;\n    }\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
\u9898\u76ee\uff1a\uff08\u9898\u53f71622\uff09 \u8bf7\u4f60\u5b9e\u73b0\u4e09\u4e2a API append\uff0caddAll \u548c multAl […]<\/p>\n","protected":false},"author":1,"featured_media":304,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[10],"tags":[],"_links":{"self":[{"href":"https:\/\/blog.frost-s.com\/index.php\/wp-json\/wp\/v2\/posts\/418"}],"collection":[{"href":"https:\/\/blog.frost-s.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.frost-s.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.frost-s.com\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.frost-s.com\/index.php\/wp-json\/wp\/v2\/comments?post=418"}],"version-history":[{"count":3,"href":"https:\/\/blog.frost-s.com\/index.php\/wp-json\/wp\/v2\/posts\/418\/revisions"}],"predecessor-version":[{"id":842,"href":"https:\/\/blog.frost-s.com\/index.php\/wp-json\/wp\/v2\/posts\/418\/revisions\/842"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/blog.frost-s.com\/index.php\/wp-json\/wp\/v2\/media\/304"}],"wp:attachment":[{"href":"https:\/\/blog.frost-s.com\/index.php\/wp-json\/wp\/v2\/media?parent=418"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.frost-s.com\/index.php\/wp-json\/wp\/v2\/categories?post=418"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.frost-s.com\/index.php\/wp-json\/wp\/v2\/tags?post=418"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}