leetcode 记录

题目:(题号1622)

请你实现三个 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 。
 

示例:

输入:
["Fancy", "append", "addAll", "append", "multAll", "getIndex", "addAll", "append", "multAll", "getIndex", "getIndex", "getIndex"]
[[], [2], [3], [7], [2], [0], [3], [10], [2], [0], [1], [2]]
输出:

[null, null, null, null, null, 10, null, null, null, 26, 34, 20]

解释:
Fancy fancy = new Fancy();
fancy.append(2); // 奇妙序列:[2]
fancy.addAll(3); // 奇妙序列:[2+3] -> [5]
fancy.append(7); // 奇妙序列:[5, 7]
fancy.multAll(2); // 奇妙序列:[52, 72] -> [10, 14]
fancy.getIndex(0); // 返回 10
fancy.addAll(3); // 奇妙序列:[10+3, 14+3] -> [13, 17]
fancy.append(10); // 奇妙序列:[13, 17, 10]
fancy.multAll(2); // 奇妙序列:[132, 172, 10*2] -> [26, 34, 20]
fancy.getIndex(0); // 返回 26
fancy.getIndex(1); // 返回 34
fancy.getIndex(2); // 返回 20
 

提示:

1 <= val, inc, m <= 100
0 <= idx <= 105
总共最多会有 105 次对 append,addAll,multAll 和 getIndex 的调用。

题解:

class Fancy {

    private final long MOD = (long) 1e9 + 7;

    private long mul, add;

    private List nums;

    private List addList, mulList;

    public Fancy() {
        nums = new ArrayList<>();
        addList = new ArrayList<>();
        mulList = new ArrayList<>();
        mul = 1;
        add = 0;
    }

    public void append(int val) {
        nums.add(val);
        addList.add(add);
        mulList.add(mul);
    }

    public void addAll(int inc) {
        add = (add + inc) % MOD;
    }

    public void multAll(int m) {
        add = (add * m) % MOD;
        mul = (mul * m) % MOD;
    }

    public int getIndex(int idx) {
        if (idx >= nums.size()) return -1;
        long ans = nums.get(idx);
        long q = qpow(mulList.get(idx), MOD - 2L);
        ans = ans * mul % MOD;
        ans = ans * q % MOD;
        ans = (ans + add) % MOD;
        ans = (ans - addList.get(idx) * mul % MOD * q % MOD + MOD) % MOD;
        return (int) ans;
    }

    private long qpow(long a, long p) {
        long ans = 1;
        while (p > 0) {
            if ((p & 1) > 0) ans = ans * a % MOD;
            a = a * a % MOD;
            p >>= 1;
        }
        return ans;
    }
}
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