怎么建设个人网站,苏州网站制作及推广,大唐网站建设,做费网站本文涉及的基础知识点
C算法#xff1a;前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频
作者推荐
动态规划LeetCode2552#xff1a;优化了6版的1324模式
题目
给你一个整数数组 nums #xff0c;请你返回所有下标对 0 i, j nums.length 的 …本文涉及的基础知识点
C算法前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频
作者推荐
动态规划LeetCode2552优化了6版的1324模式
题目
给你一个整数数组 nums 请你返回所有下标对 0 i, j nums.length 的 floor(nums[i] / nums[j]) 结果之和。由于答案可能会很大请你返回答案对109 7 取余 的结果。 函数 floor() 返回输入数字的整数部分。 示例 1 输入nums [2,5,9] 输出10 解释 floor(2 / 5) floor(2 / 9) floor(5 / 9) 0 floor(2 / 2) floor(5 / 5) floor(9 / 9) 1 floor(5 / 2) 2 floor(9 / 2) 4 floor(9 / 5) 1 我们计算每一个数对商向下取整的结果并求和得到 10 。 示例 2 输入nums [7,7,7,7,7,7,7] 输出49 参数范围 1 nums.length 105 1 nums[i] 105
分析
时间复杂度
O(nsqrt(n))。两层循环第一层枚举商第二层枚举除数。当商为1时第二层循环n次。当商为2时第二层循环n/2次。当商为3时第三层循环n/3… 。故总的时间复杂度为n n/2 n/3… 为O(nsqrt(n))。
原理
已知商i除数j被出数的范围是[i*j,(i1)*j) 左闭右开
代码
复用代码
template class C1097Int { public: C1097Int(long long llData 0) :m_iData(llData% MOD) { } C1097Int operator(const C1097Int o)const { return C1097Int(((long long)m_iData o.m_iData) % MOD); } C1097Int operator(const C1097Int o) { m_iData ((long long)m_iData o.m_iData) % MOD; return this; } C1097Int operator-(const C1097Int o) { m_iData (m_iData MOD - o.m_iData) % MOD; return this; } C1097Int operator-(const C1097Int o) { return C1097Int((m_iData MOD - o.m_iData) % MOD); } C1097Int operator(const C1097Int o)const { return((long long)m_iData * o.m_iData) % MOD; } C1097Int operator(const C1097Int o) { m_iData ((long long)m_iData * o.m_iData) % MOD; return *this; } bool operator(const C1097Int o)const { return m_iData o.m_iData; } C1097Int pow(long long n)const { C1097Int iRet 1, iCur *this; while (n) { if (n 1) { iRet * iCur; } iCur * iCur; n 1; } return iRet; } C1097Int PowNegative1()const { return pow(MOD - 2); } int ToInt()const { return m_iData; } private: int m_iData 0;; };
核心代码
class Solution { public: int sumOfFlooredPairs(vector nums) { const int iMax std::max_element(nums.begin(), nums.end()); vector vCount(iMax 1); for (const auto n : nums) { vCount[n]; } vector vPreSum { 0 };//vPreSum[i]记录值为[0,i)的数量 for (int i 0; i iMax; i) { vPreSum.emplace_back(vPreSum.back() vCount[i]); } C1097Int iiRet; for (int i 1; i iMax; i) {//商 for (int j 1; j * i iMax; j) {//除数 const long long llCount vPreSum[min((i 1) * j,iMax1)] - vPreSum[i * j]; iiRet C1097Int(i * llCountvCount[j]); } } return iiRet.ToInt(); } };
测试用例
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); }
int main() { vector nums; int res; { nums {2, 5, 9}; Solution slu; auto res slu.sumOfFlooredPairs(nums); Assert(10, res); } { nums { 7, 7, 7, 7, 7, 7, 7 }; Solution slu; auto res slu.sumOfFlooredPairs(nums); Assert(49, res); } //CConsole::Out(res); }
性能优化
先枚举除数再枚举商。如果除数的数量为0直接忽略。速度会有提升。
class Solution {
public:int sumOfFlooredPairs(vectorint nums) {const int iMax *std::max_element(nums.begin(), nums.end());vectorint vCount(iMax 1);for (const auto n : nums){vCount[n];}vectorint vPreSum { 0 };//vPreSum[i]记录值为[0,i)的数量for (int i 0; i iMax; i){vPreSum.emplace_back(vPreSum.back() vCount[i]);}C1097Int iiRet;for (int j 1; j iMax; j){//除数if (0 vCount[j]){continue;}for (int i 1; j * i iMax; i){//商 const long long llCount vPreSum[min((i 1) * j, iMax 1)] - vPreSum[i * j];iiRet C1097Int(i * llCount * vCount[j]);}}return iiRet.ToInt();}
};扩展阅读
视频课程
有效学习明确的目标 及时的反馈 拉伸区难度合适可以先学简单的课程请移步CSDN学院听白银讲师也就是鄙人的讲解。 https://edu.csdn.net/course/detail/38771
如何你想快
速形成战斗了为老板分忧请学习C#入职培训、C入职培训等课程 https://edu.csdn.net/lecturer/6176
相关下载
想高屋建瓴的学习算法请下载《喜缺全书算法册》doc版 https://download.csdn.net/download/he_zhidan/88348653
我想对大家说的话闻缺陷则喜是一个美好的愿望早发现问题早修改问题给老板节约钱。子墨子言之事无终始无务多业。也就是我们常说的专业的人做专业的事。如果程序是一条龙那算法就是他的是睛
测试环境
操作系统win7 开发环境 VS2019 C17 或者 操作系统win10 开发环境
VS2022 C17
