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

當(dāng)前位置: 首頁(yè) > news >正文

商務(wù)網(wǎng)站建設(shè)需要多少錢seo常用的優(yōu)化工具

商務(wù)網(wǎng)站建設(shè)需要多少錢,seo常用的優(yōu)化工具,求網(wǎng)站開發(fā)客戶,網(wǎng)站云空間題目鏈接 Leetcode.321 拼接最大數(shù) hard 題目描述 給定長(zhǎng)度分別為 m m m 和 n n n 的兩個(gè)數(shù)組,其元素由 0 ~ 9 0 \sim 9 0~9 構(gòu)成,表示兩個(gè)自然數(shù)各位上的數(shù)字。現(xiàn)在從這兩個(gè)數(shù)組中選出 k k k ( k ≤ m n ) (k \leq m n) (k≤mn) 個(gè)數(shù)字拼接成…

題目鏈接

Leetcode.321 拼接最大數(shù) hard

題目描述

給定長(zhǎng)度分別為 m m m n n n 的兩個(gè)數(shù)組,其元素由 0 ~ 9 0 \sim 9 09 構(gòu)成,表示兩個(gè)自然數(shù)各位上的數(shù)字?,F(xiàn)在從這兩個(gè)數(shù)組中選出 k k k ( k ≤ m + n ) (k \leq m + n) (km+n) 個(gè)數(shù)字拼接成一個(gè)新的數(shù),要求從同一個(gè)數(shù)組中取出的數(shù)字保持其在原數(shù)組中的相對(duì)順序。

求滿足該條件的最大數(shù)。結(jié)果返回一個(gè)表示該最大數(shù)的長(zhǎng)度為 k k k 的數(shù)組。

說(shuō)明: 請(qǐng)盡可能地優(yōu)化你算法的時(shí)間和空間復(fù)雜度。

示例 1:

輸入:
nums1 = [3, 4, 6, 5]
nums2 = [9, 1, 2, 5, 8, 3]
k = 5
輸出:
[9, 8, 6, 5, 3]

示例 2:

輸入:
nums1 = [6, 7]
nums2 = [6, 0, 4]
k = 5
輸出:
[6, 7, 6, 0, 4]

示例 3:

輸入:
nums1 = [3, 9]
nums2 = [8, 9]
k = 3
輸出:
[9, 8, 9]

解法:單調(diào)棧

我們假設(shè)由 k k k 個(gè)元素組成的最大數(shù),其中有 x x x 個(gè)元素來(lái)自 n u m s 1 nums1 nums1,那么就有 k ? x k - x k?x 個(gè)元素來(lái)自 n u m s 2 nums2 nums2。

我們定義 m a x _ s e q u e n c e ( S , m ) max\_sequence(S,m) max_sequence(S,m) 表示從集合 S S S 中,選出 m m m 個(gè)元素構(gòu)成的最大數(shù)(元素之間要保持在集合 S S S 中的相對(duì)位置)。

  • s 1 = m a x _ s e q u e n c e ( n u m s 1 , x ) s1 = max\_sequence(nums1,x) s1=max_sequence(nums1,x) s 1 s1 s1 表示從集合 n u m s 1 nums1 nums1 中選出 x x x 個(gè)元素組成的最大數(shù);
  • s 2 = m a x _ s e q u e n c e ( n u m s 2 , k ? x ) s2 = max\_sequence(nums2,k-x) s2=max_sequence(nums2,k?x) s 2 s2 s2 表示從集合 n u m s 2 nums2 nums2 中選出 k ? x k-x k?x 個(gè)元素組成的最大數(shù);

我們最后再將 s 1 s1 s1 s 2 s2 s2 拼接成一個(gè)最大數(shù) S S S,那么這個(gè) S S S 就是答案之一。所以我們就要遍歷 x x x ,求出所有的 S S S,最后返回最大的那個(gè)。

在實(shí)現(xiàn)上:

m a x _ s e q u e n c e ( S , m ) max\_sequence(S,m) max_sequence(S,m) 可以利用單調(diào)棧實(shí)現(xiàn):

  • 如果 S . s i z e ( ) ≤ m S.size() \leq m S.size()m,那么直接返回集合 S S S 即可;
  • 我們定義一個(gè)棧 s t k stk stk,因?yàn)槲覀円祷氐氖? m m m 個(gè)元素組成的最大數(shù),也就是說(shuō) s t k stk stk 最終有 m m m 個(gè)元素,即 s t k stk stk 能夠彈出去的元素最多只有 d e l = S . s i z e ( ) ? m del = S.size() - m del=S.size()?m 個(gè)。
  • 假設(shè)當(dāng)前遍歷到的元素為 x x x,如果 x > s t k . t o p ( ) x > stk.top() x>stk.top() 并且 d e l > 0 del > 0 del>0,那么就可以彈出棧頂元素,因?yàn)槲覀円?span id="vxwlu0yf4" class="katex--inline"> s t k stk stk 中的數(shù)字典序盡可能的大。
  • 最終返回 s t k stk stk 即可。需要注意的是:如果 S S S 中所有元素都相同 或者 S S S 是一個(gè)非降序的序列,那么 s t k stk stk 中就沒(méi)有彈出的元素,一共就有 S . s i z e ( ) S.size() S.size() 個(gè)元素,我們只需要前 m m m 個(gè)即可。

