LeetCode每日一题 | 2938.区分黑球与白球 | 数组逆序+计数器

📌题目描述

大家好，今天要分享的是一道有趣的LeetCode题目：Separate Black and White Balls！这道题的任务是计算将字符串中的所有’1’移动到所有’0’之前所需的最小步数。🤔

📌思路分析

在正式开始解题前，先来梳理一下思路：

1. 统计0的数量：每当遇到一个’0’，意味着后续所有的’1’都需要在它前面，所以我们要记录已经遇到的’0’的数量。
2. 累加步数：每当遇到一个’1’，它需要移动的步数等于它后面的’0’的数量，所以我们累加这些步数即可。

📌为什么选择逆序遍历🤔

在这里，我们需要计算每一个’1’需要移动多少步才能到达所有’0’之前。如果我们从左到右遍历，当遇到一个’1’时，我们不知道它需要移动多少步，因为我们还不知道它后面有多少个’0’。

通过逆序遍历，我们可以在一次遍历中完成所有计算，因为我们在遍历时已经知道当前’1’之后有多少个’0’了。这样就可以避免重复计算和不必要的复杂度。

📌代码实现

下面是具体的代码实现，很简单哦～😎

object Solution {
  def minimumSteps(s: String): Long = {
    var res = 0L
    var zeroCnt = 0L
    for (i <- s.toCharArray.indices.reverse) {
      if (s(i) == '0') zeroCnt += 1
      if (s(i) == '1') res += zeroCnt
    }
    res
  }
}

📌代码解析

1. 初始化两个变量：res 用来记录总的步数，zeroCnt 用来记录已经遇到的’0’的数量。
2. 逆序遍历字符串：从右向左遍历字符串的每一个字符。
3. 更新计数器：遇到’0’时，zeroCnt增加；遇到’1’时，将zeroCnt累加到res中。
4. 返回结果：最终返回累加的结果res。

📌数据结构和时空复杂度分析

主要数据结构：本题主要使用的是简单的变量 res 和 zeroCnt 来存储计算结果和计数。

时间复杂度：O(n)
字符串的长度为 n，我们遍历字符串一次，因此时间复杂度为 O(n)。

空间复杂度：O(1)
我们只使用了常数个额外的变量来存储结果和计数，没有使用与输入大小相关的额外空间，因此空间复杂度为 O(1)。

📌解题心得

这道题的关键在于如何高效地计算每一个’1’需要移动的步数。通过逆序遍历和累加zeroCnt，我们可以在一次遍历中完成计算，避免了重复计算和不必要的复杂度。这种思路不仅仅适用于这道题，也可以拓展到其他类似的移动和计数问题中。✨

📌Tags

#算法 #LeetCode #每日一题 #编程技巧 #Scala #高效解题

📌总结

这道题其实是一个思路非常清晰的题目，通过逆序遍历和计数器的巧妙使用，我们可以在一次遍历中完成所有计算。希望大家看完后能有所收获，继续加油刷题吧！💪💻

如果你觉得这篇解题思路对你有帮助，请点赞👍并分享给更多的小伙伴吧！我们下期再见～👋

记得关注我获取更多LeetCode题解和编程技巧哦！🌟