LeetCode每日一题 | 2938.区分黑球与白球 | 数组逆序+计数器
📌题目描述
大家好，今天要分享的是一道有趣的LeetCode题目：Separate Black and White Balls！这道题的任务是计算将字符串中的所有’1’移动到所有’0’之前所需的最小步数。🤔
📌思路分析
在正式开始解题前，先来梳理一下思路：
- 统计0的数量：每当遇到一个’0’，意味着后续所有的’1’都需要在它前面，所以我们要记录已经遇到的’0’的数量。
- 累加步数：每当遇到一个’1’，它需要移动的步数等于它后面的’0’的数量，所以我们累加这些步数即可。
📌为什么选择逆序遍历🤔
在这里，我们需要计算每一个’1’需要移动多少步才能到达所有’0’之前。如果我们从左到右遍历，当遇到一个’1’时，我们不知道它需要移动多少步，因为我们还不知道它后面有多少个’0’。
通过逆序遍历，我们可以在一次遍历中完成所有计算，因为我们在遍历时已经知道当前’1’之后有多少个’0’了。这样就可以避免重复计算和不必要的复杂度。
📌代码实现
下面是具体的代码实现，很简单哦～😎
object Solution {def minimumSteps(s: String): Long = {var res = 0Lvar zeroCnt = 0Lfor (i <- s.toCharArray.indices.reverse) {if (s(i) == '0') zeroCnt += 1if (s(i) == '1') res += zeroCnt}res}
}
📌代码解析
- 初始化两个变量：
res用来记录总的步数，zeroCnt用来记录已经遇到的’0’的数量。 - 逆序遍历字符串：从右向左遍历字符串的每一个字符。
- 更新计数器：遇到’0’时，
zeroCnt增加；遇到’1’时，将zeroCnt累加到res中。 - 返回结果：最终返回累加的结果
res。
📌数据结构和时空复杂度分析
主要数据结构：本题主要使用的是简单的变量 res 和 zeroCnt 来存储计算结果和计数。
时间复杂度：O(n)
字符串的长度为 n，我们遍历字符串一次，因此时间复杂度为 O(n)。
空间复杂度：O(1)
我们只使用了常数个额外的变量来存储结果和计数，没有使用与输入大小相关的额外空间，因此空间复杂度为 O(1)。
📌解题心得
这道题的关键在于如何高效地计算每一个’1’需要移动的步数。通过逆序遍历和累加zeroCnt，我们可以在一次遍历中完成计算，避免了重复计算和不必要的复杂度。这种思路不仅仅适用于这道题，也可以拓展到其他类似的移动和计数问题中。✨
📌Tags
#算法 #LeetCode #每日一题 #编程技巧 #Scala #高效解题
📌总结
这道题其实是一个思路非常清晰的题目，通过逆序遍历和计数器的巧妙使用，我们可以在一次遍历中完成所有计算。希望大家看完后能有所收获，继续加油刷题吧！💪💻
如果你觉得这篇解题思路对你有帮助，请点赞👍并分享给更多的小伙伴吧！我们下期再见～👋
记得关注我获取更多LeetCode题解和编程技巧哦！🌟