今天這題第一個想法是有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;
}
};
好像就這樣