當前位置：首頁 > news >正文

類似WordPress的Pythonseo網(wǎng)站優(yōu)化工具大全

news 2025/7/4 9:33:53

類似WordPress的Python,seo網(wǎng)站優(yōu)化工具大全,網(wǎng)絡書城網(wǎng)站開發(fā) 需求分析,中山企業(yè)網(wǎng)站多少錢作者推薦 map|動態(tài)規(guī)劃|單調棧|LeetCode975:奇偶跳涉及知識點單調棧 C算法：前綴和、前綴乘積、前綴異或的原理、源碼及測試用例包括課程視頻題目作為國王的統(tǒng)治者，你有一支巫師軍隊聽你指揮。給你一個下標從 0 開始的整數(shù)數(shù)組 strength &…

作者推薦

map|動態(tài)規(guī)劃|單調棧|LeetCode975:奇偶跳

涉及知識點

單調棧
C++算法：前綴和、前綴乘積、前綴異或的原理、源碼及測試用例包括課程視頻

題目

作為國王的統(tǒng)治者，你有一支巫師軍隊聽你指揮。
給你一個下標從 0 開始的整數(shù)數(shù)組 strength ，其中 strength[i] 表示第 i 位巫師的力量值。對于連續(xù)的一組巫師（也就是這些巫師的力量值是 strength 的子數(shù)組），總力量定義為以下兩個值的乘積：
巫師中最弱的能力值。
組中所有巫師的個人力量值之和。
請你返回所有巫師組的總力量之和。由于答案可能很大，請將答案對 109 + 7 取余后返回。
子數(shù)組是一個數(shù)組里非空連續(xù)子序列。
示例 1：
輸入：strength = [1,3,1,2]
輸出：44
解釋：以下是所有連續(xù)巫師組：

[1,3,1,2] 中 [1] ，總力量值為 min([1]) * sum([1]) = 1 * 1 = 1
[1,3,1,2] 中 [3] ，總力量值為 min([3]) * sum([3]) = 3 * 3 = 9
[1,3,1,2] 中 [1] ，總力量值為 min([1]) * sum([1]) = 1 * 1 = 1
[1,3,1,2] 中 [2] ，總力量值為 min([2]) * sum([2]) = 2 * 2 = 4
[1,3,1,2] 中 [1,3] ，總力量值為 min([1,3]) * sum([1,3]) = 1 * 4 = 4
[1,3,1,2] 中 [3,1] ，總力量值為 min([3,1]) * sum([3,1]) = 1 * 4 = 4
[1,3,1,2] 中 [1,2] ，總力量值為 min([1,2]) * sum([1,2]) = 1 * 3 = 3
[1,3,1,2] 中 [1,3,1] ，總力量值為 min([1,3,1]) * sum([1,3,1]) = 1 * 5 = 5
[1,3,1,2] 中 [3,1,2] ，總力量值為 min([3,1,2]) * sum([3,1,2]) = 1 * 6 = 6
[1,3,1,2] 中 [1,3,1,2] ，總力量值為 min([1,3,1,2]) * sum([1,3,1,2]) = 1 * 7 = 7
所有力量值之和為 1 + 9 + 1 + 4 + 4 + 4 + 3 + 5 + 6 + 7 = 44 。
示例 2：

輸入：strength = [5,4,6]
輸出：213
解釋：以下是所有連續(xù)巫師組：

[5,4,6] 中 [5] ，總力量值為 min([5]) * sum([5]) = 5 * 5 = 25
[5,4,6] 中 [4] ，總力量值為 min([4]) * sum([4]) = 4 * 4 = 16
[5,4,6] 中 [6] ，總力量值為 min([6]) * sum([6]) = 6 * 6 = 36
[5,4,6] 中 [5,4] ，總力量值為 min([5,4]) * sum([5,4]) = 4 * 9 = 36
[5,4,6] 中 [4,6] ，總力量值為 min([4,6]) * sum([4,6]) = 4 * 10 = 40
[5,4,6] 中 [5,4,6] ，總力量值為 min([5,4,6]) * sum([5,4,6]) = 4 * 15 = 60
所有力量值之和為 25 + 16 + 36 + 36 + 40 + 60 = 213 。
參數(shù)范圍：
1 <= strength.length <= 10⁵
1 <= strength[i] <= 10⁹

