- 博客(76)
- 收藏
- 关注
RSS订阅原创 回溯算法分析
1.回溯算法介绍解决一个回溯问题，实际上就是一个决策树的遍历过程。你只需要思考 3 个问题：1、路径：也就是已经做出的选择。2、选择列表：也就是你当前可以做的选择。3、结束条件：也就是到达决策树底层，无法再做选择的条件。如果你不理解这三个词语的解释，没关系，我们后面会用「全排列」和「N 皇后问题」这两个经典的回溯算法问题来帮你理解这些词语是什么意思，现在你先留着印象。代码方面，回溯算法...
2020-04-19 15:35:01
1284
原创 kmp算法及manacher算法分析
1.KMP算法kmp算法主要用来解决字符串匹配的问题，即一个字符串是否是另外一个字符串的子串。（1）暴力法首先想到的方法就是暴力匹配法，即两个字符串按位进行匹配，如果遇到不相同的，则从从头开始的下一位开始匹配。package algorithm.manacher.kmp;/** * @author chengzhengda * @version 1.0 * @date 2020-...
2020-04-19 15:29:56
273
原创 《剑指offer第二版》十一
1. 左旋转字符串（1）题目描述字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串"abcdefg"和数字2，该函数将返回左旋转两位得到的结果"cdefgab"。示例 1：输入: s = “abcdefg”, k = 2输出: “cdefgab”（2）题目分析将字符串的前半段拿出来，拼接到后半段即可。（3）代码...
2020-04-12 22:36:09
164
原创 《剑指offer第二版》十
1. 数组中数字出现的次数（1）题目描述在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。示例 1：输入：nums = [3,4,3,3]输出：4（2）题目分析本题优先想到的解法是哈希表，通过统计每个数字的次数，然后找到次数为1的那个数即可，但是哈希表需要用到额外的空间。由于除了出现一次的数字外，其他数字都出现了3次，因此这些数字的每...
2020-04-11 12:22:32
112
原创 《剑指offer第二版》九
1. 序列化二叉树（1）题目描述请实现两个函数，分别用来序列化和反序列化二叉树。示例:你可以将以下二叉树： 1 / \ 2 3 / \ 4 5序列化为 “[1,2,3,null,null,4,5]”（2）题目分析本题分为两部分来处理，首先是序列化，本题使用按层遍历的方式来处理，而二叉树的按层遍历使用队列来实现，在反序列化时同样使用一个队列...
2020-04-10 10:54:59
126
原创 《剑指offer第二版》 八
1. 从上打下打印二叉树（1）题目描述从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。例如:给定二叉树: [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7返回：[3,9,20,15,7]（2）题目分析本题可以通过队列来求解，通过依次将每个结点的左右子节点入队，然后出队，即可实现从上...
2020-04-08 20:38:25
116
原创 《剑指offer第二版》七
1. 重建二叉树（1）题目描述输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如，给出前序遍历 preorder = [3,9,20,15,7]中序遍历 inorder = [9,3,15,20,7]返回如下的二叉树： 3 / \ 9 20 / \ 15 7（2）题目分析对于二...
2020-04-05 11:50:38
93
原创 《剑指offer第二版》六
1. 把数组排成最小的数（1）题目描述输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。示例 1:输入: [10,2]输出: “102”（2）题目分析本题首先可以想到将数组排序，然后遍历以字符串的形式相加即可，但是排序规则不是比较大小，而是两个字符串s1+s2<s2+s1，则s1<s2。（3）代码package swordOf...
2020-03-26 22:58:26
99
原创 《剑指offer第二版》五
1. 包含min函数的栈（1）题目描述定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。示例：MinStack minStack = new MinStack();minStack.push(-2);minStack.push(0);minStack.push(-3);minStack...
2020-03-25 23:02:30
89
原创 《剑指offer第二版》四
1. 表示数值的字符串（1）题目描述请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串"+100"、“5e2”、"-123"、“3.1416”、“0123"及”-1E-16"都表示数值，但"12e"、“1a3.14”、“1.2.3”、"±5"及"12e+5.4"都不是。（2）题目分析本题的解法比较中规中矩，只需要考虑好可能出现情况即可，通过设置三个标志位，即numSe...
2020-03-24 20:06:53
85
原创 《剑指offer第二版》三
1. 旋转数组的最小数字（1）题目描述把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。示例 1：输入：[3,4,5,1,2]输出：1（2）题目分析遇到排序数组的查找问题，最优解一般都是二分法，这个题要分三种情况考虑...
2020-03-23 19:17:49
79
原创 《剑指offer第二版》二
1. 替换空格（1）题目描述请实现一个函数，把字符串 s 中的每个空格替换成"%20"。示例 1：输入：s = “We are happy.”输出：“We%20are%20happy.”（2）题目分析这个题没有可分析的必要，小学生都会做…（3）代码```javapackage swordOffer;/** * @author chengzhengda * @versi...
2020-03-22 13:25:06
148
原创 《剑指offer第二版》 一
一、数组中的逆序对（1）题目描述在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。示例 1:输入: [7,5,6,4]输出: 5（2）题目分析首先想的是将数组排序，在排序的过程中，比较前后数字的大小，然后统计逆序的个数。而在排序算法中，归并排序可以很好的解决这个问题。在归并排序的过程中，将两个有序的子数组合并时...
2020-03-21 13:19:22
130
原创 《Leetcode 3.10》
1. 合并排序的数组题目描述：给定两个排序后的数组 A 和 B，其中 A 的末端有足够的缓冲空间容纳 B。 编写一个方法，将 B 合并入 A 并排序。初始化 A 和 B 的元素数量分别为 m 和 n。示例:输入:A = [1,2,3,0,0,0], m = 3B = [2,5,6], n = 3输出: [1,2,2,3,5,6]代码：package leetcode...
2020-03-10 22:17:43
156
原创 《leetcode 3.7》
1. 搜索旋转排序数组题目描述：假设按照升序排序的数组在预先未知的某个点上进行了旋转。( 例如，数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2] )。编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 true，否则返回 false。代码：package leetcode.week9;/** * @author chengzhengda *...
2020-03-07 20:52:15
62
原创 Spring MVC从请求到返回结果的过程
从离开浏览器开始到获取响应返回，请求会经历好多站点，在每个站点都会留下一些信息同时也会带上其他信息。如下图所示在请求离开浏览器时，会带有用户所请求内容的信息，至少会包含请求的url，还可能带有其他信息，如用户提交的表单信息。请求旅程的第一站是Spring的DisPatcherServlet。DisPatcherServlet的任务就是将请求发送给Spring MVC控制器，一旦选择了合适的...
2020-03-06 16:34:09
344
原创 《spring实战》三 面向切面的spring
1. 什么是面向切面编程1.1 定义AOP术语描述切面的常用术语有通知，切点和连接点，如下图所示：1.1.1 通知在AOP术语中，切面的工作被称为通知。通知定义了切面是什么以及何时工作。spring切面可以应用5种类型的通知:（1）前置通知在目标方法被调用之前调用通知功能（2）后置通知在目标方法完成之后调用通知（3）返回通知在目标方法成功执行之后调用通知（4）异常通知在...
2020-03-05 13:47:08
90
原创 《spring实战》二 装配bean
1. spring配置的可选方案spring具有非常大的灵活性，它提供了3种主要的装配机制：（1）在xml中进行显示配置（2）在java中进行显示配置（3）隐示的bean发现机制和自动装配2. 自动化装配beanspring从两个角度来实现自动化配置：（1）组件扫描spring会自动发现应用上下文中所创建的bean（2）自动装配spring自动满足bean之间的依赖2.1 创...
2020-03-05 09:37:00
88
原创 《spring实战》一 spring之旅
1. 简化java开发为了降低java开发的复杂性，spring采取了以下四种关键策略：（1）基于POJO的轻量级和最小侵入性编程。（2）通过依赖注入和面向接口实现松耦合。（3）通过切面和惯例进行声明示编程。（4）通过切面和模板减少样板式代码。1.1 激发POJO的潜能spring不会强迫你实现spring规范的接口或者继承spring规范的类，相反，在基于spring构建的应用中，...
2020-03-04 20:37:58
128
原创 《java并发编程的艺术》二 java并发机制的底层实现原理
一、volatile的应用volatile的定义与实现原理volatile的两条实现原则：（1）Lock前缀指令会引起处理器缓存回写到内存。（2）一个处理器的缓存回写到内存会导致其他处理器的缓存无效。如果通过嗅探一个处理器来检测其他处理器打算写内存地址，而这个地址当前处于共享状态，那么正在嗅探的处理器将使它的缓存行无效，在下次访问相同内存地址时，强制执行缓存行填充。二、synchron...
2020-02-29 15:57:06
76
原创 《java并发编程的艺术》一并发编程的挑战
一、上下文切换CPU通过时间片分配算法来循环执行任务，当前任务执行一个时间片后会切换到下一个任务，但是，在切换前会保存上一个任务的状态，以便下次切换回这个任务时，可以再加载这个任务的状态，所以任务从保存到再加载的过程就是一次上下文切换。这样的切换是会影响效率的，同样上下文切换也会影响多线程的执行速度。二、多线程一定快吗当并发执行累加操作不超过百万次时，速度会比串行执行累加操作要慢，那么，为...
2020-02-28 15:55:22
112
原创 《java多线程核心技术》四 Lock的使用
一、使用ReentrantLock类public class MyService { public Lock lock = new ReentrantLock(); public void testMethod() { lock.lock(); for (int i = 0; i < 5; i++) { System...
2020-02-27 21:00:51
90
原创 《2.25 Leetcode》
1. 重复的子字符串题目描述：给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过10000。代码：package leetcode.week8;/** * @author chengzhengda * @version 1.0 * @date 2020-02-25 17:39 * @desc */public cl...
2020-02-25 23:36:41
36
原创 《java多线程核心技术》三线程间通信
一、等待/通知机制1. 不使用等待/通知机制实现线程间通信使用sleep()和while(true)死循环来实现多个线程间通信package multiThread;import java.util.ArrayList;import java.util.List;/** * @author chengzhengda * @version 1.0 * @date 2020-02...
2020-02-25 15:47:54
119
原创 《java多线程核心技术》二 对象及变量的并发访问
一、synchronized同步方法（1）方法内的变量为线程安全非线程安全问题存在于实例变量中，如果是方法内部的私有变量，则不存在非线程安全的问题，所得结论也就是线程安全的了。（2）实例变量非线程安全如果多个线程共同访问一个对象中的实例变量，则有可能出现非线程安全问题。在两个线程访问同一个对象中的同步方法时一定是线程安全的。（3）多个对象多个锁关键字synchronized取得的锁都...
2020-02-23 14:46:09
68
原创 《2.22 Leetcode》
1. 移除链表元素题目描述：删除链表中等于给定值 val 的所有节点。代码：package leetcode.week7;import leetcode.week5.ListNode;/** * @author chengzhengda * @version 1.0 * @date 2020-01-21 10:45 * @desc 移除链表元素 */public cla...
2020-02-22 20:19:24
69
原创 《1.20 Leetcode》
1. 阶乘后的0题目描述：给定一个整数 n，返回 n! 结果尾数中零的数量。示例 1:输入: 3输出: 0解释: 3! = 6, 尾数中没有零。代码：package leetcode.week6;/** * @author chengzhengda * @version 1.0 * @date 2020-01-20 15:24 * @desc 阶乘后的0 */pub...
2020-01-20 23:02:35
54
原创 《1.16-1.19 Leetcode》
1. 最小栈题目描述：设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。push(x) – 将元素 x 推入栈中。pop() – 删除栈顶的元素。top() – 获取栈顶元素。getMin() – 检索栈中的最小元素。代码：package leetcode.week5;import java.util.Stack;/** * @author...
2020-01-19 19:17:21
130
原创 《高性能mysql总结》
一、mysql架构1. mysql逻辑架构mysql服务器逻辑架构图（1）最上层的服务并不是Mysql所独有的，大多数基于网络的客户端/服务器的工具或者服务都有类似的架构。主要负责连接处理，身份验证，安全性等。（2）第二层架构师Mysql的核心部分，大多数mysql的核心服务都在这一层，包括查询解析、分析、优化、缓存以及所有的内置函数，同时，所有跨存储引擎的功能都在这一层实现：存储过程、...
2020-01-16 19:02:40
376
4
原创 《1.9-1.15 Leetcode》
1. 路径总和题目描述：给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。说明: 叶子节点是指没有子节点的节点。代码：package leetcode.week4;/** * @author chengzhengda * @version 1.0 * @date 2020-01-14 17:09 * @desc 路径总和...
2020-01-15 14:42:30
117
1
原创 《深入理解java虚拟机》七-线程安全与锁优化
一、线程安全当多个线程访问一个对象时，如果不用考虑这些线程在运行时环境下的调度和交替执行，也不需要进行额外的同步，或者在调用方进行任何其他的协调操作，调用这个对象的行为都可以获得正确的结果，那这个对象就是线程安全的。1.java语言中线程安全（1）不可变在Java语言中，不可变的对象一定是线程安全的，无论是对象的方法实现还是对象的调用者，都不需要再采取任何的线程安全保障措施。（2）绝对线...
2020-01-12 15:39:26
116
1
原创 《深入理解java虚拟机》六-java内存模型与线程
一、概述衡量一个服务性能的高低好坏，每秒事务处理数(TPS)是最重要的指标之一，它代表着一秒内服务端平均能响应的请求总数，而TPS值与程序的并发能力又有非常密切的关系。二、硬件的效率与一致性基于高速缓存的存储交互很好的解决了处理器与内存的速度矛盾，但是也为计算机系统带来更高的复杂度，因为它引入了一个新的问题：缓存一致性。在多处理器系统中，每个处理器都有自己的高速缓存，而他们又共享同一主内存。...
2020-01-09 23:12:41
95
原创 《1.3-1.8 Leetcode》
1. 对称二叉树题目描述：给定一个二叉树，检查它是否是镜像对称的。例如，二叉树 [1,2,2,3,4,4,3] 是对称的。代码：package leetcode.week3;/** * @author chengzhengda * @version 1.0 * @date 2020-01-08 13:13 * @desc 对称二叉树 */public class t10...
2020-01-08 20:09:06
90
原创 《深入理解java虚拟机》五-虚拟机字节码执行引擎
运行时栈帧结构栈帧是用于支持虚拟机进行方法调用和方法执行的数据结构，它是虚拟机运行时数据区中的虚拟机栈的栈元素。栈帧存储了方法的局部变量表、操作数栈、动态链接和方法返回地址等信息。每一个方法从调用开始至执行完成的过程，都对应着一个栈帧在虚拟机里面从入栈到出栈的过程。在编译代码的时候，栈帧中需要多大的局部变量表，多深的操作数栈都已经完全确定了，并且写入到方法表得Code属性之中。因此一个栈帧需要...
2020-01-07 20:53:56
92
2
原创 《深入理解java虚拟机》四-虚拟机类加载机制
一、概述虚拟机把描述类的数据从Class文件加载到内存，并对数据进行校验、转换解析和初始化，最终形成可以被虚拟机直接使用的Java类型，这就是虚拟机的类加载机制。二、类加载的时机类从加载到虚拟机内存中开始，到卸载出内存为止，它的整个生命周期包括：加载、验证、准备、解析、初始化、使用和卸载7个阶段。其中验证、准备、解析这3个部分统称为连接，这7个阶段的发生顺序如下图所示其中，加载、验证、...
2020-01-07 19:19:01
91
原创 《12.23-1.2 Leetcode》
1. 最后一个单词的长度题目描述：给定一个仅包含大小写字母和空格 ’ ’ 的字符串，返回其最后一个单词的长度。如果不存在最后一个单词，请返回 0 。说明：一个单词是指由字母组成，但不包含任何空格的字符串。代码：package leetcode.week2;/** * @author chengzhengda * @version 1.0 * @date 2019-12-23 ...
2020-01-02 23:51:35
78
原创 《深入理解java虚拟机》三 类文件结构
一、无关性的基石实现语言无关性的基础仍然是虚拟机和字节码储存格式。java虚拟机不和包括java在内的任何语言绑定，它只与"Class文件"这种特定的二进制文件格式所关联，Class文件中包含了java虚拟机指令集和符号表以及若干其他辅助信息。二、class类文件的结构Class文件是一组以8位字节为基础单位的二进制流，各个数据项目严格按照顺序紧凑地排列在Class文件之中，中间没有添加任...
2020-01-02 22:52:25
133
原创 《深入理解java虚拟机》二 垃圾收集器与内存分配策略
一、概述java内存中运行时区域的各个部分，其中程序计数器、虚拟机栈、本地方法栈3个区域随线程而生，随线程而灭。栈中的栈帧随着方法的进入和退出而有条不紊地执行着出栈和入栈的操作。每一个栈帧中分配多少内存基本上是在类结构确定下来时就已知的，因此这几个区域的内存分配和回收都具有确定性，在这几个区域内就不需要过多考虑回收的问题，因为方法结束或者线程结束时，内存自然就跟随回收了。而java堆和方法区则...
2019-12-31 14:00:35
81
原创 《深入理解java虚拟机》一 java内存区域与内存溢出异常
一、概述对于java程序员来说，在虚拟机自动内存管理机制的帮助下，不再需要为每一个new操作去写配对的delete/free代码，不容易出现内存泄露和内存溢出问题，由虚拟机管理内存这一切看起来都很美好，不过，也正是因为java程序员把内存控制的权利交给了java虚拟机，一旦出现内存泄露和溢出方面的问题，如果不了解虚拟机是怎么使用内存的，那么排查错误将会成为一项异常艰难的工作。二、运行时数据区域...
2019-12-26 13:22:45
118
原创 《高性能Mysql》四-查询性能优化
一、为什么查询速度会慢如果把查询看作是一个任务，那么它由一系列子任务组成，每个子任务都会消耗一定的时间。如果要优化查询，实际上要优化其子任务，要么消除其中一些子任务，要么减少子任务的执行次数，要么让子任务运行得更快。二、优化数据访问对于低效的查询，我们发现通过下面两个步骤来分析总是很有效:确认应用程序是否在检索大量超过需要的数据。这通常意味着访问了太多的行，但有时候也可能是访问了太多的列。...
2019-12-24 20:24:26
254
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人