付費限定

堆疊應用+模擬: 移除字串中的星號_Leetcode 精選75題解析

閱讀時間約 4 分鐘

題目敘述

題目會給我們一個字串s。

要求我們移除字串中的星號,還有刪除星號左手邊最靠近的第一個字元

以字串的形式返回輸出答案。

題目的原文敘述


測試範例

Example 1:

Input: s = "leet**cod*e"
Output: "lecoe"
Explanation: Performing the removals from left to right:
- The closest character to the 1st star is 't' in "leet**cod*e". s becomes "lee*cod*e".
- The closest character to the 2nd star is 'e' in "lee*cod*e". s becomes "lecod*e".
- The closest character to the 3rd star is 'd' in "lecod*e". s becomes "lecoe".
There are no more stars, so we return "lecoe".

Example 2:

Input: s = "erase*****"
Output: ""
Explanation: The entire string is removed, so we return an empty string.

約束條件

Constraints:

  • 1 <= s.length <= 10^5

字串s的長度介於 1 ~ 10^5 之間。

  • s consists of lowercase English letters and stars *.

字串s只會包含小寫英文字母 和 *星號。

  • The operation above can be performed on s.

定義中的操作可以在字串s中完成。


演算法

這題的關鍵在於把 *星號 當成我們平常鍵盤上使用的←Backsapce鍵的功能,向左邊吃掉一個最靠近的字元

實作的時候,先建立一個空的stack,把每個字元依序推入stack
假如遇到 *星號,則直接pop stack頂端的字元,相當於滿足題目所說的「向左邊吃掉一個最靠近的字元」。

最後,把stack內剩餘的字元轉成字串的形式輸出答案即可。


程式碼

class Solution:
def removeStars(self, s: str) -> str:

stk = []

# scan each character from left to right
for char in s:

if char != '*':
# push current character into stack
stk.append( char )

else:
# pop one character from stack, removed with * together.
stk.pop()

return "".join(stk)