單調棧+兩個前綴和

時間復雜度: O(n)。

單調棧

枚舉各數(shù)組的最小值。left 是從右向左第一個小于strength[i]的下標是left，如果不存在left是-1;right是從左向右第一個小于等于strength[i]的下標，如果不存在right為m_c。
如果一個子數(shù)組strength[li,ri]的最小值是strength[i]，且strength[i]左邊沒有和它相等的值。則：
li的取值范圍是：(left,i]
ri的取值范圍是：[i,right)
我們可以這樣計算這些子數(shù)組和的和。累加strength[i]它出現(xiàn)的次數(shù)。
無論li和ri取值什么，i都在子數(shù)組中，所以i出現(xiàn)：(i-left)(right-i)次。
li為left+1時,ri無論取值什么，都包括strength[left+1]
li為left+1和left+2時，ri無論取值什么，都包括strength[left+2]
…

(left,i)中的元素分別出現(xiàn):right-i次、(right-i)*2、(right-i)*3…

(i,right)中的元素，分別出現(xiàn)：…、(i-left)*2、(i-left)次

前綴和

vPreSum[i] 記錄：strength[j]的和，j取值范圍[0,i)。
vPreSum2[i]記錄：strength[j]*(j+1)的和，j取值范圍[0,i)。

代碼

核心代碼

