为做字符串的题做准备，复习一下自动拆箱装箱以及相互转换。   String类，基本数据类型，包装类。共同形成三组关系，如果用箭头就是6对关系，互相指向。  1.基本数据类型与成包装类（装箱拆箱） 之间的互相转换 jdk 1.5之后实现了自动装箱拆箱。 //装箱的3种示例（2种手动1中自动） int number = 1; Integer num1 = new Integer(number);//手动装箱 Integer num = new Integer(1);//手动装箱。这两个都是构造器方法 Integer num2 = number;//自动装箱 也就是Integer num2 = 1...

题目描述输入一颗二叉树的根节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前)  由于是从根节点开始，并且是找路径，所以是和前序遍历有关。仅仅分析到这里。又是看别人答案的一题... 首先，选择一种思想，要么是加入一个节点求和，最后判断和是否为target，另一种思想就是加入一个节点就做减法，直到最后减为0。 以减法为例，当检查一棵树从根到叶子节点形成的路径的和是否为target时，先将当前根节点的值 root.val 加入path, 然后检查它的左子树（若非空），...

题目描述输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。  首先要知道后续遍历的特点。一个序列可以分为三个部分[a][b][c]，其中c是根节点，a整个序列是c的左子树，都比c小，b整个序列是c的右子树，都比c大。然后[a]序列又可以分成3个部分，其分法与刚开始相同。而左子树a和右子树b的分界线在于，遍历，直到找到一个数比根节点C大时，就找到了边界。递归 public class Solution { public boolean VerifySquenceOfBST(int [] sequence) {...

最近刷了一些算法题，发现有些题目出现了这样的代码 Queue<Integer> queue = new LinkedList<>(); //为什么不是如下的代码 Queue<Integer> queue = new Queue<>(); LinkedList<Integer> queue = new LinkedList<>();由于底子不好，当时很好奇为什么左边队列，右边链表，后来复习java基础时，看到了这是一个多态的简单示例。因此重新去学习了一下多态。首先new出来的是一个链表，链表本身是实现了队列，注意Queue是...

题目描述请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。  本题是换行打印的升级版（在换行打印版本上进行更改），在换行打印时，将偶数列的添加顺序时进行翻转。如果牺牲一点效率，在翻转时采用头插法即可。设置一个变量，区别奇数层和偶数层，然后进行不同的处理，在每一层的节点循环后，变量++，因此这个变量可以理解成树的深度。这道题和二叉树求深度紧密联系。 import java.util.Queue; import java.util.LinkedList; public class Solution { p...

题目描述从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。  刚开始想法是用的print，然后看到题目给的是ArrayList<ArrayList<Integer> >还有点小懵逼。其实是让你返回一个ArrayList，其中每个元素都是一个装了整型数据的ArrayList。比如{[8],[9,10],[11,12,13]}这样的返回方式。比如树有3层，大括号表示的ArrayList就应该装了3个元素。中括号的ArrayList就表示这颗树某一层的所有节点。用这样的方式来区别换行。另外做本题之前。最好先知道普通版怎么写（不换行打印）。然后在之前的版本上迭代就...

题目描述从上往下打印出二叉树的每个节点，同层节点从左至右打印。  根据offer书上，这个题有几个变形，首先是普通版，其次是换行打印，最后是之字型打印其他两题牛客都有，所以只记录普通版首先是节点入队列，队列为空说明遍历结束，队列不为空时，队首节点出队，并进行相关操作，再将该节点的两个子节点入队即可。层次遍历使用队列，深度遍历使用栈。 import java.util.Queue; import java.util.ArrayList; import java.util.LinkedList; public class Solution { public ArrayList<Integer...

题目描述输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）  刚开始没弄清题意，简单来说，将某个序列压入栈，但是中间允许弹出。比如压入1234后，弹出4，再压入5.此时栈内是1235，则弹出序列为5321，而4之前弹出了，所以本次的弹出序列是45321。其次，条件是给了两个序列，第二个序列是用来判断的，而不是让你求出所有的可能性。弄清题意后，就可...

题目描述定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。注意：保证测试中不会当栈为空的时候，对栈调用pop()或者min()或者top()方法。    首先读懂题目，需要保留所有栈的特性（先进后出），并且该栈中有能够提供找到最小元素的min函数。普通的栈是无法实现的。说白了就是让你设计一个栈，其中有一个函数时可以返回最小值的。显然这个栈不是让你写从零写起，你可以依托于包中的栈的普通方法，而把焦点在如何实现min函数  不能用一个变量记录最小值，因为当最小值弹栈后，该变量就得变成新的最小值，这个不容易实现。所以需要定义一个辅助的数据结构，可以...

题目描述输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下4 X 4矩阵： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.  思路：显然是脑子里想的很简单，但是实际代码中的边界条件不太容易找准。因此主要分析边界。如果是4×4的矩阵，顺时针打印第一行时什么时候作为结束的判断标志，顺时针从列开始时，什么时候开始，什么时候结束，都需要考虑清楚。显然本份代码使用的边界是这样的，一共分为4轮完成一圈的遍历，1   2   3    45   6   ...

第五章 创建高性能索引 索引也叫key。是存储引擎用于快速找到记录的一种数据结构 5.1 索引基础 5.1.1 索引的类型 B+树（InnoDB引擎） B 树是为了磁盘或其它存储设备而设计的一种多叉（相对于二叉，B树每个内结点有多个分支，即多叉）平衡查找树。 在B+Tree中，所有数据记录节点都是按照键值大小顺序存放在同一层的叶子节点上，而非叶子节点上只存储key值信息，这样可以大大加大每个节点存储的key值数量，降低B+Tree的高度。 一般在数据库系统或文件系统中使用的 B+Tree 结构都在经典 B+Tree 基础上进行了优化，在叶子节点增加了顺序访问指针，做这个优化的目的是为了提高区间...

题目描述请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。  思路：当根为空，是对称的，不为空就开始比较。比较左子树A和右子树B。然后比较的是左子树的左节点和右子树的右节点。左子树的右节点和左子树的左节点。虽然都是比较两颗树，但本题与26题比较树的子结构有些区别。 public class Solution { boolean isSymmetrical(TreeNode pRoot) { if (pRoot == null) return true; return Symmetrical(pRoot.left, pRoot.righ...

题目描述输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）  首先要正确理解子结构。子树是所有节点都相同，而子结构仅要求部分相同。这里的892组成的树是左边树的子结构，但不是子树这里有三种情况，两树完全相同，B在A的左子树上，B在A的右子树上。因此需要比较B的根节点和A的根节点，左右子节点相比，这3类情况。 public class Solution { public boolean HasSubtree(TreeNode root1,TreeNode root2) { boolean result = false; //先判断根不为空，否则直接返回默认...

题目描述输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。  思路1：用新链表 public class Solution { public ListNode Merge(ListNode list1,ListNode list2) { if (list1 == null) { return list2; } if (list2 == null) { return list1; } ListNode newList = new ListNode(-1); ListNode p3 = newList; while (list1 != null &...