一即硼、數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)
1.說一下幾種常見的排序算法和分別的復(fù)雜度。
冒泡排序
核心思想：遍歷數(shù)組N次屡拨，每次將最大的數(shù)字交換到最后只酥。
時間復(fù)雜度：O(N2)
空間復(fù)雜度：O(1)快速排序
核心思想：選擇一個基準數(shù)，比它小的數(shù)放左邊呀狼，比它大的數(shù)放右邊裂允，依次遞歸。
時間復(fù)雜度：最壞情況 O(N2)赠潦，平均 O(N*lgN)
空間復(fù)雜度：主要來源于遞歸棧叫胖，因此最多O(N) 最少 O(lgN)插入排序
核心思想：打撲克牌時摸牌階段的排序。
時間復(fù)雜度：O(N2)
空間復(fù)雜度：O(1)選擇排序
核心思想：從沒有排序的數(shù)列中找到最小的放在最前面她奥，不停重復(fù)瓮增。（和冒泡類似）
時間復(fù)雜度：O(N2)
空間復(fù)雜度：O(1)堆排序
核心思想：利用“最大堆”（最小堆類似）每次找出最大的值，從而形成有序數(shù)組哩俭。
時間復(fù)雜度：O(N*lgN)
空間復(fù)雜度：O(1)歸并排序
核心思想：將兩個有序數(shù)組合并成一個數(shù)組绷跑，利用遞歸，從兩個單個元素開始一直到一整個數(shù)組凡资。
時間復(fù)雜度：O(N*lgN)
空間復(fù)雜度：O(N)砸捏，在合并數(shù)組時需要借助新的空間。
2.用Java寫一個冒泡排序算法
public static void bubble(int[] arr) {
for (int i = arr.length - 1; i >= 0; i--) {
for (int j = 0; j < i; j++) {
if (arr[j] > arr[i]) {
int temp = arr[j];
arr[j] = arr[i];
arr[i] = temp;
}
}
}
}
3.描述一下鏈式存儲結(jié)構(gòu)隙赁。
常見的鏈式存儲結(jié)構(gòu)有單向鏈表和雙向鏈表垦藏。鏈表的結(jié)構(gòu)特點就是有一個值字段，同時有指向下一個結(jié)點或者上一個結(jié)點的字段伞访。java中定義如下：
//單向鏈表
public class ListNode {
int val;
ListNode next;
}
//雙向鏈表
public class ListNode {
int val;
ListNode pre;
ListNode next;
}
4.如何遍歷一棵二叉樹掂骏？
二叉樹的遍歷有前序遍歷，中序遍歷和后續(xù)遍歷厚掷〉茏疲可以使用遞歸來完成，亦可使用循環(huán)的方式完成冒黑。
5.倒排一個LinkedList田绑。
- 方法1：如果利用一個棧來存放，那么依次入棧抡爹，再依次出棧即可立即完成倒排掩驱。
- 方法2：從左往右依次倒排，進行到
i的位置時冬竟，i前面的是倒排的昙篙，i后面還是順排的。
6.用Java寫一個遞歸遍歷目錄下面的所有文件诱咏。
//遍歷一個目錄下所有的文件
public static void ScanFiles(File file) {
if (file == null || !file.exists()) {
return;
}
if (!file.isDirectory()) {
System.out.println(file.getName());
} else {
File[] files = file.listFiles();
if (files != null) {
for (File f : files) {
ScanFiles(f);
}
}
}
}
目錄列表
一苔可、數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)
二、Java基礎(chǔ)
三袋狞、JVM
四焚辅、多線程/并發(fā)
五、Linux使用與問題分析排查
六苟鸯、框架使用
七同蜻、數(shù)據(jù)庫相關(guān)
八、網(wǎng)絡(luò)協(xié)議和網(wǎng)絡(luò)編程
九早处、Redis等緩存系統(tǒng)/中間件/NoSQL/一致性Hash等
十湾蔓、設(shè)計模式與重構(gòu)
本文是針對知乎文章《成為Java頂尖程序員，先過了下面問題》的解答
