算法理解（五）数组和字符串
数组作为一种基础的数据结构，因其高效的存储和访问方式，在早期计算机科学的发展中迅速占据了重要地位。尽管现代编程语言提供了更高级的数据结构（如链表、集合、哈希表等），但数组依然是许多应用中不可或缺的工具。其连续的内存布局、快速的访问时间使其在科学计算、图像处理和机器学习中依然发挥着重要作用。字符串的发展从早期的简单字符编码到如今支持全球语言的 Unicode 标准，伴随着计算机科学的发展而不断演进。
一、是什么
1.1 数组
数组是一种数据结构，用于存储相同类型的元素集合。数组中的元素在内存中是连续存放的，因此你可以通过索引（通常从0开始）直接访问每个元素。下面是对数组的详细介绍：
数组的基本特点
- 固定大小：数组的大小在创建时必须指定，之后不能动态改变。这意味着你必须提前知道需要存储多少数据。
- 元素类型相同：数组中的所有元素类型必须相同，例如整型数组只能存储整数，字符数组只能存储字符。
- 连续内存空间：数组中的元素在内存中是连续排列的，这让数组具有很高的访问效率。
- 通过索引访问：每个元素都有唯一的索引，索引从0开始（在大多数编程语言中），你可以通过索引快速访问任何元素。
数组的优点
- 快速访问：因为数组是连续存储的，能够通过索引直接访问任意元素，速度很快。
- 占用空间紧凑：数组在内存中连续存放，节省了空间。
数组的缺点
- 固定大小：数组的大小在创建时确定，之后不能改变。如果事先不知道需要存储的元素数量，可能会导致空间浪费或不足。
- 插入和删除不便：插入或删除元素时，需要移动数组中的其他元素，操作效率较低。
实际应用
数组通常用于存储一组相关的数据，如一组成绩、一段文本中的字符等。它们广泛用于各种算法中，尤其在排序和查找操作中。
1.2 字符串
字符串（String）是计算机编程中的一种数据类型，用来表示文本或字符序列。它通常由一组字符组成，字符可以是字母、数字、符号或其他可以表示的文本符号。
字符串的特点：
-
不可变性： 在许多编程语言（如 Python、Java 等）中，字符串是不可变的。即一旦创建了一个字符串，不能直接修改它的内容。如果需要对字符串进行修改，则会创建一个新的字符串对象。
-
长度可变： 字符串的长度可以是任意的，可以包含零个字符（空字符串）到非常多的字符。
-
索引和切片： 字符串中的每个字符都有一个位置索引。编程语言通常从 0 开始计数，因此可以通过索引访问字符串中的单个字符。还可以通过“切片”操作获取子字符串。
-
常见的操作：
- 拼接：将两个或多个字符串连接在一起。
- 查找：查找某个字符或子字符串在字符串中的位置。
- 替换：将字符串中的某个部分替换为其他内容。
- 大小写转换：将字符串转换为全大写、全小写等。
字符串的用途：
字符串在编程中有非常广泛的应用，例如：
- 存储和显示用户输入。
- 构建和操作文件路径。
- 处理自然语言文本，如在 NLP 任务中解析和生成文本。
二、为什么
2.1 数组
数组作为一种基础的数据结构，提供了高效的存储和访问机制。其主要优点和应用场景如下：
1. 快速访问数据
数组的最大特点之一是可以通过索引快速访问元素。这对于需要频繁读取数据的场景非常有用。例如，当你有一组学生的成绩，想知道某个特定学生的成绩时，通过数组可以快速定位。
例子：
students_scores = [85, 92, 78, 90, 88]
# 直接访问第三个学生的成绩
print(students_scores[2]) # 输出 78
2. 有序数据的存储
数组用于存储有序的数据。例如，当你想表示某个月份每天的温度记录时，可以用数组按照时间顺序来存储。
3. 节省内存
数组在内存中是连续存放的，这不仅保证了高效的访问，还能够减少内存的碎片化问题。与其他数据结构（如链表）相比，数组更紧凑，因为链表需要存储额外的指针。
4. 便于算法设计
数组作为很多复杂数据结构（如堆、栈、队列、矩阵等）的基础，在各种算法中具有重要地位。排序算法（如快速排序、归并排序）和查找算法（如二分查找）都依赖数组的结构来提高效率。
5. 适合静态数据
如果数据是固定大小且在使用过程中不需要频繁更改（如图片的像素点、音频的采样点等），数组可以作为非常合适的数据存储方式。
数组的历史
1. 起源
数组的概念可以追溯到早期的计算机科学发展时期，尤其是数值分析和数值计算的需求。早在20世纪40年代，随着电子计算机的诞生，科学家们发现需要一种结构来高效地存储和访问大规模的数字数据。最早的计算机程序设计语言之一是FORTRAN（1957年发布），其中就有对数组的支持。这使得科学家可以轻松地处理数值计算问题，如求解方程、矩阵运算等。
2. 语言中的引入
数组作为最基础的数据结构，几乎在所有编程语言中都有实现。在早期的汇编语言中，数组是通过固定的内存地址加上偏移量来实现的。随着编程语言的发展，高级语言如C语言、Pascal、BASIC等都引入了数组概念，使程序员能够更方便地管理数据。
- C语言中的数组：C语言（1972年发布）对数组的实现非常经典。C中的数组就是一块连续的内存区域，可以通过指针操作直接访问和修改数组元素。C语言对数组操作的高效性奠定了其在系统编程中的重要地位。
- Java和Python中的数组：Java和Python等现代编程语言也保留了数组的概念，虽然在这些语言中数组的使用更加高层次，但其背后依然依赖连续的内存管理。
3. 数组的扩展与变种
随着时间的推移，数组的概念也有所扩展。为了克服数组的一些缺点，如固定大小问题，人们设计了动态数组（如C++中的std::vector，Java中的ArrayList，Python中的列表 list）。这些变种提供了更灵活的操作方式，但其底层依然是基于传统的数组概念。
4. 多维数组和矩阵
在20世纪60年代和70年代，科学计算的兴起使得对多维数组的需求增加。多维数组允许以二维或更高维度的方式存储数据，这在图像处理、物理模拟、科学计算等领域非常重要。例如，一个二维数组可以用来表示矩阵，三维数组可以表示3D网格数据。
5. 现代应用中的数组
- 科学计算与机器学习：在现代计算中，数组仍然是科学计算的核心。例如，Python中的NumPy库是基于数组的，专门用于处理大规模矩阵和向量运算。机器学习中的模型训练、图像处理、数据处理等都高度依赖数组结构。
- 数据库与存储技术：数组概念也被引入到数据库系统中，用于高效存储和检索数据，尤其在列式存储数据库中，数据往往以数组的形式存储在磁盘上。
总结
数组作为一种基础的数据结构，因其高效的存储和访问方式，在早期计算机科学的发展中迅速占据了重要地位。尽管现代编程语言提供了更高级的数据结构（如链表、集合、哈希表等），但数组依然是许多应用中不可或缺的工具。其连续的内存布局、快速的访问时间使其在科学计算、图像处理和机器学习中依然发挥着重要作用。
2.2 字符串
字符串是计算机处理和表示文本信息的基础。在计算机和编程中，字符串起着至关重要的作用，原因包括：
-
文本处理： 许多应用程序都需要处理文本，例如：聊天应用、文档处理、网页设计、命令行输入等等。字符串为这些场景提供了表示和存储文本的结构。
-
数据交互： 在用户与程序的交互中，很多输入和输出都是基于文本的。例如，用户在网页上输入用户名和密码、系统生成的日志文件等，这些都需要使用字符串来存储和传递信息。
-
数据传输： 在不同系统或程序之间传递数据时，字符串通常是最常见的格式。比如，JSON 或 XML 文件，它们是以字符串的形式构建的结构化数据，用于不同应用程序之间进行数据交换。
-
信息存储： 字符串不仅可以存储单个字符，还可以存储词语、句子、段落甚至整个文档。许多文件格式（如纯文本文件）本质上都是字符串。
-
代码表示： 编程语言中，代码本身也可以以字符串的形式表示。例如，编写脚本、动态生成代码、解析代码时，字符串是非常常用的工具。
字符串的历史
字符串的历史和计算机科学的早期发展紧密相关。随着计算机和编程语言的发展，字符串的概念逐渐演变并变得更加复杂和多样化。
-
早期计算机与字符编码： 在早期的计算机时代，计算机只能处理数字。因此，工程师们发明了字符编码（如 ASCII）来让计算机能够理解和处理文本信息。每个字符（如字母、数字或符号）都被分配了一个唯一的数字编码，字符串则是这些编码的有序序列。
ASCII（American Standard Code for Information Interchange） 是最早的标准字符编码系统之一，它定义了128个字符，包括英文字符、数字、标点符号和一些控制字符。ASCII 在20世纪60年代发展起来，最初用于电报系统，后来成为早期计算机系统处理文本的基础。
-
扩展字符集和 Unicode： 随着计算机的全球化，ASCII 的局限性逐渐显现。它只能处理128个字符，无法支持非英文字符，如中文、日文、阿拉伯文等。为了解决这个问题，字符集得到了扩展，如 ISO 8859 系列编码和 Windows-1252。
但是，为了彻底解决全球语言字符的兼容性问题，Unicode 标准在1991年发布，目的是为每种语言的每个字符分配唯一的编码点。Unicode 支持全球几乎所有语言的字符，使字符串可以在任何地方统一表示。
-
字符串在编程语言中的发展： 随着编程语言的发展，字符串成为了一种重要的数据类型。早期的编程语言（如 C 语言）使用字符数组来表示字符串，字符串的管理（如长度、拼接等）需要手动处理。而随着高级编程语言（如 Python、Java）的出现，字符串变成了一种更为直观的、内置的数据类型，并提供了许多方便的操作函数，使得字符串处理变得更为简单高效。
-
字符串的现代应用： 随着互联网的发展，字符串在网络和信息交互中的应用越来越广泛。网页上的 HTML、JavaScript、JSON 数据传输格式、电子邮件、搜索引擎等都依赖于字符串来传递信息。此外，自然语言处理（NLP）技术的进步使得对字符串的处理更加复杂，包括分词、语义理解、文本生成等。
总结
字符串的发展从早期的简单字符编码到如今支持全球语言的 Unicode 标准，伴随着计算机科学的发展而不断演进。字符串不仅是文本表示的基本单位，也是现代计算机程序中最常用的数据类型之一，为我们提供了与机器交互、数据传递和处理的桥梁。
三、怎么办
3.1 数组
（一）数组的实现
// 声明一个数组并初始化
int[] arr = new int[5]; // 长度为5的数组，默认值为0
arr[0] = 10; // 赋值给数组的第一个元素
arr[1] = 20;
// 也可以在声明时初始化
int[] arr2 = {1, 2, 3, 4, 5}; // 数组大小为5，元素依次为1, 2, 3, 4, 5
// 遍历数组
for (int i = 0; i < arr2.length; i++) {
System.out.println(arr2[i]);
}
（二）数组的题目
1. 查找问题
查找是数组最基本的操作之一，题目可能会要求找到最大值、最小值、目标元素等。
例题： 给定一个整数数组，找到最大值。
public class FindMax {
public static void main(String[] args) {
int[] arr = {10, 20, 30, 40, 50};
int max = findMax(arr);
System.out.println("最大值是: " + max);
}
public static int findMax(int[] arr) {
int max = arr[0]; // 假设第一个元素为最大值
for (int i = 1; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
return max;
}
}
2. 双指针问题
双指针是一种常见的数组处理技巧，适用于解决对撞指针和滑动窗口等问题。
例题： 给定一个排序数组，查找两个数，使它们的和等于给定的目标值。
解法： 使用双指针法，从数组的两端开始查找。
public class TwoSum {
public static void main(String[] args) {
int[] arr = {2, 7, 11, 15};
int target = 9;
int[] result = twoSum(arr, target);
if (result != null) {
System.out.println("找到的两个数的索引: " + result[0] + ", " + result[1]);
} else {
System.out.println("没有找到符合条件的两个数。");
}
}
public static int[] twoSum(int[] arr, int target) {
int left = 0, right = arr.length - 1;
while (left < right) {
int sum = arr[left] + arr[right];
if (sum == target) {
return new int[]{left, right};
} else if (sum < target) {
left++;
} else {
right--;
}
}
return null; // 没有找到
}
}
3. 前缀和问题
前缀和用于解决子数组的和相关问题，通过计算累计和，可以快速得到任意子数组的和。
例题： 给定一个整数数组，找到连续子数组，使它们的和等于一个指定值。
解法： 使用前缀和来高效查找符合条件的子数组。
import java.util.HashMap;
public class SubarraySum {
public static void main(String[] args) {
int[] arr = {1, 2, 3, 7, 5};
int target = 12;
boolean found = hasSubarrayWithSum(arr, target);
System.out.println("是否找到和为目标值的子数组: " + found);
}
public static boolean hasSubarrayWithSum(int[] arr, int target) {
HashMap<Integer, Integer> map = new HashMap<>();
map.put(0, -1); // 处理前缀和等于target的情况
int sum = 0;
for (int i = 0; i < arr.length; i++) {
sum += arr[i];
if (map.containsKey(sum - target)) {
return true;
}
map.put(sum, i);
}
return false;
}
}
4. 排序问题
经典的排序算法也是数组中常见的考察点，比如冒泡排序、快速排序、归并排序等。
例题： 使用冒泡排序对数组进行排序。
解法：
public class BubbleSort {
public static void main(String[] args) {
int[] arr = {64, 34, 25, 12, 22, 11, 90};
bubbleSort(arr);
System.out.println("排序后的数组：");
for (int num : arr) {
System.out.print(num + " ");
}
}
public static void bubbleSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// 交换 arr[j] 和 arr[j + 1]
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
}
3. 总结
数组在算法题中非常常见，常见的考察方向有：
- 查找问题：如最大值、最小值、目标值的查找。
- 双指针问题：通过左右指针来高效解决一些特定问题。
- 前缀和问题：用于快速计算子数组的和。
- 排序问题：考察经典排序算法的实现。
3.2 字符串
（一）字符串的实现
字符串在 Java 中是通过 String 类实现的。String 类本质上是字符数组 char[] 的封装，并且字符串是不可变的，一旦创建后，字符串的内容就不能被修改。如果你对字符串进行操作（如拼接、替换等），会生成一个新的字符串对象，而不是修改原有的字符串。
public final class String implements java.io.Serializable, Comparable<String>, CharSequence {
// 字符数组，用来存储字符串内容
private final char value[];
// 缓存的字符串哈希码
private int hash; // 默认值为 0
// 构造函数
public String(char value[]) {
this.value = Arrays.copyOf(value, value.length);
}
// 获取字符串长度
public int length() {
return value.length;
}
// 获取字符串中某个字符
public char charAt(int index) {
if (index < 0 || index >= value.length) {
throw new StringIndexOutOfBoundsException(index);
}
return value[index];
}
// 字符串拼接操作
public String concat(String str) {
if (str.length() == 0) {
return this;
}
char buf[] = new char[value.length + str.value.length];
System.arraycopy(value, 0, buf, 0, value.length);
System.arraycopy(str.value, 0, buf, value.length, str.value.length);
return new String(buf);
}
// 字符串哈希码计算
public int hashCode() {
int h = hash;
if (h == 0 && value.length > 0) {
char val[] = value;
for (int i = 0; i < value.length; i++) {
h = 31 * h + val[i];
}
hash = h;
}
return h;
}
}
（二）字符串的题目
1. 反转字符串
这是一个常见的基础题目，要求你将字符串中的字符顺序反转。
public class ReverseString {
public static String reverse(String s) {
// 将字符串转为字符数组
char[] charArray = s.toCharArray();
int left = 0, right = s.length() - 1;
// 交换左右两个字符
while (left < right) {
char temp = charArray[left];
charArray[left] = charArray[right];
charArray[right] = temp;
left++;
right--;
}
// 返回新的字符串
return new String(charArray);
}
public static void main(String[] args) {
String s = "hello";
System.out.println(reverse(s)); // 输出: "olleh"
}
}
2. 判断回文字符串
判断一个字符串是否是回文串，即正读和反读相同。
public class PalindromeCheck {
public static boolean isPalindrome(String s) {
int left = 0, right = s.length() - 1;
while (left < right) {
// 跳过非字母数字字符
while (left < right && !Character.isLetterOrDigit(s.charAt(left))) left++;
while (left < right && !Character.isLetterOrDigit(s.charAt(right))) right--;
if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {
return false;
}
left++;
right--;
}
return true;
}
public static void main(String[] args) {
String s = "A man, a plan, a canal: Panama";
System.out.println(isPalindrome(s)); // 输出: true
}
}
3. 找到字符串中的第一个唯一字符
这是一个常见的算法题，要求你找到字符串中的第一个不重复的字符并返回它的索引。
import java.util.HashMap;
public class FirstUniqueChar {
public static int firstUniqChar(String s) {
HashMap<Character, Integer> count = new HashMap<>();
// 统计每个字符的出现次数
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
count.put(c, count.getOrDefault(c, 0) + 1);
}
// 找到第一个只出现一次的字符
for (int i = 0; i < s.length(); i++) {
if (count.get(s.charAt(i)) == 1) {
return i;
}
}
return -1; // 没有找到返回-1
}
public static void main(String[] args) {
String s = "leetcode";
System.out.println(firstUniqChar(s)); // 输出: 0 (因为 'l' 是第一个唯一字符)
}
}
4. 最长公共前缀
给定一组字符串，找到它们的最长公共前缀。
public class LongestCommonPrefix {
public static String longestCommonPrefix(String[] strs) {
if (strs == null || strs.length == 0) return "";
String prefix = strs[0];
for (int i = 1; i < strs.length; i++) {
while (strs[i].indexOf(prefix) != 0) {
prefix = prefix.substring(0, prefix.length() - 1);
if (prefix.isEmpty()) return "";
}
}
return prefix;
}
public static void main(String[] args) {
String[] strs = {"flower", "flow", "flight"};
System.out.println(longestCommonPrefix(strs)); // 输出: "fl"
}
}
总结
在算法题中，字符串的考察重点通常是字符串的操作、模式匹配、解析和优化处理等。
有“AI”的1024 = 2048，欢迎大家加入2048 AI社区
更多推荐
12
0- 0
已为社区贡献3条内容
所有评论(0)