- 一、线性表(广义的数组)
- 1. 数组
- 一维数组的定义和初始化
- 二维数组的定义和初始化
- Arrays工具类的一些常用方法
- 2. List接口容器
- 对象的构建
- 读写和插入删除数据
- 排序
- 反转数组
- List转为数组
- 1. 数组
- 二、字符串
- 三、Map和Set
- 1. Map
- 2. Set
- 四、栈Stack和队列Queue
- 1. 栈Stack
- 2. 队列Queue
- 五、优先队列
在算法题中,我们一般使用到的线性表一般有两种,且它们的优缺点如下:
- 数组
- 优点:可以使用
[]
运算符进行随机读写 - 缺点:数组大小固定,不能动态添加数据
- 优点:可以使用
- List对象
- 优点:可以动态添加数据
- 缺点:读写数据需要使用
get(int index)
和set(int index, Object object)
,和数组相比比较麻烦
这里数组的主要用法和c++比较类似,这里主要写一下一些特殊的操作以及Arrays工具类提供的一些方法。
一维数组的定义和初始化① 直接指定固定大小:
int[] arr = new int[n];
则开辟的空间会填充上默认值:
- 数值类型填充
0
boolean
类型填充false
- 对象类型填充
null
② 定义时进行初始化
int[] arr = new int[]{1, 2, 3, 4, 5};
二维数组的定义和初始化
① 和一维数组一样直接给定两个维度的大小(行数和列数):
int[][] matrix = new int[m][n];
② 和c++类似,二维数组也可以像c++中的type** matrix
一样,先给第一个维度分配空间,然后再为第二个维度分配不同的空间,例如下面的代码分配下三角矩阵:
int n = 5;
int[][] matrix = new int[n][];
for (int i = 0; i < n; i++) {
matrix[i] = new int[i + 1];
}
打印展示:
Arrays工具类的一些常用方法在Java中原生数组实际上并不是完全的面向对象的,对于List对象希望进行某项操作只需要使用.+方法
即可,但数组类型本身却没有带有这些操作,因而Arrays工具类填补了这部分的空白。
① Arrays.fill()
Arrays.fill有两个常见的使用:
Arrays.fill(int[] array, int value)
Arrays.fill(int[] array, int start, int end, int val)
这个函数是用于填充数组的,第一个参数是数组,第二个参数是填充的值,而第二种用法规定了填充的起止下标:[start, end)
。
② Arrays.sort()
排序函数,一般也有两种参数填充方法:
Arrays.sort(int[] array)
Arrays.sort(Object[] array, Comparator c)
tips 只有对象数组才能使用这种方式
第一种方式是按照默认的方式进行排序,数字类型按从小到大排,字符串类型按字典序排,而第二种方式中填写的第二个参数是用于改变默认的排序规则的,例如这里我希望从大到小排序():
Integer[] arr = new Integer[]{1, 2, 3, 4, 5};
Arrays.sort(arr, new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2 - o1;
}
});
// 或者使用下面的更加简洁的lambda表达式
Arrays.sort(arr, (num1, num2) -> num2 - num1);
由于添加Comparator对象的这种方式第一个参数只能是对象数组,因此我这里不再使用int[]
而是改为了使用Integer[]
。
这里就会出现一个这样的需求:如果我原来的类型是
int[]
,那么如何转换为Integer[]
呢?这里我们可以使用下面的代码进行转化(其他的例如boolean到Boolean也可以按照如下方式转化):int[] arrOrigin = new int[]{1, 2, 3, 4, 5}; Integer[] arr = (Integer[]) Arrays.stream(arrOrigin).boxed().toArray();
即将原数组转为stream对象后调用boxed方法得到
Stream<Integer>
,最后再调用Stream
类中的toArray()
成员方法即可从流重新转为数组。而Integer[]
想要转为int[]
则需要调用Stream
类的mapToInt(Integer::intValue).toArray()
。参考资料:https://codingdict.com/questions/3373
③ Arrays.toString(int[] array)
这个方法可以得到数组完整的内容,而如果直接使用arr.toString()
只会得到对象的地址等无用信息。
④ Arrays.asList(int[] array)
将数组转为List对象:
Integer[] arr = new Integer[]{1, 2, 3, 4, 5};
List<Integer> list = Arrays.asList(arr);
此外这个函数还可以分散填写各个List对象初始元素的值:
List<Integer> list = Arrays.asList(1, 2, 3, 4, 5);
⑤ 反转数组
这里可以使用工具类反转的数组也仅限是对象数组(非对象数组可能只能手写反转算法了),参考代码如下:
String[] strArr = new String[]{"e", "d", "c", "b", "a"};
Collections.reverse(Arrays.asList(strArr));
输出结果:
[a, b, c, d, e]
另外还有一些例如Arrays.copyOf等方法不太常用,这里不再详细介绍。
2. List接口容器 对象的构建实现类一般使用ArrayList
(此外还有LinkedList
,但不常用),构造对象方式如下:
List<Integer> list = new ArrayList<>();
读写和插入删除数据
读:E get(int index)
写:E set(int index, E element)
插入:boolean add(E e)
和void add(int index, E element)
删除:boolean remove(Object o)
和E remove(int index)
使用List
的接口方法sort(Comparator c)
(数字从大到小排):
List<Integer> list = Arrays.asList(1, 2, 3, 4, 5);
list.sort((num1, num2) -> num2 - num1);
输出:
[5, 4, 3, 2, 1]
或者也可以使用Collections.sort(List l, Comparator c)
,可以达到相同的效果。
// Collections工具类静态方法:Collections.reverse(List list)
List<Integer> list = Arrays.asList(1, 2, 3, 4, 5);
Collections.reverse(list);
List转为数组
List<Integer> list = Arrays.asList(1, 2, 3, 4, 5);
Integer[] arr = (Integer[]) list.toArray();
二、字符串
以下api如果没有标注则默认为String类成员方法。
int length()
获取下标对应字符
char charAt(int index)
转换为字符数组
char[] toCharArray()
取子串
String substring(int beginIdx, int endIdx)
其中endIdx
是可选的
转为int等数字类型
静态方法 Integer.parseInt(String str)
这是int类型的,其他类型以此类推
数值类型转为字符串
静态方法 String.valueOf(T val)
这里的T可以是int、double等类型
按分隔符切分字符串
String[] split(String regex)
填入的是正则表达式
反转字符串
StringBuilder成员方法 string reverse()
需要借助StringBuilder
三、Map和Set 1. Map这些容器类基本都会包含有获取元素数量(
size()
)和判断是否为空(empty()
或isEmpty()
)等相同的方法,因此后面的api表格只列出该类特有的操作。
Map这里一般使用的实现为HashMap
,少数需要按照键进行排序时使用到TreeMap
,构造对象如下:
Map<String, String> map = new HashMap<>();
常用操作和api:
V get(Object key)
写
V put(K key, V value)
是否包含key
boolean containsKey(Object key)
是否包含value
boolean containsValue(Object value)
遍历Map:
// 1. 使用forEach + lambda表达式(推荐)
map.forEach((key, value)-> {
...
});
// 2. 使用for结合keySet()
for (String key : map.keySet()) {
String value = map.get(key);
...
}
2. Set
和Map类似,这里Set的实现一般也选择HashSet
,少数需要按照键进行排序时使用到TreeSet
,构造对象如下:
Set<String> set = new HashSet<>();
常用操作和api:
boolean add(E e)
删除元素
boolean remove(Object o)
是否包含元素
boolean contains(Object o)
同理,set也可以使用forEach+lambda以及增强for两种写法遍历元素。
四、栈Stack和队列Queue 1. 栈Stack构造对象:
Stack<String> stack = new Stack<>();
常用操作和api:
E push(E item)
弹栈
E pop()
查看栈顶元素
E peek()
2. 队列Queue
Queue是一个接口,一般实现类取ArrayDeque。构造对象代码如下:
Queue<String> queue = new ArrayDeque<>();
常用操作和api:
boolean offer(E e)
出队
E poll()
查看队首
E peek()
五、优先队列
构造对象:
PriorityQueue<Integer> heap = new PriorityQueue<>();
使用无参数构造函数时得到的是小顶堆,如果我们希望得到大顶堆则需要填入一个Comparator参数,如下为构造int类型大顶堆的方式:
PriorityQueue<Integer> heap = new PriorityQueue<>((o1, o2) -> o2 - o1);
其中填入的lambda表达式为新建Comparator匿名内部类的语法糖。
常用操作和api:
boolean offer(E e)
出队
boolean poll(E e)
查看队首(堆顶)
E peek()