今天这题第一个想法是有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;
}
};
好像就这样