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

2024-06-07 08:52

本文主要是介绍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 = 0Lvar zeroCnt = 0Lfor (i <- s.toCharArray.indices.reverse) {if (s(i) == '0') zeroCnt += 1if (s(i) == '1') res += zeroCnt}res}
}
📌代码解析
  1. 初始化两个变量res 用来记录总的步数,zeroCnt 用来记录已经遇到的’0’的数量。
  2. 逆序遍历字符串:从右向左遍历字符串的每一个字符。
  3. 更新计数器:遇到’0’时,zeroCnt增加;遇到’1’时,将zeroCnt累加到res中。
  4. 返回结果:最终返回累加的结果res
📌数据结构和时空复杂度分析

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

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

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

📌解题心得

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

📌Tags

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

📌总结

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

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


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

这篇关于LeetCode每日一题 | 2938.区分黑球与白球 | 数组逆序+计数器的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1038716

相关文章

Java数组初始化的五种方式

《Java数组初始化的五种方式》数组是Java中最基础且常用的数据结构之一,其初始化方式多样且各具特点,本文详细讲解Java数组初始化的五种方式,分析其适用场景、优劣势对比及注意事项,帮助避免常见陷阱... 目录1. 静态初始化:简洁但固定代码示例核心特点适用场景注意事项2. 动态初始化:灵活但需手动管理代

C++中初始化二维数组的几种常见方法

《C++中初始化二维数组的几种常见方法》本文详细介绍了在C++中初始化二维数组的不同方式,包括静态初始化、循环、全部为零、部分初始化、std::array和std::vector,以及std::vec... 目录1. 静态初始化2. 使用循环初始化3. 全部初始化为零4. 部分初始化5. 使用 std::a

shell编程之函数与数组的使用详解

《shell编程之函数与数组的使用详解》:本文主要介绍shell编程之函数与数组的使用,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录shell函数函数的用法俩个数求和系统资源监控并报警函数函数变量的作用范围函数的参数递归函数shell数组获取数组的长度读取某下的

使用Sentinel自定义返回和实现区分来源方式

《使用Sentinel自定义返回和实现区分来源方式》:本文主要介绍使用Sentinel自定义返回和实现区分来源方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Sentinel自定义返回和实现区分来源1. 自定义错误返回2. 实现区分来源总结Sentinel自定

C++原地删除有序数组重复项的N种方法

《C++原地删除有序数组重复项的N种方法》给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度,不要使用额外的数组空间,你必须在原地修改输入数组并在使用O(... 目录一、问题二、问题分析三、算法实现四、问题变体:最多保留两次五、分析和代码实现5.1、问题分析5.

Java中数组转换为列表的两种实现方式(超简单)

《Java中数组转换为列表的两种实现方式(超简单)》本文介绍了在Java中将数组转换为列表的两种常见方法使用Arrays.asList和Java8的StreamAPI,Arrays.asList方法简... 目录1. 使用Java Collections框架(Arrays.asList)1.1 示例代码1.

C++一个数组赋值给另一个数组方式

《C++一个数组赋值给另一个数组方式》文章介绍了三种在C++中将一个数组赋值给另一个数组的方法:使用循环逐个元素赋值、使用标准库函数std::copy或std::memcpy以及使用标准库容器,每种方... 目录C++一个数组赋值给另一个数组循环遍历赋值使用标准库中的函数 std::copy 或 std::

C++初始化数组的几种常见方法(简单易懂)

《C++初始化数组的几种常见方法(简单易懂)》本文介绍了C++中数组的初始化方法,包括一维数组和二维数组的初始化,以及用new动态初始化数组,在C++11及以上版本中,还提供了使用std::array... 目录1、初始化一维数组1.1、使用列表初始化(推荐方式)1.2、初始化部分列表1.3、使用std::

C++ Primer 多维数组的使用

《C++Primer多维数组的使用》本文主要介绍了多维数组在C++语言中的定义、初始化、下标引用以及使用范围for语句处理多维数组的方法,具有一定的参考价值,感兴趣的可以了解一下... 目录多维数组多维数组的初始化多维数组的下标引用使用范围for语句处理多维数组指针和多维数组多维数组严格来说,C++语言没

Java 字符数组转字符串的常用方法

《Java字符数组转字符串的常用方法》文章总结了在Java中将字符数组转换为字符串的几种常用方法,包括使用String构造函数、String.valueOf()方法、StringBuilder以及A... 目录1. 使用String构造函数1.1 基本转换方法1.2 注意事项2. 使用String.valu