Re: [閒聊] 每日leetcode已回收
※ 引述 《enmeitiryous (enmeitiryous)》 之銘言：
:
: 1653 minimun deletion make string balance
: 題目:
: 給你一個只有a,b兩種字母構成的字串s，求最少的deletion數使的新字串中
: a一定出現在任一b前面
:
思路:
建立一個陣列
記錄當前位子出現的a b
利用前綴合來知道如果在這個位子的話
要刪除多少a 或b可以讓字串符合條件
或是
我直接全部刪掉一種
姆咪
```cpp
class Solution {
public:
int minimumDeletions(string s)
{
int len = s.size();
int as= 0;
int bs=0;
vector<int> aaa(len , 0);
vector<int> bbb(len , 0);
int res = len;
for(int i = 0; i < len ; i++)
{
if(s[i] == 'a')as++;
aaa[i] = as;
if(s[i] == 'b')bs++;
bbb[i] = bs;
}
if(as == 0)return 0;
if(bs == 0)return 0;
for(int i = 0 ; i < len ; i ++)
{
res = min(bbb[i] + aaa[len-1] - aaa[i] , res);
}
res = min(aaa[len-1] , res);
res = min(bbb[len-1] , res);
return res;
}
};
```
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.162.5.215 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1722309240.A.464.html
推
07/30 11:14,
1年前
, 1F
07/30 11:14, 1F
→
07/30 11:15,
1年前
, 2F
07/30 11:15, 2F
推
07/30 11:15,
1年前
, 3F
07/30 11:15, 3F
討論串 (同標題文章)