数据结构和操作 目录 数据结构和操作 复杂度 1.算法的时间复杂度 2.算法的空间复杂度 数据结构 1.数组Array 1.1 复杂度 1.2 java中数组常用操作 1.3 python中数组常用操作 1.4 常见注意 2.链表
- 数据结构和操作
- 复杂度
- 1.算法的时间复杂度
- 2.算法的空间复杂度
- 数据结构
- 1.数组Array
- 1.1 复杂度
- 1.2 java中数组常用操作
- 1.3 python中数组常用操作
- 1.4 常见注意
- 2.链表Linked List
- 2.1 复杂度
- 2.2 java中链表常用操作
- 2.3 python中链表常用操作
- 3.队列Queue/Deque
- 3.1 复杂度
- 3.2 java中队列常见操作
- 3.3 python中队列常用操作
- 4.栈stack
- 4.1 复杂度
- 4.2 java中栈常用操作
- 4.3 python中栈常见操作
- 4.4 栈的常见注意
- 5.哈希表HashTable
- 5.1 复杂度
- 5.2 java中哈希表常用操作
- 5.3 python中哈希表常用操作
- 5.4 常见注意
- 6.集合Set
- 6.1 复杂度
- 6.2 java中集合常见操作
- 6.3 python中集合常见操作
- 6.4 常见注意
- 6.树Tree
- 概念
- 性质
- 遍历
- 7.堆Heap
- 7.1 概念
- 7.2 复杂度
- 7.3 java中堆常用操作
- 7.4 python中堆常用操作
- 8.图Graph
- 概念
- 1.数组Array
- 总结
- 关于排序好的数组；
- 关于历史信息
- 复杂度
大O表示法，常数的就不要了，主要是去看循环，看循环体循环了多少次。其实就是主要去关注控制循环结束的条件，for里对应很多的n，n^2; while里循环条件如果有涉及到了循环体，有很多是logN；
2.算法的空间复杂度主要去关注变量，尤其是数组；然后去关注递归；
数据结构 1.数组Array连续的； 相同类型的； -> 读多写少；
1.1 复杂度访问 access：根据索引找元素：O(1);
搜索 search：在整个数组里去找元素：O(N);
插入 insert：O(N)；
删除 delete：O(N);
//创建数组的两种方法：
int[] array = new int[3]; //知道数组长度；
ArrayList<Integer> array = new ArrayList<>(); //不知道要创建的数组长度；
--------------------------------------
//ArrayList中的方法：
插入： array.add(4); //在尾端插入4；
array.add(3,4); //在索引3处插入4；
访问： array.get(3); //访问索引为3的元素；
更新： array.set(3,4); //更新索引3处的元素为4；
删除： array.remove(3); //删除元素3；
长度： array.size(); //注意不是第一种方式的length；
查找： array.contains(4);
转数组：array.toArray(new int[n]); //括号里写具体的数组类型，不然都转成object了；
List<Integer>转int[]: int[] arr = list.stream().mapToInt(Integer::valueOf).toArray();
--------------------------------------
//此外在数组中常用到排序等，可以直接调用Arrays类；
Arrays类常用方法：
Arrays.sort(nums); //对数组nums按照升序排序；复杂度：O(NlogN);
Arrays.toString(nums); //将数组内容转化为字符串；
Arrays.asList(nums[1],nums[2],nums[3]); //将数组转化为List集合。使用对象类型数组。
//注意此方法得到的list数组的长度是不可变的。也就是不能删除或添加了。
Array.binarySearch(); //二分搜索指定元素下标(找到返回下边，
//找不到返回一个负数，取反~后是该放在的位置，注意一定需要是排序好的数组。只要用二分法必须排序好)
Arrays.copyOf(arr,3); //截取arr数组的前3个数据，3指的是长度，如果大于数组长度，则补0；
Arrays.fill(arr, ‘a’); //将数组全填为a；
Collections类常用方法：
Collections.reverse(list); //直接对列表中元素反转；
a = [] # 创建数组
a.append(1) #在末尾添加；
a.insert(2,1) #在索引2添加元素1；
a[2] #访问元素；
a[2] = 2 #更新元素；
a.remove(4) #删除4这个元素；
a.pop(1) #删除1索引的元素；不指定默认是最后
a.pop() #删除最后一个元素；
del a[4] #删除索引4的元素；
size = len(a) #获取a的长度；
index = a.index(2) #获取元素2的索引；
a.sort() #升序；
a.sort(reverse = True) #降序；
a[::-1] #数组反转
--------------------------------------
for i in a: # 遍历数组的三种方法,尽量用1，2,避免出现下标
print(i)
for index, element in enumerate(a):
print("index at ",index, "is :",element)
for i in range(0, len(a)):
print("i:" , i, "element : ", a[i])
- 1、数组中经常有一类题型：往往和字符串结合起来比如找出某某子数组或者子串，其和为多少等等，这时候常用前缀和去解，即 连续子数组+和 --> 前缀和；连续子串+最值 --> 滑动窗口
- 2、如果看到要在有序数组中找某个值，那就用二分查找去解，即有序数组+搜索 --> 二分查找；
不连续的； 相同类型的； -> 写多读少；
2.1 复杂度访问 access：根据索引找元素：O(N);
搜索 search：在整个数组里去找元素：O(N);
插入 insert：O(1)；
删除 delete：O(1);
//创建链表
LinkedList<Integer> list = new LinkedList<>();
--------------------------------------
//LinkedList中的方法
添加：list.add(3); //在末尾插入元素3；
list.add(2,3); //在2的位置插入元素3；
list.addLast(3); //在末尾插入元素3，可以把链表作为栈或者队列；
访问：list.get(2); //得到索引2的元素；
搜索：list.indexOf(3); //找到元素3的索引；
更新：list.set(2,3); //更新索引2的元素为3；
删除：list.remove(2); //删除索引为2的元素；
长度：list.size(); //链表的长度；
linkedlist = deque() #创建链表；
linkedlist.append(1) #末尾添加元素1；
linkedlist.insert(2,1) #在索引2位置添加元素1；
element = linkedlist[2] # 访问索引2的元素；
index = linkedlist.index(2) #获取元素2的索引；
linkedlist.remove(4) #删除4这个元素；
del linkedlist[4] #删除索引4的元素；
size = len(linkedlist) #获取a的长度；
排队 -> 先到先得，先进先出
3.1 复杂度访问 access：根据索引找元素：O(N);
搜索 search：在整个数组里去找元素：O(N);
插入 insert：O(1)；
删除 delete：O(1);
//创建队列
Queue<Integer> queue = new LinkedList<>();
--------------------------------------
//队列的方法
添加：queue.add(3);
queue.offer(3) //在队尾添加元素3；offer要更优一些；
获取即将出队的元素：temp = queue.peek(); //获取出队的元素；
删除即将出队的元素：temp = queue.poll();
判断是否为空：queue.isEmpty();
队列长度：queue.size();
--------------------------------------
//双端队列：相当于集成了队列和栈；能够先入先出，也能后后入先出；
Deque<Integer> deque = new LinkedList<>(); //创建一个双端队列；
deque.pollLast(); //移除队尾元素；
deque.pollFirst(); //移除队首元素；
deque.peekFirst(); //队首元素；
deque.peekLast(); //队尾元素；
from Collections import deque
queue = deque() #创建双端队列；
queue.append(2) #添加元素；
temp1 = queue[0] #获取即将出队的元素；
temp2 = queue[-1] #获取队尾元素
temp2 = queue.pop() #删除队尾元素；
temp2 = queue.popleft() #删除出队的元素；
len(queue) == 0 # 判断队列是否为空；
--------------------------------------
while len(queue) > 0: #遍历队列
temp = queue.popleft()
print(temp)
箱子 -> 先进后出
4.1 复杂度访问 access：只访问栈顶：O(1);
搜索 search：在整个数组里去找元素：O(N);
插入 insert：O(1)；
删除 delete：O(1);
//创建栈
Stack<Integer> stack = new Stack<>();
--------------------------------------
//栈方法
添加：stack.push(3); //在栈顶添加元素3；
获取栈顶元素：stack.peek();
删除栈顶元素：stack.pop();
栈的大小：stack.size();
是否为空：stack.isEmpty();
stack = [] # 创建栈；
stack.append(1) #添加元素；
stack[-1] #获取栈顶元素
temp = stack.pop() #删除栈顶元素；
--------------------------------------
while len(stack) > 0: #遍历队列
temp = stack.pop()
print(temp)
1、栈往往会用来解决那种两两匹配，两两抵消消消乐的问题，比如常见的有效括号等，就是判断后入栈的相邻元素是否有相互关系能够相互抵消，
5.哈希表HashTable键值对 key-value
5.1 复杂度访问 access：无;
搜索 search：O(1); 如果碰撞：O(K) K为碰撞的个数
插入 insert：O(1)；
删除 delete：O(1);
//创建哈希表
①、String[] hashTable = new String[4]; //通过数组创建，因为数组的index默认作为了key；
②、HashMap<Integer, String> map = new HashMap<>();
--------------------------------------
//哈希表方法
添加：map.put(1, "lihua");
更新：map.put(1, "liming");
删除：map.remove(1);
获取：map.get(3);
获取键值：map.keySet(); //是个数组；
获取值： map.values(); //是个数组；
检查key存在：map.containsKey(3);
长度：map.size();
是否为空：map.isEmpty();
有key：是key对应的value，没key：默认值；map.getOrDefault(key,default);
map.put(key, val); //没key，添加；有key，会覆盖原来的；
map.getOrDefault(key, default); //有key，得到其value； 没key，得到default值；
map.putIfAbsent(key, val); //if存在key，那就不会放入，不存在的时候再存；
//遍历哈希表：
for(Map.Entry<String, Integer> entry : map.entrySet()){
entry.getKey()；
entry.getValue(); //得到key和value；
}
hashtable = [] #通过数组创建，key即为数组下标；
hashtable[2] = "liming" #添加元素/修改元素
----------------------------------------------
mapping = {} #通过字典创建；
# 这样的时候if有key1不在哈希表里直接mapping[key1]会报错
from collections import defaultdict
mapping1 = defaultdict(int) #参数是一个函数，可以是int，str，float，list等，意思就是每个元素会默认的是当前的类型的默认值
# 比如现在就是默认的是0， list就会默认的是[]
# 另外，Counter这个函数对可迭代对象统计个数后，返回也是一个字典，并且这个字典if有元素不在，然后直接count1[a]，这样不会有错。
mapping["key1"] = "liming" #添加元素/修改元素；
mapping.get(key, default = None) # 第二个参数在key不存在时可以指定一个返回值；例如 mapping.get(key, []) key不存在的时候会返回一个空列表
# 其次注意字典的key只能是不可变对象；
mapping.pop("key1") #删除元素
“key” in mapping #检查key是否存在；
mapping.values() #得到value值组成的列表
mapping.keys() #key值组成的列表
mapping.items() #仍然是列表，列表里存放的是元祖，（key, value）
# 在python3.6之后，dict是按照添加元素的顺序进行返回的；
# if想要dict是有序的，可以用OrderedDict
from collections import OrderedDict
dict1 = OrderedDict() # 则是按照元素的插入顺序；
- 哈希表在刷题的时候常常会用在涉及到次数的问题上，比如某个数字或者某个字符出现了几次；
无序、不可重复 主要作用：查看重复元素
6.1 复杂度访问 access：无;
搜索 search：无哈希冲突O(1); 有哈希冲突：O(K)
插入 insert：无哈希冲突O(1)；有哈希冲突：O(K)
删除 delete：无哈希冲突O(1)；有哈希冲突：O(K)
//创建hashset
HashSet<Integer> set = new HashSet<>();
//hashset方法
添加：set.add(4); //如果Set集合中不包含要添加的对象，则添加对象并返回true；否则返回false。
搜索：set.contains(4);
删除：set.remove(4);
长度：set.size();
遍历：
Iterator it = set.iterator();
while (it.hasNext()) {
System.out.print(it.next());
}
s = set() #创建一个集合
s.add(2) #添加元素2；
2 in s # 搜索2是否在集合s；
s.remove(2) #删除元素2；
- set在刷题的时候常常会用在涉及到有无重复，独一无二，唯一等问题上，比如某个数字是否重复，是否出现过，用的都是set的不可重复性；
父子关系
概念- 节点：根节点、叶子节点(度为0的节点)；
- 节点的度：一个节点含有的子节点的个数；
- 树的度：最大的节点的度；
- 二叉树：每个节点最多有两个孩子；节点的度可以为0,1,2；
- 满二叉树：除了叶子节点，每个节点都有两个孩子；并且所有叶子节点在一层；
- 完全二叉树：从上到下，从左到右，依次填满；
满二叉树的概念最小；限制最多，满二叉树一定是完全二叉树
性质1.完全二叉树除了最后一层外，下一层节点个数是上一层两倍，
如果一颗完全二叉树的节点总数是n，那么叶子节点个数为n/2(n为偶数)或(n+1)/2(n为奇数)；
- 前序遍历：根节点 -> 左子树 -> 右子树；
- 中序遍历：左子树 -> 根节点 -> 右子树；
- 后序遍历：左子树 -> 右子树 -> 根节点；
常用
- 二叉树解题的时候往往用到的是递归方法，注意千万不要陷入递归压栈过程中去，就想函数功能，终止条件，一层节点能做什么，什么时候做。
- 深度优先(DFS)与广度优先(BFS): DFS与BFS都是用来遍历的手段，在树和图里都是用这两种方法。
-
- DFS：DFS的意思就是比如说一颗树，就先到树的左节点，然后再往树的左节点，一直到最后走不了了，然后回到上一层，去右节点，再回到上一层，如此往复。对于图，就是去往开始节点的一个邻居节点，然后再去此邻居节点的邻居节点，然后到头，返回上一个，如此往复。所以只要用到DFS肯定会用到递归。
-
- BFS：BFS的意思就是比如说一棵树，到左节点，然后到右节点，然后再到左节点的下一层，右节点的下一层，这样子一层一层的往下走，直到最后一层。对于图，去往源点的邻居节点，把源点的邻居节点都走完之后，再去下一个节点，所以BFS就会用到队列的结构，在树里，把节点入队，然后每次出队，就把出队节点的左右孩子入队，这样做到一层一层遍历。在图里，把源点入队，然后把出队点的邻居节点都入队。这样往复。但是在图里为了防止重复访问，需要设置当前节点是否被访问过。(比如可以设置一个vis数组设置为true或false，或者设置一个哈希表这样)
-
- 在树里经常用DFS，在图里经常用BFS(因为树可以很方便的去递归左右子树，而图则对邻居节点比较方便)；
-
- 树和图里的BFS区别：
- 1.树只有一个root，而图可以有多个源点，所有首先需要将多个源点入队。
- 2.树是有向的因此不需要设置标志是否访问过，而对于无向图而言，必须得标志是否访问过！并且为了防止某个节点多次入队，需要在入队前将其设置为已访问！
- 3.一个源点的广度优先和多个源点的广度优先：广度优先搜索
- 前提：完全二叉树
- 根节点全部≥叶子节点：大根堆：堆顶元素最大；
- 根节点全部≤叶子节点：小根堆：堆顶元素最小；
访问 access：无;
搜索 search：查看堆顶元素：O(1);
插入 insert：O(logN):每次添加的元素去和父亲节点做对比；和兄弟节点没有关系；
删除 delete：O(logN)
// 创建堆
PriorityQueue<Integer> minheap = new PriorityQueue<>(); //创建小根堆；
PriorityQueue<Integer> queue = new PriorityQueue<Integer>(new Comparator<Integer>() {
public int compare(Integer num1, Integer num2) {
return num2 - num1;
}
});
//堆的排序指的是从上往下排；
//创建大根堆，注意要排序，重写比较器；
/**o1-o2为升序序排列，o2-o1为降序排列，若具体到某一字段，则根据该字段进行排列*/
@Override
public int compare(Node o1, Node o2) {
if (o1.x==o2.x) //若x属性相等，根据y来升序
return o1.y-o2.y;
return o1.x-o2.x;//x属性不相等，根据x来升序排列
}
----------------------------------------------
//PriorityQueue方法
添加元素：minheap.add(3);
堆顶元素：minheap.peek();
删除堆顶元素：minheap.poll();
堆里元素数量：minheap.size();
边遍历边删除：
while( !minheap.isEmpty() ){
System.out.println(minheap.poll());
}
import heapq
minheap = []
heapq.heapify(minheap) #第一种方法，先创建一个列表，然后堆化；只能创建小根堆
heapq.heapush(minheap, 10) #第二种方法，添加元素；
minheap[0] #堆顶元素；
heapq.headpop(minheap) #删除堆顶元素；
----------------------------------------------
while len(minheap) != 0:
print(heapq.heapop(minheap))
# 创建大根堆的方法：乘以-1
l1 = list(str1)
heapq.heapify(l1) #小根堆
newl1 = [(-i,l1[i]) for i in range(len(l1)]
heapq.heapify(newl1) #按照第一个元素变为了小根堆，也就是i的大根堆
max_heap = list()
while newl:
_, s = heapq.heappop(newl)
max_heap.append(s)
邻居关系
概念- 顶点；邻居顶点；边；
- 度(degree)：每个顶点有几条边；
- 无向图；
- 有向图：
- 入度：有多少条边指向该顶点；
- 出度：有多少条边指向别的顶点；
- 权重图：
- 求最短路径；
- 贝尔曼-福特算法；
- 迪克斯特拉算法；
- 求最短路径；
数组
链表
队列：先入先出；
栈：后入先出；
堆：最大堆；最小堆；
哈希表： key | value;
哈希集合：无序、不可重复；
树
图
- 知道每个结构的特性；
- 每个结构的增删改查复杂度；
排序好的数组有以下几种常见的处理方法：
- 1.二分查找：二分查找的使用前提就是数组必须是有序的，这样才能每次取中间值去逼近；二分查找总结
- 2.首尾双指针：首尾双指针也常常用在排序数组上，尤其是涉及到两个数之和时，因为如果和大了或者小了可以去移动首或尾指针；
- if想要记录历史中的最大值或者最小值，或者是历史中的顺序问题，那总不能再次重新遍历了，往往就会用到优先队列(堆）
比如大根堆：总是维持了历史中的k个最小的，if来的比顶还大，那就直接走，if来的比堆顶小，那就把最大的(堆顶)弹出去，小的进来，这样不断更新堆，也就维持了k个最小的；