mysql 无论输入什么都是现实 not found_Java高频面试题及答案
2.1 冒泡排序(Bubble Sort)
算法描述：(從小到大排序)
● 比較相鄰的元素。如果第一個比第二個大，就交換它們兩個；
● 對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最后一對，這樣在最后的元素應該會是最大的數；
● 針對所有的元素重復以上的步驟，除了最后一個；
● 重復步驟1~3，直到排序完成。
如果兩個元素相等，不會再交換位置，所以冒泡排序是一種穩定排序算法。
代碼實現：
package atguigu.interview.chapter02;
/**
* @author : atguigu.com
* @since 2019/7/22
* 冒泡排序
*/
public class BubbleSort {
/**
* @param data 被排序的數組
*/
public static void bubbleSort(int[] data) {
int arrayLength = data.length;
for (int i = 1; i < arrayLength; i++) {//第i次排序
for (int j = 0; j < arrayLength - i; j++) {//從索引為j的數開始
if (data[j] > data[j + 1]) { //相鄰元素兩兩對比
int temp = data[j + 1]; // 元素交換
data[j + 1] = data[j];
data[j] = temp;
}
}
System.out.println("第" + i + "次排序：\n" + java.util.Arrays.toString(data));
}
}
public static void main(String[] args) {
int[] data = { 3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
System.out.println("排序之前：\n" + java.util.Arrays.toString(data));
bubbleSort(data);
System.out.println("排序之后：\n" + java.util.Arrays.toString(data));
}
}
2.2 快速排序(Quick Sort)
算法描述：(從小到大排序)
使用分治法來把一個串(list)分為兩個子串(sub-lists)。具體算法描述如下：
● 從數列中挑出一個元素，稱為 “基準”(pivot)；
● 重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的后面(相同的數可以到任一邊)。在這個分區退出之后，該基準就處于數列的中間位置。這個稱為分區(partition)操作；
● 遞歸地(recursive)把小于基準值元素的子數列和大于基準值元素的子數列排序。
key值的選取可以有多種形式，例如中間數或者隨機數，分別會對算法的復雜度產生不同的影響。
代碼實現：
package com.atguigu.interview.chapter02;
/**
* @author : atguigu.com
* @since 2019/7/22
* 快速排序
*/
public class QuickSort {
public static void quickSort(int[] data, int low, int high) {
int i, j, temp, t;
if (low > high) {
return;
}
i = low;
j = high;
//temp就是基準位
temp = data[low];
System.out.println("基準位：" + temp);
while (i < j) {
//先看右邊，依次往左遞減
while (temp <= data[j] && i < j) {
j--;
}
//再看左邊，依次往右遞增
while (temp >= data[i] && i < j) {
i++;
}
//如果滿足條件則交換
if (i < j) {
System.out.println("交換：" + data[i] + "和" + data[j]);
t = data[j];
data[j] = data[i];
data[i] = t;
System.out.println(java.util.Arrays.toString(data));
}
}
//最后將基準位與i和j相等位置的數字交換
System.out.println("基準位" + temp + "和i、j相遇的位置" + data[i] + "交換");
data[low] = data[i];
data[i] = temp;
System.out.println(java.util.Arrays.toString(data));
//遞歸調用左半數組
quickSort(data, low, j - 1);
//遞歸調用右半數組
quickSort(data, j + 1, high);
}
public static void main(String[] args) {
int[] data = { 3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
System.out.println("排序之前：\n" + java.util.Arrays.toString(data));
quickSort(data, 0, data.length - 1);
System.out.println("排序之后：\n" + java.util.Arrays.toString(data));
}
}
2.3 歸并排序(Merge Sort)
算法描述：
● 把長度為n的輸入序列分成兩個長度為n/2的子序列；
● 對這兩個子序列分別采用歸并排序；
● 將兩個排序好的子序列合并成一個最終的排序序列。
(1)歸并排序的流程
(2)合并兩個有序數組的流程
代碼實現：
package com.atguigu.interview.chapter02;
/**
* @author : atguigu.com
* @since 2019/7/22
*/
public class MergeSort {
public static void mergeSort(int[] data) {
sort(data, 0, data.length - 1);
}
public static void sort(int[] arr, int l, int r) {
if (l == r) {
return;
}
int mid = l + ((r - l) >> 1);
sort(arr, l, mid);
sort(arr, mid + 1, r);
merge(arr, l, mid, r);
}
public static void merge(int[] arr, int l, int mid, int r) {
int[] temp = new int[r - l + 1];
int i = 0;
int p1 = l;
int p2 = mid + 1;
// 比較左右兩部分的元素，哪個小，把那個元素填入temp中
while (p1 <= mid && p2 <= r) {
temp[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
}
// 上面的循環退出后，把剩余的元素依次填入到temp中
// 以下兩個while只有一個會執行
while (p1 <= mid) {
temp[i++] = arr[p1++];
}
while (p2 <= r) {
temp[i++] = arr[p2++];
}
// 把最終的排序的結果復制給原數組
for (i = 0; i < temp.length; i++) {
arr[l + i] = temp[i];
}
}
public static void main(String[] args) {
int[] data = { 3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
System.out.println("排序之前：\n" + java.util.Arrays.toString(data));
mergeSort(data);
System.out.println("排序之后：\n" + java.util.Arrays.toString(data));
}
}
2.4 二分查找(Binary Search)
算法描述：
● 二分查找也稱折半查找，它是一種效率較高的查找方法，要求列表中的元素首先要進行有序排列。
● 首先，假設表中元素是按升序排列，將表中間位置記錄的關鍵字與查找關鍵字比較，如果兩者相等，則查找成功；
● 否則利用中間位置記錄將表分成前、后兩個子表，如果中間位置記錄的關鍵字大于查找關鍵字，則進一步查找前一子表，否則進一步查找后一子表。
● 重復以上過程，直到找到滿足條件的記錄，使查找成功，或直到子表不存在為止，此時查找不成功。
代碼實現：
package com.atguigu.interview.chapter02;
/**
* @author : atguigu.com
* @since 2019/7/22
*/
public class BinarySearch {
/**
* 二分查找 時間復雜度O(log2n);空間復雜度O(1)
*
* @param arr 被查找的數組
* @param left
* @param right
* @param findVal
* @return 返回元素的索引
*/
public static int binarySearch(int[] arr, int left, int right, int findVal) {
if (left > right) {//遞歸退出條件，找不到，返回-1
return -1;
}
int midIndex = (left + right) / 2;
if (findVal < arr[midIndex]) {//向左遞歸查找
return binarySearch(arr, left, midIndex, findVal);
} else if (findVal > arr[midIndex]) {//向右遞歸查找
return binarySearch(arr, midIndex, right, findVal);
} else {
return midIndex;
}
}
public static void main(String[] args) {
//注意：需要對已排序的數組進行二分查找
int[] data = {- 49, -30, -16, 9, 21, 21, 23, 30, 30
};
int i = binarySearch(data, 0, data.length, 21);
System.out.println(i);
}
}
拓展需求：
當一個有序數組中，有多個相同的數值時，如何將所有的數值都查找到。
代碼實現：
package com.atguigu.interview.chapter02;
import java.util.ArrayList;
import java.util.List;
/**
* @author : atguigu.com
* @since 2019/7/22
*/
public class BinarySearch2 {
/**
* {1, 8, 10, 89, 1000, 1000, 1234}
* 一個有序數組中，有多個相同的數值，如何將所有的數值都查找到，比如這里的 1000.
* 分析：
* 1. 返回的結果是一個列表 list
* 2. 在找到結果時，向左邊掃描，向右邊掃描 [條件]
* 3. 找到結果后，就加入到ArrayBuffer
*
* @return
*/
public static List binarySearch2(int[] arr, int left, int right, int findVal) {
//找不到條件?
List list = new ArrayList<>();
if (left > right) {//遞歸退出條件，找不到，返回-1
return list;
}
int midIndex = (left + right) / 2;
int midVal = arr[midIndex];
if (findVal < midVal) {//向左遞歸查找
return binarySearch2(arr, left, midIndex - 1, findVal);
} else if (findVal > midVal) { //向右遞歸查找
return binarySearch2(arr, midIndex + 1, right, findVal);
} else {
System.out.println("midIndex=" + midIndex);
//向左邊掃描
int temp = midIndex - 1;
while (true) {
if (temp < 0 || arr[temp] != findVal) {
break;
}
if (arr[temp] == findVal) {
list.add(temp);
}
temp -= 1;
}
//將中間這個索引加入
list.add(midIndex);
//向右邊掃描
temp = midIndex + 1;
while (true) {
if (temp > arr.length - 1 || arr[temp] != findVal) {
break;
}
if (arr[temp] == findVal) {
list.add(temp);
}
temp += 1;
}
return list;
}
}
public static void main(String[] args){
//注意：需要對已排序的數組進行二分查找
int[] data = {1, 8, 10, 89, 1000, 1000, 1234};
List list = binarySearch2(data, 0, data.length, 1000);
System.out.println(list);
}
}
2.5 單例模式(Singleton)
2.5.1單例模式定義
單例模式確保某個類只有一個實例，而且自行實例化并向整個系統提供這個實例。在計算機系統中，線程池、緩存、日志對象、對話框、打印機、顯卡的驅動程序對象常被設計成單例。這些應用都或多或少具有資源管理器的功能。每臺計算機可以有若干個打印機，但只能有一個Printer Spooler，以避免兩個打印作業同時輸出到打印機中。每臺計算機可以有若干通信端口，系統應當集中管理這些通信端口，以避免一個通信端口同時被兩個請求同時調用。總之，選擇單例模式就是為了避免不一致狀態。
2.5.2 單例模式的特點
● 單例類只能有一個實例。
● 單例類必須自己創建自己的唯一實例。
● 單例類必須給所有其他對象提供這一實例。
單例模式保證了全局對象的唯一性，比如系統啟動讀取配置文件就需要單例保證配置的一致性。
2.5.3 單例的四大原則
● 構造器私有化
● 以靜態方法或者枚舉返回實例
● 確保實例只有一個，尤其是多線程環境
● 確保反序列化時不會重新構建對象
2.5.4 實現單例模式的方式
(1)餓漢式(立即加載)：
餓漢式單例在類加載初始化時就創建好一個靜態的對象供外部使用，除非系統重啟，這個對象不會改變，所以本身就是線程安全的。
Singleton通過將構造方法限定為private避免了類在外部被實例化，在同一個虛擬機范圍內，Singleton的唯一實例只能通過getInstance()方法訪問。(事實上，通過Java反射機制是能夠實例化構造方法為private的類的，會使Java單例實現失效)
package com.atguigu.interview.chapter02;
/**
* @author : atguigu.com
* @since 2019/7/22
*
* 餓漢式(立即加載)
*/
public class Singleton1 {
/**
* 私有構造
*/
private Singleton1() {
System.out.println("構造函數Singleton1");
}
/**
* 初始值為實例對象
*/
private static Singleton1 single = new Singleton1();
/**
* 靜態工廠方法
* @return 單例對象
*/
public static Singleton1 getInstance() {
System.out.println("getInstance");
return single;
}
public static void main(String[] args){
System.out.println("初始化");
Singleton1 instance = Singleton1.getInstance();
}
}
懶漢式(延遲加載)：
該示例雖然用延遲加載方式實現了懶漢式單例，但在多線程環境下會產生多個Singleton對象
package com.atguigu.interview.chapter02;
/**
* @author : atguigu.com
* @since 2019/7/22
*
* 懶漢式(延遲加載)
*/
public class Singleton2 {
/**
* 私有構造
*/
private Singleton2() {
System.out.println("構造函數Singleton2");
}
/**
* 初始值為null
*/
private static Singleton2 single = null;
/**
* 靜態工廠方法
* @return 單例對象
*/
public static Singleton2 getInstance() {
if(single == null){
System.out.println("getInstance");
single = new Singleton2();
}
return single;
}
public static void main(String[] args){
System.out.println("初始化");
Singleton2 instance = Singleton2.getInstance();
}
}
同步鎖(解決線程安全問題)：
在方法上加synchronized同步鎖或是用同步代碼塊對類加同步鎖，此種方式雖然解決了多個實例對象問題，但是該方式運行效率卻很低下，下一個線程想要獲取對象，就必須等待上一個線程釋放鎖之后，才可以繼續運行。
package com.atguigu.interview.chapter02;
/**
* @author : atguigu.com
* @since 2019/7/22
*
* 同步鎖(解決線程安全問題)
*/
public class Singleton3 {
/**
* 私有構造
*/
private Singleton3() {}
/**
* 初始值為null
*/
private static Singleton3 single = null;
public static Singleton3 getInstance() {
// 等同于 synchronized public static Singleton3 getInstance()
synchronized(Singleton3.class){
// 注意：里面的判斷是一定要加的，否則出現線程安全問題
if(single == null){
single = new Singleton3();
}
}
return single;
}
}
(4)雙重檢查鎖(提高同步鎖的效率)：
使用雙重檢查鎖進一步做了優化，可以避免整個方法被鎖，只對需要鎖的代碼部分加鎖，可以提高執行效率。
package com.atguigu.interview.chapter02;
/**
* @author : atguigu.com
* @since 2019/7/22
* 雙重檢查鎖(提高同步鎖的效率)
*/
public class Singleton4 {
/**
* 私有構造
*/
private Singleton4() {}
/**
* 初始值為null
*/
private static Singleton4 single = null;
/**
* 雙重檢查鎖
* @return 單例對象
*/
public static Singleton4 getInstance() {
if (single == null) {
synchronized (Singleton4.class) {
if (single == null) {
single = new Singleton4();
}
}
}
return single;
}
}
(5)靜態內部類：
這種方式引入了一個內部靜態類(static class)，靜態內部類只有在調用時才會加載，它保證了Singleton 實例的延遲初始化，又保證了實例的唯一性。它把singleton 的實例化操作放到一個靜態內部類中，在第一次調用getInstance() 方法時，JVM才會去加載InnerObject類，同時初始化singleton 實例，所以能讓getInstance() 方法線程安全。
特點是：即能延遲加載，也能保證線程安全。
靜態內部類雖然保證了單例在多線程并發下的線程安全性，但是在遇到序列化對象時，默認的方式運行得到的結果就是多例的。
package com.atguigu.interview.chapter02;
/**
* @author : atguigu.com
* @since 2019/7/22
*
* 靜態內部類(延遲加載，線程安全)
*/
public class Singleton5 {
/**
* 私有構造
*/
private Singleton5() {}
/**
* 靜態內部類
*/
private static class InnerObject{
private static Singleton5 single = new Singleton5();
}
public static Singleton5 getInstance() {
return InnerObject.single;
}
}
(6)內部枚舉類實現(防止反射攻擊)：
事實上，通過Java反射機制是能夠實例化構造方法為private的類的。這也就是我們現在需要引入的枚舉單例模式。
package com.atguigu.interview.chapter02;
/**
* @author : atguigu.com
* @since 2019/7/22
*/
public class SingletonFactory {
/**
* 內部枚舉類
*/
private enum EnumSingleton{
Singleton;
private Singleton6 singleton;
//枚舉類的構造方法在類加載是被實例化
private EnumSingleton(){
singleton = new Singleton6();
}
public Singleton6 getInstance(){
return singleton;
}
}
public static Singleton6 getInstance() {
return EnumSingleton.Singleton.getInstance();
}
}
class Singleton6 {
public Singleton6(){}
}
上一篇: 1. 面試說明
下一篇: 3. Java SE
總結
以上是生活随笔為你收集整理的mysql 无论输入什么都是现实 not found_Java高频面试题及答案的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： mybatis 中case_mybati
- 下一篇： wcf高并发 mysql_使用nginx