本文主要是介绍Leetcode2938. 区分黑球与白球，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Every day a Leetcode
题目来源：2938. 区分黑球与白球
解法1：贪心
把 ‘0’ 挪到相应的位置。
类似于冒泡排序的思想，把 ‘0’ 挪到相应的位置。
示例：
代码：
/** @lc app=leetcode.cn id=2938 lang=cpp** [2938] 区分黑球与白球*/// @lc code=start
class Solution
{
public:long long minimumSteps(string s){int white = 0;long long steps = 0;for (int i = 0; i < s.length(); i++){if (s[i] == '0'){steps += (long long)(i - white);white++;}}return steps;}
};
// @lc code=end
结果：
复杂度分析：
时间复杂度：O(n)，其中 n 是字符串 s 的长度。
空间复杂度：O(1)。
解法2：贪心
操作次数 = Σ(每个 ‘0’ 左边的 ‘1’ 的个数)。
代码：
/** @lc app=leetcode.cn id=2938 lang=cpp** [2938] 区分黑球与白球*/// @lc code=start
// class Solution
// {
// public:
// long long minimumSteps(string s)
// {
// int white = 0;
// long long steps = 0;
// for (int i = 0; i < s.length(); i++)
// {
// if (s[i] == '0')
// {
// steps += (long long)(i - white);
// white++;
// }
// }
// return steps;
// }
// };class Solution
{
public:long long minimumSteps(string s){int black = 0;long long steps = 0;for (int i = 0; i < s.length(); i++){if (s[i] == '0')steps += black;elseblack++;}return steps;}
};
// @lc code=end
结果：
复杂度分析：
时间复杂度：O(n)，其中 n 是字符串 s 的长度。
空间复杂度：O(1)。
这篇关于Leetcode2938. 区分黑球与白球的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
