第一題

題目

刪除公共字符

思路

模擬：
遇到需要刪除的字符，則不添加到結果中

代碼

第二題

題目：

兩個鏈表的第一個公共結點

思路

模擬：

• 先計算兩個鏈表的長度
• 再讓長的先走差值步
• 最后同時走，走到結束，如果沒有相遇則為空

代碼

第三題

題目：

mari和shiny

思路

動態規劃——多狀態的線性 dp
狀態表示：

• s[i]表示：字符串[0, i]中，有多少個s
• h[i]表示：字符串[0, i]中，有多少個sh
• y[i]表示：字符串[0, i]中，有多少個shy

狀態轉移方程：
s[i]：

• str[i] == 's'，s[i - 1] + 1
• str[i] != 's'，s[i - 1]

h[i]：

• str[i] == 'h'，s[i - 1] + h[i - 1]
• str[i] != 'h'，h[i - 1]

y[i]：

• str[i] == 'y'，h[i - 1] + y[i - 1]
• str[i] != 'y'，y[i - 1]

結果返回：y[n - 1]

優化
我們發現只有當當前字符為有效時（即shy），才會相加，否則等于之前的值；

• s：當前 's'的數量
• h：當前 'sh' 子序列的數量
• y：當前 'shy' 子序列的數量

代碼