在這里需要介紹一個(gè) STL algorithm 庫(kù)的函數(shù) lexicographical_compare(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2)

template<class InputIt1, class InputIt2>
bool lexicographical_compare(InputIt1 first1, InputIt1 last1,InputIt2 first2, InputIt2 last2)
{for (; (first1 != last1) && (first2 != last2); ++first1, (void) ++first2){if (*first1 < *first2)return true;if (*first2 < *first1)return false;}return (first1 == last1) && (first2 != last2);
}

上述這個(gè)函數(shù)的作用是:判斷區(qū)間一 [ f i r s t 1 , l a s t 1 ) [first1,last1) [first1,last1) 字典序是否不大于 區(qū)間二 [ f i r s t 2 , l a s t 2 ) [first2,last2) [first2,last2)。

  • 是的話,最終返回 true
  • 否,返回 false

時(shí)間復(fù)雜度: O ( m + n + k 2 ) O(m + n + k^2) O(m+n+k2)

C++代碼:

class Solution {
public:vector<int> max_sequence(vector<int> vec,int k){int n = vec.size();if(n <= k) return vec;vector<int> stk;int del = n - k;for(int i = 0;i < n;i++){while(stk.size() && vec[i] > stk.back() && del){del--;stk.pop_back();}stk.push_back(vec[i]);}stk.resize(k);return stk;}vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {int m = nums1.size() , n = nums2.size();vector<int> res(k,0);for(int x = max(0,k - n);x <= min(k,m);x++){vector<int> temp;auto s1 = max_sequence(nums1,x);auto s2 = max_sequence(nums2,k - x);auto it1 = s1.begin() , it2 = s2.begin();while(it1 != s1.end() || it2 != s2.end()){temp.push_back(lexicographical_compare(it1,s1.end(),it2,s2.end() )? *it2++ : *it1++);}res = lexicographical_compare(res.begin(),res.end(),temp.begin(),temp.end()) ? move(temp) : res;}return res;}
};
http://www.risenshineclean.com/news/54958.html

相關(guān)文章:

  • PHP做的彩票網(wǎng)站好用嗎電腦培訓(xùn)中心
  • 研究政府網(wǎng)站建設(shè)的意義優(yōu)秀的網(wǎng)絡(luò)搜索引擎營(yíng)銷案例
  • win2003做網(wǎng)站百度關(guān)鍵詞怎么優(yōu)化
  • 教育類型網(wǎng)站如何優(yōu)化網(wǎng)絡(luò)
  • 定做微信小程序搜索引擎優(yōu)化的技巧
  • 樂(lè)清 做網(wǎng)站 多少錢中國(guó)經(jīng)濟(jì)網(wǎng)人事
  • 日本做電子賀卡網(wǎng)站軟件推廣怎么賺錢
  • 蘇州做網(wǎng)站設(shè)計(jì)的公司網(wǎng)站推廣的渠道有
  • ui培訓(xùn)的課程都有哪些seo建站收費(fèi)地震
  • 東莞做網(wǎng)站一年費(fèi)用百度指數(shù)明星搜索排名
  • 阿里云做網(wǎng)站流程網(wǎng)絡(luò)營(yíng)銷戰(zhàn)略的內(nèi)容
  • 網(wǎng)站電子地圖怎么做百度保障中心人工電話
  • 網(wǎng)站建設(shè)站長(zhǎng)免費(fèi)網(wǎng)絡(luò)營(yíng)銷軟件
  • 繪本館網(wǎng)站建設(shè)百度服務(wù)
  • dw網(wǎng)站模板下載西安seo顧問(wèn)培訓(xùn)
  • 網(wǎng)站換ip對(duì)優(yōu)化有影響嗎武漢百度推廣公司
  • 活在永久免費(fèi)服務(wù)器西安seo優(yōu)化顧問(wèn)
  • 網(wǎng)站上怎樣做輪播圖競(jìng)價(jià)推廣專員
  • 邯鄲建設(shè)網(wǎng)站的公司廣告引流推廣平臺(tái)
  • 網(wǎng)站開發(fā)與維護(hù)能做什么職業(yè)互聯(lián)網(wǎng)營(yíng)銷師證書含金量
  • 做網(wǎng)站必須要備案嗎免費(fèi)行情軟件網(wǎng)站大全
  • 怎么識(shí)別網(wǎng)站是用什么語(yǔ)言做的網(wǎng)絡(luò)推廣崗位職責(zé)和任職要求
  • 統(tǒng)計(jì)網(wǎng)站建設(shè)青島設(shè)計(jì)優(yōu)化公司
  • 電子商務(wù)網(wǎng)站項(xiàng)目預(yù)算選擇寧波seo優(yōu)化公司
  • 旅游網(wǎng)站制作過(guò)程教育培訓(xùn)機(jī)構(gòu)招生方案
  • div css做網(wǎng)站微信社群營(yíng)銷
  • ui設(shè)計(jì)和網(wǎng)站開發(fā)官方網(wǎng)站營(yíng)銷
  • 泉州開發(fā)網(wǎng)站的公司有哪些網(wǎng)站推廣費(fèi)用
  • 如何找網(wǎng)站互聯(lián)網(wǎng)公司
  • 企業(yè)信息管理系統(tǒng)er圖青島網(wǎng)絡(luò)優(yōu)化代理