力扣刷题心得_JAVA-EW帮帮网

数学 > 数组 > 链表 > 字符串 > 哈希表 > 双指针 > 递归 > 栈 > 队列 > 树
//一般力扣中传入的参数和新建的对象作为返回值,都不列入空间复杂度中
//但是面试的时候要和面试官商量好,灵活定义空间复杂度
//当然最好是就在传入的对象作为返回值,(在原对象上改,没这种方法就没办法了)
2字节是65535

文章目录

数组
- 方法API
- - 数组API
  - 针对int或integer
链表
- 关于栈\队列\链表首尾关系
字符串
哈希表
- HashMap
双指针
递归
栈
队列
树
- 广度优先搜索(BFS)和深度优先搜索(DFS)

数组

方法API

数组API

java.util.Arrays包
Arrays.toString(arr);转为字符串
Arrays.binarySearch();二分查找
Array.copyOf();拷贝数组
Array.copyOfRange();拷贝数组(指定范围)
Arrays.fill();填充数组
Arrays.sort();排序,默认升序

针对int或integer

java.lang.Math包
Math.abs() //获取绝对值
Math.pow(a,b)//获取平方值a为值,b为幂次

链表

关于栈\队列\链表首尾关系

Deque提供的重要的API
add
addAll
offer
poll
peek
push
pop
size

以LinkedList为例,[1,2,3,4,5]左边为表首,右边为表尾
入栈出栈左边入出
入队列右边进,出队列左边出
不重要的API
addFirst
addLast
offerFirst
offerLast
removeFirst
removeLast
pollFirst
pollLast
getFirst
getLast
peekFirst
peekLast

字符串

StringBuilder

提供的API
StringBuilder sb = new StringBuilder();
sb.charAt();
sb,setCharAt();
sb.deleteCharAt();

KMP模式匹配算法

一个人能能走的多快不在于他在顺境时能走多少步，而在于他在逆境时多久能找到曾经的自己。–KMP

步骤:

计算匹配串的next数组
根据next数组匹配主串和匹配串

关键点,好马不吃回头草,磨刀不误砍柴功
匹配串建立代表各位置情况的next数组

主串和匹配串的匹配能跳步,主要也是根据匹配串的子串前缀和后缀匹配特性处理的
总而言之.KMP算法就是不断保存和利用先验知识减少时间复杂度的算法

next数组的计算

next数组的计算就是匹配串的子串前缀和后缀匹配计算的过程(但并不是暴力计算,也是有技巧的)
next数组的优化步骤计算也是用到了之前子串前缀和后缀匹配的信息
关键思想:匹配串的前后缀匹不匹配,如果不匹配,后缀匹配的前缀的前后缀匹不匹配,依次类推…,如果字符串极长,这就是个迭代的过程了

哈希表

HashMap

Map<Integer,Integer> hashMap = new HashMap<>();
hashMap.put(key,value);//放入键值对
hashMap.get(key);//根据键获取值
hashMap.containsKey(key);//包不包含key
hashMap.containsValue(value);//包不包含value
hashMap.getOrDefault(key,0);//如何哈希中存在这个键,返回对应值,没有返回默认值

hashMap.entrySet()之后变为键值对对象才能增强for遍历
for(Entry<Integer,Integer> entrySet : hashMap.entrySet()){}

双指针

递归

栈

如果一个串或者线性表中要有一对数据要匹配或删除,用栈就很方便

队列

树

广度优先搜索(BFS)和深度优先搜索(DFS)

像树前中后序遍历都是深度优先搜索
深度优先搜索一般结合栈作为工具
二叉树的前中后序遍历可以用迭代遍历\递归遍历\统一迭代法遍历
无论是迭代遍历还是递归遍历都是用的栈的思想
迭代遍历使用的栈存数据
递归遍历使用的栈运行程序,每调用一次递归函数就入栈一个栈帧
可以说递归就是在逻辑和在jvm虚拟机层面上用的栈
层序遍历是广度优先搜索
广度优先搜索一般结合队列实现
用链表也可以,但是逻辑上太麻烦了,而队列就是以链表为基础,特殊的链表,实现特殊的功能,有队列为什么不用呢

力扣刷题心得_JAVA