题目描述统计一个数字在排序数组中出现的次数。比如给定{1,2,3,4,4,4,4,5,6} 和4，能知道4出现了4次。  常规解法，遍历一次，，找到元素，然后统计次数，时间复杂度O(n)，但是又想到排序，就可以使用二分，显然时间复杂度只有O(logn)。 解法1： 首先遍历，找元素，找到后，每碰到一个相同的元素，count++。 public class Solution { public int GetNumberOfK(int [] array , int k) { int count=0; for(int i=0;i<array.length;i++){ if(array[i]==...

题目描述输入两个链表，找出它们的第一个公共结点。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）  本题最容易想到的肯定是最暴力的方法：拿某一个链表的元素，去和另一个链表的所有节点匹配，然后再换一个，再拿去全部匹配一次。这样的时间复杂度肯定不会让你拿到offer。所以要优化啊。  如果经常用Java刷题的话，本题肯定也会想到使用Hash表来判断是否重复。虽然是个方法，但总使用工具类解决，在面试中不占便宜。  本题要深入本质才行，一旦两个链表有公共结点，就意味着两个链表可能不止有一个公共节点。两个链表在6处开始公共，则意味着6后面的所有节点都是公共的了。...

题目描述在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007    首先知道什么是逆序对，{3,1,2}的逆序对就是{3,1}和{3,2}。然后，取模的牛客上新加的条件，解题的重点在于如何求总数P。  在第一时间，肯定想到的是类似冒泡排序的做法，也就是取一个数，比一轮，再取一个数，再比一轮，这样的时间复杂度是O(n^2)。所以要想怎么优化。本题是利用归并排序进行优化的（主流解法），改进后时间复杂度O(nlogn)。因此解本题之前，需要理解归并排序...

7.4 类加载器 1 类与类加载器  每个都有个自己专门的类加载器。只要加载某两个类的类加载器不同，那这两个类就必定不相等。这里所指的“相等”，包括代表类的Class对象的equals()方法、isAssignableFrom()方法、isInstance()方法的返回结果，也包括了使用instanceof关键字做对象所属关系判定等各种情况。2 双亲委派模型  图7-2中展示的各种类加载器之间的层次关系被称为类加载器的“双亲委派模型（Parents Delegation Model）”。双亲委派模型要求除了顶层的启动类加载器外，其余的类加载器都应有自己的父类加载器。不过这里类加载器之间的父子关...

第6章 类文件结构 6.1 概述 6.2 无关性的基石   我的理解是，不管什么语言，只要能翻译成.class文件（字节码文件），就可以在虚拟机中运行。 6.3 Class类文件的结构   Class文件是一组以8个字节为基础单位的二进制流，各个数据项目严格按照顺序紧凑地排列在文件之中，中间没有添加任何分隔符，这使得整个Class文件中存储的内容几乎全部是程序运行的必要数据，没有空隙存在。当遇到需要占用8个字节以上空间的数据项时，则会按照高位在前的方式分割成若干个8个字节进行存储。1.魔数与Class文件的版本  每个Class文件的头4个字节被称为魔数（Magic Number），它的唯一作...

题目描述在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）.  这个题目既然是找是否出现，并且由于每个字符需要返回第一次出现，因此需要记录次数，可以使用数组来完成出现次数的统计，而数组可以改进成TreeSet，因为实现了排序，或者是使用Map集合来统计次数。 写法1： 利用数组统计次数，这里可以建一个二维数组，但是，考虑到ASCII码中，字符对应某个数字，所以可以将字符对应的数字当做数组的角标，因此，可以只用一个一维数组即可。（也就是说，当你写一个arr[a]，是会被认成arr[97]...

题目描述把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。  我开始想的是想的是通过除法，然后逐个判断方式。比如判断一个丑数，由题意知，只包含2、3、5。对于14的判断规则就是先拿掉所有的2的因子，再拿掉所有3的因子，最后拿到5的因子，最后为1，则说明是丑数。 思路1： 哈哈，一个时间复杂度比较高的算法，在牛客上没跑成功。我自己验证的时候感觉没问题 public class ac { public static void main(String[] args) {...

题目描述输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。  最容易想到的就是全排序后进行比较，然而肯定是要进行优化的，优化方式如下：对于数字m和n，可以拼接成mn和nm，如果mn<nm，则说明m应当放在n前面，哪怕还有其他的数也来拼接，都需要保证，所有的拼接方式中，m都在n的前面。  以题目的条件为例，3和321拼接成3321和3213，说明了321一定在3之前，哪怕32最后插在了中间，也要保证这个规则，因此需要重新定义这个规则。而定义完这个规则后就应当进行排序...

3.3 垃圾收集算法 分代收集理论(第三版多出的内容)  当前商业虚拟机的垃圾收集器，大多数都遵循了“分代收集”（Generational Collection）的理论进行设计。它建立在两个分代假说之上：1）弱分代假说（Weak Generational Hypothesis）：绝大多数对象都是朝生夕灭的。2）强分代假说（Strong Generational Hypothesis）：熬过越多次垃圾收集过程的对象就越难以消亡。  这两个分代假说共同奠定了多款常用的垃圾收集器的一致的设计原则：收集器应该将Java堆划分出不同的区域，然后将回收对象依据其年龄（年龄即对象熬过垃圾收集过程的次数）分配...

题目描述输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4。  最容易想到的肯定是用一个容量为4的集合记录当前的最小4个数字，并且不断的维护。这个维护过程就是一个排序过程，因此本题可以复习一些排序方式。  这个集合可以用数组，堆以及其他数据结构。因为每次加入最小值时，都会替换出集合中的最大，所以用一个大根堆来维护，比较合适。当然也可以用一些其他的排序算法。所以第1个思路就是多种排序算法中任选一个，这里选择的堆排序。  第2个思路就是，借鉴快排partition()方法，将整个数组分成两部分，左边是最小的4个，右边是比较大的。时...

题目描述输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。  本题的常规解法还是以递归解法为主，学有余力的可以用巧劲解题。可以参考题解的讨论中，五头镜子这位大佬的总结。递归思路：求整个字符串的排序，将递归设计成两步，步骤如下，第一步求所有出现在第一个位置的字符，也就是将第一个字符和后面所有字符交换，第二步固定第一个字符，求后面所有字符的排序。进入下一次递归调用时，则是将所有的字符和第二个字符交换，然后固定之后，求后面所有字符的排序。  以abc为例，首先是abc,bac,...

第2章 Java内存区域与内存溢出异常 2.1概述 2.2 运行时数据区域 程序计数器虚拟机栈：虚拟机栈描述的是Java方法执行的线程内存模型：每个方法被执行的时候，Java虚拟机都会同步创建一个栈帧（Stack Frame）用于存储局部变量表、操作数栈、动态连接、方法出口等信息。每一个方法被调用直至执行完毕的过程，就对应着一个栈帧在虚拟机栈中从入栈到出栈的过程。 特别指出：HotSpot虚拟机的栈容量是不可以动态扩展的，以前的Classic虚拟机倒是可以。所以在HotSpot虚拟机上是不会由于虚拟机栈无法扩展而导致OutOfMemoryError异常——只要线程申请栈空间成功了就不会有OOM...

题目描述请实现两个函数，分别用来序列化和反序列化二叉树    二叉树的序列化是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树遍历方式来进行修改，序列化的结果是一个字符串，序列化时通过某种符号表示空节点（#），以 ！表示一个结点值的结束（value!）。  二叉树的反序列化是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。  小白看这两段解释肯定看不明白，别问我怎么知道的。看图，下图是一个前序遍历的序列化示例。来自于剑指offer书上。只不过#换成了$。通过序列化的这个串，很容易...

题目描述输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。  思路1： 中序遍历的结果就是有序的，因此第1个方法就是考虑将中序遍历的结果记录，然后使之成为双向链表。这里的数据结构可以选择数组或者链表。以数组为例，将中序每遍历一个节点时，就添加到数组中，遍历完后数组就是有序的，然后再遍历一次数组，每遍历数组中的一个元素，就用把这个元素和下一个元素连起来。 写法1：使用数组的递归写法 import java.util.ArrayList; public class Solution { public TreeNode Convert(...