付費限定

堆疊應用+模擬: 移除字串中的星號_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題 解析+統整你目前無法檢視以下內容,可能因為尚未登入,或沒有該房間的查看權限。
86會員
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
美國總統大選只剩下三天, 我們觀察一整週民調與金融市場的變化(包含賭局), 到本週五下午3:00前為止, 誰是美國總統幾乎大概可以猜到60-70%的機率, 本篇文章就是以大選結局為主軸來討論近期甚至到未來四年美股可能的改變
Thumbnail
這本書記錄了作者廖瞇與弟弟滌的對話過程,以及如何通過對話再次與父親和母親對話,同時也是對自己的深入挖掘。通過書寫,作者細膩處理了家人之間最難以解開的謎題,並療癒自己與家人的心靈困境。這是一部近身拍攝的紙上紀錄片,讀者將在堆疊細碎的家庭日常裡,見證他人的家庭現實,並與之產生共鳴。
Thumbnail
還記得第一次失戀,椎心痛骨 意外與新詩相遇,嘗試用文字堆疊內心的苦楚,還有曾經溺愛中的美好。 《淺眠於妳》或許拙劣但十年過去了,我仍醉心此詩。 再獻上後兩首,紀念妳留給我的…… 《淺眠於妳》 曾經那麼巧,在人海中遇見彼此 那麼的剛好,眼神交會的那一次 從此只有你,左思右
Thumbnail
終至不會流於「人們仰望權威」的複製及誤解,終究是你們晃動了你們自己。
Thumbnail
死亡焦慮原來一直在我的思緒中存在著,但是我並未察覺。
Thumbnail
「被療癒」這個詞會不會有點泛濫?現代人壓力大,必須將理性思考放在第一優先,而將感性的一面埋在心底,所以當自己的感性被激發時,不知如何形容就用被「療癒了」這個詞。
最近總是感覺步調停滯,看過浩子的書"世界是我的信仰"後,發現有些東西其實在累積,在我沒發現的時候,其實慢慢成長與遺忘了!像是我的體重、腹肌XD,默默的減少與增加,很多看似無用的努力,都開始發芽了!浩子說一點一滴很小的事件累積成書籍,非常認同的反思自己的人生,小小的故事與所遇事件建構我的原則與價值觀,
Thumbnail
製造公差是你總是會碰到的東西,因此設計時沒有適當考量下很容易發生問題。 不談電子產業,光是我從網路買回來的DIY家具就常常有組不上去的問題,這很明顯就是公差太大。大東西尚且如此,小東西更是得斤斤計較了。 在計算公差堆疊的時候的基本邏輯是:  目標尺寸鏈 -> 決定計算方法 -> 設定公差或是設定設計
Thumbnail
在人生當中,我們必須不斷做出抉擇。在每次抉擇時,我們或許會想多了解自己以及眼前的情境,再根據這些了解做出行動,並預測這些行動將帶來什麼後果。越不了解自己與情境,行動就越盲目,也越看不到未來。幸運的是,大部分人都有一定的了解自己與了解他人的能力。
Thumbnail
早期的水手條紋搭配海軍領 有時候,是基底覆上幾何般的線條與形狀,只是它們是直挺挺地朝著另一端的盡頭延伸;有時候,是層層線條反覆結合在一起,漸漸成為一大片能包覆在我們身上的個性。 古著灰色襯衫。來自:MIMIGUZHU咪咪古著 線條可以擴張人類視覺反應,同時從雙目中感受到這些拖曳痕跡般的浪漫
Thumbnail
這個秋,Chill 嗨嗨!穿搭美美去賞楓,裝備款款去露營⋯⋯你的秋天怎麼過?秋日 To Do List 等你分享! 秋季全站徵文,我們準備了五個創作主題,參賽還有機會獲得「火烤兩用鍋」,一起來看看如何參加吧~
Thumbnail
美國總統大選只剩下三天, 我們觀察一整週民調與金融市場的變化(包含賭局), 到本週五下午3:00前為止, 誰是美國總統幾乎大概可以猜到60-70%的機率, 本篇文章就是以大選結局為主軸來討論近期甚至到未來四年美股可能的改變
Thumbnail
這本書記錄了作者廖瞇與弟弟滌的對話過程,以及如何通過對話再次與父親和母親對話,同時也是對自己的深入挖掘。通過書寫,作者細膩處理了家人之間最難以解開的謎題,並療癒自己與家人的心靈困境。這是一部近身拍攝的紙上紀錄片,讀者將在堆疊細碎的家庭日常裡,見證他人的家庭現實,並與之產生共鳴。
Thumbnail
還記得第一次失戀,椎心痛骨 意外與新詩相遇,嘗試用文字堆疊內心的苦楚,還有曾經溺愛中的美好。 《淺眠於妳》或許拙劣但十年過去了,我仍醉心此詩。 再獻上後兩首,紀念妳留給我的…… 《淺眠於妳》 曾經那麼巧,在人海中遇見彼此 那麼的剛好,眼神交會的那一次 從此只有你,左思右
Thumbnail
終至不會流於「人們仰望權威」的複製及誤解,終究是你們晃動了你們自己。
Thumbnail
死亡焦慮原來一直在我的思緒中存在著,但是我並未察覺。
Thumbnail
「被療癒」這個詞會不會有點泛濫?現代人壓力大,必須將理性思考放在第一優先,而將感性的一面埋在心底,所以當自己的感性被激發時,不知如何形容就用被「療癒了」這個詞。
最近總是感覺步調停滯,看過浩子的書"世界是我的信仰"後,發現有些東西其實在累積,在我沒發現的時候,其實慢慢成長與遺忘了!像是我的體重、腹肌XD,默默的減少與增加,很多看似無用的努力,都開始發芽了!浩子說一點一滴很小的事件累積成書籍,非常認同的反思自己的人生,小小的故事與所遇事件建構我的原則與價值觀,
Thumbnail
製造公差是你總是會碰到的東西,因此設計時沒有適當考量下很容易發生問題。 不談電子產業,光是我從網路買回來的DIY家具就常常有組不上去的問題,這很明顯就是公差太大。大東西尚且如此,小東西更是得斤斤計較了。 在計算公差堆疊的時候的基本邏輯是:  目標尺寸鏈 -> 決定計算方法 -> 設定公差或是設定設計
Thumbnail
在人生當中,我們必須不斷做出抉擇。在每次抉擇時,我們或許會想多了解自己以及眼前的情境,再根據這些了解做出行動,並預測這些行動將帶來什麼後果。越不了解自己與情境,行動就越盲目,也越看不到未來。幸運的是,大部分人都有一定的了解自己與了解他人的能力。
Thumbnail
早期的水手條紋搭配海軍領 有時候,是基底覆上幾何般的線條與形狀,只是它們是直挺挺地朝著另一端的盡頭延伸;有時候,是層層線條反覆結合在一起,漸漸成為一大片能包覆在我們身上的個性。 古著灰色襯衫。來自:MIMIGUZHU咪咪古著 線條可以擴張人類視覺反應,同時從雙目中感受到這些拖曳痕跡般的浪漫