自己建网站备案,免费的网站空间申请,html网页源码下载,大学 两学一做专题网站相关
源码测试用例下载 https://download.csdn.net/download/he_zhidan/88430716 包括4个压缩包#xff0c;初始代码#xff0c;实现前缀和#xff0c;实现前缀积#xff0c;实现前缀异或。都是在前者的基础上修改的。 本博文是CSDN学院课程的讲义 https://edu.csdn.net/c…相关
源码测试用例下载 https://download.csdn.net/download/he_zhidan/88430716 包括4个压缩包初始代码实现前缀和实现前缀积实现前缀异或。都是在前者的基础上修改的。 本博文是CSDN学院课程的讲义 https://edu.csdn.net/course/detail/38771
前缀和前缀积、前缀异或应用的博文 C前缀和算法应用和至少为 K 的最短子数组 C算法前缀和的应用得分最高的最小轮调的原理、源码及测试用例 C算法前缀和的应用分割数组的最大值的原理、源码及测试用例 C前缀和算法应用矩形区域不超过 K 的最大数值和 C前缀和算法构造乘积矩阵
原理
长度为n的数组nums共有n1个以nums[0]开始的子数组。索引范围分别为[0,i)i取值区间[0,n]。preSum[i]记录子数组[0,i)的和。比如nums {1,2,3,4},则preSum {0,1,3,6,10}。通过preSum我们可以求任意nums的子数组和。子数组[i,j)等于子数组[0,j)减去[0,i)也就是子数组[i,j)的和等于preSum[j] – preSum[i]。如果i等于j则preSum[i]-preSum[i]和为0符合计算公式。如果i大于j则非法需要提前排除。
暴力法
时间复杂度O(n*n)。
核心代码
class CPreSum { public: //左闭右开空间 long long SumO2(int left, int r) { long long llRet 0; for (; left r; left) { llRet m_sums[left]; } return llRet; } vector m_sums; };
测试代码
template void Assert(const vector v1, const vector v2) { if (v1.size() ! v2.size()) { assert(false); return; } for (int i 0; i v1.size(); i) { assert(v1[i] v2[i]); } }
template void Assert(const T t1, const T t2) { assert(t1 t2); }
void Test1() { CPreSum preSum; preSum.m_sums { 1,2,3,4 }; vector ans { 0,1,3,6,10 }; auto res preSum.SumO2(0, 4); Assert(10LL, res); res preSum.SumO2(0, 3); Assert(6LL, res); res preSum.SumO2(0, 2); Assert(3LL, res); res preSum.SumO2(0, 1); Assert(1LL, res); res preSum.SumO2(0, 0); Assert(0LL, res); res preSum.SumO2(1, 4); Assert(9LL, res); res preSum.SumO2(1, 3); Assert(5LL, res); }
void Test2() { srand(time(nullptr)); int n rand() % 10 1; CPreSum preSum; for (int i 0; i n; i) { preSum.m_sums.emplace_back(rand() % 10000); } preSum.Init(); for (int left 0; left n; left) { for (int r left; r n; r) { long long res1 preSum.SumO1(left, r); long long res2 preSum.SumO2(left, r); assert(res1res2); } } } int main() { Test1(); Test2(); }
前缀和
时间复杂度O(n)预处理O(n)每次查询O(1)。
代码
void Init() { m_vPreSum.emplace_back(0); for (const auto n : m_nums) { m_vPreSum.emplace_back(n m_vPreSum.back()); } } long long SumO1(int left, int r) { return m_vPreSum[r] - m_vPreSum[left]; } vector m_vPreSum;
前缀乘积
只需要修改三处m_vPreSum[0]1变成*-变成除。
修改后的代码
class CPreSum { public: //左闭右开空间 long long SumO2(int left, int r) { long long llRet 1; for (; left r; left) { llRet * m_nums[left]; } return llRet; } void Init() { m_vPreSum.emplace_back(1); for (const auto n : m_nums) { m_vPreSum.emplace_back(n * m_vPreSum.back()); } } long long SumO1(int left, int r) { return m_vPreSum[r] / m_vPreSum[left]; } vector m_vPreSum; vector m_nums;
};
前缀异或
C语言异或的符合是初始0,也就是m_vPreSum.emplace_back(0)。异或的逆运算是本身所以乘除都换成。 其它
视频课程
要是你认为本篇难道较大不好入手推荐你先学习基础算法的课程我已完成部分余下部分持续更新中就在CSDN学院。 https://edu.csdn.net/course/detail/38771
C#入职培训、C入职培训等课程 https://edu.csdn.net/lecturer/6176
测试环境
操作系统win7 开发环境 VS2019 C17
相关下载
如果你想观其大略建设下载《闻缺陷则喜算法册》doc版 https://download.csdn.net/download/he_zhidan/88348653
博主想队大家说的话墨家名称的来源有所得以墨记之。闻缺陷则喜的来由早发现早修改问题成本更低程序是龙算法是睛
