1 sky国士无双

尚未进行身份认证

不积跬步,无以至千里。

等级
TA的排名 12w+

回溯算法分析

1.回溯算法介绍解决一个回溯问题,实际上就是一个决策树的遍历过程。你只需要思考 3 个问题:1、路径:也就是已经做出的选择。2、选择列表:也就是你当前可以做的选择。3、结束条件:也就是到达决策树底层,无法再做选择的条件。如果你不理解这三个词语的解释,没关系,我们后面会用「全排列」和「N 皇后问题」这两个经典的回溯算法问题来帮你理解这些词语是什么意思,现在你先留着印象。代码方面,回溯算法...

2020-04-19 15:35:01

kmp算法及manacher算法分析

1.KMP算法kmp算法主要用来解决字符串匹配的问题,即一个字符串是否是另外一个字符串的子串。(1)暴力法首先想到的方法就是暴力匹配法,即两个字符串按位进行匹配,如果遇到不相同的,则从从头开始的下一位开始匹配。package algorithm.manacher.kmp;/** * @author chengzhengda * @version 1.0 * @date 2020-...

2020-04-19 15:29:56

《剑指offer第二版》十一

1. 左旋转字符串(1)题目描述字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如,输入字符串"abcdefg"和数字2,该函数将返回左旋转两位得到的结果"cdefgab"。示例 1:输入: s = “abcdefg”, k = 2输出: “cdefgab”(2)题目分析将字符串的前半段拿出来,拼接到后半段即可。(3)代码...

2020-04-12 22:36:09

《剑指offer第二版》十

1. 数组中数字出现的次数(1)题目描述在一个数组 nums 中除一个数字只出现一次之外,其他数字都出现了三次。请找出那个只出现一次的数字。示例 1:输入:nums = [3,4,3,3]输出:4(2)题目分析本题优先想到的解法是哈希表,通过统计每个数字的次数,然后找到次数为1的那个数即可,但是哈希表需要用到额外的空间。由于除了出现一次的数字外,其他数字都出现了3次,因此这些数字的每...

2020-04-11 12:22:32

《剑指offer第二版》九

1. 序列化二叉树(1)题目描述请实现两个函数,分别用来序列化和反序列化二叉树。示例:你可以将以下二叉树: 1 / \ 2 3 / \ 4 5序列化为 “[1,2,3,null,null,4,5]”(2)题目分析本题分为两部分来处理,首先是序列化,本题使用按层遍历的方式来处理,而二叉树的按层遍历使用队列来实现,在反序列化时同样使用一个队列...

2020-04-10 10:54:59

《剑指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

《剑指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

《剑指offer第二版》六

1. 把数组排成最小的数(1)题目描述输入一个正整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。示例 1:输入: [10,2]输出: “102”(2)题目分析本题首先可以想到将数组排序,然后遍历以字符串的形式相加即可,但是排序规则不是比较大小,而是两个字符串s1+s2<s2+s1,则s1<s2。(3)代码package swordOf...

2020-03-26 22:58:26

《剑指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

《剑指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

《剑指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

《剑指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

《剑指offer第二版》 一

一、数组中的逆序对(1)题目描述在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数。示例 1:输入: [7,5,6,4]输出: 5(2)题目分析首先想的是将数组排序,在排序的过程中,比较前后数字的大小,然后统计逆序的个数。而在排序算法中,归并排序可以很好的解决这个问题。在归并排序的过程中,将两个有序的子数组合并时...

2020-03-21 13:19:22

《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

《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

Spring MVC从请求到返回结果的过程

从离开浏览器开始到获取响应返回,请求会经历好多站点,在每个站点都会留下一些信息同时也会带上其他信息。如下图所示在请求离开浏览器时,会带有用户所请求内容的信息,至少会包含请求的url,还可能带有其他信息,如用户提交的表单信息。请求旅程的第一站是Spring的DisPatcherServlet。DisPatcherServlet的任务就是将请求发送给Spring MVC控制器,一旦选择了合适的...

2020-03-06 16:34:09

《spring实战》三 面向切面的spring

1. 什么是面向切面编程1.1 定义AOP术语描述切面的常用术语有通知,切点和连接点,如下图所示:1.1.1 通知在AOP术语中,切面的工作被称为通知。通知定义了切面是什么以及何时工作。spring切面可以应用5种类型的通知:(1)前置通知在目标方法被调用之前调用通知功能(2)后置通知在目标方法完成之后调用通知(3)返回通知在目标方法成功执行之后调用通知(4)异常通知在...

2020-03-05 13:47:08

《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

《spring实战》一 spring之旅

1. 简化java开发为了降低java开发的复杂性,spring采取了以下四种关键策略:(1)基于POJO的轻量级和最小侵入性编程。(2)通过依赖注入和面向接口实现松耦合。(3)通过切面和惯例进行声明示编程。(4)通过切面和模板减少样板式代码。1.1 激发POJO的潜能spring不会强迫你实现spring规范的接口或者继承spring规范的类,相反,在基于spring构建的应用中,...

2020-03-04 20:37:58

《java并发编程的艺术》二 java并发机制的底层实现原理

一、volatile的应用volatile的定义与实现原理volatile的两条实现原则:(1)Lock前缀指令会引起处理器缓存回写到内存。(2)一个处理器的缓存回写到内存会导致其他处理器的缓存无效。如果通过嗅探一个处理器来检测其他处理器打算写内存地址,而这个地址当前处于共享状态,那么正在嗅探的处理器将使它的缓存行无效,在下次访问相同内存地址时,强制执行缓存行填充。二、synchron...

2020-02-29 15:57:06

查看更多

勋章 我的勋章
  • GitHub
    GitHub
    绑定GitHub第三方账户获取
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv2
    勤写标兵Lv2
    授予每个自然周发布4篇到6篇原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。