数组Array

在连续的内存空间中，存储一组相同类型的元素。
时间复杂度：访问o(1)、搜索o(n)、插入o(n)、删除o(n)
适合读不适合写

常用操作

创建数组

  • int[] arr = {1,2,4, …};
  • int[] arr1= new int[3];//所有的元素值均为0
  • int[][] arr = {{1,2,3},{4,5,6},{7,8,9}};//多维数组
  • int[][] arr = new int[m][n];
  • List arr = new ArrayList<>();
  • List转数组：String[] arr = list.toArray(new String[list.size()]);
  • 数组转List：List list = Arrays.asList(arr);
  • 数组转List：List list = Arrays.stream(nums).boxed().collect(Collectors.toList());

添加元素

  • arr[index] = m;//o(1)
  • list.add(m);//o(1)
  • list.add(n,m);//o(n)->在n处插入m

访问元素o(1)

  • arr[index];
  • list.get(index);

修改元素o(1)

  • arr[index] = m;
  • list.set(n,m);

删除元素o(n)

  • list.remove(index);

遍历数组o(n)

  • for (int i=0;i<arr.length;i++) {arr[i]…}
  • for (int i=0;i<list.size();i++) {list.get(i)…}

查找元素o(n)

  • for (int i=0;i<arr.length;i++) {arr[i]==m?…:…}
  • boolean flag = arr.contains(m);

数组的长度

  • arr.length;
  • list.size();

数组排序o(nlogn)

  • Arrays.sort(arr);
  • Collections.sort(list));

  • Collections.sort(list,Colections.reversOrder());//反序，数组arr若要反序则需将int[]转为Integer[]，也用该方法

    链表LinkedList

    存在指针，指向上一个或下一个
    时间复杂度：访问o(n)、搜索o(n)、插入o(1)、删除o(1)
    适合写不适合读

    常用操作

    创建链表

  • LinkedList list = new LinkedList<>();

添加元素

  • list.add(integer);//o(1)
  • list.add(2,99);//o(n)

访问元素

  • list.get(index)

查找元素

  • list.indexof(integer);//返回索引值

更新元素

  • list.set(2,88);

删除元素

  • list.remove(index);

链表的长度

  • list.size();

    队列Queue

    先入先出
    时间复杂度：访问o(n)、搜索o(n)、插入o(1)、删除o(1)

    常用操作

    创建队列

  • Queue queue= new LinkedList<>();

添加元素o(1)
queue.add(integer);
获取即将出队的元素o(1)
queue.peek();
删除即将出队的元素o(1)
queue.poll();
判断队列是否为空o(1)
queue.isEmpty();
队列长度o(1)
queue.size();

栈Stack

先入后出
时间复杂度：访问o(1)、搜索o(n)、插入o(1)、删除o(1)

常用操作

创建栈
Stack stack= new Stack<>();
添加元素o(1)
stack.push(integer);
获取栈顶元素o(1)
stack.peek();
删除栈顶元素o(1)
stack.pop();
栈的长度o(1)
stack.size();
栈是否为空o(1)
stack.isEmpty();
遍历栈o(n)
while(!stack.isEmpty()) {
sout(stack.pop());
}

哈希表HashTable

key、value键值对
哈希碰撞：2个不同的key通过同一个哈希函数得到了相同的地址，则将后面一个key以链的方式连接在前一个key上
时间复杂度：访问不存在、搜索o(1)、插入o(1)、删除o(1)、碰撞o(k)，k为碰撞元素的个数

常用操作

创建哈希表

  • String[] hashTable = new String[4];
  • HashMap map = new HashMap<>();

添加元素o(1)

  • hashTable[1] = “1”;
  • map.put(1,”1”);

更新元素o(1)

  • hashTable[1] = “1”;
  • map.put(1,”1”);

删除元素o(1)

  • hashTable[1] = “”;
  • map.remove(1);

获取key的值o(1)

  • hashTable[1];
  • map.get(3);

检查key是否存在o(1)

  • map.containsKey(3);

哈希表长度o(1)

  • map.size();

哈希表是否还有元素o(1)

  • map.isEmpty();

    集合Set

    无顺序且数据不重复
    主要作用：检查某个元素是否存在、有无重复元素
    时间复杂度：访问不存在、搜索无哈希冲突o(1)/有哈希冲突o(k)、插入无哈希冲突o(1)/有哈希冲突o(k)、删除无哈希冲突o(1)/有哈希冲突o(k)，k为冲突元素的个数

    常用操作

    创建集合

  • HashSet set= new HashSet<>();

添加元素o(1)

  • set.add(1);

删除元素o(1)

  • set.remove(2);

查询元素o(1)

  • set.contains(2);

长度o(1)

  • set.size();

    树Tree

    是一种父子关系

  • 高度：从叶子节点往根节点方向数，从0开始

  • 深度：从根节点往叶子节点方向数，从0开始

  • 层：从根节点往叶子节点方向数，从1开始

    二叉树

  • 普通二叉树：每个节点至多两个孩子

  • 满二叉树：除了叶子节点，每个节点都有两个孩子，且所有叶子节点都在同一层上
  • 完全二叉树：从根节点起，从上到下，从左到右，依次填满节点形成的二叉树

遍历

  • 前序：根左右
  • 中序：左根右

  • 后序：左右根

    堆Heap

    一种二叉树的结构，是完全二叉树，且每个节点的数量大于等于叶子节点的数量(最大堆)，或每个节点的数量小于等于叶子节点的数量(最小堆)。
    最大堆：堆顶元素是最大值
    最小堆：堆顶元素是最小值
    时间复杂度：访问不存在、搜索o(n)、插入o(logn)、删除o(logn)

    常用操作

    创建堆

  • PriortyQueue minheap= new PriortyQueue<>();

  • PriortyQueue maxheap= new PriortyQueue<>(Collections.reverseOrder());

添加元素

  • minheap.add(1);

获取堆顶元素

  • minheap.peek();

删除堆顶元素

  • minheap.poll();

堆的长度

  • minheap.size();

堆的遍历

  • while(!minheap.isEmpty()) {

…
}

图Graph

是一种邻居关系
一个顶点有几条边，则有几个度
图分为无向图、有向图、权重图
有向图有入度与出度的概念
入度：多少边指向该顶点
出读：多少边从这个点为起点，指向别的顶点