00 DSA-- 入门、实现动态数组

两种代码模式

核心代码模式

核心代码模式：就是给你一个函数框架，你需要实现函数逻辑，这种模式一般称之为。
目前大部分刷题平台和技术面试/笔试场景都是核心代码模式。

比如力扣第一题两数之和，就是给出 twoSum 函数的框架如下，然后要求给出具体实现

class Solution // 即后台会自动输入数组 nums 和目标值 target，你需要实现算法逻辑，最后计算返回一个数组。public int[] twoSum(int[] nums, int target) {}
}

ACM 模式

简单来说，ACM 模式就是预先不提供函数框架，代码提交到后台后，系统会把每个测试用例（字符串）用标准输入传给你的程序，然后对比你程序的标准输出和预期输出是否相同，以此判断你的代码是否正确。

对于 ACM 模式，一个技巧就是要对代码分层，把对字符串输入的处理逻辑和真正的算法逻辑分开，类似这样：

public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);// 主要负责接收处理输入的数据，构建输入的用例int[] nums;int target;int N = scanner.nextInt();...// 调用算法逻辑进行求解System.out.println(twoSum(nums, target));}public static int[] twoSum(int[] nums, int target) {// 转化为核心代码模式，在这里写算法逻辑}
}

常见错误

• 编译错误（Compile Error）
  • 代码无法通过编译，这种错误一般是语法错误，比如拼写错误、缺少分号等。一般网页上手搓代码容易出现这种错误
• 运行错误（Runtime Error）
  • 代码可以编译通过，但是在运行时出现了数组越界、空指针异常等错误。这种错误一般是由于边界条件处理不当，你需要留意边界条件、特殊测试用例（也叫做 Corner case，比如输入为空等情况）。
• 答案错误（Wrong Answer）
  • 代码可以编译通过，也可以运行，但是某些测试用返回的结果和正确答案不一致。这种错误一般是因为你的算法有问题，需要你根据出错的用例反思，甚至可能整个思路都错了，需要你推倒重来。
• 超时（Time Limit Exceeded，常简称为 TLE）
• 力扣预定义的测试用例中，越靠后的用例数据规模就越大。如果你的算法的时间复杂度太高，在运行这些大规模的测试用例时就容易超过系统规定的时间限制，导致超时错误。如果你卡在大规模的测试用例，一般就能说明你的算法结果是正确的，因为前面的小规模测试用例都通过了，只不过是时间复杂度太高，需要优化。可能的错误有：
  • 是否有冗余计算，是否有更高效的解法思路来降低时间复杂度。
  • 是否有编码错误，比如边界控制出错，错误地传值传引用导致无意义的数据拷贝等。
• 笔试中，一般是按照通过的测试用例数量来计分的。所以如果你实在是想不出最优解法通过所有用例，提交一个暴力解，过几个用例捞点分，也是一种聪明的策略。
• 内存超限（Memory Limit Exceeded，常简称为 MLE）
  • 和超时错误类似，内存超限一般是算法的空间复杂度太高，在运行大数据规模的测试用例时，占用的内存超过了系统规定的内存限制。想要解决这个问题，你需要检查以下几点：
    • 是否有申请了多余的空间，是否有更高效的解法思路来降低空间复杂度。
    • 是否在递归函数中错误地使用了传值参数导致无意义的数据拷贝。

数组

我们在说「数组」的时候有多种不同的语境，因为不同的编程语言提供的数组类型和 API 是不一样的，所以开头先统一一下说辞：可以把「数组」分为两大类，一类是「静态数组」，一类是「动态数组」。

• 「静态数组」就是一块连续的内存空间，我们可以通过索引来访问这块内存空间中的元素，这才是数组的原始形态。
• 「动态数组」是编程语言为了方便我们使用，在静态数组的基础上帮我们添加了一些常用的 API，比如 push, insert, remove 等等方法，这些 API 可以让我们更方便地操作数组元素，不用自己去写代码实现这些操作。

有了动态数组，后面讲到的队列、栈、哈希表等复杂数据结构都会依赖它进行实现。

静态数组

静态数组在创建的时候就要确定数组的元素类型和元素数量。只有在 C++、Java、Golang 这类语言中才提供了创建静态数组的方式，类似 Python、JavaScript 这类语言并没有提供静态数组的定义方式。

静态数组的用法比较原始，实际软件开发中很少用到，写算法题也没必要用，我们一般直接用动态数组。

定义一个静态数组的方法如下：

// 定义一个大小为 10 的静态数组
int arr[10];// 用 memset 函数把数组的值初始化为 0
memset(arr, 0, sizeof(arr));// 使用索引赋值
arr[0] = 1;// 使用索引取值
int a = arr[0];

用 memset 将数组元素初始化为 0 是 C/CPP 的特有操作。
因为在 C/CPP 中，申请静态数组的语句（即 int arr[10] ）只是请操作系统在内存中开辟了一块连续的内存空间，你也不知道这块空间是谁使用过的二手内存，你也不知道里面存了什么奇奇怪怪的东西。所以一般我们会用 memset 函数把这块内存空间的值初始化一下再使用。

其他比如 Java Golang ，静态数组创建出来后会自动帮你把元素值都初始化为 0，所以不需要再显式进行初始化。

动态数组

动态数组底层还是静态数组，只是自动帮我们进行数组空间的扩缩容，并把增删查改操作进行了封装，让我们使用起来更方便而已。

因此，动态数组也不能解决静态数组在中间增删元素时效率差的问题。数组随机访问的超能力源于数组连续的内存空间，而连续的内存空间就不可避免地面对数据搬移和扩缩容的问题。

// java 中创建动态数组不用显式指定数组大小，它会根据实际存储的元素数量自动扩缩容
// ArrayList 很熟悉了，即可重复的集合，底层是静态数组
ArrayList<Integer> arr = new ArrayList<>();for (int i = 0; i < 10; i++) {// 在末尾追加元素，时间复杂度 O(1)arr.add(i);
}// 在中间插入元素，时间复杂度 O(N)
// 在索引 2 的位置插入元素 666
arr.add(2, 666);// 在头部插入元素，时间复杂度 O(N)
arr.add(0, -1);// 删除末尾元素，时间复杂度 O(1)
arr.remove(arr.size() - 1);// 删除中间元素，时间复杂度 O(N)
// 删除索引 2 的元素
arr.remove(2);// 根据索引查询元素，时间复杂度 O(1)
int a = arr.get(0);// 根据索引修改元素，时间复杂度 O(1)
arr.set(0, 100);// 根据元素值查找索引，时间复杂度 O(N)
int index = arr.indexOf(666);

实现动态数组