● 如何打印二叉树每层的节点？
考察点：二叉树
参考回答：
实现代码：
import
java.util.ArrayList;
import
java.util.Scanner;
public class Main
{
// 定义节点
class Node{
int
val;
Node
left;
Node
right;
public
Node(``int val) {
this``.val = val;
}
}
public
ArrayList<Integer> gzy; // 保存根左右的序列
public
ArrayList<Integer> zgy; // 保存左跟右的序列
public
ArrayList<Node> pack; // 保存已经排好的节点
public static void main(String[] args) {
Main
main = new Main();
main.getResult();
}
public void getResult() {
//
init
Scanner
scanner = new Scanner(System.in);
int
count = scanner.nextInt();
gzy
= new ArrayList<>();
zgy
= new ArrayList<>();
for``(``int
i = 0``; i < count; i++) {
gzy.add(scanner.nextInt());
}
for``(``int
j = 0``; j < count; j++) {
zgy.add(scanner.nextInt());
}
pack
= new ArrayList<>(); // 已经还原的节点
//
exception
if``(count
== 1``) {
System.out.println(gzy.get(``0``));
return``;
}
// 构造最左侧节点的二叉树
Node
node = new Node(gzy.get(``0``));
pack.add(node);
int
index1 = 1``; // 根左右的下标
Node
tmp = node;
while``(gzy.get(index1)
!= zgy.get(``0``)) { // 如果没访问到最左边的叶子节点,继续还原最左侧二叉树
tmp.left = new Node(gzy.get(index1++));
tmp = tmp.left;
pack.add(tmp);
}
tmp.left
= new Node(gzy.get(index1++));
pack.add(tmp.left);
// 加入剩余的节点完善二叉树
for``(``int
k = index1; k < gzy.size(); k++) {
fillErCS(gzy.get(k));
}
// 层次遍历
ArrayList<Node>
res = new ArrayList<>();
res.add(node);
int
num = 0``;
while``(res.size()
!= num) {
System.out.print(res.get(num).val + "
");
if``(res.get(num).left != null``) {
res.add(res.get(num).left);
}
if``(res.get(num).right != null``) {
res.add(res.get(num).right);
}
num++;
}
}
// 将值为val的节点加入二叉树
private void fillErCS(``int val) {
int
index = zgy.indexOf(val);
// 每一个遍历的节点都是val节点的根或者在其左边
for``(``int
i = index-``1``; i >= 0``; i--) {
if``(findNode(zgy.get(i)) != null``) { // 找到待插入节点的根节点或者其左边的节点
Node
node = findNode(zgy.get(i));
insert(node,
val);
break``;
}
}
}
// 将节点val插入二叉树
private void insert(Node node, int val) {
if``(zgy.indexOf(node.val)
> zgy.indexOf(val)) { // node在待插入节点的右边
if``(node.left == null``) {
node.left
= new Node(val);
pack.add(node.left);
return``;
}
insert(node.left, val);
}``else
{ //
node在待插入节点的左边或是其根
if``(node.right == null``) {
node.right
= new Node(val);
pack.add(node.right);
return``;
}
insert(node.right, val);
}
}
// 根据val找到pack里的节点
private Node findNode(``int val) {
for``(Node
node : pack) {
if``(node.val == val) {
return
node;
}
}
return
null``;
}
}
|
● 如何知道二叉树的深度？
考察点：二叉树
参考回答：
实现二叉树的深度方式有两种，递归以及非递归。
①递归实现：
为了求树的深度，可以先求其左子树的深度和右子树的深度，可以用递归实现，递归的出口就是节点为空。返回值为0；
②非递归实现：
利用层次遍历的算法，设置变量level记录当前节点所在的层数，设置变量last指向当前层的最后一个节点，当处理完当前层的最后一个节点，让level指向+1操作。设置变量cur记录当前层已经访问的节点的个数，当cur等于last时，表示该层访问结束。
层次遍历在求树的宽度、输出某一层节点，某一层节点个数，每一层节点个数都可以采取类似的算法。
树的宽度：在树的深度算法基础上，加一个记录访问过的层节点个数最多的变量max,在访问每层前max与last比较，如果max比较大，max不变，如果max小于last，把last赋值给max;
代码解释：
import
java.util.LinkedList;
public class Deep
{
//递归实现1
public int findDeep(BiTree root)
{
int
deep = 0``;
if``(root != null``)
{
int lchilddeep = findDeep(root.left);
int rchilddeep = findDeep(root.right);
deep = lchilddeep > rchilddeep ?
lchilddeep + 1 : rchilddeep + 1``;
}
return deep;
}
//递归实现2
public int findDeep1(BiTree root)
{
if``(root == null``)
{
return 0``;
}
else
{
int
lchilddeep = findDeep1(root.left);``//求左子树的深度
int
rchilddeep = findDeep1(root.left);``//求右子树的深度
return lchilddeep > rchilddeep ? lchilddeep + 1 : rchilddeep + 1``;``//左子树和右子树深度较大的那个加一等于整个树的深度
}
}
//非递归实现
public int findDeep2(BiTree root)
{
if``(root == null``)
return 0``;
BiTree current = null``;
LinkedList<BiTree> queue = new
LinkedList<BiTree>();
queue.offer(root);
int
cur,last;
int
level = 0``;
while``(!queue.isEmpty())
{
cur = 0``;``//记录本层已经遍历的节点个数
last = queue.size();``//当遍历完当前层以后，队列里元素全是下一层的元素，队列的长度是这一层的节点的个数
while``(cur < last)``//当还没有遍历到本层最后一个节点时循环
{
current = queue.poll();``//出队一个元素
cur++;
//把当前节点的左右节点入队（如果存在的话）
if``(current.left != null``)
{
queue.offer(current.left);
}
if``(current.right != null``)
{
queue.offer(current.right);
}
}
level++;``//每遍历完一层level+1
}
return level;
}
public static void main(String[] args)
{
BiTree root = BiTree.buildTree();
Deep deep = new Deep();
System.out.println(deep.findDeep(root));
System.out.println(deep.findDeep1(root));
System.out.println(deep.findDeep2(root));
}
}
|
● 二叉树任意两个节点之间路径的最大长度
考察点：树
参考回答：
int maxDist(Tree
root) {
//如果树是空的，则返回0
if``(root == NULL)
return 0``;
if``(root->left != NULL) {
root->lm = maxDist(root->left) +``1``;
}
if``(root->right != NULL)
root->rm = maxDist(root->right) +``1``;
//如果以该节点为根的子树中有最大的距离，那就更新最大距离
int sum = root->rm + root->lm;
if``(sum > max) {
max = sum;
}
return root->rm > root->lm ?
root->rm : root->lm;
}
|
● 算法题：二叉树层序遍历，进一步提问：要求每层打印出一个换行符
考察点：二叉树
参考回答：
public
List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res =
new ArrayList<List<Integer>>();
LinkedList<TreeNode> queue = new
LinkedList<TreeNode>();
if (root == null``) {
return res;
}
queue.offer(root);
while (queue.size() != 0``) {
List<Integer> l = new
ArrayList<Integer>();
int size = queue.size();
for (``int i = 0``; i < size; i++) {
TreeNode temp = queue.poll();
l.add(temp.val);
if (temp.left != null``) {
queue.offer(temp.left);
}
if (temp.right != null``) {
queue.offer(temp.right);
}
}
res.add(l);
}
return res;
}
|
● 怎么求一个二叉树的深度?手撕代码?
考察点：二叉树
参考回答：
public int
maxDepth(TreeNode root) {
if (root == null``) {
return 0``;
}
int left = maxDepth(root.left);
int right = maxDepth(root.right);
int bigger = Math.max(left, right);
return bigger + 1``;
}
|
● 请你说一下，B+树和B-树？
考察点：树
参考回答：
b+树的中间节点不保存数据，所以磁盘页能容纳更多节点元素，更“矮胖”；
b+树查询必须查找到叶子节点，b树只要匹配到即可不用管元素位置，因此b+树查找更稳定（并不慢）；
对于范围查找来说，b+树只需遍历叶子节点链表即可，b树却需要重复地中序遍历。
</article>
● 二叉树 Z 字型遍历
考察点：遍历
参考回答：
public
List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> res =
new ArrayList<List<Integer>>();
LinkedList<TreeNode> l = new
LinkedList<TreeNode>();
boolean flag = true``;
if (root == null``) {
return res;
}
l.add(root);
while (l.size() != 0``) {
flag = !flag;
int size = l.size();
List<Integer> list = new
ArrayList<Integer>();
for (``int i = 0``; i < size; i++) {
TreeNode temp = l.remove();
list.add(temp.val);
if (temp.left != null``)
l.add(temp.left);
if (temp.right != null``)
l.add(temp.right);
}
if (flag) {
Collections.reverse(list);
}
res.add(list);
}
return res;
}
|
● 编程题：写一个函数，找到一个文件夹下所有文件，包括子文件夹
考察点：遍历
参考回答：
import
java.io.File;
public class
Counter2 {
public static void main(String[] args) {
//取得目标目录
File
file = new File(``"D:"``);
//获取目录下子文件及子文件夹
File[]
files = file.listFiles();
readfile(files);
}
public static void readfile(File[] files) {
if
(files == null``) {``// 如果目录为空，直接退出
return``;
}
for``(File
f:files) {
//如果是文件，直接输出名字
if``(f.isFile()) {
System.out.println(f.getName());
}
//如果是文件夹，递归调用
else if``(f.isDirectory()) {
readfile(f.listFiles());
}
}
}
}
|
● 现在有一个单向链表，谈一谈，如何判断链表中是否出现了环
考察点：链表
参考回答：
单链表有环，是指单链表中某个节点的next指针域指向的是链表中在它之前的某一个节点，这样在链表的尾部形成一个环形结构。
// 链表的节点结构如下 typedef struct node { int data; struct node *next; } NODE;
最常用方法：定义两个指针，同时从链表的头节点出发，一个指针一次走一步，另一个指针一次走两步。如果走得快的指针追上了走得慢的指针，那么链表就是环形链表；如果走得快的指针走到了链表的末尾（next指向 NULL）都没有追上第一个指针，那么链表就不是环形链表。
通过使用STL库中的map表进行映射。首先定义 map<NODE *, int> m; 将一个 NODE * 指针映射成数组的下标，并赋值为一个 int 类型的数值。然后从链表的头指针开始往后遍历，每次遇到一个指针p，就判断 m[p] 是否为0。如果为0，则将m[p]赋值为1，表示该节点第一次访问；而如果m[p]的值为1，则说明这个节点已经被访问过一次了，于是就形成了环。
● 谈一谈，bucket如果用链表存储，它的缺点是什么？
考察点：链表
参考回答：
①查找速度慢，因为查找时，需要循环链表访问
②如果进行频繁插入和删除操作，会导致速度很慢。
● 有一个链表，奇数位升序偶数位降序，如何将链表变成升序
考察点：链表
参考回答：
● 写一个算法，可以将一个二维数组顺时针旋转90度，说一下思路。
考察点：数组
参考回答：
public void
rotate(``int``[][] matrix) {
int n = matrix.length;
for (``int i = 0``; i < n/``2``; i++) {
for (``int j = i; j < n-``1``-i; j++)
{
int temp = matrix[i][j];
matrix[i][j] =
matrix[n-``1``-j][i];
matrix[n-``1``-j][i] =
matrix[n-``1``-i][n-``1``-j];
matrix[n-``1``-i][n-``1``-j] =
matrix[j][n-``1``-i];
matrix[j][n-``1``-i] = temp;
}
}
}
|
● 一个数组，除一个元素外其它都是两两相等，求那个元素?
考察点：数组
public static int find1From2(``int``[] a){
int len = a.length, res = 0``;
for``(``int i = 0``; i < len; i++){
res= res ^ a[i];
}
return res;
}
|
● 找出数组中和为S的一对组合，找出一组就行
考察点：数组
参考回答：
public int``[]
twoSum(``int``[] nums, int target) {
HashMap<Integer, Integer> map =
new HashMap<Integer, Integer>();
int``[] a = new int``[``2``];
map.put(nums[``0``], 0``);
for (``int i = 1``; i < nums.length;
i++) {
if (map.containsKey(target - nums[i])) {
a[``0``] = map.get(target -
nums[i]);
a[``1``] = i;
return a;
} else {
map.put(nums[i], i);
}
}
return a;
}
|
● 求一个数组中连续子向量的最大和
考察点：数组
参考回答：
public int
maxSubArray(``int``[] nums) {
int sum = 0``;
int maxSum = Integer.MIN_VALUE;
if (nums == null || nums.length == 0``) {
return sum;
}
for (``int i = 0``; i < nums.length;
i++) {
sum += nums[i];
maxSum = Math.max(maxSum, sum);
if (sum < 0``) {
sum = 0``;
}
}
return maxSum;
}
|
● 寻找一数组中前K个最大的数
考察点：数组
参考回答：
|
public int
findKthLargest(``int``[] nums, int k) {
if (k < 1 || nums == null``) {
return
0``;
}
return getKth(nums.length - k +``1``, nums, 0``,
nums.length - 1``);
}
public int
getKth(``int k, int``[] nums, int start, int end) {
int pivot = nums[end];
int left = start;
int right = end;
while (``true``) {
while
(nums[left] < pivot && left < right) {
left++;
}
while
(nums[right] >= pivot && right > left) {
right--;
}
if
(left == right) {
break``;
}
swap(nums,
left, right);
}
swap(nums, left, end);
if (k == left + 1``) {
return
pivot;
} else if (k < left + 1``) {
return
getKth(k, nums, start, left - 1``);
} else {
return
getKth(k, nums, left + 1``, end);
}
}
public void
swap(``int``[] nums, int n1, int n2) {
int tmp = nums[n1];
nums[n1] = nums[n2];
nums[n2] = tmp;
}
|
<article class="post-topic-des entry-content nc-post-content js-nc-pop-image" itemprop="text">
● 用java写一个冒泡排序？
考察点：冒泡排序
参考回答：
|
import
java.util.Comparator;
/**
* 排序器接口(策略模式: 将算法封装到具有共同接口的独立的类中使得它们可以相互替换)
*/
public interface Sorter {
/**
*
*/
public interface Sorter {
/**
* 排序
* @param list 待排序的数组
*/
public <T extends Comparable<T>> void sort(T[] list);
/**
* 排序
* @param list 待排序的数组
* @param comp 比较两个对象的比较器
*/
public <T> void sort(T[] list, Comparator<T> comp);
}
import java.util.Comparator;
/**
* 冒泡排序
*
*/
public class BubbleSorter implements Sorter {
@Override
public <T extends Comparable<T>> void sort(T[]
list) {
boolean swapped = true``;
for (``int i = 1``, len = list.length; i
< len && swapped; ++i) {
swapped =
false``;
for (``int j =
0``; j < len - i; ++j) {
if (list[j].compareTo(list[j + 1``]) > 0``) {
T temp = list[j];
list[j] = list[j + 1``];
list[j + 1``] = temp;
swapped = true``;
}
}
}
}
@Override
public <T> void sort(T[] list, Comparator<T>
comp) {
boolean swapped = true``;
for (``int i = 1``, len = list.length; i
< len && swapped; ++i) {
swapped =
false``;
for (``int j =
0``; j < len - i; ++j) {
if (comp.compare(list[j], list[j + 1``]) > 0``) {
T temp = list[j];
list[j] = list[j + 1``];
list[j + 1``] = temp;
swapped = true``;
}
}
}
|
● 介绍一下，排序都有哪几种方法？请列举出来。
考察点：排序
参考回答：
排序的方法有：插入排序（直接插入排序、希尔排序），交换排序（冒泡排序、快速排序），选择排序（直接选择排序、堆排序）， 归并排序，分配排序（箱排序、基数排序） 快速排序的伪代码。 / /使用快速排序方法对a[ 0 :n- 1 ]排序 从a[ 0 :n- 1 ]中选择一个元素作为m i d d l e，该元素为支点 把余下的元素分割为两段left 和r i g h t，使得l e f t中的元素都小于等于支点，而right 中的元素都大于等于支点 递归地使用快速排序方法对left 进行排序 递归地使用快速排序方法对right 进行排序 所得结果为l e f t + m i d d l e + r i g h t
● 介绍一下，归并排序的原理是什么？
考察点：归并排序
参考回答：
（1）归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
（2）首先考虑下如何将将二个有序数列合并。这个非常简单，只要从比较二个数列的第一个数，谁小就先取谁，取了后就在对应数列中删除这个数。然后再进行比较，如果有数列为空，那直接将另一个数列的数据依次取出即可。
（3）解决了上面的合并有序数列问题，再来看归并排序，其的基本思路就是将数组分成二组A，B，如果这二组组内的数据都是有序的，那么就可以很方便的将这二组数据进行排序。如何让这二组组内数据有序了？
可以将A，B组各自再分成二组。依次类推，当分出来的小组只有一个数据时，可以认为这个小组组内已经达到了有序，然后再合并相邻的二个小组就可以了。这样通过先递归的分解数列，再合并数列就完成了归并排序。
● 介绍一下，堆排序的原理是什么？
考察点：堆排序
参考回答：
堆排序就是把最大堆堆顶的最大数取出，将剩余的堆继续调整为最大堆，再次将堆顶的最大数取出，这个过程持续到剩余数只有一个时结束。在堆中定义以下几种操作：
（1）最大堆调整（Max-Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点。
（2）创建最大堆（Build-Max-Heap）：将堆所有数据重新排序，使其成为最大堆。
（3）堆排序（Heap-Sort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算
● 谈一谈，如何得到一个数据流中的中位数？
考察点：排序
参考回答：
数据是从一个数据流中读出来的，数据的数目随着时间的变化而增加。如果用一个数据容器来保存从流中读出来的数据，当有新的数据流中读出来时，这些数据就插入到数据容器中。
数组是最简单的容器。如果数组没有排序，可以用 Partition 函数找出数组中的中位数。在没有排序的数组中插入一个数字和找出中位数的时间复杂度是 O(1)和 O(n)。
我们还可以往数组里插入新数据时让数组保持排序，这是由于可能要移动 O(n)个数，因此需要 O(n)时间才能完成插入操作。在已经排好序的数组中找出中位数是一个简单的操作，只需要 O(1)时间即可完成。
排序的链表时另外一个选择。我们需要 O(n)时间才能在链表中找到合适的位置插入新的数据。如果定义两个指针指向链表的中间结点（如果链表的结点数目是奇数，那么这两个指针指向同一个结点），那么可以在 O（1）时间得出中位数。此时时间效率与及基于排序的数组的时间效率一样。
如果能够保证数据容器左边的数据都小于右边的数据，这样即使左、右两边内部的数据没有排序，也可以根据左边最大的数及右边最小的数得到中位数。如何快速从一个容器中找出最大数？用最大堆实现这个数据容器，因为位于堆顶的就是最大的数据。同样，也可以快速从最小堆中找出最小数。
因此可以用如下思路来解决这个问题：用一个最大堆实现左边的数据容器，用最小堆实现右边的数据容器。往堆中插入一个数据的时间效率是 O(logn)。由于只需 O(1)时间就可以得到位于堆顶的数据，因此得到中位数的时间效率是 O(1)。
● 你知道哪些排序算法，这些算法的时间复杂度分别是多少，解释一下快排？
考察点：快排
参考回答：
快排：快速排序有两个方向，左边的i下标一直往右走（当条件a[i] <= a[center_index]时），其中center_index是中枢元素的数组下标，一般取为数组第0个元素。
而右边的j下标一直往左走（当a[j] > a[center_index]时）。
如果i和j都走不动了，i <= j, 交换a[i]和a[j],重复上面的过程，直到i>j。交换a[j]和a[center_index]，完成一趟快速排序。
</article>
public class
OddIncreaseEvenDecrease {
/**
* 按照奇偶位拆分成两个链表
* @param head
* @return
*/
public static Node[] getLists(Node head){
Node head1 = null``;
Node head2 = null``;
Node cur1 = null``;
Node cur2 = null``;
int count = 1``;``//用来计数
while``(head != null``){
if``(count % 2 == 1``){
if``(cur1 != null``){
cur1.next = head;
cur1 = cur1.next;
}``else``{
cur1 = head;
head1 = cur1;
}
}``else``{
if``(cur2 != null``){
cur2.next = head;
cur2 = cur2.next;
}``else``{
cur2 = head;
head2 = cur2;
}
}
head = head.next;
count++;
}
//跳出循环，要让最后两个末尾元素的下一个都指向null
cur1.next = null``;
cur2.next = null``;
Node[] nodes = new Node[]{head1,
head2};
return nodes;
}
/**
* 反转链表
* @param head
* @return
*/
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;
}
/**
* 合并两个有序链表
* @param head1
* @param head2
* @return
*/
public static Node CombineList(Node head1,
Node head2){
if``(head1 == null || head2 == null``){
return head1 != null ? head1 :
head2;
}
Node head = head1.value < head2.value ?
head1 : head2;
Node cur1 = head == head1 ? head1 :
head2;
Node cur2 = head == head1 ? head2 :
head1;
Node pre = null``;
Node next = null``;
while``(cur1 != null && cur2 !=
null``){
if``(cur1.value <= cur2.value){``//这里一定要有=，否则一旦cur1的value和cur2的value相等的话，下面的pre.next会出现空指针异常
pre = cur1;
cur1 = cur1.next;
}``else``{
next = cur2.next;
pre.next = cur2;
cur2.next = cur1;
pre = cur2;
cur2 = next;
}
}
pre.next = cur1 == null ? cur2 : cur1;
return head;
}
}
|
● 随机链表的复制
考察点：链表
参考回答：
public RandomListNode copyRandomList(RandomListNode head) {
if (head == null``)
return null``;
RandomListNode p = head;
// copy every node and insert to list
while (p != null``) {
RandomListNode copy = new RandomListNode(p.label);
copy.next = p.next;
p.next = copy;
p = copy.next;
}
// copy random pointer for each new node
p = head;
while (p != null``) {
if (p.random != null``)
p.next.random = p.random.next;
p = p.next.next;
}
// break list to two
p = head;
RandomListNode newHead = head.next;
while (p != null``) {
RandomListNode temp = p.next;
p.next = temp.next;
if (temp.next != null``)
temp.next = temp.next.next;
p = p.next;
}
return newHead;
}
|
● 如何反转单链表
考察点：链表
参考回答：
ListNode
reverseList(ListNode* head) {
if``(head == nullptr || head->next ==
nullptr)
return head;
ListNode* p;
ListNode* q;
ListNode* r;
p = head;
q = head->next;
head->next = nullptr;``//旧的头指针是新的尾指针 指向NULL
while``(q){
r = q->next;``//用来保存下一步要处理的指针
q->next = p;``//p q 交替处理 进行反转单链表
p = q;
q = r;
}
head = p;``//最后的q必定指向NULL，p就成了新链表的头指针
return head;
}
● 请你解释一下，内存中的栈(stack)、堆(heap) 和静态区(static area) 的用法。
考察点：堆栈
参考回答：
通常我们定义一个基本数据类型的变量，一个对象的引用，还有就是函数调用的现场保存都使用内存中的栈空间；而通过new关键字和构造器创建的对象放在堆空间；程序中的字面量（literal）如直接书写的100、"hello"和常量都是放在静态区中。栈空间操作起来最快但是栈很小，通常大量的对象都是放在堆空间，理论上整个内存没有被其他进程使用的空间甚至硬盘上的虚拟内存都可以被当成堆空间来使用。
String str = new String("hello");
上面的语句中变量str放在栈上，用new创建出来的字符串对象放在堆上，而"hello"这个字面量放在静态区。
● 说一说，heap和stack有什么区别。
考察点：堆与栈
参考回答：
栈是一种线形集合，其添加和删除元素的操作应在同一段完成。栈按照后进先出的方式进行处理。
堆是栈的一个组成元素。
● 介绍一下，堆与栈的不同是什么？
考察点：堆，栈
参考回答：
（1）Java的堆是一个运行时数据区，类的对象从中分配空间。通过比如：new等指令建立，不需要代码显式的释放，由垃圾回收来负责。
优点：可以动态地分配内存大小，垃圾收集器会自动回收垃圾数据。
缺点：由于其优点，所以存取速度较慢。
（2）栈：
其数据项的插入和删除都只能在称为栈顶的一端完成，后进先出。栈中存放一些基本类型的 变量 和 对象句柄。
优点：读取数度比堆要快，仅次于寄存器，栈数据可以共享。
缺点：比堆缺乏灵活性，存在栈中的数据大小与生存期必须是确定的。
举例：
String是一个特殊的包装类数据。可以用：
String str = new String("csdn");
String str = "csdn";
两种的形式来创建，第一种是用new()来新建对象的，它会在存放于堆中。每调用一次就会创建一个新的对象。而第二种是先在栈中创建一个对String类的对象引用变量str，然后查找栈中有没有存放"csdn"，如果没有，则将"csdn"存放进栈，并令str指向”abc”，如果已经有”csdn” 则直接令str指向“csdn”。
● 什么是Java优先级队列(Priority Queue)？
考察点：队列
参考回答：
PriorityQueue是一个基于优先级堆的无界队列，它的元素是按照自然顺序(natural order)排序的。在创建的时候，我们可以给它提供一个负责给元素排序的比较器。PriorityQueue不允许null值，因为他们没有自然顺序，或者说他们没有任何的相关联的比较器。最后，PriorityQueue不是线程安全的，入队和出队的时间复杂度是O(log(n))。
● 请你讲讲LRU算法的实现原理？
考察点：LRU算法
参考回答：
①LRU（Least recently used，最近最少使用）算法根据数据的历史访问记录来进行淘汰数据，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也很高”，反过来说“如果数据最近这段时间一直都没有访问,那么将来被访问的概率也会很低”，两种理解是一样的；常用于页面置换算法，为虚拟页式存储管理服务。
②达到这样一种情形的算法是最理想的：每次调换出的页面是所有内存页面中最迟将被使用的；这可以最大限度的推迟页面调换，这种算法，被称为理想页面置换算法。可惜的是，这种算法是无法实现的。
为了尽量减少与理想算法的差距，产生了各种精妙的算法，最近最少使用页面置换算法便是其中一个。LRU 算法的提出，是基于这样一个事实：在前面几条指令中使用频繁的页面很可能在后面的几条指令中频繁使用。反过来说，已经很久没有使用的页面很可能在未来较长的一段时间内不会被用到 。这个，就是著名的局部性原理——比内存速度还要快的cache，也是基于同样的原理运行的。因此，我们只需要在每次调换时，找到最近最少使用的那个页面调出内存。
算法实现的关键
命中率：
当存在热点数据时，LRU的效率很好，但偶发性的、周期性的批量操作会导致 LRU 命中率急剧下降，缓存污染情况比较严重。
复杂度：
实现起来较为简单。
存储成本：
几乎没有空间上浪费。
代价：
命中时需要遍历链表，找到命中的数据块索引，然后需要将数据移到头部。
● 为什么要设计 后缀表达式，有什么好处？
考察点：逆波兰表达式
参考回答：
后缀表达式又叫逆波兰表达式，逆波兰记法不需要括号来标识操作符的优先级。
● 请你设计一个算法，用来压缩一段URL？
考察点：MD5加密算法
参考回答：
该算法主要使用MD5 算法对原始链接进行加密（这里使用的MD5 加密后的字符串长度为32 位），然后对加密后的字符串进行处理以得到短链接的地址。
● 谈一谈，id全局唯一且自增，如何实现？
考察点：SnowFlake雪花算法
参考回答；
SnowFlake雪花算法
雪花ID生成的是一个64位的二进制正整数，然后转换成10进制的数。64位二进制数由如下部分组成：
snowflake id生成规则
1位标识符：始终是0，由于long基本类型在Java中是带符号的，最高位是符号位，正数是0，负数是1，所以id一般是正数，最高位是0。
41位时间戳：41位时间截不是存储当前时间的时间截，而是存储时间截的差值（当前时间截 - 开始时间截 )得到的值，这里的的开始时间截，一般是我们的id生成器开始使用的时间，由我们程序来指定的。
10位机器标识码：可以部署在1024个节点，如果机器分机房（IDC）部署，这10位可以由 5位机房ID + 5位机器ID 组成。
12位序列：毫秒内的计数，12位的计数顺序号支持每个节点每毫秒(同一机器，同一时间截)产生4096个ID序号
优点
简单高效，生成速度快。
时间戳在高位，自增序列在低位，整个ID是趋势递增的，按照时间有序递增。
灵活度高，可以根据业务需求，调整bit位的划分，满足不同的需求。
缺点
依赖机器的时钟，如果服务器时钟回拨，会导致重复ID生成。
在分布式环境上，每个服务器的时钟不可能完全同步，有时会出现不是全局递增的情况
0.如果遇到相等的值不进行交换，那这种排序方式是稳定的排序方式。
1.原理：比较两个相邻的元素，将值大的元素交换到右边
2.思路：依次比较相邻的两个数，将比较小的数放在前面，比较大的数放在后面。
(1)第一次比较：首先比较第一和第二个数，将小数放在前面，将大数放在后面。
(2)比较第2和第3个数，将小数 放在前面，大数放在后面。
......
(3)如此继续，知道比较到最后的两个数，将小数放在前面，大数放在后面，重复步骤，直至全部排序完成
(4)在上面一趟比较完成后，最后一个数一定是数组中最大的一个数，所以在比较第二趟的时候，最后一个数是不参加比较的。
(5)在第二趟比较完成后，倒数第二个数也一定是数组中倒数第二大数，所以在第三趟的比较中，最后两个数是不参与比较的。
(6)依次类推，每一趟比较次数减少依次
3.举例：
(1)要排序数组:[10,1,35,61,89,36,55]
(2)第一趟排序：
第一次排序：10和1比较，10大于1，交换位置 [1,10,35,61,89,36,55]
第二趟排序：10和35比较，10小于35，不交换位置 [1,10,35,61,89,36,55]
第三趟排序：35和61比较，35小于61，不交换位置 [1,10,35,61,89,36,55]
第四趟排序：61和89比较，61小于89，不交换位置 [1,10,35,61,89,36,55]
第五趟排序：89和36比较，89大于36，交换位置 [1,10,35,61,36,89,55]
第六趟排序：89和55比较，89大于55，交换位置 [1,10,35,61,36,55,89]
第一趟总共进行了六次比较，排序结果：[1,10,35,61,36,55,89]
(3)第二趟排序：
第一次排序：1和10比较，1小于10，不交换位置 1,10,35,61,36,55,89
第二次排序：10和35比较，10小于35，不交换位置 1,10,35,61,36,55,89
第三次排序：35和61比较，35小于61，不交换位置 1,10,35,61,36,55,89
第四次排序：61和36比较，61大于36，交换位置 1,10,35,36,61,55,89
第五次排序：61和55比较，61大于55，交换位置 1,10,35,36,55,61,89
第二趟总共进行了5次比较，排序结果：1,10,35,36,55,61,89
(4)第三趟排序：
1和10比较，1小于10，不交换位置 1,10,35,36,55,61,89
第二次排序：10和35比较，10小于35，不交换位置 1,10,35,36,55,61,89
第三次排序：35和36比较，35小于36，不交换位置 1,10,35,36,55,61,89
第四次排序：36和61比较，36小于61，不交换位置 1,10,35,36,55,61,89
第三趟总共进行了4次比较，排序结果：1,10,35,36,55,61,89
到目前位置已经为有序的情形了。
4.算法分析：
(1)由此可见：N个数字要排序完成，总共进行N-1趟排序，每i趟的排序次数为(N-i)次，所以可以用双重循环语句，外层控制循环多少趟，内层控制每一趟的循环次数
(2)冒泡排序的优点：每进行一趟排序，就会少比较一次，因为每进行一趟排序都会找出一个较大值。如上例：第一趟比较之后，排在最后的一个数一定是最大的一个数，第二趟排序的时候，只需要比较除了最后一个数以外的其他的数，同样也能找出一个最大的数排在参与第二趟比较的数后面，第三趟比较的时候，只需要比较除了最后两个数以外的其他的数，以此类推……也就是说，没进行一趟比较，每一趟少比较一次，一定程度上减少了算法的量。
(3)时间复杂度
1.如果我们的数据正序，只需要走一趟即可完成排序。所需的比较次数C和记录移动次数M均达到最小值，即：Cmin=n-1;Mmin=0;所以，冒泡排序最好的时间复杂度为O(n)。
2.如果很不幸我们的数据是反序的，则需要进行n-1趟排序。每趟排序要进行n-i次比较(1≤i≤n-1)，且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下，比较和移动次数均达到最大值：
综上所述：冒泡排序总的平均时间复杂度为：O(n2) ,时间复杂度和数据状况无关。
5.java代码实现，代码的实现用到了对数发生器
[
](javascript:void(0); "复制代码")
<pre>import java.util.Arrays;
//算法的最终时间复杂度为n^2
public class BubbleSort {
public static void main(String[] args) {
int testTime=500000;
int size = 10;
int value=100;
boolean succeed = true;
for(int i = 0 ;i<testTime;i++){
int[] arr1 = generateRandomArray(size,value);
int[] arr2 = copyArray(arr1);
int[] arr3= copyArray(arr1);
bubbleSort(arr1);
rightMethod(arr2);
if(!isEqual(arr1,arr2)){
succeed=false;
printArray(arr3);
break;
}
}
System.out.println(succeed?"Nice":"Fucking fucked!");
int[] arr= generateRandomArray(size,value);
printArray(arr);
bubbleSort(arr);
printArray(arr);
}
//产生一个随机数组，数组的长度和值都是随机的，
public static int[] generateRandomArray(int size,int value){
//在java中，Math.random() ->double(0,1)
//(int)((size+1)Math.random())--->产生的是[0,size]之间的整数
//生成长度随机的数组，数组的最大长度是size的长度
int[] arr = new int[(int)((size+1)Math.random())];
for(int i = 0 ;i<arr.length;i++){
//针对数组中的每个值都可以随机一下，一个随机数减去另外一个随机数，可能产生正数，也可能产生负数
arr[i]=(int)((value+1)Math.random())-(int)(valueMath.random());//值也可以是随机的
}
return arr;
}
//复制数组
public static int[] copyArray(int[] arr){
if(arr==null){
return null;
}
int[] res = new int[arr.length];
for(int i = 0 ;i<arr.length;i++){
res[i]=arr[i] ;
}
return res;
}
//绝对正确的方法,这个方法可以时间复杂度很差，但是要保证其准确性
public static void rightMethod(int[] arr){
Arrays.sort(arr);
}
//
public static boolean isEqual(int[] arr1,int[] arr2){
if(arr1==null&&arr2!=null||arr1!=null&&arr2==null){
return false;
}
if (arr1==null&&arr2==null){
return true;
}
if (arr1.length!=arr2.length){
return false;
}
for(int i = 0;i<arr1.length;i++){
if(arr1[i]!=arr2[i]){
return false;
}
}
return true;
}
//打印出数组
public static void printArray(int[] arr){
if(arr==null){
return;
}
for(int i = 0 ;i<arr.length;i++){
System.out.print(arr[i]+" ");
}
System.out.println();
}
//N个数字冒泡排序，总共要进行N-1趟比较，每趟的排序次数为(N-i)次比较
public static void bubbleSort(int[] arr){
//一定要记住判断边界条件，很多人不注意这些细节，面试官看到你的代码的时候都懒得往下看，你的代码哪个项目敢往里面加？
if(arr==null||arr.length<2){
return;
}
//需要进行arr.length趟比较
for(int i = 0 ;i<arr.length-1;i++){
//第i趟比较
for(int j = 0 ;j<arr.length-i-1;j++){
//开始进行比较，如果arr[j]比arr[j+1]的值大，那就交换位置
if(arr[j]>arr[j+1]){
int temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
}
}
// System.out.println("最终得出的数组为：");
// for (int k =0 ; k < arr.length;k++){
// System.out.print(arr[k]+" ");
// }
}
//生成一个对数器。产生一个随机样本的数组，数组的长度和值都是随机的
//size是生成数组的最大长度
// public static int[] generateRandomArray(int size,int value){
// //生成长度随机的数组
// int[] arr = new int[(int)((size+1)Math.random())];
// for(int i = 0 ;i<arr.length;i++){
// arr[i]=(int)((value+1)Math.random())-(int)(value*Math.random());
// }
// return arr;
// }
//for test
public static void rightMathods(int[] arr){
//调用系统调用的函数来进行验证
Arrays.sort(arr);
}
}</pre>
<article class="post-topic-des entry-content nc-post-content js-nc-pop-image" itemprop="text">
● 介绍一下 如何实现动态代理？
考察点：动态代理流程
参考回答：
Java实现动态代理的大致步骤如下：
1.定义一个委托类和公共接口。
2.自己定义一个类（调用处理器类，即实现 InvocationHandler 接口），这个类的目的是指定运行时将生成的代理类需要完成的具体任务（包括Preprocess和Postprocess），即代理类调用任何方法都会经过这个调用处理器类（在本文最后一节对此进行解释）。
3.生成代理对象（当然也会生成代理类），需要为他指定(1)委托对象(2)实现的一系列接口(3)调用处理器类的实例。因此可以看出一个代理对象对应一个委托对象，对应一个调用处理器实例。
4.Java 实现动态代理主要涉及以下几个类：
①java.lang.reflect.Proxy: 这是生成代理类的主类，通过 Proxy 类生成的代理类都继承了 Proxy 类，即 DynamicProxyClass extends Proxy。
②java.lang.reflect.InvocationHandler: 这里称他为"调用处理器"，他是一个接口，我们动态生成的代理类需要完成的具体内容需要自己定义一个类，而这个类必须实现 InvocationHandler 接口。
示例代码：
|
1
2
3
4
5
6
7
8
|
public final class $Proxy1 extends Proxy implements Subject{
private InvocationHandler h;
private $Proxy1(){}
public $Proxy1(InvocationHandler h){
this``.h = h; }
public int request(``int i){
Method method = Subject.``class``.getMethod(``"request"``, new Class[]{``int``.``class``}); //创建method对象
return (Integer)h.invoke(``this``, method, new Object[]{``new Integer(i)}); //调用了invoke方法 } }
|
● 谈一谈，java中有哪些代理模式？
考察点：代理模式
参考回答：
静态代理，动态代理，Cglib代理。
● Java IO都有哪些设计模式，简单介绍一下。
考察点：装饰模式，适配器模式
参考回答：
装饰模式和适配器模式
</article>
● 请你介绍一下单例模式？再说一说 懒汉式的单例模式如何实现单例？
考察点：单例模式
参考回答：
定义：保证一个类仅有一个实例，并提供一个访问它的全局访问点。优点：单例类只有一个实例、共享资源，全局使用节省创建时间，提高性能。可以用静态内部实现，保证是懒加载就行了，就是使用才会创建实例对象。
<article class="post-topic-des entry-content nc-post-content js-nc-pop-image" itemprop="text">
● 请你介绍一下策略模式？
考察点：策略模式
参考回答：
策略模式也叫政策模式，是一种行为型设计模式，是一种比较简单的设计模式。策略模式采用了面向对象的继承和多态机制。略模式适合使用在：1.多个类只有在算法或行为上稍有不同的场景。2.算法需要自由切换的场景。3.需要屏蔽算法规则的场景。 使用策略模式当然也有需要注意的地方，那么就是策略类不要太多，如果一个策略家族的具体策略数量超过4个，则需要考虑混合模式，解决策略类膨胀和对外暴露问题。在实际项目中，我们一般通过工厂方法模式来实现策略类的声明。
优点：算法可以自由切换。2.避免使用多重条件判断。3.扩展性良好。
● 对于设计模式，你了解哪些？请手写一下观察者模式。
考察点：观察者模式
参考回答：
观察者模式优点：
观察者模式在被观察者和观察者之间建立一个抽象的耦合。被观察者角色所知道的只是一个具体观察者列表，每一个具体观察者都符合一个抽象观察者的接口。被观察者并不认识任何一个具体观察者，它只知道它们都有一个共同的接口。由于被观察者和观察者没有紧密地耦合在一起，因此它们可以属于不同的抽象化层次。如果被观察者和观察者都被扔到一起，那么这个对象必然跨越抽象化和具体化层次。
观察者模式缺点：
如果一个被观察者对象有很多的直接和间接的观察者的话，将所有的观察者都通知到会花费很多时间。
如果在被观察者之间有循环依赖的话，被观察者会触发它们之间进行循环调用，导致系统崩溃。在使用观察者模式是要特别注意这一点。
如果对观察者的通知是通过另外的线程进行异步投递的话，系统必须保证投递是以自恰的方式进行的。
虽然观察者模式可以随时使观察者知道所观察的对象发生了变化，但是观察者模式没有相应的机制使观察者知道所观察的对象是怎么发生变化的。
</article>
● 谈一谈，你了解的 Java设计模式。
考察点：设计模式
参考回答：
所谓设计模式，就是一套被反复使用的代码设计经验的总结（情境中一个问题经过证实的一个解决方案）。使用设计模式是为了可重用代码、让代码更容易被他人理解、保证代码可靠性。设计模式使人们可以更加简单方便的复用成功的设计和体系结构。将已证实的技术表述成设计模式也会使新系统开发者更加容易理解其设计思路。
在GoF的《Design Patterns: Elements of Reusable Object-Oriented Software》中给出了三类（创建型[对类的实例化过程的抽象化]、结构型[描述如何将类或对象结合在一起形成更大的结构]、行为型[对在不同的对象之间划分责任和算法的抽象化]）共23种设计模式，包括：Abstract Factory（抽象工厂模式），Builder（建造者模式），Factory Method（工厂方法模式），Prototype（原始模型模式），Singleton（单例模式）；Facade（门面模式），Adapter（适配器模式），Bridge（桥梁模式），Composite（合成模式），Decorator（装饰模式），Flyweight（享元模式），Proxy（代理模式）；Command（命令模式），Interpreter（解释器模式），Visitor（访问者模式），Iterator（迭代子模式），Mediator（调停者模式），Memento（备忘录模式），Observer（观察者模式），State（状态模式），Strategy（策略模式），Template Method（模板方法模式）， Chain Of Responsibility（责任链模式）。
● 谈一谈，开发中都用到了 哪些设计模式? 用在什么场合?
考察点：设计模式
参考回答：
每个模式都描述了一个在我们的环境中不断出现的问题，然后描述了该问题的解决方案的核心。通过这种方式，你可以无数次地使用那些已有的解决方案，无需在重复相同的工作。主要用到了MVC的设计模式。用来开发JSP/Servlet或者J2EE的相关应用。简单工厂模式等。
● 谈一谈 J2EE 的常用 设计模式有哪些？再详细说说工厂模式。
考察点：j2ee设计模式
参考回答：
Java中的23种设计模式：
Factory（工厂模式）， Builder（建造模式）， Factory Method（工厂方法模式），Prototype（原始模型模式），Singleton（单例模式）， Facade（门面模式），Adapter（适配器模式）， Bridge（桥梁模式）， Composite（合成模式），Decorator（装饰模式）， Flyweight（享元模式）， Proxy（代理模式），Command（命令模式）， Interpreter（解释器模式）， Visitor（访问者模式），Iterator（迭代子模式）， Mediator（调停者模式）， Memento（备忘录模式），Observer（观察者模式）， State（状态模式）， Strategy（策略模式），Template Method（模板方法模式）， Chain Of Responsibleity（责任链模式）工厂模式：工厂模式是一种经常被使用到的模式，根据工厂模式实现的类可以根据提供的数据生成一组类中某一个类的实例，通常这一组类有一个公共的抽象父类并且实现了相同的方法，但是这些方法针对不同的数据进行了不同的操作。首先需要定义一个基类，该类的子类通过不同的方法实现了基类中的方法。然后需要定义一个工厂类，工厂类可以根据条件生成不同的子类实例。当得到子类的实例后，开发人员可以调用基类中的方法而不必考虑到底返回的是哪一个子类的实例。
● 说说你所熟悉 或听说过的，J2EE中的几种常用模式。再讲讲你对设计模式的一些看法
考察点：J2EE设计模式
参考回答：
Session Facade Pattern：使用SessionBean访问EntityBean Message Facade Pattern：实现异步调用EJB Command Pattern：使用Command JavaBeans取代SessionBean，实现轻量级访问Data Transfer Object Factory：通过DTO Factory简化EntityBean数据提供特性Generic Attribute Access：通过AttibuteAccess接口简化EntityBean数据提供特性Business Interface：通过远程（本地）接口和Bean类实现相同接口规范业务逻辑一致性ＥＪＢ架构的设计好坏将直接影响系统的性能、可扩展性、可维护性、组件可重用性及开发效率。项目越复杂，项目队伍越庞大则越能体现良好设计的重要性。
● 请你讲讲UML中有哪些常用的图？
考察点：用例图
参考回答：
UML定义了多种图形化的符号来描述软件系统部分或全部的静态结构和动态结构，包括：用例图（use case diagram）、类图（class diagram）、时序图（sequence diagram）、协作图（collaboration diagram）、状态图（statechart diagram）、活动图（activity diagram）、构件图（component diagram）、部署图（deployment diagram）等。在这些图形化符号中，有三种图最为重要，分别是：用例图（用来捕获需求，描述系统的功能，通过该图可以迅速的了解系统的功能模块及其关系）、类图（描述类以及类与类之间的关系，通过该图可以快速了解系统）、时序图（描述执行特定任务时对象之间的交互关系以及执行顺序，通过该图可以了解对象能接收的消息也就是说对象能够向外界提供的服务）。
