● 如何打印二叉樹每層的節(jié)點(diǎn)窥妇？
考察點(diǎn)：二叉樹
參考回答：
實(shí)現(xiàn)代碼：
import
java.util.ArrayList;
import
java.util.Scanner;
public class Main
{
// 定義節(jié)點(diǎn)
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; // 保存已經(jīng)排好的節(jié)點(diǎn)
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<>(); // 已經(jīng)還原的節(jié)點(diǎn)
//
exception
if``(count
== 1``) {
System.out.println(gzy.get(``0``));
return``;
}
// 構(gòu)造最左側(cè)節(jié)點(diǎn)的二叉樹
Node
node = new Node(gzy.get(``0``));
pack.add(node);
int
index1 = 1``; // 根左右的下標(biāo)
Node
tmp = node;
while``(gzy.get(index1)
!= zgy.get(``0``)) { // 如果沒訪問到最左邊的葉子節(jié)點(diǎn),繼續(xù)還原最左側(cè)二叉樹
tmp.left = new Node(gzy.get(index1++));
tmp = tmp.left;
pack.add(tmp);
}
tmp.left
= new Node(gzy.get(index1++));
pack.add(tmp.left);
// 加入剩余的節(jié)點(diǎn)完善二叉樹
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的節(jié)點(diǎn)加入二叉樹
private void fillErCS(``int val) {
int
index = zgy.indexOf(val);
// 每一個(gè)遍歷的節(jié)點(diǎn)都是val節(jié)點(diǎn)的根或者在其左邊
for``(``int
i = index-``1``; i >= 0``; i--) {
if``(findNode(zgy.get(i)) != null``) { // 找到待插入節(jié)點(diǎn)的根節(jié)點(diǎn)或者其左邊的節(jié)點(diǎn)
Node
node = findNode(zgy.get(i));
insert(node,
val);
break``;
}
}
}
// 將節(jié)點(diǎn)val插入二叉樹
private void insert(Node node, int val) {
if``(zgy.indexOf(node.val)
> zgy.indexOf(val)) { // node在待插入節(jié)點(diǎn)的右邊
if``(node.left == null``) {
node.left
= new Node(val);
pack.add(node.left);
return``;
}
insert(node.left, val);
}``else
{ //
node在待插入節(jié)點(diǎn)的左邊或是其根
if``(node.right == null``) {
node.right
= new Node(val);
pack.add(node.right);
return``;
}
insert(node.right, val);
}
}
// 根據(jù)val找到pack里的節(jié)點(diǎn)
private Node findNode(``int val) {
for``(Node
node : pack) {
if``(node.val == val) {
return
node;
}
}
return
null``;
}
}
|
● 如何知道二叉樹的深度挺益？
考察點(diǎn)：二叉樹
參考回答：
實(shí)現(xiàn)二叉樹的深度方式有兩種牲尺，遞歸以及非遞歸。
①遞歸實(shí)現(xiàn)：
為了求樹的深度戳玫，可以先求其左子樹的深度和右子樹的深度熙掺，可以用遞歸實(shí)現(xiàn)，遞歸的出口就是節(jié)點(diǎn)為空咕宿。返回值為0币绩；
②非遞歸實(shí)現(xiàn)：
利用層次遍歷的算法，設(shè)置變量level記錄當(dāng)前節(jié)點(diǎn)所在的層數(shù)府阀，設(shè)置變量last指向當(dāng)前層的最后一個(gè)節(jié)點(diǎn)缆镣，當(dāng)處理完當(dāng)前層的最后一個(gè)節(jié)點(diǎn)，讓level指向+1操作肌似。設(shè)置變量cur記錄當(dāng)前層已經(jīng)訪問的節(jié)點(diǎn)的個(gè)數(shù)费就，當(dāng)cur等于last時(shí)诉瓦，表示該層訪問結(jié)束川队。
層次遍歷在求樹的寬度、輸出某一層節(jié)點(diǎn)睬澡，某一層節(jié)點(diǎn)個(gè)數(shù)固额，每一層節(jié)點(diǎn)個(gè)數(shù)都可以采取類似的算法。
樹的寬度：在樹的深度算法基礎(chǔ)上煞聪，加一個(gè)記錄訪問過的層節(jié)點(diǎn)個(gè)數(shù)最多的變量max,在訪問每層前max與last比較斗躏，如果max比較大，max不變昔脯，如果max小于last啄糙，把last賦值給max;
代碼解釋：
import
java.util.LinkedList;
public class Deep
{
//遞歸實(shí)現(xiàn)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;
}
//遞歸實(shí)現(xiàn)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``;``//左子樹和右子樹深度較大的那個(gè)加一等于整個(gè)樹的深度
}
}
//非遞歸實(shí)現(xiàn)
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``;``//記錄本層已經(jīng)遍歷的節(jié)點(diǎn)個(gè)數(shù)
last = queue.size();``//當(dāng)遍歷完當(dāng)前層以后笛臣，隊(duì)列里元素全是下一層的元素，隊(duì)列的長(zhǎng)度是這一層的節(jié)點(diǎn)的個(gè)數(shù)
while``(cur < last)``//當(dāng)還沒有遍歷到本層最后一個(gè)節(jié)點(diǎn)時(shí)循環(huán)
{
current = queue.poll();``//出隊(duì)一個(gè)元素
cur++;
//把當(dāng)前節(jié)點(diǎn)的左右節(jié)點(diǎn)入隊(duì)（如果存在的話）
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));
}
}
|
● 二叉樹任意兩個(gè)節(jié)點(diǎn)之間路徑的最大長(zhǎng)度
考察點(diǎn)：樹
參考回答：
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``;
//如果以該節(jié)點(diǎn)為根的子樹中有最大的距離沈堡，那就更新最大距離
int sum = root->rm + root->lm;
if``(sum > max) {
max = sum;
}
return root->rm > root->lm ?
root->rm : root->lm;
}
|
● 算法題：二叉樹層序遍歷，進(jìn)一步提問：要求每層打印出一個(gè)換行符
考察點(diǎn)：二叉樹
參考回答：
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;
}
|
● 怎么求一個(gè)二叉樹的深度?手撕代碼?
考察點(diǎn)：二叉樹
參考回答：
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``;
}
|
● 請(qǐng)你說一下燕雁，B+樹和B-樹诞丽？
考察點(diǎn)：樹
參考回答：
b+樹的中間節(jié)點(diǎn)不保存數(shù)據(jù)僧免，所以磁盤頁能容納更多節(jié)點(diǎn)元素懂衩，更“矮胖”金踪；
b+樹查詢必須查找到葉子節(jié)點(diǎn)勃痴，b樹只要匹配到即可不用管元素位置，因此b+樹查找更穩(wěn)定（并不慢）热康；
對(duì)于范圍查找來說沛申，b+樹只需遍歷葉子節(jié)點(diǎn)鏈表即可，b樹卻需要重復(fù)地中序遍歷姐军。
</article>
● 二叉樹 Z 字型遍歷
考察點(diǎn)：遍歷
參考回答：
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;
}
|
● 編程題：寫一個(gè)函數(shù)铁材，找到一個(gè)文件夾下所有文件，包括子文件夾
考察點(diǎn)：遍歷
參考回答：
import
java.io.File;
public class
Counter2 {
public static void main(String[] args) {
//取得目標(biāo)目錄
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());
}
//如果是文件夾，遞歸調(diào)用
else if``(f.isDirectory()) {
readfile(f.listFiles());
}
}
}
}
|
● 現(xiàn)在有一個(gè)單向鏈表惊暴，談一談，如何判斷鏈表中是否出現(xiàn)了環(huán)
考察點(diǎn)：鏈表
參考回答：
單鏈表有環(huán)肄鸽，是指單鏈表中某個(gè)節(jié)點(diǎn)的next指針域指向的是鏈表中在它之前的某一個(gè)節(jié)點(diǎn)逮诲，這樣在鏈表的尾部形成一個(gè)環(huán)形結(jié)構(gòu)。
// 鏈表的節(jié)點(diǎn)結(jié)構(gòu)如下 typedef struct node { int data; struct node *next; } NODE;
最常用方法：定義兩個(gè)指針淑掌，同時(shí)從鏈表的頭節(jié)點(diǎn)出發(fā)担敌，一個(gè)指針一次走一步桃犬，另一個(gè)指針一次走兩步。如果走得快的指針追上了走得慢的指針就轧，那么鏈表就是環(huán)形鏈表乎莉；如果走得快的指針走到了鏈表的末尾（next指向 NULL）都沒有追上第一個(gè)指針，那么鏈表就不是環(huán)形鏈表魄宏。
通過使用STL庫中的map表進(jìn)行映射椭坚。首先定義 map<NODE *, int> m; 將一個(gè) NODE * 指針映射成數(shù)組的下標(biāo)垂涯，并賦值為一個(gè) int 類型的數(shù)值。然后從鏈表的頭指針開始往后遍歷，每次遇到一個(gè)指針p，就判斷 m[p] 是否為0。如果為0冀惭，則將m[p]賦值為1戚丸，表示該節(jié)點(diǎn)第一次訪問；而如果m[p]的值為1，則說明這個(gè)節(jié)點(diǎn)已經(jīng)被訪問過一次了寥裂，于是就形成了環(huán)褐啡。
● 談一談，bucket如果用鏈表存儲(chǔ)，它的缺點(diǎn)是什么？
考察點(diǎn)：鏈表
參考回答：
①查找速度慢司光，因?yàn)椴檎視r(shí)售躁，需要循環(huán)鏈表訪問
②如果進(jìn)行頻繁插入和刪除操作，會(huì)導(dǎo)致速度很慢。
● 有一個(gè)鏈表酒觅，奇數(shù)位升序偶數(shù)位降序蜓肆，如何將鏈表變成升序
考察點(diǎn)：鏈表
參考回答：
● 寫一個(gè)算法瑞信，可以將一個(gè)二維數(shù)組順時(shí)針旋轉(zhuǎn)90度精肃，說一下思路黎烈。
考察點(diǎn)：數(shù)組
參考回答：
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;
}
}
}
|
● 一個(gè)數(shù)組，除一個(gè)元素外其它都是兩兩相等，求那個(gè)元素?
考察點(diǎn)：數(shù)組
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;
}
|
● 找出數(shù)組中和為S的一對(duì)組合，找出一組就行
考察點(diǎn)：數(shù)組
參考回答：
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;
}
|
● 求一個(gè)數(shù)組中連續(xù)子向量的最大和
考察點(diǎn)：數(shù)組
參考回答：
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;
}
|
● 尋找一數(shù)組中前K個(gè)最大的數(shù)
考察點(diǎn)：數(shù)組
參考回答：
|
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寫一個(gè)冒泡排序？
考察點(diǎn)：冒泡排序
參考回答：
|
import
java.util.Comparator;
/**
* 排序器接口(策略模式: 將算法封裝到具有共同接口的獨(dú)立的類中使得它們可以相互替換)
*/
public interface Sorter {
/**
*
*/
public interface Sorter {
/**
* 排序
* @param list 待排序的數(shù)組
*/
public <T extends Comparable<T>> void sort(T[] list);
/**
* 排序
* @param list 待排序的數(shù)組
* @param comp 比較兩個(gè)對(duì)象的比較器
*/
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``;
}
}
}
|
● 介紹一下类腮，排序都有哪幾種方法？請(qǐng)列舉出來需频。
考察點(diǎn)：排序
參考回答：
排序的方法有：插入排序（直接插入排序藐守、希爾排序），交換排序（冒泡排序、快速排序），選擇排序（直接選擇排序越走、堆排序）骡澈， 歸并排序护锤，分配排序（箱排序赤炒、基數(shù)排序） 快速排序的偽代碼雪情。 / /使用快速排序方法對(duì)a[ 0 :n- 1 ]排序 從a[ 0 :n- 1 ]中選擇一個(gè)元素作為m i d d l e，該元素為支點(diǎn) 把余下的元素分割為兩段left 和r i g h t正卧，使得l e f t中的元素都小于等于支點(diǎn)，而right 中的元素都大于等于支點(diǎn) 遞歸地使用快速排序方法對(duì)left 進(jìn)行排序 遞歸地使用快速排序方法對(duì)right 進(jìn)行排序 所得結(jié)果為l e f t + m i d d l e + r i g h t
● 介紹一下，歸并排序的原理是什么？
考察點(diǎn)：歸并排序
參考回答：
（1）歸并排序是建立在歸并操作上的一種有效的排序算法纬黎。該算法是采用分治法（Divide and Conquer）的一個(gè)非常典型的應(yīng)用拆座。
（2）首先考慮下如何將將二個(gè)有序數(shù)列合并。這個(gè)非常簡(jiǎn)單冠息，只要從比較二個(gè)數(shù)列的第一個(gè)數(shù)挪凑，誰小就先取誰，取了后就在對(duì)應(yīng)數(shù)列中刪除這個(gè)數(shù)逛艰。然后再進(jìn)行比較丹诀，如果有數(shù)列為空，那直接將另一個(gè)數(shù)列的數(shù)據(jù)依次取出即可。
（3）解決了上面的合并有序數(shù)列問題椭员，再來看歸并排序虱肄，其的基本思路就是將數(shù)組分成二組A，B晚凿，如果這二組組內(nèi)的數(shù)據(jù)都是有序的谢揪，那么就可以很方便的將這二組數(shù)據(jù)進(jìn)行排序辽慕。如何讓這二組組內(nèi)數(shù)據(jù)有序了卫旱？
可以將A壁却，B組各自再分成二組疮方。依次類推动壤，當(dāng)分出來的小組只有一個(gè)數(shù)據(jù)時(shí)，可以認(rèn)為這個(gè)小組組內(nèi)已經(jīng)達(dá)到了有序藤韵，然后再合并相鄰的二個(gè)小組就可以了。這樣通過先遞歸的分解數(shù)列喧兄，再合并數(shù)列就完成了歸并排序锌畸。
● 介紹一下命咐，堆排序的原理是什么？
考察點(diǎn)：堆排序
參考回答：
堆排序就是把最大堆堆頂?shù)淖畲髷?shù)取出蚣抗，將剩余的堆繼續(xù)調(diào)整為最大堆侈百，再次將堆頂?shù)淖畲髷?shù)取出，這個(gè)過程持續(xù)到剩余數(shù)只有一個(gè)時(shí)結(jié)束翰铡。在堆中定義以下幾種操作：
（1）最大堆調(diào)整（Max-Heapify）：將堆的末端子節(jié)點(diǎn)作調(diào)整，使得子節(jié)點(diǎn)永遠(yuǎn)小于父節(jié)點(diǎn)讽坏。
（2）創(chuàng)建最大堆（Build-Max-Heap）：將堆所有數(shù)據(jù)重新排序锭魔，使其成為最大堆。
（3）堆排序（Heap-Sort）：移除位在第一個(gè)數(shù)據(jù)的根節(jié)點(diǎn)路呜，并做最大堆調(diào)整的遞歸運(yùn)算
● 談一談迷捧，如何得到一個(gè)數(shù)據(jù)流中的中位數(shù)织咧？
考察點(diǎn)：排序
參考回答：
數(shù)據(jù)是從一個(gè)數(shù)據(jù)流中讀出來的，數(shù)據(jù)的數(shù)目隨著時(shí)間的變化而增加漠秋。如果用一個(gè)數(shù)據(jù)容器來保存從流中讀出來的數(shù)據(jù)笙蒙，當(dāng)有新的數(shù)據(jù)流中讀出來時(shí)，這些數(shù)據(jù)就插入到數(shù)據(jù)容器中庆锦。
數(shù)組是最簡(jiǎn)單的容器捅位。如果數(shù)組沒有排序，可以用 Partition 函數(shù)找出數(shù)組中的中位數(shù)搂抒。在沒有排序的數(shù)組中插入一個(gè)數(shù)字和找出中位數(shù)的時(shí)間復(fù)雜度是 O(1)和 O(n)艇搀。
我們還可以往數(shù)組里插入新數(shù)據(jù)時(shí)讓數(shù)組保持排序，這是由于可能要移動(dòng) O(n)個(gè)數(shù)求晶，因此需要 O(n)時(shí)間才能完成插入操作焰雕。在已經(jīng)排好序的數(shù)組中找出中位數(shù)是一個(gè)簡(jiǎn)單的操作，只需要 O(1)時(shí)間即可完成芳杏。
排序的鏈表時(shí)另外一個(gè)選擇矩屁。我們需要 O(n)時(shí)間才能在鏈表中找到合適的位置插入新的數(shù)據(jù)。如果定義兩個(gè)指針指向鏈表的中間結(jié)點(diǎn)（如果鏈表的結(jié)點(diǎn)數(shù)目是奇數(shù)爵赵，那么這兩個(gè)指針指向同一個(gè)結(jié)點(diǎn)）吝秕，那么可以在 O（1）時(shí)間得出中位數(shù)。此時(shí)時(shí)間效率與及基于排序的數(shù)組的時(shí)間效率一樣亚再。
如果能夠保證數(shù)據(jù)容器左邊的數(shù)據(jù)都小于右邊的數(shù)據(jù)郭膛，這樣即使左、右兩邊內(nèi)部的數(shù)據(jù)沒有排序氛悬，也可以根據(jù)左邊最大的數(shù)及右邊最小的數(shù)得到中位數(shù)则剃。如何快速從一個(gè)容器中找出最大數(shù)？用最大堆實(shí)現(xiàn)這個(gè)數(shù)據(jù)容器如捅，因?yàn)槲挥诙秧數(shù)木褪亲畲蟮臄?shù)據(jù)棍现。同樣，也可以快速從最小堆中找出最小數(shù)镜遣。
因此可以用如下思路來解決這個(gè)問題：用一個(gè)最大堆實(shí)現(xiàn)左邊的數(shù)據(jù)容器己肮，用最小堆實(shí)現(xiàn)右邊的數(shù)據(jù)容器。往堆中插入一個(gè)數(shù)據(jù)的時(shí)間效率是 O(logn)悲关。由于只需 O(1)時(shí)間就可以得到位于堆頂?shù)臄?shù)據(jù)谎僻，因此得到中位數(shù)的時(shí)間效率是 O(1)。
● 你知道哪些排序算法寓辱，這些算法的時(shí)間復(fù)雜度分別是多少艘绍，解釋一下快排？
考察點(diǎn)：快排
參考回答：
快排：快速排序有兩個(gè)方向，左邊的i下標(biāo)一直往右走（當(dāng)條件a[i] <= a[center_index]時(shí)）娶耍，其中center_index是中樞元素的數(shù)組下標(biāo)桐臊，一般取為數(shù)組第0個(gè)元素鸳址。
而右邊的j下標(biāo)一直往左走（當(dāng)a[j] > a[center_index]時(shí)）汗贫。
如果i和j都走不動(dòng)了莺匠，i <= j, 交換a[i]和a[j],重復(fù)上面的過程万牺，直到i>j关顷。交換a[j]和a[center_index]阳掐，完成一趟快速排序始衅。
</article>
public class
OddIncreaseEvenDecrease {
/**
* 按照奇偶位拆分成兩個(gè)鏈表
* @param head
* @return
*/
public static Node[] getLists(Node head){
Node head1 = null``;
Node head2 = null``;
Node cur1 = null``;
Node cur2 = null``;
int count = 1``;``//用來計(jì)數(shù)
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++;
}
//跳出循環(huán)，要讓最后兩個(gè)末尾元素的下一個(gè)都指向null
cur1.next = null``;
cur2.next = null``;
Node[] nodes = new Node[]{head1,
head2};
return nodes;
}
/**
* 反轉(zhuǎn)鏈表
* @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;
}
/**
* 合并兩個(gè)有序鏈表
* @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會(huì)出現(xiàn)空指針異常
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;
}
}
|
● 隨機(jī)鏈表的復(fù)制
考察點(diǎn)：鏈表
參考回答：
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;
}
|
● 如何反轉(zhuǎn)單鏈表
考察點(diǎn)：鏈表
參考回答：
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 交替處理 進(jìn)行反轉(zhuǎn)單鏈表
p = q;
q = r;
}
head = p;``//最后的q必定指向NULL，p就成了新鏈表的頭指針
return head;
}
● 請(qǐng)你解釋一下涮俄，內(nèi)存中的棧(stack)蛉拙、堆(heap) 和靜態(tài)區(qū)(static area) 的用法。
考察點(diǎn)：堆棧
參考回答：
通常我們定義一個(gè)基本數(shù)據(jù)類型的變量彻亲，一個(gè)對(duì)象的引用孕锄，還有就是函數(shù)調(diào)用的現(xiàn)場(chǎng)保存都使用內(nèi)存中的棧空間苞尝；而通過new關(guān)鍵字和構(gòu)造器創(chuàng)建的對(duì)象放在堆空間畸肆；程序中的字面量（literal）如直接書寫的100、"hello"和常量都是放在靜態(tài)區(qū)中宙址。椫崞辏空間操作起來最快但是棧很小，通常大量的對(duì)象都是放在堆空間抡砂，理論上整個(gè)內(nèi)存沒有被其他進(jìn)程使用的空間甚至硬盤上的虛擬內(nèi)存都可以被當(dāng)成堆空間來使用大咱。
String str = new String("hello");
上面的語句中變量str放在棧上，用new創(chuàng)建出來的字符串對(duì)象放在堆上注益，而"hello"這個(gè)字面量放在靜態(tài)區(qū)碴巾。
● 說一說，heap和stack有什么區(qū)別丑搔。
考察點(diǎn)：堆與棧
參考回答：
棧是一種線形集合厦瓢，其添加和刪除元素的操作應(yīng)在同一段完成。棧按照后進(jìn)先出的方式進(jìn)行處理啤月。
堆是棧的一個(gè)組成元素煮仇。
● 介紹一下，堆與棧的不同是什么谎仲？
考察點(diǎn)：堆欺抗，棧
參考回答：
（1）Java的堆是一個(gè)運(yùn)行時(shí)數(shù)據(jù)區(qū)，類的對(duì)象從中分配空間强重。通過比如：new等指令建立绞呈，不需要代碼顯式的釋放，由垃圾回收來負(fù)責(zé)间景。
優(yōu)點(diǎn)：可以動(dòng)態(tài)地分配內(nèi)存大小佃声，垃圾收集器會(huì)自動(dòng)回收垃圾數(shù)據(jù)。
缺點(diǎn)：由于其優(yōu)點(diǎn)倘要，所以存取速度較慢圾亏。
（2）棧：
其數(shù)據(jù)項(xiàng)的插入和刪除都只能在稱為棧頂?shù)囊欢送瓿桑筮M(jìn)先出封拧。棧中存放一些基本類型的 變量 和 對(duì)象句柄志鹃。
優(yōu)點(diǎn)：讀取數(shù)度比堆要快，僅次于寄存器泽西，棧數(shù)據(jù)可以共享曹铃。
缺點(diǎn)：比堆缺乏靈活性，存在棧中的數(shù)據(jù)大小與生存期必須是確定的捧杉。
舉例：
String是一個(gè)特殊的包裝類數(shù)據(jù)陕见。可以用：
String str = new String("csdn");
String str = "csdn";
兩種的形式來創(chuàng)建味抖，第一種是用new()來新建對(duì)象的评甜，它會(huì)在存放于堆中。每調(diào)用一次就會(huì)創(chuàng)建一個(gè)新的對(duì)象仔涩。而第二種是先在棧中創(chuàng)建一個(gè)對(duì)String類的對(duì)象引用變量str忍坷，然后查找棧中有沒有存放"csdn"，如果沒有熔脂，則將"csdn"存放進(jìn)棧佩研，并令str指向”abc”，如果已經(jīng)有”csdn” 則直接令str指向“csdn”锤悄。
● 什么是Java優(yōu)先級(jí)隊(duì)列(Priority Queue)韧骗？
考察點(diǎn)：隊(duì)列
參考回答：
PriorityQueue是一個(gè)基于優(yōu)先級(jí)堆的無界隊(duì)列，它的元素是按照自然順序(natural order)排序的零聚。在創(chuàng)建的時(shí)候袍暴，我們可以給它提供一個(gè)負(fù)責(zé)給元素排序的比較器。PriorityQueue不允許null值隶症，因?yàn)樗麄儧]有自然順序政模，或者說他們沒有任何的相關(guān)聯(lián)的比較器。最后蚂会，PriorityQueue不是線程安全的淋样，入隊(duì)和出隊(duì)的時(shí)間復(fù)雜度是O(log(n))。
● 請(qǐng)你講講LRU算法的實(shí)現(xiàn)原理胁住？
考察點(diǎn)：LRU算法
參考回答：
①LRU（Least recently used趁猴，最近最少使用）算法根據(jù)數(shù)據(jù)的歷史訪問記錄來進(jìn)行淘汰數(shù)據(jù)刊咳，其核心思想是“如果數(shù)據(jù)最近被訪問過，那么將來被訪問的幾率也很高”儡司，反過來說“如果數(shù)據(jù)最近這段時(shí)間一直都沒有訪問,那么將來被訪問的概率也會(huì)很低”娱挨，兩種理解是一樣的；常用于頁面置換算法捕犬，為虛擬頁式存儲(chǔ)管理服務(wù)跷坝。
②達(dá)到這樣一種情形的算法是最理想的：每次調(diào)換出的頁面是所有內(nèi)存頁面中最遲將被使用的；這可以最大限度的推遲頁面調(diào)換碉碉，這種算法柴钻，被稱為理想頁面置換算法」噶福可惜的是贴届，這種算法是無法實(shí)現(xiàn)的。
為了盡量減少與理想算法的差距足丢，產(chǎn)生了各種精妙的算法粱腻，最近最少使用頁面置換算法便是其中一個(gè)。LRU 算法的提出斩跌，是基于這樣一個(gè)事實(shí)：在前面幾條指令中使用頻繁的頁面很可能在后面的幾條指令中頻繁使用绍些。反過來說，已經(jīng)很久沒有使用的頁面很可能在未來較長(zhǎng)的一段時(shí)間內(nèi)不會(huì)被用到 耀鸦。這個(gè)柬批，就是著名的局部性原理——比內(nèi)存速度還要快的cache，也是基于同樣的原理運(yùn)行的袖订。因此氮帐，我們只需要在每次調(diào)換時(shí)，找到最近最少使用的那個(gè)頁面調(diào)出內(nèi)存洛姑。
算法實(shí)現(xiàn)的關(guān)鍵
命中率：
當(dāng)存在熱點(diǎn)數(shù)據(jù)時(shí)上沐，LRU的效率很好，但偶發(fā)性的楞艾、周期性的批量操作會(huì)導(dǎo)致 LRU 命中率急劇下降参咙，緩存污染情況比較嚴(yán)重。
復(fù)雜度：
實(shí)現(xiàn)起來較為簡(jiǎn)單硫眯。
存儲(chǔ)成本：
幾乎沒有空間上浪費(fèi)蕴侧。
代價(jià)：
命中時(shí)需要遍歷鏈表，找到命中的數(shù)據(jù)塊索引两入，然后需要將數(shù)據(jù)移到頭部净宵。
● 為什么要設(shè)計(jì) 后綴表達(dá)式，有什么好處？
考察點(diǎn)：逆波蘭表達(dá)式
參考回答：
后綴表達(dá)式又叫逆波蘭表達(dá)式择葡，逆波蘭記法不需要括號(hào)來標(biāo)識(shí)操作符的優(yōu)先級(jí)紧武。
● 請(qǐng)你設(shè)計(jì)一個(gè)算法，用來壓縮一段URL刁岸？
考察點(diǎn)：MD5加密算法
參考回答：
該算法主要使用MD5 算法對(duì)原始鏈接進(jìn)行加密（這里使用的MD5 加密后的字符串長(zhǎng)度為32 位）脏里，然后對(duì)加密后的字符串進(jìn)行處理以得到短鏈接的地址。
● 談一談虹曙，id全局唯一且自增，如何實(shí)現(xiàn)番舆？
考察點(diǎn)：SnowFlake雪花算法
參考回答酝碳；
SnowFlake雪花算法
雪花ID生成的是一個(gè)64位的二進(jìn)制正整數(shù)，然后轉(zhuǎn)換成10進(jìn)制的數(shù)恨狈。64位二進(jìn)制數(shù)由如下部分組成：
snowflake id生成規(guī)則
1位標(biāo)識(shí)符：始終是0疏哗，由于long基本類型在Java中是帶符號(hào)的，最高位是符號(hào)位禾怠，正數(shù)是0返奉，負(fù)數(shù)是1，所以id一般是正數(shù)吗氏，最高位是0芽偏。
41位時(shí)間戳：41位時(shí)間截不是存儲(chǔ)當(dāng)前時(shí)間的時(shí)間截，而是存儲(chǔ)時(shí)間截的差值（當(dāng)前時(shí)間截 - 開始時(shí)間截 )得到的值弦讽，這里的的開始時(shí)間截污尉，一般是我們的id生成器開始使用的時(shí)間，由我們程序來指定的往产。
10位機(jī)器標(biāo)識(shí)碼：可以部署在1024個(gè)節(jié)點(diǎn)被碗，如果機(jī)器分機(jī)房（IDC）部署，這10位可以由 5位機(jī)房ID + 5位機(jī)器ID 組成仿村。
12位序列：毫秒內(nèi)的計(jì)數(shù)锐朴，12位的計(jì)數(shù)順序號(hào)支持每個(gè)節(jié)點(diǎn)每毫秒(同一機(jī)器，同一時(shí)間截)產(chǎn)生4096個(gè)ID序號(hào)
優(yōu)點(diǎn)
簡(jiǎn)單高效蔼囊，生成速度快焚志。
時(shí)間戳在高位，自增序列在低位压真，整個(gè)ID是趨勢(shì)遞增的娩嚼，按照時(shí)間有序遞增。
靈活度高滴肿，可以根據(jù)業(yè)務(wù)需求岳悟，調(diào)整bit位的劃分，滿足不同的需求。
缺點(diǎn)
依賴機(jī)器的時(shí)鐘贵少，如果服務(wù)器時(shí)鐘回?fù)芎乔危瑫?huì)導(dǎo)致重復(fù)ID生成。
在分布式環(huán)境上滔灶，每個(gè)服務(wù)器的時(shí)鐘不可能完全同步普碎，有時(shí)會(huì)出現(xiàn)不是全局遞增的情況
0.如果遇到相等的值不進(jìn)行交換，那這種排序方式是穩(wěn)定的排序方式录平。
1.原理：比較兩個(gè)相鄰的元素麻车，將值大的元素交換到右邊
2.思路：依次比較相鄰的兩個(gè)數(shù)，將比較小的數(shù)放在前面斗这，比較大的數(shù)放在后面动猬。
(1)第一次比較：首先比較第一和第二個(gè)數(shù)，將小數(shù)放在前面表箭，將大數(shù)放在后面赁咙。
(2)比較第2和第3個(gè)數(shù)，將小數(shù) 放在前面免钻，大數(shù)放在后面彼水。
......
(3)如此繼續(xù)，知道比較到最后的兩個(gè)數(shù)极舔，將小數(shù)放在前面凤覆，大數(shù)放在后面，重復(fù)步驟姆怪，直至全部排序完成
(4)在上面一趟比較完成后叛赚，最后一個(gè)數(shù)一定是數(shù)組中最大的一個(gè)數(shù)，所以在比較第二趟的時(shí)候稽揭，最后一個(gè)數(shù)是不參加比較的俺附。
(5)在第二趟比較完成后，倒數(shù)第二個(gè)數(shù)也一定是數(shù)組中倒數(shù)第二大數(shù)溪掀，所以在第三趟的比較中事镣，最后兩個(gè)數(shù)是不參與比較的。
(6)依次類推揪胃，每一趟比較次數(shù)減少依次
3.舉例：
(1)要排序數(shù)組:[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]
第一趟總共進(jìn)行了六次比較户矢，排序結(jié)果：[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
第二趟總共進(jìn)行了5次比較荠藤，排序結(jié)果：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
第三趟總共進(jìn)行了4次比較币狠，排序結(jié)果：1,10,35,36,55,61,89
到目前位置已經(jīng)為有序的情形了游两。
4.算法分析：
(1)由此可見：N個(gè)數(shù)字要排序完成，總共進(jìn)行N-1趟排序漩绵，每i趟的排序次數(shù)為(N-i)次贱案，所以可以用雙重循環(huán)語句，外層控制循環(huán)多少趟止吐，內(nèi)層控制每一趟的循環(huán)次數(shù)
(2)冒泡排序的優(yōu)點(diǎn)：每進(jìn)行一趟排序宝踪，就會(huì)少比較一次，因?yàn)槊窟M(jìn)行一趟排序都會(huì)找出一個(gè)較大值碍扔。如上例：第一趟比較之后瘩燥，排在最后的一個(gè)數(shù)一定是最大的一個(gè)數(shù)，第二趟排序的時(shí)候不同，只需要比較除了最后一個(gè)數(shù)以外的其他的數(shù)厉膀，同樣也能找出一個(gè)最大的數(shù)排在參與第二趟比較的數(shù)后面，第三趟比較的時(shí)候，只需要比較除了最后兩個(gè)數(shù)以外的其他的數(shù)站蝠，以此類推……也就是說汰具，沒進(jìn)行一趟比較，每一趟少比較一次菱魔，一定程度上減少了算法的量留荔。
(3)時(shí)間復(fù)雜度
1.如果我們的數(shù)據(jù)正序，只需要走一趟即可完成排序澜倦。所需的比較次數(shù)C和記錄移動(dòng)次數(shù)M均達(dá)到最小值聚蝶，即：Cmin=n-1;Mmin=0;所以，冒泡排序最好的時(shí)間復(fù)雜度為O(n)藻治。
2.如果很不幸我們的數(shù)據(jù)是反序的碘勉，則需要進(jìn)行n-1趟排序。每趟排序要進(jìn)行n-i次比較(1≤i≤n-1)桩卵，且每次比較都必須移動(dòng)記錄三次來達(dá)到交換記錄位置雏节。在這種情況下涝涤，比較和移動(dòng)次數(shù)均達(dá)到最大值：
綜上所述：冒泡排序總的平均時(shí)間復(fù)雜度為：O(n2) ,時(shí)間復(fù)雜度和數(shù)據(jù)狀況無關(guān)罪针。
5.java代碼實(shí)現(xiàn)拓轻，代碼的實(shí)現(xiàn)用到了對(duì)數(shù)發(fā)生器
[
](javascript:void(0); "復(fù)制代碼")
<pre>import java.util.Arrays;
//算法的最終時(shí)間復(fù)雜度為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);
}
//產(chǎn)生一個(gè)隨機(jī)數(shù)組，數(shù)組的長(zhǎng)度和值都是隨機(jī)的，
public static int[] generateRandomArray(int size,int value){
//在java中魄藕，Math.random() ->double(0,1)
//(int)((size+1)Math.random())--->產(chǎn)生的是[0,size]之間的整數(shù)
//生成長(zhǎng)度隨機(jī)的數(shù)組，數(shù)組的最大長(zhǎng)度是size的長(zhǎng)度
int[] arr = new int[(int)((size+1)Math.random())];
for(int i = 0 ;i<arr.length;i++){
//針對(duì)數(shù)組中的每個(gè)值都可以隨機(jī)一下，一個(gè)隨機(jī)數(shù)減去另外一個(gè)隨機(jī)數(shù)玄帕，可能產(chǎn)生正數(shù)部脚，也可能產(chǎn)生負(fù)數(shù)
arr[i]=(int)((value+1)Math.random())-(int)(valueMath.random());//值也可以是隨機(jī)的
}
return arr;
}
//復(fù)制數(shù)組
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;
}
//絕對(duì)正確的方法,這個(gè)方法可以時(shí)間復(fù)雜度很差，但是要保證其準(zhǔn)確性
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;
}
//打印出數(shù)組
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個(gè)數(shù)字冒泡排序裤纹，總共要進(jìn)行N-1趟比較委刘，每趟的排序次數(shù)為(N-i)次比較
public static void bubbleSort(int[] arr){
//一定要記住判斷邊界條件，很多人不注意這些細(xì)節(jié)服傍，面試官看到你的代碼的時(shí)候都懶得往下看钱雷，你的代碼哪個(gè)項(xiàng)目敢往里面加？
if(arr==null||arr.length<2){
return;
}
//需要進(jìn)行arr.length趟比較
for(int i = 0 ;i<arr.length-1;i++){
//第i趟比較
for(int j = 0 ;j<arr.length-i-1;j++){
//開始進(jìn)行比較吹零，如果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("最終得出的數(shù)組為：");
// for (int k =0 ; k < arr.length;k++){
// System.out.print(arr[k]+" ");
// }
}
//生成一個(gè)對(duì)數(shù)器。產(chǎn)生一個(gè)隨機(jī)樣本的數(shù)組灿椅，數(shù)組的長(zhǎng)度和值都是隨機(jī)的
//size是生成數(shù)組的最大長(zhǎng)度
// public static int[] generateRandomArray(int size,int value){
// //生成長(zhǎng)度隨機(jī)的數(shù)組
// 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){
//調(diào)用系統(tǒng)調(diào)用的函數(shù)來進(jìn)行驗(yàn)證
Arrays.sort(arr);
}
}</pre>
<article class="post-topic-des entry-content nc-post-content js-nc-pop-image" itemprop="text">
● 介紹一下 如何實(shí)現(xiàn)動(dòng)態(tài)代理套蒂？
考察點(diǎn)：動(dòng)態(tài)代理流程
參考回答：
Java實(shí)現(xiàn)動(dòng)態(tài)代理的大致步驟如下：
1.定義一個(gè)委托類和公共接口。
2.自己定義一個(gè)類（調(diào)用處理器類茫蛹，即實(shí)現(xiàn) InvocationHandler 接口）操刀，這個(gè)類的目的是指定運(yùn)行時(shí)將生成的代理類需要完成的具體任務(wù)（包括Preprocess和Postprocess），即代理類調(diào)用任何方法都會(huì)經(jīng)過這個(gè)調(diào)用處理器類（在本文最后一節(jié)對(duì)此進(jìn)行解釋）婴洼。
3.生成代理對(duì)象（當(dāng)然也會(huì)生成代理類）骨坑，需要為他指定(1)委托對(duì)象(2)實(shí)現(xiàn)的一系列接口(3)調(diào)用處理器類的實(shí)例。因此可以看出一個(gè)代理對(duì)象對(duì)應(yīng)一個(gè)委托對(duì)象柬采，對(duì)應(yīng)一個(gè)調(diào)用處理器實(shí)例欢唾。
4.Java 實(shí)現(xiàn)動(dòng)態(tài)代理主要涉及以下幾個(gè)類：
①java.lang.reflect.Proxy: 這是生成代理類的主類，通過 Proxy 類生成的代理類都繼承了 Proxy 類粉捻，即 DynamicProxyClass extends Proxy礁遣。
②java.lang.reflect.InvocationHandler: 這里稱他為"調(diào)用處理器"，他是一個(gè)接口肩刃，我們動(dòng)態(tài)生成的代理類需要完成的具體內(nèi)容需要自己定義一個(gè)類祟霍，而這個(gè)類必須實(shí)現(xiàn) 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``}); //創(chuàng)建method對(duì)象
return (Integer)h.invoke(``this``, method, new Object[]{``new Integer(i)}); //調(diào)用了invoke方法 } }
|
● 談一談盈包，java中有哪些代理模式沸呐？
考察點(diǎn)：代理模式
參考回答：
靜態(tài)代理，動(dòng)態(tài)代理续语，Cglib代理垂谢。
● Java IO都有哪些設(shè)計(jì)模式，簡(jiǎn)單介紹一下疮茄。
考察點(diǎn)：裝飾模式滥朱，適配器模式
參考回答：
裝飾模式和適配器模式
</article>
● 請(qǐng)你介紹一下單例模式根暑？再說一說 懶漢式的單例模式如何實(shí)現(xiàn)單例？
考察點(diǎn)：?jiǎn)卫Ｊ?br> 參考回答：
定義：保證一個(gè)類僅有一個(gè)實(shí)例徙邻，并提供一個(gè)訪問它的全局訪問點(diǎn)排嫌。優(yōu)點(diǎn)：?jiǎn)卫愔挥幸粋€(gè)實(shí)例、共享資源缰犁，全局使用節(jié)省創(chuàng)建時(shí)間淳地，提高性能∷荩可以用靜態(tài)內(nèi)部實(shí)現(xiàn)颇象，保證是懶加載就行了，就是使用才會(huì)創(chuàng)建實(shí)例對(duì)象并徘。
<article class="post-topic-des entry-content nc-post-content js-nc-pop-image" itemprop="text">
● 請(qǐng)你介紹一下策略模式遣钳？
考察點(diǎn)：策略模式
參考回答：
策略模式也叫政策模式，是一種行為型設(shè)計(jì)模式麦乞，是一種比較簡(jiǎn)單的設(shè)計(jì)模式蕴茴。策略模式采用了面向?qū)ο蟮睦^承和多態(tài)機(jī)制。略模式適合使用在：1.多個(gè)類只有在算法或行為上稍有不同的場(chǎng)景姐直。2.算法需要自由切換的場(chǎng)景倦淀。3.需要屏蔽算法規(guī)則的場(chǎng)景。 使用策略模式當(dāng)然也有需要注意的地方声畏，那么就是策略類不要太多撞叽，如果一個(gè)策略家族的具體策略數(shù)量超過4個(gè)，則需要考慮混合模式插龄，解決策略類膨脹和對(duì)外暴露問題能扒。在實(shí)際項(xiàng)目中，我們一般通過工廠方法模式來實(shí)現(xiàn)策略類的聲明辫狼。
優(yōu)點(diǎn)：算法可以自由切換。2.避免使用多重條件判斷辛润。3.擴(kuò)展性良好膨处。
● 對(duì)于設(shè)計(jì)模式，你了解哪些砂竖？請(qǐng)手寫一下觀察者模式真椿。
考察點(diǎn)：觀察者模式
參考回答：
觀察者模式優(yōu)點(diǎn)：
觀察者模式在被觀察者和觀察者之間建立一個(gè)抽象的耦合。被觀察者角色所知道的只是一個(gè)具體觀察者列表乎澄，每一個(gè)具體觀察者都符合一個(gè)抽象觀察者的接口突硝。被觀察者并不認(rèn)識(shí)任何一個(gè)具體觀察者，它只知道它們都有一個(gè)共同的接口置济。由于被觀察者和觀察者沒有緊密地耦合在一起解恰，因此它們可以屬于不同的抽象化層次锋八。如果被觀察者和觀察者都被扔到一起，那么這個(gè)對(duì)象必然跨越抽象化和具體化層次护盈。
觀察者模式缺點(diǎn)：
如果一個(gè)被觀察者對(duì)象有很多的直接和間接的觀察者的話挟纱，將所有的觀察者都通知到會(huì)花費(fèi)很多時(shí)間。
如果在被觀察者之間有循環(huán)依賴的話腐宋，被觀察者會(huì)觸發(fā)它們之間進(jìn)行循環(huán)調(diào)用紊服，導(dǎo)致系統(tǒng)崩潰。在使用觀察者模式是要特別注意這一點(diǎn)胸竞。
如果對(duì)觀察者的通知是通過另外的線程進(jìn)行異步投遞的話欺嗤，系統(tǒng)必須保證投遞是以自恰的方式進(jìn)行的。
雖然觀察者模式可以隨時(shí)使觀察者知道所觀察的對(duì)象發(fā)生了變化卫枝，但是觀察者模式?jīng)]有相應(yīng)的機(jī)制使觀察者知道所觀察的對(duì)象是怎么發(fā)生變化的煎饼。
</article>
● 談一談，你了解的 Java設(shè)計(jì)模式剃盾。
考察點(diǎn)：設(shè)計(jì)模式
參考回答：
所謂設(shè)計(jì)模式腺占，就是一套被反復(fù)使用的代碼設(shè)計(jì)經(jīng)驗(yàn)的總結(jié)（情境中一個(gè)問題經(jīng)過證實(shí)的一個(gè)解決方案）。使用設(shè)計(jì)模式是為了可重用代碼痒谴、讓代碼更容易被他人理解衰伯、保證代碼可靠性。設(shè)計(jì)模式使人們可以更加簡(jiǎn)單方便的復(fù)用成功的設(shè)計(jì)和體系結(jié)構(gòu)积蔚。將已證實(shí)的技術(shù)表述成設(shè)計(jì)模式也會(huì)使新系統(tǒng)開發(fā)者更加容易理解其設(shè)計(jì)思路媳危。
在GoF的《Design Patterns: Elements of Reusable Object-Oriented Software》中給出了三類（創(chuàng)建型[對(duì)類的實(shí)例化過程的抽象化]、結(jié)構(gòu)型[描述如何將類或?qū)ο蠼Y(jié)合在一起形成更大的結(jié)構(gòu)]羊异、行為型[對(duì)在不同的對(duì)象之間劃分責(zé)任和算法的抽象化]）共23種設(shè)計(jì)模式螟够，包括：Abstract Factory（抽象工廠模式），Builder（建造者模式）漱贱，F(xiàn)actory Method（工廠方法模式）槐雾，Prototype（原始模型模式），Singleton（單例模式）幅狮；Facade（門面模式）募强，Adapter（適配器模式），Bridge（橋梁模式）崇摄，Composite（合成模式）擎值，Decorator（裝飾模式），F(xiàn)lyweight（享元模式）逐抑，Proxy（代理模式）鸠儿；Command（命令模式），Interpreter（解釋器模式）厕氨，Visitor（訪問者模式）进每，Iterator（迭代子模式）汹粤，Mediator（調(diào)停者模式），Memento（備忘錄模式）品追，Observer（觀察者模式）玄括，State（狀態(tài)模式），Strategy（策略模式）肉瓦，Template Method（模板方法模式）遭京， Chain Of Responsibility（責(zé)任鏈模式）。
● 談一談泞莉，開發(fā)中都用到了 哪些設(shè)計(jì)模式? 用在什么場(chǎng)合?
考察點(diǎn)：設(shè)計(jì)模式
參考回答：
每個(gè)模式都描述了一個(gè)在我們的環(huán)境中不斷出現(xiàn)的問題哪雕，然后描述了該問題的解決方案的核心。通過這種方式鲫趁，你可以無數(shù)次地使用那些已有的解決方案斯嚎，無需在重復(fù)相同的工作。主要用到了MVC的設(shè)計(jì)模式挨厚。用來開發(fā)JSP/Servlet或者J2EE的相關(guān)應(yīng)用堡僻。簡(jiǎn)單工廠模式等。
● 談一談 J2EE 的常用 設(shè)計(jì)模式有哪些疫剃？再詳細(xì)說說工廠模式钉疫。
考察點(diǎn)：j2ee設(shè)計(jì)模式
參考回答：
Java中的23種設(shè)計(jì)模式：
Factory（工廠模式）， Builder（建造模式）巢价， Factory Method（工廠方法模式）牲阁，Prototype（原始模型模式），Singleton（單例模式）壤躲， Facade（門面模式）城菊，Adapter（適配器模式）， Bridge（橋梁模式）碉克， Composite（合成模式）凌唬，Decorator（裝飾模式）， Flyweight（享元模式）漏麦， Proxy（代理模式）法瑟，Command（命令模式）， Interpreter（解釋器模式）唁奢， Visitor（訪問者模式），Iterator（迭代子模式）窝剖， Mediator（調(diào)停者模式）麻掸， Memento（備忘錄模式），Observer（觀察者模式）赐纱， State（狀態(tài)模式）脊奋， Strategy（策略模式）熬北，Template Method（模板方法模式）， Chain Of Responsibleity（責(zé)任鏈模式）工廠模式：工廠模式是一種經(jīng)常被使用到的模式诚隙，根據(jù)工廠模式實(shí)現(xiàn)的類可以根據(jù)提供的數(shù)據(jù)生成一組類中某一個(gè)類的實(shí)例讶隐，通常這一組類有一個(gè)公共的抽象父類并且實(shí)現(xiàn)了相同的方法，但是這些方法針對(duì)不同的數(shù)據(jù)進(jìn)行了不同的操作久又。首先需要定義一個(gè)基類巫延，該類的子類通過不同的方法實(shí)現(xiàn)了基類中的方法。然后需要定義一個(gè)工廠類地消，工廠類可以根據(jù)條件生成不同的子類實(shí)例炉峰。當(dāng)?shù)玫阶宇惖膶?shí)例后，開發(fā)人員可以調(diào)用基類中的方法而不必考慮到底返回的是哪一個(gè)子類的實(shí)例脉执。
● 說說你所熟悉 或聽說過的疼阔，J2EE中的幾種常用模式。再講講你對(duì)設(shè)計(jì)模式的一些看法
考察點(diǎn)：J2EE設(shè)計(jì)模式
參考回答：
Session Facade Pattern：使用SessionBean訪問EntityBean Message Facade Pattern：實(shí)現(xiàn)異步調(diào)用EJB Command Pattern：使用Command JavaBeans取代SessionBean半夷，實(shí)現(xiàn)輕量級(jí)訪問Data Transfer Object Factory：通過DTO Factory簡(jiǎn)化EntityBean數(shù)據(jù)提供特性Generic Attribute Access：通過AttibuteAccess接口簡(jiǎn)化EntityBean數(shù)據(jù)提供特性Business Interface：通過遠(yuǎn)程（本地）接口和Bean類實(shí)現(xiàn)相同接口規(guī)范業(yè)務(wù)邏輯一致性ＥＪＢ架構(gòu)的設(shè)計(jì)好壞將直接影響系統(tǒng)的性能婆廊、可擴(kuò)展性、可維護(hù)性巫橄、組件可重用性及開發(fā)效率淘邻。項(xiàng)目越復(fù)雜，項(xiàng)目隊(duì)伍越龐大則越能體現(xiàn)良好設(shè)計(jì)的重要性嗦随。
● 請(qǐng)你講講UML中有哪些常用的圖列荔？
考察點(diǎn)：用例圖
參考回答：
UML定義了多種圖形化的符號(hào)來描述軟件系統(tǒng)部分或全部的靜態(tài)結(jié)構(gòu)和動(dòng)態(tài)結(jié)構(gòu)，包括：用例圖（use case diagram）枚尼、類圖（class diagram）贴浙、時(shí)序圖（sequence diagram）、協(xié)作圖（collaboration diagram）署恍、狀態(tài)圖（statechart diagram）崎溃、活動(dòng)圖（activity diagram）、構(gòu)件圖（component diagram）盯质、部署圖（deployment diagram）等袁串。在這些圖形化符號(hào)中，有三種圖最為重要呼巷，分別是：用例圖（用來捕獲需求囱修，描述系統(tǒng)的功能，通過該圖可以迅速的了解系統(tǒng)的功能模塊及其關(guān)系）王悍、類圖（描述類以及類與類之間的關(guān)系破镰，通過該圖可以快速了解系統(tǒng)）、時(shí)序圖（描述執(zhí)行特定任務(wù)時(shí)對(duì)象之間的交互關(guān)系以及執(zhí)行順序，通過該圖可以了解對(duì)象能接收的消息也就是說對(duì)象能夠向外界提供的服務(wù)）鲜漩。