template<int MOD = 1000000007>
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 CRangIndex
{
public:template<class _Pr>CRangIndex(const vector<int>& nums, _Pr CurIndexCmpStackTopIndex){m_c = nums.size();m_vLeft.assign(m_c, -1);m_vRight.assign(m_c, m_c);stack<int> sta;for (int i = 0; i < m_c; i++){while (sta.size() && (CurIndexCmpStackTopIndex(i, sta.top()))){m_vRight[sta.top()] = i;sta.pop();}if (sta.size()){m_vLeft[i] = sta.top();}sta.emplace(i);}}int m_c;vector<int> m_vLeft, m_vRight;//vLeft[i] 從右向左第一個小于nums[i] ;vRight[i] 是第一個小于等于nums[i]。
};template<class T = long long >
vector<T> CreatePreSum(const vector<int>& nums)
{vector<T> preSum;preSum.push_back(0);for (int i = 0; i < nums.size(); i++){preSum.push_back (preSum[i]+ nums[i]);}return preSum;
}class Solution {
public:int totalStrength(vector<int>& strength) {CRangIndex ri(strength, [&](int i1, int i2) {return strength[i1] <= strength[i2]; });auto vPreSum = CreatePreSum<C1097Int<>>(strength);vector<C1097Int<>> vPreSum2 = { 0 };for (int i = 0 ; i < ri.m_c ;  i++ ){const auto& n = strength[i];vPreSum2.emplace_back(vPreSum2.back() + C1097Int<>(n)*(i+1));}C1097Int<> biRet = 0;for (int i = 0; i < ri.m_c; i++){const int left = ri.m_vLeft[i];const int right = ri.m_vRight[i];const int leftLen = i - left;//左邊界的可選范圍(left,i]const int rightLen = right - i;//右邊界的可選范圍[i,right)//計算(left,i)的巫師和C1097Int<> leftTotal = vPreSum2[i] - vPreSum2[left + 1] - (vPreSum[i] - vPreSum[left + 1]) * (left+1);//計算(i,right)的巫師和C1097Int<> rightTotal = (vPreSum[right] - vPreSum[i + 1])*(right+1) - ( vPreSum2[right] - vPreSum2[i + 1] );C1097Int<> iTotal = C1097Int<>(strength[i]) * leftLen * rightLen;//計算以小標i為最弱力量的子數(shù)組C1097Int<> cur = leftTotal * rightLen + rightTotal * leftLen + iTotal;cur *= strength[i];biRet += cur;}return biRet.ToInt();}
};

測試用例

template<class T>
void Assert(const T& t1, const T& t2)
{assert(t1 == t2);
}template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{if (v1.size() != v2.size()){assert(false);return;}for (int i = 0; i < v1.size(); i++){Assert(v1[i], v2[i]);}
}int main()
{vector<int> strength;{Solution slu;strength = { 2,3,4 };auto res = slu.totalStrength(strength);Assert(78, res);}{Solution slu;strength = { 1 };auto res = slu.totalStrength(strength);Assert(1, res);}{Solution slu;strength = { 1,3 };auto res = slu.totalStrength(strength);Assert(14, res);}{Solution slu;strength = { 1, 3, 1, 2 };auto res = slu.totalStrength(strength);Assert(44, res);}{Solution slu;strength = { 5,4,6 };auto res = slu.totalStrength(strength);Assert(213, res);}{Solution slu;strength.assign(100'000, 1000'000'000);auto res = slu.totalStrength(strength);Assert(611131623, res);}//CConsole::Out(res);
}

2023年3月版

class Solution {
public:
int totalStrength(vector& strength) {
m_c = strength.size();
vector vSum1(1), vSum2(1);
for (int i = 0; i < m_c; i++)
{
vSum1.push_back(vSum1.back() + strength[i]);
vSum2.push_back(vSum2.back() + (long long)strength[i] * (i + 1));
}
vector vLeft(m_c), vRight(m_c);
{
std::vector<std::pair<int, int>> vValueIndex;
for (int i = 0; i < m_c; i++)
{
const int iLessEqualNum = std::lower_bound(vValueIndex.begin(), vValueIndex.end(), strength[i] + 1, LessPairInt) - vValueIndex.begin();
vLeft[i] = (0 == iLessEqualNum) ? -1 : vValueIndex[iLessEqualNum - 1].second;
while (vValueIndex.size() && (vValueIndex.back().first >= strength[i]))
{
vValueIndex.pop_back();
}
vValueIndex.emplace_back(strength[i], i);
}
}
{
std::vector<std::pair<int, int>> vValueIndex;
for (int i = m_c - 1; i >= 0; i–)
{
const int iLessNum = std::lower_bound(vValueIndex.begin(), vValueIndex.end(), strength[i], LessPairInt) - vValueIndex.begin();
vRight[i] = (0 == iLessNum) ? m_c : vValueIndex[iLessNum - 1].second;
while (vValueIndex.size() && (vValueIndex.back().first >= strength[i]))
{
vValueIndex.pop_back();
}
vValueIndex.emplace_back(strength[i], i);
}
}

	 C1097Int llSum = 0;for (int i = 0; i < m_c; i++){const int iLeftLeft = vLeft[i] + 1;const int iLeftRight = i - 1;const int iRightLeft = i + 1;const int iRightRight = vRight[i] - 1;const int iLeftLen = iLeftRight - iLeftLeft + 1;const int iRightLen = iRightRight - iRightLeft + 1;C1097Int llCurSun = ((long long)iLeftLen + 1)*(iRightLen + 1)*strength[i];C1097Int llLeftSum = 0, llRightSum = 0;if (iLeftLen > 0){llLeftSum = vSum2[iLeftRight + 1] - vSum2[iLeftLeft] - (vSum1[iLeftRight + 1] - vSum1[iLeftLeft])*iLeftLeft;llLeftSum *= (iRightLen + 1);}if (iRightLen > 0){llRightSum = (vSum1[iRightRight + 1] - vSum1[iRightLeft])*(iRightRight + 2) - (vSum2[iRightRight + 1] - vSum2[iRightLeft]);llRightSum *= (iLeftLen + 1);}llCurSun += llLeftSum;llCurSun += llRightSum;llSum += llCurSun*strength[i];}return llSum.ToInt();}int m_c;

};

擴展閱讀

視頻課程

有效學習：明確的目標及時的反饋拉伸區(qū)（難度合適），可以先學簡單的課程，請移步CSDN學院，聽白銀講師（也就是鄙人）的講解。
https://edu.csdn.net/course/detail/38771

如何你想快

速形成戰(zhàn)斗了，為老板分憂，請學習C#入職培訓、C++入職培訓等課程
https://edu.csdn.net/lecturer/6176

我想對大家說的話
聞缺陷則喜是一個美好的愿望，早發(fā)現(xiàn)問題，早修改問題，給老板節(jié)約錢。
子墨子言之：事無終始，無務多業(yè)。也就是我們常說的專業(yè)的人做專業(yè)的事。
如果程序是一條龍，那算法就是他的是睛