文章目录
- 算法
- 暴力穷举
- 双指针和滑动窗口
- 桶计数
- 递归
- 动态规划
- 分治
- KMP算法
- 数据结构
- 数组
- 二维数组
- 字符串
- 哈希表
- 链表
- 树
- 队列
- 栈
- 图
- 场景
- 模式串匹配
- 前缀和
- 字符串去重问题
- 位运算(这类型题目有点炫技...就不多补充了...感兴趣的可以去leetcode自行找位运算专题)
算法
暴力穷举
O(n^2)
双指针和滑动窗口
一般用来优化暴力穷举,时间复杂度O(n)
常用场景:快慢指针,左右指针以及滑动窗口[left,right]
滑动窗口用来解决子串最值问题
滑动窗口算法模板
int left,right,len=0 //初始化while(right<xx){window_conditonwhile(condition){window_changeleft++}if(condition)(len_change)right++;}
无重复字符的最长子串
桶计数
假设区间范围为[0,5] 整数
可声明6个桶 来分别计数
桶计数技巧可用来计数,统计分布
递归
有起始和终止条件,有递归关系用递归很好解
经典题目:
杨辉三角
斐波那契数列
动态规划
分治
KMP算法
时间复杂度:O(m+n)
s1="ABCDEF" //主串
S2="ABAA" //模式串
最大公共前后缀长度表
A | B | A | A |
---|---|---|---|
0 | 0 | 1 | 1 |
最大公共前后缀长度表计算
失配时,模式串向右移动的位数为:已匹配字符数 - 失配字符的上一位字符所对应的最大长度值
next数组的话
next 数组的值是除当前字符外(注意不包括当前字符)的公共前后缀最长长度
等价于最大公共前后缀长度表往右移动一位,首位为-1
A | B | A | A |
---|---|---|---|
-1 | 0 | 0 | 1 |
KMP算法详解(写的非常通俗易懂)
数据结构
数组
存相同的数据类型,有索引
查找O(1)
插入和删除 O(n)
二维数组
int[][] array = new int[][]{{1,2,3}};
int[][] array = new int{{1,2,3}};
字符串
实质就是不可变(final)的char数组
哈希表
key-value 键值对 哈希函数
解决哈希冲突 (链地址法)
链表
树
队列
先进先出的结构,front 队首指针,rear 队尾下标
栈
先进后出的结构,push,pop,peek方法
计算器
有效的括号
图
场景
模式串匹配
KMP
前缀和
即声明一个长度比原数组大一的preSum数组存sum[i0]+…+sum[ij] ,第一个索引值为0,二维数组则是增加一列第一列值为0
这样在计算总和时用这个preSum数组时间复杂度O(n)
1480. 一维数组的动态和
643. 子数组最大平均数 I
304. 二维区域和检索 - 矩阵不可变
字符串去重问题
位运算(这类型题目有点炫技…就不多补充了…感兴趣的可以去leetcode自行找位运算专题)
两个相同的数字进行异或操作得到0
a^a=0;
只出现一次的数字
交换两个数字 (一个数异或同一个数两次还是那个数)
int a=10;b=30;
a=a^b;
b=a^b;
a=a^b;
相同的数字进行异或操作得到0
a^a=0;
待更新…