请你实现三个 API append,addAll 和 multAll 来实现奇妙序列。 请实现 Fancy 类 : Fancy() 初始化一个空序列对象。 void…
- User
请你实现三个 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, 7 2] -> [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, 17 2, 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 的调用。
使用C语言进行编写,我需要你再分析完上面的题目后,使用下面的初始框架进行题解,并且优化到最优解
typedef struct {
} Fancy;
Fancy* fancyCreate() {
}
void fancyAppend(Fancy* obj, int val) {
}
void fancyAddAll(Fancy* obj, int inc) {
}
void fancyMultAll(Fancy* obj, int m) {
}
int fancyGetIndex(Fancy* obj, int idx) {
}
void fancyFree(Fancy* obj) {
}
/**
Your Fancy struct will be instantiated and called as such: Fancy* obj = fancyCreate(); fancyAppend(obj, val); fancyAddAll(obj, inc); fancyMultAll(obj, m); int param_4 = fancyGetIndex(obj, idx); fancyFree(obj); */
- Assistant
实现这个问题需要维护一个“奇妙序列”,支持在序列末尾添加元素,以及对整个序列进行加法和乘法操作,最后能够在 O(1) 时间内获取序列中某个索引的元素。
为此,我们可以利用线性函数的特性来处理序列中的操作。每个元素都会受到一系列的加法和乘法操作,我们可以将这些操作合并为一个线性函数,对每个元素而言,其新值可以表示为:
new_value = old_value * total_multiplication + total_addition为了在 O(1) 时间内获取某个索引处的元素,我们需要在添加元素时记录当时的乘法和加法累计值(
cm[idx]和ca[idx]),以及当前全局的乘法和加法累计值(cm_now和ca_now)。当我们需要获取元素时,我们可以根据以下公式计算出元素的实际值:
value = val[idx] * (cm_now * modInverse(cm[idx], MOD) % MOD) % MOD + (ca_now - ca[idx] * (cm_now * modInverse(cm[idx], MOD) % MOD) % MOD + MOD) % MOD以下是完整的 C 语言代码:
#include <stdio.h> #include <stdlib.h> #define MAX_SIZE 100005 #define MOD 1000000007 typedef struct { long long *val; long long *cm; long long *ca; long long cm_now; long long ca_now; int size; } Fancy; long long modPow(long long base, long long exp, int mod) { long long result = 1; base %= mod; while (exp > 0) { if (exp % 2 == 1) result = result * base % mod; base = base * base % mod; exp /= 2; } return result; } long long modInverse(long long a, int mod) { return modPow(a, mod - 2, mod); } Fancy* fancyCreate() { Fancy* obj = (Fancy*)malloc(sizeof(Fancy)); obj->val = (long long*)malloc(sizeof(long long) * MAX_SIZE); obj->cm = (long long*)malloc(sizeof(long long) * MAX_SIZE); obj->ca = (long long*)malloc(sizeof(long long) * MAX_SIZE); obj->cm_now = 1; obj->ca_now = 0; obj->size = 0; return obj; } void fancyAppend(Fancy* obj, int val) { obj->val[obj->size] = val; obj->cm[obj->size] = obj->cm_now; obj->ca[obj->size] = obj->ca_now; obj->size++; } void fancyAddAll(Fancy* obj, int inc) { obj->ca_now = (obj->ca_now + inc) % MOD; } void fancyMultAll(Fancy* obj, int m) { obj->cm_now = (obj->cm_now * m) % MOD; obj->ca_now = (obj->ca_now * m) % MOD; } int fancyGetIndex(Fancy* obj, int idx) { if (idx >= obj->size) return -1; long long val = obj->val[idx]; long long cm_idx = obj->cm[idx]; long long ca_idx = obj->ca[idx]; long long inv_cm_idx = modInverse(cm_idx, MOD); long long cm_diff = (obj->cm_now * inv_cm_idx) % MOD; long long ca_diff = (obj->ca_now - (ca_idx * cm_diff % MOD) + MOD) % MOD; long long result = (val * cm_diff % MOD + ca_diff) % MOD; return (int)result; } void fancyFree(Fancy* obj) { if (obj) { if (obj->val) free(obj->val); if (obj->cm) free(obj->cm); if (obj->ca) free(obj->ca); free(obj); } } /** Your Fancy struct will be instantiated and called as such: Fancy* obj = fancyCreate(); fancyAppend(obj, val); fancyAddAll(obj, inc); fancyMultAll(obj, m); int param_4 = fancyGetIndex(obj, idx); fancyFree(obj); */这段代码首先定义了必要的辅助函数
modPow和modInverse来计算模的乘方和模的逆。然后,我们在Fancy结构体中维护了需要的数组和变量。在
fancyAppend函数中,我们将新的值以及当时的cm_now和ca_now记录下来。在fancyAddAll和fancyMultAll函数中,我们更新全局的乘法和加法累计值。最后,在
fancyGetIndex函数中,我们根据前面提到的公式计算出指定索引处的元素的实际值,并返回。这个实现方法能够确保每个操作都是 O(1) 的时间复杂度,满足了题目的要求。
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.