一区二区三区三上|欧美在线视频五区|国产午夜无码在线观看视频|亚洲国产裸体网站|无码成年人影视|亚洲AV亚洲AV|成人开心激情五月|欧美性爱内射视频|超碰人人干人人上|一区二区无码三区亚洲人区久久精品

0
  • 聊天消息
  • 系統(tǒng)消息
  • 評論與回復
登錄后你可以
  • 下載海量資料
  • 學習在線課程
  • 觀看技術(shù)視頻
  • 寫文章/發(fā)帖/加入社區(qū)
會員中心
創(chuàng)作中心

完善資料讓更多小伙伴認識你,還能領(lǐng)取20積分哦,立即完善>

3天內(nèi)不再提示

空間復雜度O(n)的棧模擬方法

算法與數(shù)據(jù)結(jié)構(gòu) ? 來源:代碼隨想錄 ? 作者:代碼隨想錄 ? 2022-07-10 17:24 ? 次閱讀
加入交流群
微信小助手二維碼

掃碼添加小助手

加入工程師交流群

這種匹配(消除)問題也是棧的擅長所在!

844.比較含退格的字符串

給定 S 和 T 兩個字符串,當它們分別被輸入到空白的文本編輯器后,判斷二者是否相等,并返回結(jié)果。# 代表退格字符。

注意:如果對空文本輸入退格字符,文本繼續(xù)為空。 示例 1:

  • 輸入:S = "ab#c", T = "ad#c"
  • 輸出:true
  • 解釋:S 和 T 都會變成 “ac”。

示例 2:

  • 輸入:S = "ab##", T = "c#d#"
  • 輸出:true
  • 解釋:S 和 T 都會變成 “”。

示例 3:

  • 輸入:S = "a##c", T = "#a#c"
  • 輸出:true
  • 解釋:S 和 T 都會變成 “c”。

示例 4:

  • 輸入:S = "a#c", T = "b"
  • 輸出:false
  • 解釋:S 會變成 “c”,但 T 仍然是 “b”。

思路

本文將給出 空間復雜度O(n)的棧模擬方法 以及空間復雜度是O(1)的雙指針方法。

普通方法(使用棧的思路)

這道題目一看就是要使用棧的節(jié)奏,這種匹配(消除)問題也是棧的擅長所在,跟著一起刷題的同學應該知道,在棧與隊列:匹配問題都是棧的強項,我就已經(jīng)提過了一次使用棧來做類似的事情了。

那么本題,確實可以使用棧的思路,但是沒有必要使用棧,因為最后比較的時候還要比較棧里的元素,有點麻煩。

這里直接使用字符串string,來作為棧,末尾添加和彈出,string都有相應的接口,最后比較的時候,只要比較兩個字符串就可以了,比比較棧里的元素方便一些。

代碼如下:

