網(wǎng)頁界面設(shè)計的構(gòu)成要素電商seo是什么意思啊
相關(guān)
源碼測試用例下載
https://download.csdn.net/download/he_zhidan/88430716 包括4個壓縮包,初始代碼,實現(xiàn)前綴和,實現(xiàn)前綴積,實現(xiàn)前綴異或。都是在前者的基礎(chǔ)上修改的。
本博文是CSDN學院課程的講義
https://edu.csdn.net/course/detail/38771
前綴和(前綴積、前綴異或)應(yīng)用的博文
C++前綴和算法:構(gòu)造乘積矩陣
原理
長度為n的數(shù)組nums,共有n+1個以nums[0]開始的子數(shù)組。索引范圍分別為[0,i),i取值區(qū)間[0,n]。preSum[i]記錄子數(shù)組[0,i)的和。比如:nums = {1,2,3,4},則preSum = {0,1,3,6,10}。通過preSum,我們可以求任意nums的子數(shù)組和。子數(shù)組[i,j)等于子數(shù)組[0,j)減去[0,i),也就是子數(shù)組[i,j)的和等于preSum[j] – preSum[i]。如果i等于j,則preSum[i]-preSum[i],和為0,符合計算公式。如果i大于j,則非法,需要提前排除。
暴力法
時間復(fù)雜度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(res1==res2);
}
}
}
int main()
{
Test1();
Test2();
}
前綴和
時間復(fù)雜度O(n),預(yù)處理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)。異或的逆運算是本身,所以乘除都換成。
其它
視頻課程
要是你認為本篇難道較大,不好入手,推薦你先學習基礎(chǔ)算法的課程,我已完成部分,余下部分持續(xù)更新中,就在CSDN學院。
https://edu.csdn.net/course/detail/38771
C#入職培訓、C++入職培訓等課程
https://edu.csdn.net/lecturer/6176
測試環(huán)境
操作系統(tǒng):win7 開發(fā)環(huán)境: VS2019 C++17
相關(guān)下載
如果你想觀其大略,建設(shè)下載《聞缺陷則喜算法冊》doc版
https://download.csdn.net/download/he_zhidan/88348653
博主想隊大家說的話 |
---|
墨家名稱的來源:有所得以墨記之。 |
聞缺陷則喜的來由:早發(fā)現(xiàn),早修改問題,成本更低 |
程序是龍,算法是睛 |