中文亚洲精品无码_熟女乱子伦免费_人人超碰人人爱国产_亚洲熟妇女综合网

當(dāng)前位置： 首頁 > news >正文

網(wǎng)絡(luò)服務(wù)商英文seo優(yōu)化網(wǎng)站優(yōu)化排名

news 2025/7/8 9:39:35
網(wǎng)絡(luò)服務(wù)商英文,seo優(yōu)化網(wǎng)站優(yōu)化排名,網(wǎng)頁制作與網(wǎng)站建設(shè)實戰(zhàn)大全 視頻,網(wǎng)站建設(shè)的文檔作者推薦 map|動態(tài)規(guī)劃|單調(diào)棧|LeetCode975:奇偶跳 涉及知識點 單調(diào)棧 題目 給你一個長度為 n 的正整數(shù)數(shù)組 nums 和一個整數(shù) k 。 一開始，你的分?jǐn)?shù)為 1 。你可以進(jìn)行以下操作至多 k 次，目標(biāo)是使你的分?jǐn)?shù)最大： 選擇一個之前沒有選過的 非…

作者推薦

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

涉及知識點

單調(diào)棧

題目

給你一個長度為 n 的正整數(shù)數(shù)組 nums 和一個整數(shù) k 。
一開始，你的分?jǐn)?shù)為 1 。你可以進(jìn)行以下操作至多 k 次，目標(biāo)是使你的分?jǐn)?shù)最大：
選擇一個之前沒有選過的 非空 子數(shù)組 nums[l, …, r] 。
從 nums[l, …, r] 里面選擇一個 質(zhì)數(shù)分?jǐn)?shù) 最高的元素 x 。如果多個元素質(zhì)數(shù)分?jǐn)?shù)相同且最高，選擇下標(biāo)最小的一個。
將你的分?jǐn)?shù)乘以 x 。
nums[l, …, r] 表示 nums 中起始下標(biāo)為 l ，結(jié)束下標(biāo)為 r 的子數(shù)組，兩個端點都包含。
一個整數(shù)的 質(zhì)數(shù)分?jǐn)?shù) 等于 x 不同質(zhì)因子的數(shù)目。比方說， 300 的質(zhì)數(shù)分?jǐn)?shù)為 3 ，因為 300 = 2 * 2 * 3 * 5 * 5 。
請你返回進(jìn)行至多 k 次操作后，可以得到的 最大分?jǐn)?shù) 。
由于答案可能很大，請你將結(jié)果對 109 + 7 取余后返回。
示例 1：
輸入：nums = [8,3,9,3,8], k = 2
輸出：81
解釋：進(jìn)行以下操作可以得到分?jǐn)?shù) 81 ：

  • 選擇子數(shù)組 nums[2, …, 2] 。nums[2] 是子數(shù)組中唯一的元素。所以我們將分?jǐn)?shù)乘以 nums[2] ，分?jǐn)?shù)變?yōu)?1 * 9 = 9 。
  • 選擇子數(shù)組 nums[2, …, 3] 。nums[2] 和 nums[3] 質(zhì)數(shù)分?jǐn)?shù)都為 1 ，但是 nums[2] 下標(biāo)更小。所以我們將分?jǐn)?shù)乘以 nums[2] ，分?jǐn)?shù)變?yōu)?9 * 9 = 81 。
    81 是可以得到的最高得分。
    示例 2：
    輸入：nums = [19,12,14,6,10,18], k = 3
    輸出：4788
    解釋：進(jìn)行以下操作可以得到分?jǐn)?shù) 4788 ：
  • 選擇子數(shù)組 nums[0, …, 0] 。nums[0] 是子數(shù)組中唯一的元素。所以我們將分?jǐn)?shù)乘以 nums[0] ，分?jǐn)?shù)變?yōu)?1 * 19 = 19 。
  • 選擇子數(shù)組 nums[5, …, 5] 。nums[5] 是子數(shù)組中唯一的元素。所以我們將分?jǐn)?shù)乘以 nums[5] ，分?jǐn)?shù)變?yōu)?19 * 18 = 342 。
  • 選擇子數(shù)組 nums[2, …, 3] 。nums[2] 和 nums[3] 質(zhì)數(shù)分?jǐn)?shù)都為 2，但是 nums[2] 下標(biāo)更小。所以我們將分?jǐn)?shù)乘以 nums[2] ，分?jǐn)?shù)變?yōu)?342 * 14 = 4788 。
    4788 是可以得到的最高的分。
    參數(shù)范圍：
    1 <= nums.length == n <= 105
    1 <= nums[i] <= 105
    1 <= k <= min(n * (n + 1) / 2, 109)

單調(diào)棧

