【数据结构】顺序表 Sequential List
什么是顺序表？
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改（棒读）。
顺序表的特点主要集中在它的存储上面，因为它使用的是一段连续的存储空间，所以实际上我们如果要不依靠数据，自己手写一个顺序表的话，实际上我们只需要指定一个地址作为开始，规定好最大指示的范围，就可以了。
但是Java并不支持直接操作地址，如果我们要尝试这类操作，可以参考以下的C++代码：
#include <cstdio>
using namespace std;
struct LinearList {
int linearListBeginPosition;
int maxsize;
int numberOfThisPosition(int pos) {
int *p = &linearListBeginPosition;
p = p + pos;
return *p;
}
void setThisPositionNumber(int pos,int number) {
int *p = &linearListBeginPosition;
p = p + pos;
*p = number;
}
};
int main() {
LinearList T;
T.maxsize = 200;
T.setThisPositionNumber(1,2);
printf("%d\n",T.numberOfThisPosition(1));
}上述代码中我们定义了一个结构体（可以理解为类）。
其中有两个成员变量linearListBeginPosition和maxsize，其中linearListBeginPosition代表的是这个顺序表的开始元素，它的地址就是顺序表的开始地址，对应到我们一般用的数组，其实就是a[0]，而maxsize则表示这个顺序表的最大容量，这时候我们就可以非常直观地看到我们日常使用中的数组是怎么构成的了。
而numberOfThisPosition()这个函数则是会返回当前位置的值，而setThisPositionNumber()这个函数则是修改当前位置的值。这样子我们就可以基本上实现一个顺序表的基本功能了。
顺序表的特性
紧紧接着我们就能由这个定义，我们就能得到顺序表的一个重要特性：
每个存储在顺序表中的元素都由一个唯一位置表示，可以由（顺序表开始地址+唯一位置）找到
这是顺序表最为重要的特点，我们在各种编程语言中见到的数组符号（[]就这个玩意），其实较为正式应该称为下标运算符，做的就是上述开始地址+唯一位置这个操作。
这样子有什么好处呢？
首先是我们能够直接访问一个位置的元素，不必像一些其他数据结构（如链表），需要从头位置开始依次访问，才能访问到自己需要的那个元素，同样，也能够直接修改这个位置的元素。
但是坏处就是，我们如果要一次性移动很多个连续的元素，需要的时间则相比较链表等数据结构，实在是太多了。
其实数组就是一个封装得非常好的 顺序表 。我们这时候返回来重新看一下我们最基础学习的数组
class LinearList {
int[] a = new int[100];
public void test() {
a[0] = 100;
System.out.println(a[0]);
a[100] = 101;
System.out.println(a[100]);
}
public static void main(String[] args) {
LinearList test = new LinearList();
test.test();
}
}这时候我们的代码会报错，因为a[100]这个位置超出我们预设的100的范围，而且由于Java优秀的内存管理机制，它会直接报错，防止引发更大的问题。
但是我们可以参考一份C++代码，C++是允许访问超出数组预设范围的地址（但是，这样子做非常危险！这样子做非常危险！这样子做非常危险！在这里仅仅是为了演示而使用）
#include <cstdio>
using namespace std;
int main(){
int a[100];
a[0] = 100;
printf("%d\n",a[0]);
a[100] = 101;
printf("%d\n",a[100]);
return 0;
}结果也会和我们预期的一样
100
101
--------------------------------
Process exited after 0.00826 seconds with return value 0所以一般的线性表都会加入 范围检测 这个东西，为了防止我们访问超出一开始指定的数据范围的地址（就像Java做的那样），这是防止 未定义行为、内存破坏、安全漏洞、调试困难 的重点。
同时，尽管越界本身并不会直接导致内存泄漏，但会影响到程序的内存管理，从而间接导致内存泄漏。例如，如果越界访问导致指针指向了错误的内存区域，该区域可能被错误地分配并在后续无法访问到，从而引发内存泄漏。所幸，Java已经帮我们尽可能地规范好了这些（即便牺牲了直接访问内存地址这一功能），但是我仍觉得，了解这些，并且能够在编程的时候意识到这些隐形的、可能存在的问题，是程序员应该做到的。
实战讲解
T1 珠心算测验
题目背景：NOIP2014 普及 T1
题目描述：给你一个集合
a[i]，问其中有多少个数，恰好等于集合中另外两个（不同的）数之和？数据范围：3\leq n \leq 100,0 \leq a_i \leq 10000
本题并不难，我们要做的只有一件事，只需要确定这个数字能否通过集合内的两个数字相加得到。
我们采用一个大小为20001的布尔类型的顺序表mark[]，并使用一个二重循环，将所有的两个数的组合都尝试一遍，并且记录到这个顺序表中mark[a[i]+a[j]]=true。再遍历一遍a[i]，如果mark[a[i]]为真，则就代表这个数字为不同两数之和。
import java.io.*;
import java.util.*;
class Main{
public static void main(String[] args) throws Exception {
Scanner cin = new Scanner(System.in);
int n = cin.nextInt();
int[] a = new int[101];
for(int i = 0;i < n;i++){
a[i] = cin.nextInt();
}
boolean[] mark = new boolean[20001];
for(int i = 0;i < n;i++){
for(int j = i + 1;j < n;j++){
mark[a[i] + a[j]] = true;
}
}
int ans = 0;
for(int i = 0;i < n;i++){
if(mark[a[i]]) {
ans++;
}
}
System.out.println(ans);
}
} 注：这是竞赛中常用的解题格式，算法竞赛中要求的输出格式中，不能有多余的内容，而且并非像
Leetcode刷题中直接给我们对应的数组，必须依靠解题者自行读入，因为竞赛中有些题目对于读入的方式也是题目考察的一部分。此处为第一次遇到这类代码，后续笔记中再遇到，不会再特殊注明，自行观察理解即可。
本题并没有太大的难点，但是我们举这道题目的例子是为了引出下一道题目。
T2 三数之和
题目背景：我脑子里的题
题目描述：给你一个集合
a[i]，问其中有多少个数，恰好等于集合中另外三个数（可重复使用）之和？数据范围：3 <= n <= 1000,0 <= a_i <= 10000
这题相较于刚刚那题，变成了三个数，而且范围变成了1000，这时候如果我们还是使用类似上面的方法，使用一个三层循环能解决吗？
我们稍微计算一下计算量，就会知道1000^3差不多是1000000000，一亿的一个计算量，一般我们解算法题，都要将其尽量计算量压在一亿/秒以内，而本题如果使用三层循环时间复杂度就来到了O(n^3)的一个等级，而我们的每个操作又有着相当的常数，所以使用上一题的方法实在是难以通过本题。
我们稍微总结一下题目的式子：a[i] + a[j] + a[k] = a[l]
我们之前在上一题中是直接统计a[i] + a[j]的结果并记录，从而使得我们的时间复杂度只需要O(n^2)，这时候我们就能不能考虑转化一下这个式子，使得式子的左边只剩下两个数呢？当然可以！a[i] + a[j] = a[l] - a[k]
这样子我们左边就只需要一个两重循环就可以枚举完了，你会说，右边不需要也是需要两重循环来枚举吗？一起不就甚至是四重循环了吗？其实并不是这样子的，我们可以在先前的循环之外另外再用一个两重循环来枚举a[l]和a[k]，这样子时间复杂度就降低到O(n^2)了。
有个细节是这题的数字是可重复的，倘若是不可重复的，我们也可以解决，留作思考题，并不难。批注，后续记得添加对应解法
import java.io.*;
import java.util.*;
class Main {
public static void main(String[] args) throws Exception {
Scanner cin = new Scanner(System.in);
int n = cin.nextInt();
int[] a = new int[1001];
for (int i = 0;i < n;i++){
a[i] = cin.nextInt();
}
boolean[] mark = new boolean[20001];
for (int i = 0;i < n;i++) {
for(int j = 0;j < n;j++){
mark[a[i] + a[j]] = true;
}
}
int ans = 0;
for (int k = 0;k < n;k++) {
for (int l = 0;l < n;l++) {
if (a[k] - a[l] < 0) {
continue;
}
if (mark[a[k] - a[l]]) {
ans++;
}
}
}
System.out.println(ans);
}
}T3 梦中的统计
题目背景：洛谷P1554
题目描述：给出两个整数 M 和 N，求在序列 [M,M+1,M+2,…,N−1,N] 中每一个数码（如
123可以拆分为1,2,3三个数码）出现了多少次。数据范围：1 \leq M \leq N \leq 2 \times 10^9，N-M \leq 5 \times 10^5
本题的难点主要集中在如何拆分数码，我们这里需要用到两个操作——%,/，我们接触的一般数字都是十进制的，故我们将一个数字%10便可以得到其个位上的数字，而/10又能实现类似二进制中右移的功能，将原本的个位直接抹除，这样子我们就能够通过——获取个位，抹除个位，这个循环，来将整数拆分成数码。
以下是一个整数拆分为数码并记录在nums[]的函数：
int[] nums = new int[10];
public void getDigital(int number) {
while (number != 0) {
nums[number % 10]++;
number /= 10;
}
}接下来就只需要套一层循环，遍历[M,N]即可：
import java.io.*;
import java.util.*;
class Digital {
private int[] nums = new int[10];
public void getDigital(int number) {
while (number != 0) {
nums[number % 10]++;
number /= 10;
}
}
public void getNums() {
for (int i = 0;i <= 9;i++) {
System.out.printf("%d ",nums[i]);
}
}
}
class Main {
public static void main(String[] args) throws Exception {
Scanner cin = new Scanner(System.in);
int m = cin.nextInt(),n = cin.nextInt();
Digital digital = new Digital();
for (int i = m;i <= n;i++) {
digital.getDigital(i);
}
digital.getNums();
}
}T4 MC生存
题目背景：洛谷P1789
题目描述：话说有一天 linyorson 在“我的世界”开了一个 n \times n 的方阵，现在他有 m 个火把和 k 个萤石，分别放在 (x_1, y_1) \sim (x_m, y_m) 和 (o_1, p_1) \sim (o_k, p_k) 的位置，没有光并且没放东西的地方会生成怪物。请问在这个方阵中有几个点会生成怪物？
P.S. 火把的照亮范围是：
|暗|暗| 光 |暗|暗| |暗|光| 光 |光|暗| |光|光|火把|光|光| |暗|光| 光 |光|暗| |暗|暗| 光 |暗|暗|萤石：
|光|光| 光 |光|光| |光|光| 光 |光|光| |光|光|萤石|光|光| |光|光| 光 |光|光| |光|光| 光 |光|光|数据范围：1 \le n \le 100，1 \leq m+k \leq 25，1 \leq m \leq 25，0 \leq k \leq 5。
这道题目则是考察我们对二维空间的理解，以及对于方向的一个运用。
首先我们来考虑火把的情况
倘若我们现在有个二维数组，并且有个起始位置（例如map[x][y]的情况，x指行，y指列），我们如果想要向上方移动一个位置就相当于列不变，而行减少1，即，将map[x][y]转化成map[x-1][y]，其实也就相当于我们利用了一个二维向量(-1,0)，作用于原本的坐标上。
所以我们可以把上下左右都抽象成四个二维向量：
上：
(-1,0)下：
(1,0)左：
(0,-1)右：
(0,1)
再将其记录下来，我们就可以完成上下左右四个方向的移动了。同理再结合一下，我们就可以获得八个方向的对应向量。
所以有了这个，我们就可以写出火把的对应照亮的区域的标记过程了
int[] dx = new int[]{0,1,0,-1};
int[] dy = new int[]{1,0,-1,0};
int[] dxx = new int[]{1,-1,1,-1};
int[] dyy = new int[]{-1,-1,1,1};
map[x][y] = true;
for(int dir = 0;dir < 4;dir++){
map[Math.max(0,x + dx[dir])][Math.max(0,y + dy[dir])] = true;
map[Math.max(0,x + 2 * dx[dir])][Math.max(0,y + 2 * dy[dir])] = true;
map[Math.max(0,x + dxx[dir])][Math.max(0,y + dyy[dir])] = true;
}当然也可以一个个位置直接通过计算得出，但是这样子太麻烦了。
而代码中的max函数，则是为了防止相应的空间超出我们声明的范围（即防止变成负数，从而导致程序崩溃）。
接下来就是萤石的照亮区域，这就简单得多了，我们注意到可以以map[x-2][y-2]的位置作为矩形的左上角，以map[x+2][y+2]的位置作为右下角，遍历这个矩形并且标记就可以了。
for(int i = 1;i <= k;i++){
int x = cin.nextInt(),y = cin.nextInt();
for(int j = Math.max(0,x - 2);j <= Math.min(n,x + 2);j++)
for(int kk = Math.max(0,y - 2);kk <= Math.min(n,y + 2);kk++)
map[j][kk] = true;
}最后我们再遍历一遍整个map[][]，并统计答案就可以了。
import java.io.*;
import java.util.*;
class Main {
private static boolean[][] map = new boolean[110][110];
private static int[] dx = new int[]{0,1,0,-1};
private static int[] dy = new int[]{1,0,-1,0};
private static int[] dxx = new int[]{1,-1,1,-1};
private static int[] dyy = new int[]{-1,-1,1,1};
public static void main(String[] args) throws Exception {
Scanner cin = new Scanner(System.in);
int n = cin.nextInt(),m = cin.nextInt(),k = cin.nextInt();
for(int i = 1;i <= m;i++){
int x = cin.nextInt(),y = cin.nextInt();
map[x][y] = true;
for(int dir = 0;dir < 4;dir++){
map[Math.max(0,x + dx[dir])][Math.max(0,y + dy[dir])] = true;
map[Math.max(0,x + 2 * dx[dir])][Math.max(0,y + 2 * dy[dir])] = true;
map[Math.max(0,x + dxx[dir])][Math.max(0,y + dyy[dir])] = true;
}
}
for(int i = 1;i <= k;i++){
int x = cin.nextInt(),y = cin.nextInt();
for(int j = Math.max(0,x - 2);j <= Math.min(n,x + 2);j++)
for(int kk = Math.max(0,y - 2);kk <= Math.min(n,y + 2);kk++)
map[j][kk] = true;
}
int ans = 0;
for(int i = 1;i <= n;i++)
for(int j = 1;j <= n;j++)
if(!map[i][j])
ans++;
System.out.println(ans);
}
}