【已完结】手把手跟饲养员刷算法+jucdemo
我再不更新，就要接着鄙视自己了~
好家伙，平时也不推文了，写了技术类文章都不闻不问，写点心理活动都看的起劲。讲真，我通宵加完班那天，做了个实现弹幕的梦，我的天，没把我累屎，最近的研究一下这个
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/