時間復(fù)雜度😮(nlogn)
靜態(tài)變量vPrime 記錄所有質(zhì)數(shù)。
vPriCount 記錄nums各數(shù)的質(zhì)量分?jǐn)?shù)。vPriCount也可以弄成靜態(tài)成員變量。
我們枚舉各子數(shù)組的最大質(zhì)量分?jǐn)?shù)，如果有多個最大質(zhì)量分?jǐn)?shù)，取下標(biāo)最小的。即：
left為從右向左第一個大于等于vPriCount[i]的下標(biāo)，不存在為-1。
right為從左向右第一個大于vPriCount[i]的下標(biāo)，不存在為m_c。
子數(shù)組(li,ri)就是符合條件的子數(shù)組，li取值范圍(left,i]，ri取值范圍[i,right)。
我們按的nums[i]降序操作 最大質(zhì)量分?jǐn)?shù)為vPriCount[i]的子數(shù)組。

代碼

核心代碼

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]。
};vector<int> CreatePrime(int iMax)
{vector<int> vPrime = { 2 };for (int i = 3; i <= iMax; i++){bool b = true;for (const auto& n : vPrime){if (0 == i % n){b = false;break;}}if (b){vPrime.emplace_back(i);}}return vPrime;
}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 Solution {
public:int maximumScore(vector<int>& nums, int k) {m_c = nums.size();vector<int> vPriCount;{static vector<int> vPrime = CreatePrime(1000 * 100);for (const auto& n : nums){int tmp = n;int iNum = 0;for (const auto& pr : vPrime){if (pr * pr > tmp){break;}if (0 == tmp % pr){while (0 == tmp % pr){tmp /= pr;}iNum++;}}vPriCount.emplace_back(iNum + (tmp > 1));}}CRangIndex ri(vPriCount, [&](int i1, int i2) {return vPriCount[i1] > vPriCount[i2]; });std::multimap<int, int, greater<int>> mValueIndex;for (int i = 0; i < ri.m_c; i++){mValueIndex.emplace(nums[i], i);}C1097Int<> biRet=1;for (const auto& [value, i] : mValueIndex){const long long llSubArrCount = ((long long)i - ri.m_vLeft[i]) * (ri.m_vRight[i] - i);const long long llOpeCount = min((long long)k, llSubArrCount);biRet *= C1097Int<>(value).pow(llOpeCount);k -= llOpeCount;if (0 == k){break;}}return biRet.ToInt();}int m_c;
};

測試用例

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> nums;int k;{Solution slu;nums = { 8, 3, 9, 3, 8 };k = 2;auto res = slu.maximumScore(nums, k);Assert(81, res);}{Solution slu;nums = { 19,12,14,6,10,18 };k = 3;auto res = slu.maximumScore(nums, k);Assert(4788, res);}//CConsole::Out(res);
}

2023年8月

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(int 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;;
};template<int MOD = 1000000007>
int operator+(int iData, const C1097Int<MOD>& int1097)
{int iRet = int1097.operator+(C1097Int<MOD>(iData)).ToInt();return iRet;
}template<int MOD = 1000000007>
int& operator+=(int& iData, const C1097Int<MOD>& int1097)
{iData = int1097.operator+(C1097Int<MOD>(iData)).ToInt();return iData;
}template<int MOD = 1000000007>
int operator*(int iData, const C1097Int<MOD>& int1097)
{int iRet = int1097.operator*(C1097Int(iData)).ToInt();return iRet;
}template<int MOD = 1000000007>
int& operator*=(int& iData, const C1097Int<MOD>& int1097)
{iData = int1097.operator*(C1097Int(iData)).ToInt();return iData;
}class Solution {
public:int maximumScore(vector<int>& nums, int k) {m_c = nums.size();vector<int> vScore;for ( int n : nums){int iScore = 0;for (int i = 2; i * i <= n; i++){if (0 != n % i){continue;}iScore++;while (0 == n % i){n /= i;}}if (n > 1){iScore++;}vScore.emplace_back(iScore);}stack<int> sta;vector<int> vLeft(m_c), vRight(m_c, m_c);for (int i = 0 ; i < m_c ; i++ ){while (sta.size() && (vScore[sta.top()] < vScore[i])){vRight[sta.top()] = i;sta.pop();}vLeft[i] = sta.size() ? sta.top() : -1;sta.emplace(i);			}std::map<int, long long,std::greater<int>> mValueNum;for (int i = 0; i < m_c; i++){mValueNum[nums[i]] += (i - vLeft[i])*(long long)(vRight[i] - i);}C1097Int<> biRet = 1;while (k > 0){for (auto it : mValueNum){long long llMulMul = min((long long)k, it.second);k -= llMulMul;auto cur = C1097Int<>(it.first).pow((int)llMulMul);biRet *= cur;}}return biRet.ToInt();}int m_c;
};

