5.0.1 游戏规则
Robert Sedgewick Kevin Wayne
为了简洁高效,我们将使用 Java 的 String 类来表示字符串,但我们将有意识地尽量少使用该类的方法以使算法能够适用于其他字符串数据类型以及其他编程语言。我们已经在 1.2 节中详细介绍过各种字符串,这里简要回顾一下它们最主要的性质。
字符。String 是由一系列字符组成的。字符的类型是 char,可能有
个值。数十年以来,程序员的注意力都局限于 7 位 ASCII 码(请见表 5.5.4)或是 8 位扩展 ASCII 码表示的字符,但许多现代的应用程序都已经需要使用 16 位 Unicode 编码了。
![](https://static001.geekbang.org/files/resource/ebook/100010/image01622.gif)
不可变性。String 对象是不可变的,因此可以将它们用于赋值语句、作为函数的参数或是返回值,而不用担心它们的值会发生变化。
索引。我们最常完成的操作就是从某个字符串中提取一个特定的字符,即 Java 的 String 类的 charAt() 方法。我们希望 charAt() 方法能够在常数时间内完成,就好像字符串是保存在一个 char[] 数组中一样。根据第 1 章中的讨论,这种期望是非常合理的。
长度。在 Java 中,String 类型的 length() 方法实现了获取字符串的长度的操作。同样,我们也希望 length() 方法能够在常数时间内完成,这也是合情合理的,尽管在某些编程环境中实现这一点并不容易。
![](https://static001.geekbang.org/files/resource/ebook/100010/image01623.gif)
图 5.0.1 String 类型的基本常数时间操作
子字符串。Java 的 substring() 方法实现了提取特定的子字符串的操作。同样,我们也希望这个方法能够在常数时间内完成,Java 的标准实现也做到了这一点。如果你还不熟悉 substring() 方法和为什么它只需要常数时间,请务必重新阅读 1.2 节中讨论的 Java 字符串的标准实现(请见表 1.2.7 和图 1.4.10)。
公开
同步至部落
取消
完成
0/2000
笔记
复制
AI
- 深入了解
- 翻译
- 解释
- 总结
![](https://static001.geekbang.org/resource/image/d0/e4/d0880927e2a522a038be2d04bf19dfe4.png)
本文介绍了在 Java 中使用 String 类表示字符串的基本规则和操作。文章首先强调了字符串的不可变性和字符的索引操作,以及获取字符串长度和提取子字符串的常数时间操作。此外,文章还介绍了字符串的连接操作和字符数组的表示方法。作者指出,理解这些操作的运行效率是理解许多字符串处理算法效率的关键部分,并提到不同编程语言中的 String 类实现可能存在性能差异。在文章的后半部分,作者强调了在性能优先的应用场景中,用例在 String 类和字符数组表示方法之间权衡的重要性。总的来说,本文通过简洁清晰的语言,为读者提供了在 Java 中处理字符串的基本规则和操作,以及在不同编程语言中可能面临的挑战和机遇。
仅可试看部分内容,如需阅读全部内容,请付费购买文章所属专栏
《算法(第 4 版)》
《算法(第 4 版)》
立即购买
登录 后留言
精选留言
由作者筛选后的优质留言将会公开显示,欢迎踊跃留言。
收起评论