【已完结】手把手跟饲养员刷算法+jucdemo
【摘要】 我再不更新，就要接着鄙视自己了~好家伙，平时也不推文了，写了技术类文章都不闻不问，写点心理活动都看的起劲。讲真，我通宵加完班那天，做了个实现弹幕的梦，我的天，没把我累屎，最近的研究一下这个github地址```javascripthttps://github.com/kkget/LeetcodeDemo.git```耗时15天刷完，但也不是完全刷完，因为后面的是只刷了概念，现在结合起来是Da...
我再不更新，就要接着鄙视自己了~
好家伙，平时也不推文了，写了技术类文章都不闻不问，写点心理活动都看的起劲。讲真，我通宵加完班那天，做了个实现弹幕的梦，我的天，没把我累屎，最近的研究一下这个
github地址
```javascript
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
```javascript
给定一个二进制数组， 计算其中最大连续 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的大小，谁大返回谁
```javascript
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的源码
```javascript
boolean removed = false;
final Iterator<E> each = iterator();
while (each.hasNext()) {
if (filter.test(each.next())) {
each.remove();
removed = true;
}
}
return removed;
```
```javascript
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
```javascript
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 非常相似带有指向数据的指针
图文版见博客地址
```javascript
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/
```
【声明】本内容来自华为云开发者社区博主，不代表华为云及华为云开发者社区的观点和立场。转载时必须标注文章的来源（华为云社区）、文章链接、文章作者等基本信息，否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）