【已完结】手把手跟饲养员刷算法+jucdemo

原创
05/04 13:17
阅读数 0

我再不更新,就要接着鄙视自己了~


好家伙,平时也不推文了,写了技术类文章都不闻不问,写点心理活动都看的起劲。讲真,我通宵加完班那天,做了个实现弹幕的梦,我的天,没把我累屎,最近的研究一下这个

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. 
提示:
输入的数组只包含 01输入数组的长度是正整数,且不超过 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/

本文分享自微信公众号 - 赵KK日常技术记录(gh_cc4c9f1a9521)。
如有侵权,请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一起分享。

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部