以行動支持創作者!付費即可解鎖
本篇內容共 1712 字、1 則留言,僅發佈於Leetcode精選75題 解析+統整你目前無法檢視以下內容,可能因為尚未登入,或沒有該房間的查看權限。
88會員
425內容數
由有業界實戰經驗的演算法工程師, 手把手教你建立解題的框架, 一步步寫出高效、清晰易懂的解題答案。 著重在讓讀者啟發思考、理解演算法,熟悉常見的演算法模板。 深入淺出地介紹題目背後所使用的演算法意義,融會貫通演算法與資料結構的應用。 在幾個經典的題目融入一道題目的多種解法,或者同一招解不同的題目,擴展廣度,並加深印象。
留言0
查看全部
發表第一個留言支持創作者!
題目敘述 題目會給我們一個定義好的類別和function介面,要求我們實作建構子和ping() function來滿足指定的需求。 RecentCounter類別的建構子 建構子應該初始化來電紀錄,內容為空(零筆資料) int ping(int t) t代表來電時刻,單位是毫秒m
題目敘述 題目會給定一個輸入字串s和一套編碼規則,要求我們針對字串s進行解碼,並且以字串的形式返回答案。 編碼規則: 數字[字串] -> []內的字串以對應倍數做展開,而且允許巢狀編碼。 例如: 3[a] 解碼完就是 aaa 2[bc] 解碼完就是 bcbc 2[a2[b]] = 2
題目敘述 題目會給定我們一個二維陣列,要求我們計算內部元素相同的column row pairs總共有多少條? 註: pair的定義就是row i 和 column j 彼此內部元素值都相同,這樣就算一條pair。 題目的原文敘述 測試範例 Example 1: Input: gr
題目敘述 題目會給定我們一個整數陣列asteroids,每個元素代表每顆星球的大小和飛行方向。 絕對值的部分越大,代表星球的大小越大。 若數值為正,代表星球向右飛。 若數值為負,代表星球向左飛。 當兩顆星球碰撞時,會有以下碰撞規則規定: 如果一顆比較大,另一顆比較小,則比較大的那棵
題目敘述 題目會給定我們兩個整數陣列作為輸入nums1, nums2,要求我們找出兩個陣列的差異值。 找出在nums1但是不在nums2的元素,以陣列的形式放在answer[0]輸出。 找出在nums2但是不在nums1的元素,以陣列的形式放在answer[1]輸出。 題目的原文敘述
題目敘述 題目會給我們一個整數陣列nums,要求我們計算平衡軸心點在哪? 平衡軸心的意思就是軸心點索引左側的元素總合 = 軸心點索引右側的元素總合 例如 整數陣列nums=[1,2,2,7,2,3] 7左側的元素總合為 1 + 2 + 2 = 5 7右側的元素總合為 2 + 3 = 5
題目敘述 題目會給我們一個定義好的類別和function介面,要求我們實作建構子和ping() function來滿足指定的需求。 RecentCounter類別的建構子 建構子應該初始化來電紀錄,內容為空(零筆資料) int ping(int t) t代表來電時刻,單位是毫秒m
題目敘述 題目會給定一個輸入字串s和一套編碼規則,要求我們針對字串s進行解碼,並且以字串的形式返回答案。 編碼規則: 數字[字串] -> []內的字串以對應倍數做展開,而且允許巢狀編碼。 例如: 3[a] 解碼完就是 aaa 2[bc] 解碼完就是 bcbc 2[a2[b]] = 2
題目敘述 題目會給定我們一個二維陣列,要求我們計算內部元素相同的column row pairs總共有多少條? 註: pair的定義就是row i 和 column j 彼此內部元素值都相同,這樣就算一條pair。 題目的原文敘述 測試範例 Example 1: Input: gr
題目敘述 題目會給定我們一個整數陣列asteroids,每個元素代表每顆星球的大小和飛行方向。 絕對值的部分越大,代表星球的大小越大。 若數值為正,代表星球向右飛。 若數值為負,代表星球向左飛。 當兩顆星球碰撞時,會有以下碰撞規則規定: 如果一顆比較大,另一顆比較小,則比較大的那棵
題目敘述 題目會給定我們兩個整數陣列作為輸入nums1, nums2,要求我們找出兩個陣列的差異值。 找出在nums1但是不在nums2的元素,以陣列的形式放在answer[0]輸出。 找出在nums2但是不在nums1的元素,以陣列的形式放在answer[1]輸出。 題目的原文敘述
題目敘述 題目會給我們一個整數陣列nums,要求我們計算平衡軸心點在哪? 平衡軸心的意思就是軸心點索引左側的元素總合 = 軸心點索引右側的元素總合 例如 整數陣列nums=[1,2,2,7,2,3] 7左側的元素總合為 1 + 2 + 2 = 5 7右側的元素總合為 2 + 3 = 5
你可能也想看
Google News 追蹤
Thumbnail
這個秋,Chill 嗨嗨!穿搭美美去賞楓,裝備款款去露營⋯⋯你的秋天怎麼過?秋日 To Do List 等你分享! 秋季全站徵文,我們準備了五個創作主題,參賽還有機會獲得「火烤兩用鍋」,一起來看看如何參加吧~
Thumbnail
11/20日NVDA即將公布最新一期的財報, 今天Sell Side的分析師, 開始調高目標價, 市場的股價也開始反應, 未來一週NVDA將重新回到美股市場的焦點, 今天我們要分析NVDA Sell Side怎麼看待這次NVDA的財報預測, 以及實際上Buy Side的倉位及操作, 從
Thumbnail
Hi 大家好,我是Ethan😊 相近大家都知道保濕是皮膚保養中最基本,也是最重要的一步。無論是在畫室裡長時間對著畫布,還是在旅途中面對各種氣候變化,保持皮膚的水分平衡對我來說至關重要。保濕化妝水不僅能迅速為皮膚補水,還能提升後續保養品的吸收效率。 曾經,我的保養程序簡單到只包括清潔和隨意上乳液
Thumbnail
這本書記錄了作者廖瞇與弟弟滌的對話過程,以及如何通過對話再次與父親和母親對話,同時也是對自己的深入挖掘。通過書寫,作者細膩處理了家人之間最難以解開的謎題,並療癒自己與家人的心靈困境。這是一部近身拍攝的紙上紀錄片,讀者將在堆疊細碎的家庭日常裡,見證他人的家庭現實,並與之產生共鳴。
Thumbnail
還記得第一次失戀,椎心痛骨 意外與新詩相遇,嘗試用文字堆疊內心的苦楚,還有曾經溺愛中的美好。 《淺眠於妳》或許拙劣但十年過去了,我仍醉心此詩。 再獻上後兩首,紀念妳留給我的…… 《淺眠於妳》 曾經那麼巧,在人海中遇見彼此 那麼的剛好,眼神交會的那一次 從此只有你,左思右
Thumbnail
終至不會流於「人們仰望權威」的複製及誤解,終究是你們晃動了你們自己。
Thumbnail
死亡焦慮原來一直在我的思緒中存在著,但是我並未察覺。
Thumbnail
「被療癒」這個詞會不會有點泛濫?現代人壓力大,必須將理性思考放在第一優先,而將感性的一面埋在心底,所以當自己的感性被激發時,不知如何形容就用被「療癒了」這個詞。
最近總是感覺步調停滯,看過浩子的書"世界是我的信仰"後,發現有些東西其實在累積,在我沒發現的時候,其實慢慢成長與遺忘了!像是我的體重、腹肌XD,默默的減少與增加,很多看似無用的努力,都開始發芽了!浩子說一點一滴很小的事件累積成書籍,非常認同的反思自己的人生,小小的故事與所遇事件建構我的原則與價值觀,
Thumbnail
製造公差是你總是會碰到的東西,因此設計時沒有適當考量下很容易發生問題。 不談電子產業,光是我從網路買回來的DIY家具就常常有組不上去的問題,這很明顯就是公差太大。大東西尚且如此,小東西更是得斤斤計較了。 在計算公差堆疊的時候的基本邏輯是:  目標尺寸鏈 -> 決定計算方法 -> 設定公差或是設定設計
Thumbnail
在人生當中,我們必須不斷做出抉擇。在每次抉擇時,我們或許會想多了解自己以及眼前的情境,再根據這些了解做出行動,並預測這些行動將帶來什麼後果。越不了解自己與情境,行動就越盲目,也越看不到未來。幸運的是,大部分人都有一定的了解自己與了解他人的能力。
Thumbnail
早期的水手條紋搭配海軍領 有時候,是基底覆上幾何般的線條與形狀,只是它們是直挺挺地朝著另一端的盡頭延伸;有時候,是層層線條反覆結合在一起,漸漸成為一大片能包覆在我們身上的個性。 古著灰色襯衫。來自:MIMIGUZHU咪咪古著 線條可以擴張人類視覺反應,同時從雙目中感受到這些拖曳痕跡般的浪漫
Thumbnail
這個秋,Chill 嗨嗨!穿搭美美去賞楓,裝備款款去露營⋯⋯你的秋天怎麼過?秋日 To Do List 等你分享! 秋季全站徵文,我們準備了五個創作主題,參賽還有機會獲得「火烤兩用鍋」,一起來看看如何參加吧~
Thumbnail
11/20日NVDA即將公布最新一期的財報, 今天Sell Side的分析師, 開始調高目標價, 市場的股價也開始反應, 未來一週NVDA將重新回到美股市場的焦點, 今天我們要分析NVDA Sell Side怎麼看待這次NVDA的財報預測, 以及實際上Buy Side的倉位及操作, 從
Thumbnail
Hi 大家好,我是Ethan😊 相近大家都知道保濕是皮膚保養中最基本,也是最重要的一步。無論是在畫室裡長時間對著畫布,還是在旅途中面對各種氣候變化,保持皮膚的水分平衡對我來說至關重要。保濕化妝水不僅能迅速為皮膚補水,還能提升後續保養品的吸收效率。 曾經,我的保養程序簡單到只包括清潔和隨意上乳液
Thumbnail
這本書記錄了作者廖瞇與弟弟滌的對話過程,以及如何通過對話再次與父親和母親對話,同時也是對自己的深入挖掘。通過書寫,作者細膩處理了家人之間最難以解開的謎題,並療癒自己與家人的心靈困境。這是一部近身拍攝的紙上紀錄片,讀者將在堆疊細碎的家庭日常裡,見證他人的家庭現實,並與之產生共鳴。
Thumbnail
還記得第一次失戀,椎心痛骨 意外與新詩相遇,嘗試用文字堆疊內心的苦楚,還有曾經溺愛中的美好。 《淺眠於妳》或許拙劣但十年過去了,我仍醉心此詩。 再獻上後兩首,紀念妳留給我的…… 《淺眠於妳》 曾經那麼巧,在人海中遇見彼此 那麼的剛好,眼神交會的那一次 從此只有你,左思右
Thumbnail
終至不會流於「人們仰望權威」的複製及誤解,終究是你們晃動了你們自己。
Thumbnail
死亡焦慮原來一直在我的思緒中存在著,但是我並未察覺。
Thumbnail
「被療癒」這個詞會不會有點泛濫?現代人壓力大,必須將理性思考放在第一優先,而將感性的一面埋在心底,所以當自己的感性被激發時,不知如何形容就用被「療癒了」這個詞。
最近總是感覺步調停滯,看過浩子的書"世界是我的信仰"後,發現有些東西其實在累積,在我沒發現的時候,其實慢慢成長與遺忘了!像是我的體重、腹肌XD,默默的減少與增加,很多看似無用的努力,都開始發芽了!浩子說一點一滴很小的事件累積成書籍,非常認同的反思自己的人生,小小的故事與所遇事件建構我的原則與價值觀,
Thumbnail
製造公差是你總是會碰到的東西,因此設計時沒有適當考量下很容易發生問題。 不談電子產業,光是我從網路買回來的DIY家具就常常有組不上去的問題,這很明顯就是公差太大。大東西尚且如此,小東西更是得斤斤計較了。 在計算公差堆疊的時候的基本邏輯是:  目標尺寸鏈 -> 決定計算方法 -> 設定公差或是設定設計
Thumbnail
在人生當中,我們必須不斷做出抉擇。在每次抉擇時,我們或許會想多了解自己以及眼前的情境,再根據這些了解做出行動,並預測這些行動將帶來什麼後果。越不了解自己與情境,行動就越盲目,也越看不到未來。幸運的是,大部分人都有一定的了解自己與了解他人的能力。
Thumbnail
早期的水手條紋搭配海軍領 有時候,是基底覆上幾何般的線條與形狀,只是它們是直挺挺地朝著另一端的盡頭延伸;有時候,是層層線條反覆結合在一起,漸漸成為一大片能包覆在我們身上的個性。 古著灰色襯衫。來自:MIMIGUZHU咪咪古著 線條可以擴張人類視覺反應,同時從雙目中感受到這些拖曳痕跡般的浪漫