推 cities516: C++好難喔 10/15 15:06
→ orangeNoob: 我也好想用python 可是C++還是得練習 :( 10/15 15:08
推 DJYOSHITAKA: 別卷了 10/15 15:34
今天這題第一個想法是有bubble sort的既視感
不過想說應該有更快的方法
觀察後發現可以簡單的動態規劃一下
假設S[i]是 0在左邊 1在右邊 已經排好的字串
那根據下個讀到的字元是0還是1就可以計算新的S[i+1]所需要交換的次數
class Solution {
public:
long long minimumSteps(string s) {
long long one_num = 0;
long long sum = 0;
bool flag = false;
for (long long i = 0; i < s.length();i++) {
if (!flag && s[i] != '1') continue;
else {
if (s[i] == '1') {
flag = true;
one_num += 1;
}
else
sum += one_num;
}
}
return sum;
}
};
好像就這樣
--
https://i.imgur.com/7bQdjkb.png
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.241.135.214 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1728975875.A.54B.html