- 博客(32)
- 收藏
- 关注
RSS订阅原创 两条链表相交一些列问题
public class LoopNode { //首先得判断这条链表有没有环 public Node getLoopNode(Node head){ //有环的话必须上三个节点以上，因此 if (head == null || head.next == null || head.next.next == null){ return null; } //链表有环情况，使用快慢指针 Nod
2021-07-15 14:57:09
85
原创 反转单链表中的部分链表
给定一个单向链表的头节点 head，以及两个整数 from 和 to，在单向链表上把第 from 个节点到第 to 个节点这一部分进行反转大致思路：1、找到要反转部分链表的前一个节点fPre和后一个节点tPos，把反转的部分先反转，然后重新连接fPre和tPos；2、若fPre为null，说明反转部分包括头节点，则返回的是反转部分的最后一个节点，即反转后的头结点，若不为空，则返回旧的头节点。public Node reversePart(Node head,int from,int to){.
2021-03-07 16:54:39
367
原创 反转单向链表和反转双向链表
反转单向链表和反转双向链表单向链表具体代码public static Node reverseList(Node head){ Node pre = null; Node next = null; while (head != null){ next = head.next; head.next = pre; pre = head; head = next; } return pre;}.
2021-03-07 16:51:10
103
原创 删除链表的中间节点和 a/b 处的节点
删除链表的中间节点和 a/b 处的节点首先是删除中间节点链表长度为n，n = 0, 不删除；n = 1, 不删除；n = 2, 删除第 1 个节点；n = 3, 删除第 2 个节点；n = 4, 删除第 2个节点；n = 5, 删除第 3 个节点；n = 6, 删除第 3 个节点；n = 7, 删除第 4 个节点；总结：从链表长度大于等于2时，每增加两个节点，删除节点后移一位。具体代码public static Node removeMidNode(Node head) {.
2021-03-05 15:51:57
118
原创 在单链表和双链表中删除倒数第K个节点
在单链表和双链表中删除倒数第K个节点先看单链表如果链表为空或者K值小于1，直接返回即可，除此之外，让链表从头走到尾，每走一步，K值减一，如下图：走到链表尾时:当K>0，说明没有倒数第K个节点，因此直接返回原链表即可；当K=0，说明链表刚好有K个节点，删除倒数第K个节点就是删除第一个节点，因此返回第二个节点，即head.next;当K<0，要找到删除节点的前一个节点，需要： 1、重新从头节点开始走，每移动一步，k值加1； 2、当k=.
2021-03-05 15:36:33
222
原创 打印有序链表的相同部分
打印有序链表的相同部分首先是有序链表，所以从两个链表的头开始遍历进行判断：如果head1的值<head2的，则移动head1；如果head1的值>head2的，则移动head2；如果head1的值=head2的，则打印这个值，然后head1和head2同时往下移动；具体代码public class Node { public int value; public Node next; public Node(int data){ th.
2021-03-05 15:33:44
82
原创 删除链表中指定节点
删除链表中指定节点思路：利用其他结构（这里利用栈结构）存放链表中除要删除的节点外的其他节点。依次将链表元素放入栈中，当遇到要删除的元素时跳过，最后将栈中元素重新连接成链表。具体代码public class removeValue { public static class Node{ public int val; public Node next; public Node(int val){ this.val =.
2021-03-05 15:23:15
378
2
原创 重建二叉树
根据前序遍历和中序遍历结果重建二叉树思路：1、前序遍历的第一个数字为原二叉树根节点的值；2、遍历中序序列，找到根节点位置，根节点左边序列即为左子树所有节点，右边序列即为右子树所有节点；3、用同样的方法（上面两个步骤）对剩下的小序列进行操作，即一个递归的过程。具体代码public class TreeNode { TreeNode left; TreeNode right; int value; public TreeNode(int value){ .
2021-03-04 13:55:06
120
2
原创 二叉树神级遍历方法--Morris遍历
Morris遍历morris遍历可以将额外空间复杂度降到O(1)，而常规的递归或者非递归遍历额外空间复杂度都是O(h)。常规的递归或者非递归遍历其实也用到了栈结构，在处理完子节点之后可以回到父节点，然而对于二叉树这种结构，都是从父节点指向子节点，所以子节点指向父节点通常使用栈结构来实现。 morris遍历避免使用栈结构来实现子节点到父节点，而是利用二叉树最下面一层节点指向null节点的指针指向上面某一个节点。比如二叉树最下面一层某个节点没有右孩子，那么该节点的right指针就指向空，这些指针被叫做空
2021-03-04 00:56:57
211
3
原创 求最大子矩阵的大小
给定一个整型矩阵 map，其中的值只有 0 和 1 两种，求其中全是 1 的所有矩形区域中，最大的矩形区域为 1 的数量。比如：map为矩阵，红框内即为所求，一共有6个1，返回值为6。解题思路：将问题转化为单调栈结构处理。1、遍历矩阵每一行元素，统计以当前行作为底的情况下，每个位置往上的 1的数量。使用高度数组 height 来表示。遍历到第一行时，height={1,0,1,1}；遍历到第二行时，height={2,1,2,2}；遍历到第三行时，height={3,2,3,0}；.
2021-03-02 19:53:23
172
原创 单调栈--找出数组中任意元素左右两边最近且比它小的元素位置
给定一个不含有重复值的数组 arr，找到每一个 i 位置左边和右边离 i 位置最近且值比 arr[i]小的位置。返回所有位置相应的信息。比如：输入： arr = [3,4,1,5,6,2,7]返回：{[-1, 2], [0, 2], [-1, -1], [2, 5], [3, 5], [2, -1], [5, -1]}解题思路：这个题目利用单调栈结构可以使时间复杂度降低到O(N)。首先题目是没有重复值的数组，注意，如果是有重复值的数组稍有区别。1、先准备一个栈，用来存放所给数组元素的位置；.
2021-03-02 15:57:12
737
原创 数据结构与算法--栈与队列
栈与队列1、设计一个能获取当前栈的最小值的栈1、设计一个能获取当前栈的最小值的栈设计一个能获取当前栈的最小值的栈。大致思路：1、申请两个栈，一个普通栈stackData，一个能获取最小值的栈stackMin；2、给两个栈中同时压入数据，压数规则：同时给两个栈压入数据，当要压入的数比stackMin栈顶的元素小时，将该数同时压入两栈，如果要压入的数大于stackMin栈顶的元素小时，将该数压入stackData中，将stackMin栈顶的数重新再压入stackMin，具体细节详见代码注释。举例
2021-02-24 08:39:07
199
原创 23种设计模式之观察者模式
观察者模式 (Observer)观察者属于行为型模式，其目的就是定义对象间的一对多的依赖关系，当一个对象的状态发生改变时，所有依赖于它的对象都得到通知并被自动更新。画图简单分析一下观察者模式一步一步的演化过程：1、图一，最简单的两个观察者A、B监听一个主题Subject；2、由于主题直接耦合观察者，因此产生了图二模式；3、由于图二中主题不具有复用性，因此产生了图三模式；4、形成最终版，其中：Subject：被观察的对象接口，一个Subject可以有多个IObserver；NewsP.
2021-01-19 21:06:12
127
2
原创 23种设计模式之代理模式--动态代理
代理模式（Proxy）代理模式就是为其他对象提供一种代理功能以控制对被代理对象的访问，其作用就是通过一个中间层达到间接访问目标对象的目的。代理模式分为静态代理和动态代理静态：由程序员创建代理类或特定工具自动生成源代码再对其编译。在程序运行前代理类的.class文件就已经存在了。动态：在程序运行时运用反射机制动态创建而成。2、动态代理在上一节中的静态代理中，一个代理只能代理一种类型，而且是在编译器就已经确定被代理的对象。而动态代理是在运行时，通过反射机制实现动态代理，并且能够代理各种类型的对象.
2021-01-17 00:39:39
173
原创 23种设计模式之代理模式--静态代理
代理模式（Proxy）代理模式就是为其他对象提供一种代理功能以控制对被代理对象的访问，其作用就是通过一个中间层达到间接访问目标对象的目的。代理模式分为静态代理和动态代理静态：由程序员创建代理类或特定工具自动生成源代码再对其编译。在程序运行前代理类的.class文件就已经存在了。动态：在程序运行时运用反射机制动态创建而成。1、静态代理静态代理的实现比较简单，代理类通过实现与目标对象相同的接口，并在类中维护一个代理对象。通过构造器塞入目标对象，赋值给代理对象，进而执行代理对象实现的接口方法，并实.
2021-01-17 00:35:41
103
原创 这种方式实现的字典序简直不要太简单!
字典序什么是字典序？举个例子给定一个字符串数组strs={“ba”,“b”}，可以将这些字符串进行任意顺序的拼接，然而得到的所有情况中只有一种是字典序最小的字符串拼接顺序。拿到这种题目首先想到的是可以将所有的strs按照字典序排序，然后将串起来的结果返回，但是这种方式是错误的，按照这种思路得到上述例子的结果是bba，而正确答案是bab。因此这里提供了另外一种思路。假如要比较两个字符串，可以比较将两个字符串起来之后比较其字典序，得到较小的字典序排序，将最后的结果全部串起来就是最终答案。.
2020-08-14 10:21:46
161
原创 设计一个能够获取栈中最小值的栈。
设计一个栈要求：支持 push，pop，top 操作，并能在常数时间内检索到栈中最小元素。示例public Stack<Integer> stackMin = new Stack<Integer>();stackMin.push(-3);stackMin.push(10);stackMin.push(-32);stackMin.getMin();-->返回-32stackMin.pop();stackMin.top();stackMin.getMin.
2020-08-08 09:25:54
219
原创 两句话总结8锁问题
1、被synchronized 修饰的方法，锁的对象是方法的调用者也就是实际new的对象，先调用的先执行！执行sleep（）方法的线程并不会释放锁。2、只要方法被 static 修饰，锁的对象就是 Class模板对象,这个则全局唯一！...
2020-07-17 09:23:00
73
原创 轻松了解Volatile关键字
Volatile关键字Volatile是java虚拟机提供的轻量级的同步机制。1、保证可见性可见性：举个例子，有三个线程A、B、C，假设A线程想要修改主内存中的一个数据num，因为每个线程都有自己的工作内存，想要修改数据的话，需要将num获得放到自己的工作内存，然后修改完成再返回给主内存。num在修改之前等于5，A线程修改之后变为8，当B线程或C线程再去拿num数据时，获得的是8而不是5，这就是保证了可见性。总结一句话就是，某一线程修改数据后，要立马通知其他线程自己修改了！public cl.
2020-07-16 16:41:58
82
原创 HashMap系列之重要方法源码详解
** HashMap 中重要的构造方法：**1、构造一个空的 HashMap，默认初始容量（16）和默认负载因子（0.75）。public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; // 将默认的加载因子0.75赋值给loadFactor，并没有创建数组}2、 构造一个具有指定的初始容量和默认负载因子（0.75）HashMap。 // 指定“容量大小”的构造函数 public HashMap(int initialCapa.
2020-07-11 16:35:16
123
原创 HashMap系列之成员变量介绍
1、初始化容量当我们根据key的hash确定其在数组的位置时，如果n为2的幂次方，可以保证数据的均匀插入，如果n不是2的幂次方，可能数组的一些位置永远不会插入数据，浪费数组的空间，加大hash冲突；一般我们可能会想通过 % 求余来确定位置，只不过性能不如 & 运算。而且当n是2的幂次方时：hash & (length - 1) == hash % length；HashMap 容量为2次幂的原因，就是为了数据的的均匀分布，减少hash冲突，毕竟hash冲突越大，代表数组中一个链的长度
2020-07-11 15:23:15
687
原创 23种设计模式之外观模式
外观模式（Facade）[fəˈsɑːd]核心思想：为子系统中的一组接口提供一个统一的界面，Facade定义它为一个高层接口，目的是更加容易的使用这些子系统。举个生活中的简单例子 你去超市买空调，首先导购带着你进行商品选购，选定之后你带着有销售人员开好的小票去收银台结账，然后去送货处登记住址及联系方式，好让送货人员在合适的时间去上门送货安装，经过调试正常后本次购物完成。简单分析一下这个例子。 首先这个例子是一个顾客，如果是多个顾客的话，每个顾客需要按照自己的需求调用超市的各种系统，就会.
2020-07-11 14:35:58
173
原创 HashMap系列之底层数据结构
HashMap系列之底层数据结构数据结构的概念 数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。HashMap的底层数据存储过程使用代码：public class Demo01 { public static void main(String[] args) { HashMap<String, Inte
2020-07-06 16:35:36
269
原创 HashMap系列之基本概念
理论概念HashMap基于哈希丟的Map接口实现，是以key-value存锗形式存在。它是线程不安全的，key值和value值允许为null。JDK1.8 之前 HashMap 由 数组+链表 组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的，哈希冲突是由于两个对象调用的hashCode方法计算的哈希码值一致导致计算的数组索引值相同引起的，通常采用“拉链法”解决冲突。JDK1.8 以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（或者红黑树的边界值，默认为8）并且.
2020-07-06 15:44:37
150
原创 轻松搞定荷兰国旗问题
问题描述： 给定一个数组arr，和一个数num，请把小于num的数放在数组的左边，等于num的数放在数组的中间，大于num的数放在数组的右边。（要求额外空间复杂度O(1)，时间复杂度O(N)）思路： 准备三个指针l、r、cur，l指向数组的第一个元素之前，代表小于num的区域，r指向数组最后一个元素之后，代表大于num的区域，cur为当前元素所在位置，遍历数组与num比较，小于num放左边，等于num放中间，大于num放右边。具体流程：一开始从数组第一个元素开始遍历，cur指针.
2020-07-01 00:49:47
90
原创 归并排序
归并排序归并的意思就是说将多个有序表（两个或以上）合并成一个新的有序表。并排序的思路归并排序采用分治思想，其解决思路为：将一个长度为n的数组通过二分的方式进行划分，直到划分为长度为1的有序子表；然后两两合并，并对两个子序列进行排序；合并两个已排好序的子序列得到最终排序结果。实现原理如图所示具体代码实现public class MergeSort { public static void MergeSort(int[]arr){ if(arr.
2020-06-30 17:44:17
98
原创 左神算法之获取栈中最小值
设计一个能够获取当前栈最小值的栈问题描述 实现一个特殊的栈，在实现栈的基本功能的基础上，再实现返回栈中最小元素的操作，要求pop、push、getMin 操作的时间复杂度都是 O(1)。解题思路 使用两个栈来实现这一功能，一个普通栈stackData，一个能获取最小值的栈stackMin。具体实现将当前数压入stackData中，设当前要压入值为newNum，直接压入stackData；将当前数压入stackMin中：判断最小栈stackMin是否有数，没有的话直接将
2020-06-30 17:37:36
313
原创 服务治理：Spring Cloud Eureka
Spring Cloud Eureka是Spring Cloud Netflix 微服务套件中的一部分，它基于Netflix Eureka做了二次封装，主要负责完成微服务架构中的服务治理功能。以下是它的核心内容：构建服务注册中心服务注册与发现Eureka 的基础架构Eureka 的服务治理机制Eureka 的配置服务治理 服务治理实现了各个微服务实例的自动化注册与发现。简单理解，比如说你想买衣服，你就得去商场，商场里面有很多的商店可以供你选择，然而这些商店的衣服又不是凭空来的
2020-06-30 17:05:33
133
原创 Spring Cloud简介
在学习Spring Cloud之前先思考下面两个问题？1、Spring Cloud是什么？2、怎么用Spring Cloud？接下来带着这两个问题来学习Spring Cloud。Spring Cloud是什么 Spring Cloud是一款基于Spring Boot实现的微服务架构开发工具，不太了解微服务架构的可以参考这篇文章带你快速了解什么是微服务架构–>什么是微服务架构，它为微服务中涉及的服务治理、负载均衡、配置管理、断路器、智能路由、API网关等操作提供了一种简单的开发方式。
2020-06-30 17:02:14
65
原创 简单了解什么是微服务架构
微服务与微服务架构微服务： 从字面意思理解，它就是一个小的服务，是为了解决某个问题或是完成一个具体功能而落地实现的某个服务应用，可以简单理解为IDEA里面的一个Moudle。微服务架构： 简单来说，它就是一种架构设计风格，本质就是将一个独立的系统拆成多个小型服务，每个小型服务都存在于独立的进程中，它们有各自的数据库、业务逻辑和独立部署机制，服务之间通过HTTP的RESTful API进行通信。由于有了轻量级的通信协作基础，因此这些微服务可以用不同的语言来编写。微服务的优点能够独.
2020-06-30 16:59:24
142
原创 23种设计模式之适配器模式
适配器模式从字面意思来看就是，一种东西去适配另一种东西。通俗地讲，适配器模式就是将两个不兼容的接口放在一起工作，那么什么是不兼容？举个简单栗子，大家用的笔记本都带有适配器，它的作用就是将我们的交流电220V电压转换成电脑的工作电压，使得家用电压能够适配电脑，二者协同工作，这就是生活中的适配器模式。适配器的结构常见的适配器模式有类适配器和对象适配器两种模式，区别：类适配器采用继承的方式使用源信息（可理解为上述例子中的家用电压），对象适配器采用委托的方式使用源信息。废话不多说，直接上代码！创建.
2020-06-30 16:17:22
156
原创 二叉树序列化和反序列化
二叉树序列化和反序列化二叉树的序列化和反序列其实很简单。序列化可以暴力的理解为将一颗形象的树型结构压扁成链型结构，这个链型结构可以想象成一列火车，这列火车可以用队列表示，里面每节车厢存储了二叉树的各个节点值和辅助信息(方便反序列)； 反序列就是将火车车厢里的东西倒出来，根据其进入车厢的顺序，将节点值和辅助信息有序的排列起来，还原成原来的二叉树。eg:该二叉树序列化可表示为：具体代码实现public class Codec { // Encodes a tree to a sin.
2020-06-30 16:10:40
175
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人