Re: [閒聊] 每日leetcode
※ 引述《dont (dont)》之銘言：
: 1963. Minimum Number of Swaps to Make the String Balanced
: ## 思路
: 計算不match的pair數量, swap次數=(res+1) // 2
#思路
一開始：靠杯 這樣是隨便換嗎
這樣我換一次就要check valid嗎
想了一下：改成+1 -1
做成線段樹check prefix sum
小於等於0就好ㄟ
不對啊這樣我直接count最大的就好啊
換一次就是+2
+1 再 /2
來送ㄉ欸
class Solution {
public:
int minSwaps(string s) {
int mx = 0, cnt = 0;
for(char c: s){
if(c == '['){
cnt--;
}
else cnt++;
mx = max(mx, cnt);
}
return (mx + 1)/2;
}
};
-----
Sent from JPTT on my iPad
--
很姆的咪
姆之咪
http://i.imgur.com/5sw7QOj.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.205.121.194 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1728356219.A.84D.html
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 963 之 1548 篇)：