leetcode 2938.区分白球与黑球(传送门)
思路:把1放右边,0放左边,只要把0全部放好那么1肯定也全部放好了。考虑将靠左的0放在靠左的位置,也就是第i个0要放到下标为i-1的位置,所以直接遍历并更新已就位的0的个数即可。
时间复杂度 O(n)
class Solution {
public:long long minimumSteps(string s) {long long n=s.length(),sum=0,ct=0;for(int i=0;i<n;i++){if(s[i]=='0'){sum+=i-ct;ct++;}}return sum;}
};