使用封裝類后

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(int iVectorSize, _Pr CurIndexCmpStackTopIndex){m_c = iVectorSize;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);}}template<class _Pr>CRangIndex(const vector<int>& nums, _Pr CurValueCmpStackTopValue){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() && (CurValueCmpStackTopValue(nums[i], nums[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]。
};vector<int> CreatePrime(int iMax)
{vector<int> vPrime = { 2 };for (int i = 3; i <= iMax; i++){bool b = true;for (const auto& n : vPrime){if (0 == i % n){b = false;break;}}if (b){vPrime.emplace_back(i);}}return vPrime;
}
class Solution {
public:int maximumScore(vector<int>& nums, int k) {m_c = nums.size();vector<int> vPriCount;{static vector<int> vPrime = CreatePrime(1000 * 100);for (const auto& n : nums){int tmp = n;int iNum = 0;for (const auto& pr : vPrime){if (pr * pr > tmp){break;}if (0 == tmp % pr){while (0 == tmp % pr){tmp /= pr;}iNum++;}}vPriCount.emplace_back(iNum + (tmp > 1));}}CRangIndex ri(vPriCount, std::greater<>());std::multimap<int, int, greater<int>> mValueIndex;for (int i = 0; i < ri.m_c; i++){mValueIndex.emplace(nums[i], i);}C1097Int<> biRet=1;for (const auto& [value, i] : mValueIndex){const long long llSubArrCount = ((long long)i - ri.m_vLeft[i]) * (ri.m_vRight[i] - i);const long long llOpeCount = min((long long)k, llSubArrCount);biRet *= C1097Int<>(value).pow(llOpeCount);k -= llOpeCount;if (0 == k){break;}}return biRet.ToInt();}int m_c;
};

擴(kuò)展閱讀

視頻課程

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

如何你想快

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

相關(guān)

下載

想高屋建瓴的學(xué)習(xí)算法，請下載《喜缺全書算法冊》doc版
https://download.csdn.net/download/he_zhidan/88348653

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

測試環(huán)境

操作系統(tǒng)：win7 開發(fā)環(huán)境： VS2019 C++17
或者 操作系統(tǒng)：win10 開發(fā)環(huán)境： VS2022 C++17
如無特殊說明，本算法用C++ 實現(xiàn)。

http://www.risenshineclean.com/news/5905.html

相關(guān)文章：

  • 杭州高端網(wǎng)站網(wǎng)站seo排名免費咨詢
  • 山東建設(shè)網(wǎng)站首頁建網(wǎng)站多少錢
  • 深圳網(wǎng)站開發(fā)公司寶網(wǎng)seo外包優(yōu)化公司
  • 網(wǎng)站 意義百度查重入口
  • 汽車網(wǎng)站頁面設(shè)計雅虎搜索引擎中文版
  • 浙江省人才網(wǎng)官方網(wǎng)站建設(shè)廳招聘企業(yè)網(wǎng)站有哪些功能
  • wordpress顯示慢網(wǎng)站推廣seo設(shè)置
  • 公司做網(wǎng)站設(shè)計的百度熱點排行榜
  • 網(wǎng)站升級中模板站長統(tǒng)計幸福寶
  • 怎樣修改網(wǎng)站模板百度seo網(wǎng)站優(yōu)化 網(wǎng)絡(luò)服務(wù)
  • 赤峰專業(yè)的網(wǎng)站建設(shè)谷歌搜索引擎優(yōu)化
  • 哪個網(wǎng)站可以做付郵免費送活動怎么免費自己做推廣
  • 做詐騙網(wǎng)站犯什么法西安百度公司地址介紹
  • 煙臺網(wǎng)站改版網(wǎng)站快速收錄
  • 新手去哪個網(wǎng)站做翻譯搜索引擎哪個最好用
  • 餐飲網(wǎng)站建設(shè)百度com百度一下你
  • 平安好車主app下載官方網(wǎng)站下載推廣拉新app哪幾個靠譜
  • 做涉黃的視頻網(wǎng)站用什么服務(wù)器域名注冊需要多少錢
  • 湖北省建設(shè)招投標(biāo)監(jiān)督機構(gòu)網(wǎng)站營銷型網(wǎng)站建設(shè)多少錢
  • 無錫網(wǎng)站的建設(shè)搜索引擎優(yōu)化關(guān)鍵詞選擇的方法有哪些
  • 做網(wǎng)站設(shè)計的都轉(zhuǎn)行干啥了網(wǎng)址如何被快速收錄
  • 做網(wǎng)站找云無限seo搜索優(yōu)化排名
  • 北京的制作網(wǎng)站的公司在哪里seo學(xué)校培訓(xùn)
  • 汽車圖片查詢網(wǎng)站源碼十大網(wǎng)站排行榜
  • 醫(yī)療網(wǎng)站建設(shè)公司哪家好百度站點
  • 電子商務(wù)網(wǎng)站規(guī)劃書范文桂林市天氣預(yù)報
  • 寧波網(wǎng)站設(shè)計企業(yè)網(wǎng)頁制作的步驟
  • 設(shè)計師培訓(xùn) 網(wǎng)站seo資訊
  • 網(wǎng)站建設(shè)是在商標(biāo)哪個類別16888精品貨源入口
  • 做圖片詳情網(wǎng)站如何注冊自己的網(wǎng)站