classSolution{
public:
boolbackspaceCompare(stringS,stringT){
strings;//當棧來用
stringt;//當棧來用
for(inti=0;iif(S[i]!='#')s+=S[i];
elseif(!s.empty()){
s.pop_back();

}
for(inti=0;iif(T[i]!='#')t+=T[i];
elseif(!t.empty()){
t.pop_back();
}
}
if(s==t)returntrue;//直接比較兩個字符串是否相等,比用棧來比較方便多了
returnfalse;
}
};
  • 時間復雜度:O(n + m), n為S的長度,m為T的長度 ,也可以理解是O(n)的時間復雜度
  • 空間復雜度:O(n + m)

當然以上代碼,大家可以發(fā)現(xiàn)有重復的邏輯處理S,處理T,可以把這塊公共邏輯抽離出來,代碼精簡如下:

classSolution{
private:
stringgetString(conststring&S){
strings;
for(inti=0;iif(S[i]!='#')s+=S[i];
elseif(!s.empty()){
s.pop_back();
}
}
returns;
}
public:
boolbackspaceCompare(stringS,stringT){
returngetString(S)==getString(T);
}
};

性能依然是:

  • 時間復雜度:O(n + m)
  • 空間復雜度:O(n + m)

優(yōu)化方法(從后向前雙指針)

當然還可以有使用 O(1) 的空間復雜度來解決該問題。

同時從后向前遍歷S和T(i初始為S末尾,j初始為T末尾),記錄#的數(shù)量,模擬消除的操作,如果#用完了,就開始比較S[i]和S[j]。

動畫如下:

1abd8eba-f681-11ec-ba43-dac502259ad0.gif

如果S[i]和S[j]不相同返回false,如果有一個指針(i或者j)先走到的字符串頭部位置,也返回false。

代碼如下:

classSolution{
public:
boolbackspaceCompare(stringS,stringT){
intsSkipNum=0;//記錄S的#數(shù)量
inttSkipNum=0;//記錄T的#數(shù)量
inti=S.size()-1;
intj=T.size()-1;
while(1){
while(i>=0){//從后向前,消除S的#
if(S[i]=='#')sSkipNum++;
else{
if(sSkipNum>0)sSkipNum--;
elsebreak;
}
i--;
}
while(j>=0){//從后向前,消除T的#
if(T[j]=='#')tSkipNum++;
else{
if(tSkipNum>0)tSkipNum--;
elsebreak;
}
j--;
}
//后半部分#消除完了,接下來比較S[i]!=T[j]
if(i0||j0)break;//S或者T遍歷到頭了
if(S[i]!=T[j])returnfalse;
i--;j--;
}
//說明S和T同時遍歷完畢
if(i==-1&&j==-1)returntrue;
returnfalse;
}
};
  • 時間復雜度:O(n + m)
  • 空間復雜度:O(1)
審核編輯:湯梓紅

聲明:本文內(nèi)容及配圖由入駐作者撰寫或者入駐合作網(wǎng)站授權(quán)轉(zhuǎn)載。文章觀點僅代表作者本人,不代表電子發(fā)燒友網(wǎng)立場。文章及其配圖僅供工程師學習之用,如有內(nèi)容侵權(quán)或者其他違規(guī)問題,請聯(lián)系本站處理。 舉報投訴
  • 字符串
    +關(guān)注

    關(guān)注

    1

    文章

    590

    瀏覽量

    22314
  • 代碼
    +關(guān)注

    關(guān)注

    30

    文章

    4900

    瀏覽量

    70801
  • 編輯器
    +關(guān)注

    關(guān)注

    1

    文章

    822

    瀏覽量

    32064

原文標題:比較含退格的字符串

文章出處:【微信號:TheAlgorithm,微信公眾號:算法與數(shù)據(jù)結(jié)構(gòu)】歡迎添加關(guān)注!文章轉(zhuǎn)載請注明出處。

收藏 人收藏
加入交流群
微信小助手二維碼

掃碼添加小助手

加入工程師交流群

    評論

    相關(guān)推薦
    熱點推薦

    CT-3046-O\\CT-3045-N鐵氧體環(huán)行器UTE Microwave

    質(zhì)量要求高的場景;CT-3045-N雖然插入損耗較高,但隔離仍能滿足一般應用需求。l 功率容量與溫度穩(wěn)定性 CT-3046-O的功率容量更高,溫度穩(wěn)定性更好,適合大功率和高可靠性
    發(fā)表于 05-23 10:06

    ADIN2111集成10BASE-T1L PHY的低復雜度、2端口以太網(wǎng)交換機技術(shù)手冊

    ADIN2111是一款低功耗、低復雜度、雙以太網(wǎng)端口交換機,它集成了10BASE-T1L PHY和一個串行外設接口(SPI)端口。該器件使用低功率受限節(jié)點,面向工業(yè)以太網(wǎng)應用且符合IEEE
    的頭像 發(fā)表于 05-15 11:41 ?353次閱讀
    ADIN2111集成10BASE-T1L PHY的低<b class='flag-5'>復雜度</b>、2端口以太網(wǎng)交換機技術(shù)手冊

    VirtualLab Fusion應用:多層超表面空間板的模擬

    的同時使系統(tǒng)盡可能小,解決元件之間的距離問題也是必要的。例如,可以通過將系統(tǒng)折疊起來,利用相同的體積實現(xiàn)多個傳播步驟,但這并不是唯一可行的策略。 我們將介紹多層超表面空間板的模擬(由 O. Reshef
    發(fā)表于 04-09 08:51

    CT-3042-O,CT-3041-N鐵氧體環(huán)行器UTE Microwave

    CT-3042-O,CT-3041-N鐵氧體環(huán)行器UTE MicrowaveCT-3042-O與CT-3041-N鐵氧體環(huán)行器屬于非互易型多端口微波組件,它們利用鐵氧體材料的旋磁特性來
    發(fā)表于 03-24 10:27

    CT-3038-O/CT-3037-N鐵氧體環(huán)行器UTE Microwave

    × 1英寸 連接器類型: CT-3038-O:SMA母頭 CT-3037-NN母頭 典型性能指標: 隔離:最低18 dB 插入損耗:最高0.40 dB 駐波比:最高1.30:1
    發(fā)表于 02-25 10:18

    N2O(一氧化二氮)氣體和紅外N2O(一氧化二氮)氣體傳感器

    本文聚焦一氧化二氮(N?O,俗稱笑氣)。自然環(huán)境中,土壤微生物活動及海洋浮游生物等產(chǎn)生 N?O ,海洋釋放量約占全球自然源排放總量三分之一。但因農(nóng)業(yè)、化石燃料燃燒等人類活動排放,
    的頭像 發(fā)表于 01-22 14:45 ?1794次閱讀
    <b class='flag-5'>N2O</b>(一氧化二氮)氣體和紅外<b class='flag-5'>N2O</b>(一氧化二氮)氣體傳感器

    AI時代下芯片復雜度飆升,思爾芯國產(chǎn)硬件仿真加速芯片創(chuàng)新

    引言在人工智能(AI)技術(shù)蓬勃發(fā)展的今天,芯片的復雜度正以前所未有的速度飆升,輕松跨越了百億邏輯門級別的大關(guān)。這一趨勢不僅推動了半導體行業(yè)的快速發(fā)展,也對硬件仿真系統(tǒng)提出了更高的挑戰(zhàn)和要求。在近日
    的頭像 發(fā)表于 12-27 18:01 ?843次閱讀
    AI時代下芯片<b class='flag-5'>復雜度</b>飆升,思爾芯國產(chǎn)硬件仿真加速芯片創(chuàng)新

    芯片設計復雜度劇增,紫光芯片云 3.0 助力企業(yè)搭建專業(yè)設計環(huán)境

    。 ? 實際上,國內(nèi)中小IC設計企業(yè)居多,而如今他們面臨更加復雜的設計需求。隨著芯片制程和規(guī)模要求不斷提高,芯片設計環(huán)境所需資源越來越大,設計環(huán)境構(gòu)建更加復雜,初創(chuàng)企業(yè)如何搭建設計環(huán)境,中小企業(yè)如何在人員經(jīng)驗欠缺的情況下完成有效布局,又如
    的頭像 發(fā)表于 12-26 17:04 ?1500次閱讀
    芯片設計<b class='flag-5'>復雜度</b>劇增,紫光芯片云 3.0 助力企業(yè)搭建專業(yè)設計環(huán)境

    DoIP協(xié)議簡介及主要功能

    隨著汽車的智能化和網(wǎng)聯(lián)化,車載電子系統(tǒng)的復雜度不斷增加,對數(shù)據(jù)通信的帶寬需求越來越大,通信速度要求也越來越高。借助于傳統(tǒng)因特網(wǎng)的成熟技術(shù),引入到車載網(wǎng)絡得以解決當前的通信需求,通過對傳統(tǒng)以太網(wǎng)的技術(shù)
    的頭像 發(fā)表于 11-13 15:35 ?1854次閱讀
    DoIP協(xié)議<b class='flag-5'>棧</b>簡介及主要功能

    熱真空試驗箱 空間環(huán)境地面模擬試驗設備

    產(chǎn)品用途:空間環(huán)境地面模擬試驗設備用于軍工和航天產(chǎn)品在地面環(huán)境中模擬太空的真空、冷黑和太陽輻射的環(huán)境,進行熱真空試驗和熱平衡試驗。空間環(huán)境地面模擬
    的頭像 發(fā)表于 11-01 11:16 ?560次閱讀
    熱真空試驗箱 <b class='flag-5'>空間</b>環(huán)境地面<b class='flag-5'>模擬</b>試驗設備

    線程分配惹的禍?系統(tǒng)異常這樣解決!

    ,尤其當項目規(guī)模擴大、代碼復雜度增加時,各種“難以捉摸”的bug便會頻繁出現(xiàn),令工程師們一頭霧水,不知從何入手。這些問題可能涉及內(nèi)存管理、任務調(diào)度、溢出等復雜內(nèi)
    的頭像 發(fā)表于 10-31 08:08 ?1618次閱讀
    線程<b class='flag-5'>棧</b>分配惹的禍?系統(tǒng)異常這樣解決!

    時間復雜度O(n^2) 的排序算法

    作者:京東保險 王奕龍 對于小規(guī)模數(shù)據(jù),我們可以選用時間復雜度O(n2) 的排序算法。因為時間復雜度并不代表實際代碼的執(zhí)行時間,它省去了低階、系數(shù)和常數(shù),僅代表的增長趨勢,所以在小
    的頭像 發(fā)表于 10-19 16:31 ?1745次閱讀
    時間<b class='flag-5'>復雜度</b>為 <b class='flag-5'>O</b>(<b class='flag-5'>n</b>^2) 的排序算法

    PCB與PCBA工藝復雜度的量化評估與應對措施

    一站式PCBA智造廠家今天為大家講講PCBA工藝復雜嗎?PCBA工藝的復雜性應對PCBA工藝復雜性的措施。在電子制造領(lǐng)域,PCBA工藝是至關(guān)重要的環(huán)節(jié)。盡管對許多人來說,PCBA工藝可能看似
    的頭像 發(fā)表于 09-13 09:21 ?861次閱讀

    業(yè)務復雜度治理方法論--十年系統(tǒng)設計經(jīng)驗總結(jié)

    一、復雜度綜述 1、什么是復雜度 軟件設計的核心在于降低復雜性。 --《軟件設計的哲學》 業(yè)界對于復雜度并沒有統(tǒng)一的定義, 斯坦福教授John Ousterhout從認知負擔和工作量方
    的頭像 發(fā)表于 09-05 14:11 ?1322次閱讀
    業(yè)務<b class='flag-5'>復雜度</b>治理<b class='flag-5'>方法</b>論--十年系統(tǒng)設計經(jīng)驗總結(jié)

    CISC(復雜指令集)與RISC(精簡指令集)的區(qū)別  

    復雜度, 將復雜性交給編譯器。舉一個例子,CISC提供的乘法指令,調(diào)用時可完成內(nèi)存a和內(nèi)存b中的兩個數(shù)相乘,結(jié)果存入內(nèi)存a ,需要多個CPU周期才可以完成;而RISC不提供“一站式”的乘法指令,需
    發(fā)表于 07-30 17:21