我再不更新,就要接着鄙视自己了~
好家伙,平时也不推文了,写了技术类文章都不闻不问,写点心理活动都看的起劲。讲真,我通宵加完班那天,做了个实现弹幕的梦,我的天,没把我累屎,最近的研究一下这个
github地址
https://github.com/kkget/LeetcodeDemo.git
耗时15天刷完,但也不是完全刷完,因为后面的是只刷了概念,现在结合起来是Day5Test,一共是15天。
里面是结合题目,注释,伪代码,demo,并个别题目搭配了leetcode的高赞评论写的,后续还要不间断的去刷题,另外小马哥的juc系列实在是太肝了,三刷仍然进行中。肝的很起劲,也因为都是干货,干脆放一起得了。
算法百科
算法(Algorithm)是指解题方案的准确而完整的描述,是一系列解决问题的清晰指令,算法代表着用系统的方法描述解决问题的策略机制。也就是说,能够对一定规范的输入,在有限时间内获得所要求的输出。如果一个算法有缺陷,或不适合于某个问题,执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量
算法的时间复杂度
算法的执行效率,算法的执行时间与算法的输入值之间的关系
用大O表示法表示O(1)<O(log N)<O(N)<O(NlogN)
先看里面是否有循环,有循环不看常量,没有循环基本就是O(1)
算法的空间复杂度
算法的存储空间与输入值之间的关系
1.永远都是占用int类型的空间O(1)
2.占空间的都是变量O(N)
看空间复杂度要找的就是变量,array随着nums变化而变化
数据结构篇
数组:连续空间存储相同类型的元素,必须都要满足
衡量一个数据结构的复杂度从
访问O(1)
搜索O(N)
插入O(N)
删除O(N)
四个方面去衡量
访问快,那么适合读多写少的场景
配套代码题见github
经典题:485
给定一个二进制数组, 计算其中最大连续 1 的个数。
示例:
输入:[1,1,0,1,1,1]
输出:3
解释:开头的两位和最后的三位都是连续 1 ,所以最大连续 1 的个数是 3.
提示:
输入的数组只包含 0 和 1 。
输入数组的长度是正整数,且不超过 10,000。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/max-consecutive-ones
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
解题思路:
1.既然是连续1的个数,需要一个变量计算count,结果值result 2.如果是1就count++否则要清空本次的计数直到遍历完毕
3.比较result与count的大小,谁大返回谁
public class ArrayDemo485 {
public static void main(String[] args) {
ArrayList<Integer> list = new ArrayList<>();
//最大连续1的个数 485
String str="1,2,1,1,1,1,1,2,3,4,3,1,2,1,1,1,1,1,1";
String[] split = str.split(",");
for (String s : split) {
list.add(Integer.parseInt(s));
}
int count=0;
int result=0;
//判空返回
for (int i = 0; i < list.size(); i++) {
if(list.get(i).equals(1)){
count=count+1;
}else{
result=max(result,count);
count=0;
}
}
System.out.println(max(result,count));
}
private static int max(int result, int count) {
if(result>count){
return result;
}else{
return count;
}
}
}
链表Linked List:存储了元素和下一个元素的指针next index
单端链表:比较常见
双端链表:还存储了前一个元素的next index
访问O(N)
搜索O(N)
插入O(1)
删除O(1)
特点:读少写多
LeetCode203.206题
思路:
如果头节点等于给定值,把节点执行头结点的下一个元素,移除后,头节点指向下一个元素
不等于给定值,移到下一个元素
如果项目实际操作肯定用api了removeif了
看下removeif的源码
boolean removed = false;
final Iterator<E> each = iterator();
while (each.hasNext()) {
if (filter.test(each.next())) {
each.remove();
removed = true;
}
}
return removed;
public static ListNode removeElements(ListNode head, int val) {
ListNode dummy = new ListNode(0);
//临时节点的指针
dummy.next = head;
ListNode prev = dummy;
while (head != null) {
//记录前置指针
if (head.val == val) {
prev.next = dummy.next;
} else {
prev = head;
}
head = head.next;
}
return dummy.next;
}
后续代码见git,就不再给出了
队列Queue:先入先出
访问O(N)
搜索O(N)
插入O(1)
删除O(1)
API
java中定义队列 一般这样定义:Queue queue = new LinkedList();
当采用LinkedList来实现时,api的使用和对用关系如下:
队列方法 等效方法
offer(e) offer(e)/offerLast(e) //进队列,将元素加入队列末尾
poll() poll()/pollFirst() //获取队列头的元素并移除
peek() peek()/peekFirst() //获取队列头的元素 isEmpty() //判断是否为空
933
栈的数据结构:先进后出,压栈,浏览器后退,子弹夹
访问O(1)
搜索O(N)
插入O(1)
删除O(1)
哈希表HashTable:键值对
解决hash碰撞,进化成链表,指针指向nextIndex
如果发生碰撞,时间复杂度是O(K)
k:碰撞元素的个数
set集合:无序不重复
数据结构 树
1.父子关系
节点,根节点,叶子节点
高度 深度 层
二叉树 最多有两个节点
完全二叉树,满二叉树,普通二叉树
满二叉树一定是完全二叉树
堆数据结构:一种二叉树的结构,最大堆,最小堆
堆:1.完全二叉树
2.每个节点>= or <=孩子节点
最大堆 最小堆
Graph 图:
无向图
有向图
权重图
算法篇 1.双指针算法
对撞双指针
快慢双指针
2.二分查找
二分查找一定要有序
时间复杂度(logN)
3.滑动窗口 Sliding Window
减少while循环
1+2+3=6
6-1+6=11 = 2+3+6 6-移除的数+加入的数
11-2+4=13 =3+6+4
13-3+5=15 =6+4+5
4.递归 Recursion 函数直接或间接调自己
禁止套娃,有明确的结束条件
5.分治算法,大问题切割为小问题
6.回溯算法Backtracking一层一层向下递归
找到所有的结果,枚举
7.深度优先搜索算法DFS
从根节点开始,尽可能深的搜索每一个分支
迷宫
8.宽度优先算法BFS
层层遍历,层层递归
9.并查集 Union Find
union:合并两个元素为同一个根节点
Find:找到元素的根节点
10.并查集优化
Union Find Optimization
Quick Find
Quick Union
11.贪心算法 Greedy
每一步做出的都是当前看起来最好的选择,局部最优解,不是全局
最优解不满足时取次优解
12记忆化搜索 Memoization
把计算出来的结果放到某个地方以便下一次使用
减少重复计算
13.动态规划 Dynamic Programming
计数
求值
求存在性
14前缀树 Trie 字典树,前缀树
跟B+tree 非常相似带有指向数据的指针
图文版见博客地址
https://kkget.github.io/2021/04/21/%E8%B7%9F%E9%A5%B2%E5%85%BB%E5%91%98%E5%88%B7%E7%AE%97%E6%B3%95/