算法----数组常见知识点

1. 在Java中，数组可以分为以下几种类型：

1. 一维数组：一维数组是最常见的数组类型，它包含一系列具有相同数据类型的元素。数组中的每个元素可以通过索引访问，索引从0开始。

2. 二维数组：二维数组是由一维数组组成的数组。它可以被看作是一个表格或者矩阵，其中的元素可以通过两个索引进行访问。每个元素都是由行索引和列索引确定的。

3. 多维数组：多维数组是由一维或二维数组组成的数组。例如，三维数组由一系列二维数组组成，四维数组由一系列三维数组组成，以此类推。

此外，还有两种特殊类型的数组：

1. 动态数组（ArrayList）：动态数组是一种可以自动调整大小的数组，它可以根据需要动态添加或删除元素。

2. 不规则数组：不规则数组是指每个一维数组的长度可以不同的二维数组。不规则数组在某些情况下可以提供更灵活的数据存储和处理方式。

2. 在Java中，数组需要进行初始化才能使用。

在声明数组时，需要指定数组的类型和大小。初始化数组有两种方法：静态初始化和动态初始化。

1. 静态初始化：静态初始化是在声明数组时直接为数组元素赋予初始值。语法如下：

   数据类型[] 数组名 = {元素1, 元素2, ...};
   1

   例如，可以通过以下方式静态初始化一个整型数组：

   int[] numbers = {1, 2, 3, 4, 5};
   1

   静态初始化可以在声明数组时一次性完成，非常方便。

2. 动态初始化：动态初始化是在声明数组时只指定数组的类型和大小，并没有为数组元素赋初值。语法如下：

   数据类型[] 数组名 = new 数据类型[数组大小];
   1

   例如，可以通过以下方式动态初始化一个整型数组：

   int[] numbers = new int[5];
   1

   动态初始化后，数组的每个元素的初始值将根据数据类型的默认值进行赋值，如int类型默认为0。

需要注意的是，一旦数组被初始化，其大小就无法再更改。如果需要动态调整数组的大小，可以考虑使用动态数组（ArrayList）来代替。

3. 在Java中，不同类型的数组具有不同的性质和常用方法。

以下是一些常见的数组类型及其特点和常用方法：

1. 一维数组：

   • 性质：一维数组是由具有相同数据类型的元素组成的。数组的长度是固定的，一旦创建，无法改变。
   • 常用方法：
     • length：返回数组的长度。
     • clone：创建并返回一个数组的副本。
     • toString：将数组转换为字符串。

2. 二维数组：

   • 性质：二维数组是由一维数组组成的数组，可以看作是一个表格或矩阵。
   • 常用方法：
     • length：返回数组的长度（即行数）。
     • length：返回指定行的长度（即列数）。

3. 多维数组：

   • 性质：多维数组是由一维或二维数组组成的数组，可以有更多的维度。
   • 常用方法：多维数组的常用方法与一维数组和二维数组类似。

4. 动态数组（ArrayList）：

   • 性质：动态数组是一种可以自动调整大小的数组，可以动态添加或删除元素。
   • 常用方法：
     • add：向数组末尾添加元素。
     • remove：从数组中删除指定元素。
     • size：返回数组的大小。
     • get：获取指定索引位置的元素。
     • set：设置指定索引位置的元素。
     • toArray：将数组转换为普通的数组。

4. 求二维数组的边长度，可以通过使用数组的length属性来获取。

在Java中，二维数组实际上是由一维数组组成的数组。因此，二维数组的边长度就是它包含的一维数组的数量。

下面是一个示例代码：

public class Main {
    public static void main(String[] args) {
        int[][] twoDimensionalArray = {
            {1, 2, 3},
            {4, 5, 6},
            {7, 8, 9}
        };

        int rows = twoDimensionalArray.length; // 获取二维数组的行数
        int columns = twoDimensionalArray[0].length; // 获取二维数组的列数

        System.out.println("二维数组的行数：" + rows);
        System.out.println("二维数组的列数：" + columns);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

在这个示例中，我们创建了一个二维数组twoDimensionalArray，并初始化了3行3列的数组。通过使用length属性，我们可以获取二维数组的行数和列数。在这个示例中，我们分别使用twoDimensionalArray.length获取行数，使用twoDimensionalArray[0].length获取列数。最后，我们将行数和列数打印出来。

• 需要注意的是，如果二维数组是不规则的，也就是说每一行的列数不相等，那么获取边长度的方法会有所不同。在这种情况下，你需要遍历每一行，获取每一行的长度，然后找出最大的长度作为边长度。

5. 栈

• 栈是一种后进先出（LIFO）的数据结构，类似于一叠盘子，只能从顶部插入和删除元素。
• Java中的栈可以用Stack类或者Deque接口的实现类（如ArrayDeque）来实现。
• 常用的栈操作包括push（将元素压入栈顶）、pop（将栈顶元素弹出）和peek（获取栈顶元素但不弹出）等。

示例代码：

Stack<Integer> stack = new Stack<>();
stack.push(1);
stack.push(2);
stack.push(3);
System.out.println(stack.pop());  // 输出3
System.out.println(stack.peek());  // 输出2
1
2
3
4
5
6

• 使用栈解决括号匹配问题

我们可以遍历字符串，当遇到左括号时，将其压入栈中；当遇到右括号时，检查栈顶元素是否为对应的左括号，如果是，则弹出栈顶元素，继续遍历；如果不是，则说明括号不匹配，返回false。最后检查栈是否为空，如果为空，则说明所有括号都匹配，返回true。

public static boolean isParenthesesMatch(String str) {
    Stack<Character> stack = new Stack<>();

    for (char c : str.toCharArray()) {
        if (c == '(' || c == '[' || c == '{') {
            stack.push(c);
        } else if (c == ')' || c == ']' || c == '}') {
            if (stack.isEmpty()) {
                return false;
            }
            char top = stack.peek();
            if ((c == ')' && top == '(') || (c == ']' && top == '[') || (c == '}' && top == '{')) {
                stack.pop();
            } else {
                return false;
            }
        }
    }

    return stack.isEmpty();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

6. 队列

• 队列是一种先进先出（FIFO）的数据结构，类似于排队，只能从队尾插入元素，从队头删除元素。
• Java中的队列可以用Queue接口的实现类（如LinkedList）来实现。
• 常用的队列操作包括offer（将元素插入队尾）、poll（删除队头元素并返回）和peek（获取队头元素但不删除）等。

示例代码：

Queue<Integer> queue = new LinkedList<>();
queue.offer(1);
queue.offer(2);
queue.offer(3);
System.out.println(queue.poll());  // 输出1
System.out.println(queue.peek());  // 输出2
1
2
3
4
5
6

• 使用队列实现对二叉树的层次遍历问题

import java.util.LinkedList;
import java.util.Queue;

// 定义二叉树节点
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

public class LevelOrderTraversal {
    public static void levelOrder(TreeNode root) {
        if (root == null) {
            return;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            System.out.print(node.val + " ");

            if (node.left != null) {
                queue.offer(node.left);
            }

            if (node.right != null) {
                queue.offer(node.right);
            }
        }
    }

    public static void main(String[] args) {
        // 创建二叉树
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.left = new TreeNode(6);
        root.right.right = new TreeNode(7);

        // 层次遍历二叉树
        System.out.print("层次遍历结果：");
        levelOrder(root);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

运行以上代码，输出结果为：1 2 3 4 5 6 7，表示对二叉树进行层次遍历的结果。