个人git仓库,不定期更新

1
https://github.com/kkget/LeetcodeDemo.git

时间复杂度

算法的执行效率，算法的执行时间与算法的输入值之间的关系
O(N) 大O表示法
O(1)
O(log N):二分查找

图1
图1
图1
图1
图1
图1
图1
图1
图1
图1
图1
图1

1.先看里面是否有循环，有循环不看常量
没有循环基本就是O(1)

图1
图1

空间复杂度：

算法的存储空间与输入值之间的关系

图1
图1

1.永远都是占用int类型的空间O(1)
2.站空间的都是变量O(N)
看空间复杂度要找的就是变量，array随着nums变化而变化

图1
图1

如果是递归也是O(N)

图1
图1

时间换空间，空间换时间
面试官喜欢哪一种？

图1
图1

数组：连续空间存储相同类型的元素，必须都要满足
数组的
访问
搜索
插入
删除
时间复杂度
访问是O(1),其他是O(N)
特点:适合读多写少

图1
图1

P10【数据结构】【链表Linked List】知识点讲解
存储了元素和下一个元素的指针next index
单端链表
双端链表：还存储了前一个元素的next index
插入和删除快 O(1) O(1)
访问
搜索

图1
图1

特点:读少写多

图1
图1

new LinkedList
add
list.get(i)
iter
remove
.size

图1
图1
图1
图1
  1. 【数据结构】【队列Queue】知识点讲解
    图1
    图1
    图1
    图1
    图1
    图1
1
2
3
4
5
6
7
8
9
10
11
java中定义队列 一般这样定义： Queue queue = new LinkedList();

当采用LinkedList来实现时，api的使用和对用关系如下：

队列方法       等效方法

offer(e)      offer(e)/offerLast(e)  //进队列，将元素加入队列末尾

poll()        poll()/pollFirst()  //获取队列头的元素并移除

peek()        peek()/peekFirst()  //获取队列头的元素       isEmpty() //判断是否为空
图1
图1

栈的数据结构

压栈，浏览器后退
访问O(1)
搜索O(N)
插入O(1)
删除O(1)

图1
图1
图1
图1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
 

示例 1：

输入：s = "()"
输出：true
示例 2：

输入：s = "()[]{}"
输出：true
示例 3：

输入：s = "(]"
输出：false
示例 4：

输入：s = "([)]"
输出：false
示例 5：

输入：s = "{[]}"
输出：true
 

提示：

1 <= s.length <= 104
s 仅由括号 '()[]{}' 组成

来源：力扣（LeetCode）

思路
把所有左括号先入栈，如果遇到右括号则pop出来，
最后看栈的长度

数据结构哈希表HashTable

Hash碰撞
解决hash碰撞，进化成链表，指针指向nextIndex
如果发生碰撞，时间复杂度是O(K)
k:碰撞元素的个数

图1
图1

数据结构 树

1.父子关系
节点，根节点，叶子节点
高度 深度 层
二叉树 最多有两个节点

图1
图1

完全二叉树 从上到下 从左到右

图1
图1

堆数据结构

一种二叉树的结构
堆：1.完全二叉树
2.每个节点>= or <=孩子节点
最大堆 最小堆
删除时删除的堆顶元素
堆的常用操作