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

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

威海高區(qū)有沒有建設(shè)局的網(wǎng)站uc搜索引擎入口

威海高區(qū)有沒有建設(shè)局的網(wǎng)站,uc搜索引擎入口,婚紗網(wǎng)站免費(fèi)源碼,深圳網(wǎng)站建設(shè)深圳網(wǎng)絡(luò)前綴和 前綴和指數(shù)組的前 N項(xiàng)之和,是個(gè)比較基礎(chǔ)的算法 例題 面試題 17.05. 字母與數(shù)字 給定一個(gè)放有字母和數(shù)字的數(shù)組,找到最長的子數(shù)組,且包含的字母和數(shù)字的個(gè)數(shù)相同。 返回該子數(shù)組,若存在多個(gè)最長子數(shù)組,返回左…

前綴和

前綴和指數(shù)組的前 N項(xiàng)之和,是個(gè)比較基礎(chǔ)的算法

例題

面試題 17.05. 字母與數(shù)字

給定一個(gè)放有字母和數(shù)字的數(shù)組,找到最長的子數(shù)組,且包含的字母和數(shù)字的個(gè)數(shù)相同。
返回該子數(shù)組,若存在多個(gè)最長子數(shù)組,返回左端點(diǎn)下標(biāo)值最小的子數(shù)組。若不存在這樣的數(shù)組,返回一個(gè)空數(shù)組。

示例 1:
輸入: [“A”,“1”,“B”,“C”,“D”,“2”,“3”,“4”,“E”,“5”,“F”,“G”,“6”,“7”,“H”,“I”,“J”,“K”,“L”,“M”]
輸出: [“A”,“1”,“B”,“C”,“D”,“2”,“3”,“4”,“E”,“5”,“F”,“G”,“6”,“7”]

示例 2:
輸入: [“A”,“A”]
輸出: []

提示:
array.length <= 100000

思路

使用前綴和+哈希
為字母則取1,數(shù)字為-1,即要求和為0的最大子數(shù)組。
前綴和表示第i個(gè)數(shù)及之前的所有數(shù)的和。哈希存儲前綴和c第一次出現(xiàn)的位置i,循環(huán)時(shí)維護(hù)一個(gè)maxlen表示最大的子數(shù)組長度,start表示最長子數(shù)組起始下標(biāo)。
初始化時(shí),前綴和為0,下標(biāo)為-1。遍歷到i時(shí),前綴和為sum,如果此時(shí)哈希表中沒有關(guān)于前綴和為sum的記錄,則更新indices[sum]=i。如果已有,則對比maxlen和i-indices[sum],如果i-indices[sum]較大,則maxlen更新為i-indices[sum],start更新為indices[sum]+1。
如果maxlen不為0,返回array中array[start]到array[start+maxlen]的部分。

代碼

class Solution {
public:vector<string> findLongestSubarray(vector<string>& array) {int n=array.size();int sum=0;int maxlen=0;int start=-1;unordered_map<int,int> indices;indices[0]=-1;for(int i=0;i<n;i++){if(isalpha(array[i][0])){sum++;}else{sum--;}if(indices.find(sum)==indices.end()){indices[sum]=i;}else{if(i-indices[sum]>maxlen){maxlen=i-indices[sum];start=indices[sum]+1;}}}if(maxlen==0) return {};return vector<string>(array.begin()+start,array.begin()+start+maxlen);}
};

209. 長度最小的子數(shù)組

給定一個(gè)含有 n 個(gè)正整數(shù)的數(shù)組和一個(gè)正整數(shù) target 。
找出該數(shù)組中滿足其和 ≥ target 的長度最小的 連續(xù)子數(shù)組 [numsl, numsl+1, …, numsr-1, numsr] ,并返回其長度。如果不存在符合條件的子數(shù)組,返回 0 。

示例 1:
輸入:target = 7, nums = [2,3,1,2,4,3]
輸出:2
解釋:子數(shù)組 [4,3] 是該條件下的長度最小的子數(shù)組。

示例 2:
輸入:target = 4, nums = [1,4,4]
輸出:1

示例 3:
輸入:target = 11, nums = [1,1,1,1,1,1,1,1]
輸出:0

提示:
1 <= target <= 109
1 <= nums.length <= 105
1 <= nums[i] <= 105

進(jìn)階:
如果你已經(jīng)實(shí)現(xiàn) O(n) 時(shí)間復(fù)雜度的解法, 請嘗試設(shè)計(jì)一個(gè) O(n log(n)) 時(shí)間復(fù)雜度的解法。

思路

首先計(jì)算前綴和,presum[i]表示從0加到i-1的和,
對于遍歷每個(gè)子數(shù)組的起始點(diǎn)nums[i],用二分搜索找到presum[j]-presum[i]大于或等于target的第一個(gè)下標(biāo)j,遍歷過程中維護(hù)最短子數(shù)組的長度minlen。

或者用滑動窗口做

代碼

//前綴和+二分搜索
class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int n=nums.size();int minlen=n+1;vector<int> presum(n+1,0);//presum[i]是從0加到i-1for(int i=0;i<n;i++){presum[i+1]=presum[i]+nums[i];}for(int i=0;i<n;i++){int l=i+1,r=n;while(l<r){int m=(l+r)/2;if(presum[m]-target<presum[i]){l=m+1;}else{r=m;}}if(presum[l]-target>=presum[i]){minlen=min(l-i,minlen);}}if(minlen>n) return 0;else return minlen;}
};
class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int n=nums.size();int l=0,r=0;int sum=nums[0],minlen=n+1;while(r<n){while(sum<target&&r<n){if(++r<n) sum+=nums[r];}if(sum>=target){minlen=min(minlen,r-l+1);sum-=nums[l];l++;}else break;}return minlen<=n?minlen:0;}
};
http://www.risenshineclean.com/news/5685.html

相關(guān)文章:

  • 簡歷怎么制作網(wǎng)站新聞發(fā)稿
  • 如何做導(dǎo)航網(wǎng)站市場推廣怎么寫
  • 泉州企業(yè)網(wǎng)站維護(hù)制作域名歸屬查詢
  • 家庭寬帶怎么做網(wǎng)站網(wǎng)站如何宣傳推廣
  • 網(wǎng)站建設(shè) 徐州聯(lián)合早報(bào) 即時(shí)消息
  • seo建站是什么意思愛廷玖達(dá)泊西汀
  • 成都seo整站上海搜索引擎優(yōu)化1
  • 企業(yè)網(wǎng)站建設(shè)費(fèi)用定金怎么做賬官網(wǎng)排名優(yōu)化方案
  • 網(wǎng)站廣告形式合肥seo推廣公司哪家好
  • 百度網(wǎng)站下拉怎么做的怎么在百度上注冊店鋪
  • 上海專業(yè)制作網(wǎng)站口碑營銷的案例及分析
  • 數(shù)碼產(chǎn)品網(wǎng)站建設(shè)百度seo優(yōu)化技巧
  • php是專門做網(wǎng)站的最全資源搜索引擎
  • 如何建設(shè)網(wǎng)站并與數(shù)據(jù)庫相連百度輸入法免費(fèi)下載
  • 鄭州網(wǎng)站制作漢獅杭州seo網(wǎng)站推廣排名
  • 裝修的網(wǎng)站都有哪些手機(jī)seo排名軟件
  • 網(wǎng)頁圖片大小怎么調(diào)整sem優(yōu)化怎么做
  • 中山市 做網(wǎng)站網(wǎng)站建立具體步驟是
  • 美女做基網(wǎng)站微信上如何投放廣告
  • 北京百子灣后現(xiàn)代城網(wǎng)站建設(shè)商業(yè)網(wǎng)站
  • 靜態(tài)網(wǎng)站開發(fā) 內(nèi)容磁力屋torrentkitty
  • 旅游景區(qū)網(wǎng)站建設(shè)win10優(yōu)化大師
  • c2c電商平臺網(wǎng)站外貿(mào)建站推廣哪家好
  • 小程序要先做網(wǎng)站seoul是啥意思
  • c access做網(wǎng)站登錄頁面網(wǎng)站推廣的渠道有
  • 公關(guān)公司排行搜索引擎優(yōu)化的定義是什么
  • 許昌做網(wǎng)站公司哪家專業(yè)抖音關(guān)鍵詞排名查詢
  • 做旅游網(wǎng)站的目的是什么企業(yè)軟文范例
  • 做再生料的網(wǎng)站小紅書如何引流推廣
  • 免費(fèi)推廣網(wǎng)站搭建seo技術(shù)培訓(xùn)教程