1.冒泡排序
從頭開始羹铅，不斷的比較相鄰的兩個數蚀狰，小的放前邊，大的放后邊职员，一次比較之后麻蹋，最大的數字會出現(xiàn)在數組的尾端；不斷重復這個過程焊切，直到排序完成
細節(jié)問題：外層循環(huán)表示完成排序需要進行的次數扮授，數組長度為n,就需要n-1次，因為每次都會得到一個最大的专肪，那么假如數列長度為10刹勃，那么9次排序之后，有9個最大的數字已經被篩選出來牵祟，那么最后一次不需要再做比較深夯，一定是最小的；內層循環(huán)控制每次排序需要比較的次數诺苹，數組長度為n,則需要比較n-1次咕晋，這是-1的原因;每次比較完成之后，最大的數字已經排在尾端收奔，所以下一次比較會新增一個不需要參與比較的數字掌呜，這就是-i的原因
特點：穩(wěn)定；平均時間復雜度O(n2)坪哄，最壞時間復雜度O(n2)质蕉，最佳時間復雜度O(n),空間復雜度O(1)
public static void bubbleSort(int[] arr) {
int temp;
for (int i = 0; i < arr.length - 1; i++) {
for (int j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
2.選擇排序
冒泡排序第一次排序完成之后，會得到最大的數字翩肌，而選擇排序是第一次排序之后模暗，得到最小的數字。顧名思義念祭，選擇排序就是從未排序的序列中選擇出最卸矣睢（或最大，這里以從小到大排序為例說明）的數字放在數組的首位粱坤，不斷的重復這個過程隶糕，直到排序完成,既然是選擇最小的數字，那么一定有一個記錄本次比較最小值的操作
細節(jié)問題：外層循環(huán)同樣是控制需要進行的次數站玄，長度為n,需要進行n-1次枚驻；內層循環(huán)控制每次需要比較的次數，選擇排序每進行一層比較株旷，就會得到一個最小的數字再登，放在最左邊达箍，那么這個得到的最小的數字就不需要再參與比較矮男，所以j=i+1,內層循環(huán)每循環(huán)一次抹沪，就能得到這個數列中最小的元素的index拴袭，如果它比本次比較的起始位置（當前i位置）的值小崭放，則交換即可卓舵。
特點：不穩(wěn)定（數列中有相同元素的情況下蜈垮，如a = b,a本來在b的前邊汰寓，但是排序之后雕什，二者的位置可能被交換）缠俺；平均時間復雜度O(n2)，最壞時間復雜度O(n2)贷岸，最佳時間復雜度O(n2),空間復雜度O(1)
public static void selectSort(int[] arr) {
int minIndex,temp;
for (int i = 0; i < arr.length - 1; i++) {
minIndex = I;
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
3.簡單插入排序
工作原理是通過構建有序序列壹士，對于未排序數據，在已排序序列中從后向前掃描偿警，找到相應位置并插入躏救。
1.從第一個元素開始，該元素可以認為已經被排序螟蒸；
2.取出下一個元素盒使，在已經排序的元素序列中從后向前掃描；
3.如果該元素（已排序）大于新元素七嫌，將該元素移到下一位置少办；
4.重復步驟3，直到找到已排序的元素小于或者等于新元素的位置诵原；
5.將新元素插入到該位置后英妓；
6.重復步驟2~5。
public static void insertSort(int[] arr) {
int current,preIndex;
for (int i = 1; i < arr.length; i++) {
preIndex = i - 1;
current = arr[I];
while (preIndex >= 0 && arr[preIndex] > current){
arr[preIndex + 1] = arr[preIndex];
preIndex--;
}
arr[preIndex+1] = current;
}
}
3.堆排序
參考：http://www.reibang.com/p/938789fde325
堆排序的堆并不是java內存的堆的概念绍赛，它依托于一個完全二叉樹的結構來實現(xiàn)排序蔓纠，首先將數列調整成一個大頂堆（還有稱為大根堆的）或者小頂堆（小根堆），以大頂堆為例(父節(jié)點中的元素不小于任意子節(jié)點的元素這種情形吗蚌。所以腿倚，在一個大頂堆中，一個節(jié)點的元素在其子樹所有元素組成的集合中必定是最大值)褪测，調整完成之后猴誊，最大的數字是這個完全二叉樹的根節(jié)點，接下來把這個最大的值和完全二叉樹的最后一個節(jié)點交換侮措，交換之后可能會破壞大頂堆的結構(父節(jié)點中的元素不小于（不大于）任意子節(jié)點的元素)懈叹，所以交換之后需要同時再次調整大頂堆，重復這個操作直到排序完成
什么是完全二叉樹分扎？ 如 [2,4,1,3,8,6,9]形成一個完全二叉樹
關鍵點：
1.當我們知道某一數字在數組中的索引后澄成，就可以計算出二叉樹中該數字的左右子節(jié)點的索引，或者父節(jié)點在數組中的索引。以數字4為例墨状，它的數組表示為A[1],根據二叉樹特點卫漫，其父節(jié)點為2，即A[0];同時其左節(jié)點為3肾砂，右節(jié)點為8列赎，分別對應A[3],A[4]，可得出一個結論镐确，A[i]的左節(jié)點為A[2i+1],右節(jié)點為A[2i+2]包吝，父節(jié)點為A[i/2]。
2.開始位置(從最后一個非葉子結點開始（葉結點自然不用調整源葫，第一個非葉子結點 arr.length/2-1（完全二叉樹）诗越，從左至右，從下至上進行調整息堂。)
public static void heap(int[] arr, int size, int index) {
//左子節(jié)點的index（完全二叉樹）
//A[i]的左節(jié)點為A[2i+1],右節(jié)點為A[2i+2]嚷狞，父節(jié)點為A[i/2]
int leftNode = 2 * index + 1;
//右子節(jié)點的index
int rightNode = 2 * index + 2;
//設置最大值
int max = index;
//進行和左子節(jié)點比較
if (leftNode < size && arr[leftNode] > arr[max]) {
max = leftNode;
}
//和右子節(jié)點比較
if (rightNode < size && arr[rightNode] > arr[max]) {
max = rightNode;
}
//找到最大的節(jié)點之后就替換
if (max != index) {
int temp = arr[index];
arr[index] = arr[max];
arr[max] = temp;
//然后如果還有的話就繼續(xù)替換
heap(arr, size, max);
}
}
public static int [] heapSort(int [] arr){
//開始位置(從最后一個非葉子結點開始（葉結點自然不用調整，第一個非
//葉子結點 arr.length/2-1（完全二叉樹）荣堰，從左至右床未，從下至上進行調整。)
int start = (arr.length) / 2 - 1;
//1.得到一個大頂堆
for (int i = start; i >= 0; i--) {
heap(arr, arr.length, i);
}
//2.根結點和尾節(jié)點交換持隧，并再次調整維持大頂堆
for (int i = arr.length - 1; i > 0; i--) {
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
//每交換一次之后即硼，最大的值已經到了堆的最后一個節(jié)點，所以這個
//最大值不需要再參與排序屡拨，所以heap第二個參數size = i
heap(arr, i, 0);
}
return arr;
}
總體復雜度為O(n*log n)
3.top-k排序
1.整體排序
將n個數排序之后只酥，取出最大的k個
2.局部排序
只對最大的k個排序，冒泡排序冒泡k次呀狼，就會得到前k個最大元素
3.堆
a.只找到TopK裂允，省去了排序過程，先用前k個元素生成一個小頂堆哥艇，這個小頂堆用于存儲绝编，當前最大的k個元素。
b.接著貌踏，從第k+1個元素開始掃描十饥，和堆頂（堆中最小的元素）比較，如果被掃描的元素大于堆頂祖乳，則替換堆頂的元素逗堵，并調整堆，以保證堆內的k個元素眷昆，總是當前最大的k個元素蜒秤。
c.直到掃描完所有n-k個元素汁咏，最終堆中的k個元素，就是TopK
快速排序
快速排序是由冒泡排序改進而得到的作媚，是一種分區(qū)交換排序方法攘滩。思想如下：
一趟快速排序采用從兩頭向中間掃描的方法，同時交換與基準記錄逆序的記錄纸泡。
1.在待排序的N個記錄中任取一個元素(通常取第一個記錄)作為基準漂问，稱為基準記錄；
2.定義兩個索引 left 和 right 分別表示“首索引” 和 “尾索引”弟灼，key 表示“基準值”级解；
3.首先冒黑，尾索引向前掃描田绑，直到找到比基準值小的記錄(left != righ)，并替換首索引對應的值抡爹；
4.然后掩驱，首索引向后掃描，直到找到比基準值大于的記錄(left != righ)冬竟，并替換尾索引對應的值欧穴；
5.若在掃描過程中首索引等于尾索引(left = right),則一趟排序結束；將基準值(key)替換首索引所對應的值泵殴；
6.再進行下一趟排序時涮帘，待排序列被分成兩個區(qū):[0,left-1],[righ+1,end]
7.對每一個分區(qū)重復步驟2~6，直到所有分區(qū)中的記錄都有序笑诅，排序成功调缨。
快速排序最好時間復雜度為nlogn,最壞時間復雜度為n的平方,平均時間復雜度為nlogn
private static void quickSort(int[] arr, int leftIndex, int rightIndex) {
if (leftIndex >= rightIndex) {
return;
}
int left = leftIndex;
int right = rightIndex;
//待排序的第一個元素作為基準值
int key = arr[leftIndex];
//從左右兩邊交替掃描，直到left = right
//左往右查找的話吆你，每次停下來的位置對應的元素必然比基準要大弦叶，如果這
//時跳出循環(huán)的話，這個較大元素就會被換到前面伤哺，得到的結果就是錯的；而先
//從右往左查找的話者祖，停下來的位置對應的元素必然比基準要小立莉，如果這時跳出
//循環(huán)的話，這個較小元素就會被換到前面七问。所以蜓耻，如果我們要排升序的序列，
//一定記得先從右往左查找烂瘫！順序不錯媒熊，結果才會正確奇适。
while (left < right) {
while (left < right && arr[right] >= key) {
//從右往左掃描，找到第一個比基準值小的元素
right--;
}
while (left < right && arr[left] <= key) {
//從左往右掃描芦鳍，找到第一個比基準值大的元素
left++;
}
if (left < right){
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
}
}
//基準值歸位
arr[leftIndex] = arr[left];
arr[left] = key;
//對基準值左邊的元素進行遞歸排序
quickSort(arr, leftIndex, left - 1);
//對基準值右邊的元素進行遞歸排序嚷往。
quickSort(arr, right + 1, rightIndex);
}
4,二分查找
一般二分查找
public static int binarySearch(int arr[], int num) {
int left = 0;
int right = arr.length - 1;
//等號必須加，不然部分情況無法搜索到結果
while (left <= right) {
// 等同于(left+ right) /2 只是可以避免溢出
int center = left + (right - left) / 2;
if (arr[center] > num) {
right = center - 1;
} else if (arr[center] < num) {
left = center + 1;
} else {
return center;
}
}
return -1;
}
左邊界二分查找
static int leftBoundBinarySearch(int[] nums, int target) {
int left = 0;
int right = nums.length-1; // 注意
//while的條件不能是<= ,比如當前l(fā)eft = 3柠衅， right = 4皮仁，那么mid = 3，
// 更新right = 3菲宴，然后滿足while贷祈，并且mid = 3，更新right = 3喝峦，就會死循環(huán)
while (left < right) { // 注意
int center = left + (right - left) / 2;
if (nums[center] == target) {
//如果找到相等的势誊，繼續(xù)向左查找，這里right必須設置為等于谣蠢，
// 以防止如果沒有左邊界粟耻，還能返回當前找到的值
right = center;
} else if (nums[center] < target) {
//已經不想等了，就沒有必要下次參與查找了
left = center + 1;
} else if (nums[center] > target) {
//已經不想等了眉踱，就沒有必要下次參與查找了
right = center-1;
}
}
return left;
}
右邊界二分查找
static int rightBoundBinarySearch(int[] arr, int target) {
int left = 0;
int right = arr.length - 1;
while (left < right) {
// +1 其實是上取整挤忙，避免最后left 和right對應值相等且等于target，這樣center還是等于left谈喳，然后判斷賦值left = center 册烈，這樣就死循環(huán)了
int center = left + (right - left + 1) / 2;
if (arr[center] > target) {
right = center - 1;
} else if (arr[center] < target) {
left = center + 1;
} else {
left = center;
}
}
return left;
}
二分查找變形
給定一個排序數組和一個目標值，在數組中找到目標值婿禽，并返回其索引赏僧。如果目標值不存在于數組中，返回它將會被按順序插入的位置谈宛。
請必須使用時間復雜度為 O(log n) 的算法次哈。
public static int searchInsert(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while(left <= right) {
int mid = left+(right-left)/2;
if(nums[mid] == target) {
return mid;
} else if(nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left;
}
實現(xiàn) int sqrt(int x) 函數。
計算并返回 x 的平方根吆录，其中 x 是非負整數窑滞。
由于返回類型是整數，結果只保留整數的部分恢筝，小數部分將被舍去哀卫。
由于x 平方根的整數部分ans 是滿足k的平方≤x 的最大值，因此我們可以對k 進行二分查找撬槽，從而得到答案此改。
找到最后一個滿足a的平方小于等于x的情況下，a的值侄柔，和上邊的二分查找變形共啃，找插入位置剛好相反
int left = 0;
int right = x;
while(left <= right){
int middle = (right - left) / 2 + left;
if((long)middle*middle < x){
left = middle+1;
}else if((long)middle * middle > x){
right = middle - 1;
}else{
return middle;
}
}
return right;
5.數組類
1.刪除有序數組中的重復項（小米）
給你一個有序數組 nums 占调，請你 原地 刪除重復出現(xiàn)的元素，使每個元素 只出現(xiàn)一次 移剪，返回刪除后數組的新長度究珊。注意關鍵詞有序，因為有序纵苛，所以重復的元素一定是緊挨著的
不要使用額外的數組空間剿涮，你必須在 原地 修改輸入數組 并在使用 O(1) 額外空間的條件下完成。
例如：輸入：nums = [0,0,1,1,1,2,2,3,3,4]
輸出：5, nums = [0,1,2,3,4]
解釋：函數應該返回新的長度 5 攻人， 并且原數組 nums 的前五個元素被修改為 0, 1, 2, 3, 4 取试。不需要考慮數組中超出新長度后面的元素。
思路：定義兩個指針fast 和slow怀吻，分別為快指針和慢指針瞬浓，快指針表示遍歷數組到達的下標位置，慢指針表示下一個不同元素要填入的下標位置烙博，初始時兩個指針都指向下標1瑟蜈，假設數組nums 的長度為n。將快指針fast 依次遍歷從1到n?1 的每個位置渣窜，對于每個位置，如果nums[fast]≠nums[fast?1]宪躯，說明nums[fast] 和之前的元素都不同乔宿，因此將nums[fast] 的值復制到nums[slow]，然后將slow的值加1访雪，即指向下一個位置详瑞，遍歷結束之后，從 nums[0] 到 nums[slow?1]的每個元素都不相同且包含原數組中的每個不同的元素臣缀，因此新的長度即為slow坝橡，返回slow 即可。
public static int removeDuplicates(int[] nums) {
if (nums == null || nums.length == 0){
return 0;
}
int fast=1,slow = 1;
while(fast < nums.length){
if (nums[fast] != nums[fast - 1]){
nums[slow] = nums[fast];
slow++;
}
fast++;
}
return slow;
}
2.找出數組中任意一個重復的數字（小米）
在一個長度為 n 的數組 nums 里的所有數字都在 0～n-1 的范圍內精置。數組中某些數字是重復的计寇，但不知道有幾個數字重復了，也不知道每個數字重復了幾次脂倦。請找出數組中任意一個重復的數字番宁。
這道題看起來很簡單，直接用個集合存一下赖阻，有重復的就反回蝶押，但是假如不準使用其他數據結構，對空間復雜度要求為O(1)的時候就不行了
參考選擇排序的方式來解(快慢指針解法)：
public static int findRepeatNumber2(int[] nums) {
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
if (nums[i] == nums[j]) {
return nums[I];
}
}
}
return -1;
}
變形一下：
public static int findRepeatNumber3(int[] nums) {
int i = 0;
while (i < nums.length) {
for (int j = i + 1; j < nums.length; j++) {
if (nums[i] == nums[j]) {
return nums[j];
}
}
I++;
}
return 0;
}
3. 0～n-1中缺失的數字（Google火欧，Tencent）
一個長度為n-1的遞增排序數組中的所有數字都是唯一的棋电，并且每個數字都在范圍0～n-1之內茎截。在范圍0～n-1內的n個數字中有且只有一個數字不在該數組中，請找出這個數字赶盔。
注意是有序的
如果沒有任何一個缺失的數字稼虎，那么這個數組應該是這樣的：
arr[0] = 0;
arr[1] = 1;
arr[2] = 2;
arr[3] = 3;
......
arr[n-1] = n-1;
也就是說，數組下標和數組值相同招刨，但是缺了一個霎俩，那么一定從某一個index開始沉眶，index != value打却。這種題的解法看起來很簡單孽查，直接遍歷禽绪，找到這個index和value不想等的數字返回洋满，不過還有更好的解法-二分查找（有序數組叹洲，又是要找某個數癣丧，就要想到二分查找）
public static int findLostNum(int[] nums) {
int start = 0;
int end = nums.length - 1;
while(start < end){
int middle = (end - start) / 2 + start;
if(nums[middle] > middle){
end = middle;
}else{
start = middle + 1;
}
}
// 當左邊界與右邊界相等時，可能已經指向該缺失的數字洪灯，但是還有一種可能是缺失的數字就在最后一個數組的后邊
// 即[0,1,2]坎缭，缺少3，長度為3签钩，即n=4，數的范圍0~3
return start == nums[start]?start+1:start;
4.給定一個存放整數的數組坏快，重新排列數組使得數組左邊為奇數，右邊為偶數。 要求：空間復雜度O(1)躬翁，時間復雜度為O（n）
注意：空間復雜度要求為O(1)拜轨，那么就不能使用額外的數據結構，只能直接來操作這個數組祥得，這里還是用雙指針法來處理兔沃。既然奇數在左，偶數在右级及，那么定義兩個指針乒疏，一個從左往右，一個從右往左（可以看作二分查找的變形）,從左往右找到第一個偶數饮焦，從右往左找到第一個奇數怕吴，交換兩個數字的位置窍侧，然后重復上邊的步驟
public static int[] reSortArray(int[] nums) {
int left = 0, right = nums.length - 1;
while (left < right) {
while (left < right && nums[left] % 2 != 0) {
left++;
}
while (left < right && nums[right] % 2 == 0) {
right--;
}
if (left < right) {
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
}
}
return nums;
}
6.鏈表類
1.反轉單鏈表(小米/美團/快手)
a.非遞歸方法：
定義一個函數，輸入一個鏈表的頭節(jié)點转绷，反轉該鏈表并輸出反轉后鏈表的頭節(jié)點伟件。
示例:
輸入: 1->2->3->4->5->NULL
輸出: 5->4->3->2->1->NULL
思路：在遍歷鏈表時，將當前節(jié)點的next 指針改為指向前一個節(jié)點议经。由于節(jié)點沒有引用其前一個節(jié)點斧账，因此必須事先存儲其前一個節(jié)點。在更改引用之前煞肾，還需要存儲后一個節(jié)點咧织。最后返回新的頭引用。
public class Node {
int value;
Node next;
Node(int x) {
value = x;
}
}
public static Node reverseList(Node head) {
Node cur = head, pre = null;
while (cur != null) {
Node tmp = cur.next;
cur.next = pre;
pre = cur;
cur = tmp;
}
return pre;
}
b.遞歸方法：
public static Node reverseList2(Node head) {
return recur(head, null); // 調用遞歸并返回
}
private static Node recur(Node cur, Node pre) {
if (cur == null) return pre; // 終止條件
Node res = recur(cur.next, cur); // 遞歸后繼節(jié)點
cur.next = pre; // 修改節(jié)點引用指向
return res; // 返回反轉鏈表的頭節(jié)點
}
2.鏈表的中間結點(中國平安)
給定一個頭結點為 head 的非空單鏈表扯旷，返回鏈表的中間結點,如果有兩個中間結點拯爽，則返回第二個中間結點。
public static Node getMiddleNode(Node head) {
Node fast = head;
Node slow = head;
while(fast != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
3.如何檢測一個鏈表是否有環(huán)（優(yōu)酷騰訊滴滴）
A -> B -> C -> D -> E -> A這樣的鏈表表示有環(huán)钧忽，鏈表的頭節(jié)點和鏈表的尾節(jié)點相連毯炮；或者另一種情況，鏈表并非首尾相連耸黑，而是尾節(jié)點指向了中間某節(jié)點A -> B -> C -> D -> E -> C, 這樣也表示這個鏈表有環(huán)
思路：設置一個快指針fast桃煎，一個慢指針slow，二者初始都指向鏈表頭大刊，fast一次走兩步为迈，slow一次走一步，兩個指針同時向前移動缺菌，每移動一次葫辐，兩個指針都要進行比較，如果快指針等于慢指針伴郁，則證明這是個有環(huán)的單鏈表耿战。
如果是有環(huán)的鏈表，那么這個鏈表就沒有尾部焊傅， while (fast != null && fast.next != null) 會一直成立剂陡，直到找到兩個值相同的節(jié)點；如果沒有環(huán)狐胎，那么當fast節(jié)點到達尾端的時候就會跳出循環(huán)鸭栖，恰恰證明了這個鏈表沒有環(huán)
public static boolean isLoop(Node head) {
boolean flag = false;
Node slow = head;
Node fast = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (fast.value == slow.value) {
flag = true;
break;
}
}
return flag;
}
4.相交鏈表（華為）
給你兩個單鏈表的頭節(jié)點 headA和headB ，請你找出并返回兩個單鏈表相交的起始節(jié)點握巢。如果兩個鏈表沒有交點晕鹊，返回null 。
思路：
設第一個公共節(jié)點為 node ，鏈表 headA的節(jié)點數量為
a 捏题，鏈表 headB的節(jié)點數量為b 玻褪，兩鏈表的公共尾部的節(jié)點數量為c ，則有
頭節(jié)點 headA 到 node 前公荧，共有a?c 個節(jié)點
頭節(jié)點 headB 到 node 前带射，共有b?c 個節(jié)點
考慮構建兩個節(jié)點指針 A , B 分別指向兩鏈表頭節(jié)點 headA ,headB ，做如下操作：
指針 A 先遍歷完鏈表 headA 循狰，再開始遍歷鏈表 headB 窟社，當走到 node 時，共走步數為a+(b?c)
指針 B 先遍歷完鏈表 headB 绪钥，再開始遍歷鏈表 headA 灿里，當走到 node 時，共走步數為b+(a?c)
此時指針 A , B 重合程腹，并有兩種情況
a+(b?c)=b+(a?c)
若兩鏈表有公共尾部 (即 c>0 ) ：指針A , B同時指向第一個公共節(jié)點node
若兩鏈表無公共尾部 (即c=0 ) ：指針 A , B 同時指向null
public static Node getIntersectionNode(Node headA, Node headB) {
if (headA == null || headB == null) {
return null;
}
Node first = headA;
Node second = headB;
while (first != second) {
first = first == null ? headB : first.next;
second = second == null ? headA : second.next;
}
return first;
}
5.鏈表中倒數第k個節(jié)點
輸入一個鏈表匣吊，輸出該鏈表中倒數第k個節(jié)點
示例：
給定一個鏈表: 1->2->3->4->5, 和 k = 2.返回鏈表 4->5.
public Node getNodeEnd(Node head, int k) {
Node former = head, latter = head;
for (int i = 0; i < k; I++)
former = former.next;
while (former != null) {
former = former.next;
latter = latter.next;
}
return latter;
}
時間復雜度O(N) ：N 為鏈表長度；總體看寸潦， former 走了N 步色鸳， latter 走了(N?k) 步。
空間復雜度O(1) ： 雙指針 former , latter 使用常數大小的額外空間见转。
6.兩數相加（今日頭條命雀，美團）
給你兩個 非空 鏈表來代表兩個非負整數。數字最高位位于鏈表開始位置斩箫。它們的每個節(jié)點只存儲一位數字吏砂。將這兩數相加會返回一個新的鏈表。
你可以假設除了數字 0 之外乘客，這兩個數字都不會以零開頭
如：
輸入：l1 = [7,2,4,3], l2 = [5,6,4]
輸出：[7,8,0,7]
public Node addTwoNumbers(Node l1, Node l2) {
Stack<Integer> stack1 = new Stack<>();
Stack<Integer> stack2 = new Stack<>();
while (l1 != null) {
stack1.push(l1.value);
l1 = l1.next;
}
while (l2 != null) {
stack2.push(l2.value);
l2 = l2.next;
}
int carry = 0;
Node head = null;
while (!stack1.isEmpty() || !stack2.isEmpty() || carry > 0) {
int sum = carry;
sum += stack1.isEmpty() ? 0 : stack1.pop();
sum += stack2.isEmpty() ? 0 : stack2.pop();
//構建一個節(jié)點
Node node = new Node(sum % 10);
//頭插法中狐血，第一個構建的節(jié)點作為最終的尾節(jié)點，尾節(jié)點
//的next指向null易核，head指向null氛雪，新建的節(jié)點也指向null
node.next = head;
//移動head節(jié)點指向當前創(chuàng)建的節(jié)點，作為頭節(jié)點耸成，下一次循環(huán)
//新建的節(jié)點仍會被作為新節(jié)點的next節(jié)點，就這樣不停的移動head指針
head = node;
carry = sum / 10;
}
return head;
}
時間復雜度：O(max(m,n))浴鸿，其中m 和n 分別為兩個鏈表的長度井氢。我們需要遍歷兩個鏈表的全部位置，而處理每個位置只需要
O(1) 的時間岳链。
空間復雜度：O(m+n)花竞，其中m 和n 分別為兩個鏈表的長度。空間復雜度主要取決于我們把鏈表內容放入棧中所用的空間约急。
變形
給你兩個 非空 的鏈表零远，表示兩個非負的整數。它們每位數字都是按照 逆序 的方式存儲的厌蔽，并且每個節(jié)點只能存儲 一位 數字牵辣。請你將兩個數相加，并以相同形式返回一個表示和的鏈表奴饮。
你可以假設除了數字 0 之外纬向，這兩個數都不會以 0 開頭。
由于輸入的兩個鏈表都是逆序存儲數字的位數的戴卜，因此兩個鏈表中同一位置的數字可以直接相加逾条。我們同時遍歷兩個鏈表，逐位計算它們的和投剥，并與當前位置的進位值相加
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode head = null, tail = null;
int carry = 0;
while (l1 != null || l2 != null) {
int n1 = l1 != null ? l1.val : 0;
int n2 = l2 != null ? l2.val : 0;
int sum = n1 + n2 + carry;
if (head == null) {
head = tail = new ListNode(sum % 10);
} else {
tail.next = new ListNode(sum % 10);
tail = tail.next;
}
carry = sum / 10;
if (l1 != null) {
l1 = l1.next;
}
if (l2 != null) {
l2 = l2.next;
}
}
if (carry > 0) {
tail.next = new ListNode(carry);
}
return head;
}
7.隊列师脂，堆棧
1.用兩個棧實現(xiàn)隊列
根據棧先進后出的特性，我們每次往第一個棧里插入元素后江锨，第一個棧的底部元素是最后插入的元素吃警，第一個棧的頂部元素是下一個待刪除的元素。為了維護隊列先進先出的特性泳桦，我們引入第二個棧汤徽，用第二個棧維護待刪除的元素，在執(zhí)行刪除操作的時候我們首先看下第二個棧是否為空灸撰。如果為空谒府，我們將第一個棧里的元素一個個彈出插入到第二個棧里，這樣第二個棧里元素的順序就是待刪除的元素的順序浮毯，要執(zhí)行刪除操作的時候我們直接彈出第二個棧的元素返回即可完疫。
public class TwoStackQueue {
private final Stack<Integer> stackPush;
private final Stack<Integer> stackPop;
public TwoStackQueue() {
stackPush = new Stack();
stackPop = new Stack();
}
public void addTail(int num) {
stackPush.push(num);
}
public int removeHead() {
if (stackPop.isEmpty()) {
while (!stackPush.isEmpty()) {
stackPop.push(stackPush.pop());
}
}
return stackPop.pop();
}
8.二叉樹
1.前序遍歷
遞歸
public static void preOrderRecur(TreeNode head) {
if (head == null) {
return;
}
System.out.print(head.value + " ");
preOrderRecur(head.left);
preOrderRecur(head.right);
}
迭代
public List<Integer> preorderTraversal(TreeNode root) {
LinkedList<TreeNode> stack = new LinkedList();
List<Integer> list = new ArrayList();
while(root != null || !stack.isEmpty()){
while(root != null){
list.add(root.val);
stack.push(root);
root = root.left;
}
TreeNode node = stack.pop();
root = node.right;
}
return list;
}
2.中序遍歷
遞歸
public static void preOrderRecur(TreeNode head) {
if (head == null) {
return;
}
preOrderRecur(head.left);
System.out.print(head.value + " ");
preOrderRecur(head.right);
}
迭代
public List<Integer> inorderTraversal(TreeNode root) {
LinkedList<TreeNode> stack = new LinkedList();
List<Integer> list = new ArrayList();
while(root != null || !stack.isEmpty()){
while(root != null){
stack.push(root);
root = root.left;
}
TreeNode node = stack.pop();
list.add(node.val);
root = node.right;
}
return list;
}
3.后序遍歷
遞歸
public static void postOrderRecur(TreeNode head) {
if (head == null) {
return;
}
postOrderRecur(head.left);
postOrderRecur(head.right);
System.out.print(head.value + " ");
}
迭代
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList();
LinkedList<TreeNode> stack = new LinkedList();
TreeNode pre = null;
while(root != null || !stack.isEmpty()){
while(root != null){
stack.push(root);
root = root.left;
}
TreeNode node = stack.pop();
if(node.right == null || node.right == pre){
list.add(node.val);
pre = node;
root = null;
}else{
stack.push(node);
root = node.right;
}
}
return list;
}
4.檢查子樹(愛奇藝)
檢查子樹。你有兩棵非常大的二叉樹：T1债蓝，有幾萬個節(jié)點壳鹤；T2，有幾萬個節(jié)點饰迹。設計一個算法芳誓，判斷 T2 是否為 T1 的子樹。
如果 T1 有這么一個節(jié)點 n啊鸭，其子樹與 T2 一模一樣锹淌，則 T2 為 T1 的子樹，也就是說赠制，從節(jié)點 n 處把樹砍斷赂摆，得到的樹與 T2 完全相同。
示例1:
輸入：t1 = [1, 2, 3], t2 = [2]
輸出：true
示例2:
輸入：t1 = [1, null, 2, 4], t2 = [3, 2]
輸出：false
public boolean checkSubTree(TreeNode n1, TreeNode n2) {
if (n2 == null) {
return true;
}
if (n1 == null) {
return false;
}
return isEquals(n1, n2) || checkSubTree(n1.left, n2) || checkSubTree(n1.right, n2);
}
private boolean isEquals(TreeNode n1, TreeNode n2) {
if (n1 == n2) {
return true;
}
if (n1 == null || n2 == null) {
return false;
}
return n1.value == n2.value && isEquals(n1.left, n2.left) && isEquals(n1.right, n2.right);
}
class TreeNode {
int value;
TreeNode left;
TreeNode right;
}
時間復雜度分析：最差情況下,t1在小于t2子樹高度以上節(jié)點都要比對M次，M是t2節(jié)點的大小烟号，所以時間復雜度為O（N*M）
變形：
給你兩棵二叉樹的根節(jié)點 p 和 q 绊谭，編寫一個函數來檢驗這兩棵樹是否相同。如果兩個樹在結構上相同汪拥，并且節(jié)點具有相同的值达传，則認為它們是相同的。
public boolean isSameTree(TreeNode p, TreeNode q) {
if(p == null && q == null){
return true;
}
if(p == null || q == null){
return false;
}
return p.val == q.val && isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
}
給定一個二叉樹喷楣，檢查它是否是鏡像對稱的趟大。
例如，二叉樹 [1,2,2,3,4,4,3] 是對稱的铣焊。
1
/ \
2 2
/ \ / \
3 4 4 3
如果同時滿足下面的條件逊朽，兩個樹互為鏡像：
它們的兩個根結點具有相同的值
每個樹的右子樹都與另一個樹的左子樹鏡像對稱
我們可以實現(xiàn)這樣一個遞歸函數，通過「同步移動」兩個指針的方法來遍歷這棵樹曲伊，p 指針和q 指針一開始都指向這棵樹的根叽讳，隨后p 右移時,q 左移，p 左移時,q 右移坟募。每次檢查當前p 和q 節(jié)點的值是否相等岛蚤，如果相等再判斷左右子樹是否對稱。
public boolean isSymmetric(TreeNode root) {
TreeNode left = root;
TreeNode right = root;
return check(left,right);
}
public boolean check(TreeNode left,TreeNode right){
if(left == null && right == null){
return true;
}
if(left == null || right == null){
return false;
}
return left.val == right.val && check(left.left,right.right) && check(left.right, right.left);
}
給定一個二叉樹懈糯，找出其最大深度涤妒。
二叉樹的深度為根節(jié)點到最遠葉子節(jié)點的最長路徑上的節(jié)點數。
如果我們知道了左子樹和右子樹的最大深度l 和r赚哗，那么該二叉樹的最大深度即max(l,r)+1
而左子樹和右子樹的最大深度又可以以同樣的方式進行計算她紫。因此我們可以用「深度優(yōu)先搜索」的方法來計算二叉樹的最大深度。具體而言屿储，在計算當前二叉樹的最大深度時贿讹，可以先遞歸計算出其左子樹和右子樹的最大深度，然后在O(1) 時間內計算出當前二叉樹的最大深度够掠。遞歸在訪問到空節(jié)點時退出民褂。
public int maxDepth(TreeNode root) {
if(root == null){
return 0;
}else{
int leftMaxLength = maxDepth(root.left);
int rightMaxLength = maxDepth(root.right);
return Math.max(leftMaxLength,rightMaxLength)+1;
}
}
給你一個整數數組 nums ，其中元素已經按 升序 排列疯潭，請你將其轉換為一棵 高度平衡 二叉搜索樹赊堪。
高度平衡 二叉樹是一棵滿足「每個節(jié)點的左右兩個子樹的高度差的絕對值不超過 1 」的二叉樹。
選擇中間位置左邊的數字作為根節(jié)點
public TreeNode sortedArrayToBST(int[] nums) {
return transferArrayToTree(nums,0,nums.length - 1);
}
public TreeNode transferArrayToTree(int[] nums,int left,int right){
if(left > right){
return null;
}
int mid = (left + right)/2;
TreeNode node = new TreeNode(nums[mid]);
node.left = transferArrayToTree(nums,left,mid - 1);
node.right = transferArrayToTree(nums,mid+1,right);
return node;
}
給定一個單鏈表竖哩，其中的元素按升序排序雹食，將其轉換為高度平衡的二叉搜索樹。
本題中期丰，一個高度平衡二叉樹是指一個二叉樹每個節(jié)點 的左右兩個子樹的高度差的絕對值不超過 1。
將給定的有序鏈表轉換為二叉搜索樹的第一步是確定根節(jié)點,如何找出這樣的一個根節(jié)點呢？我們可以找出鏈表元素的中位數作為根節(jié)點的值.找出鏈表中位數節(jié)點的方法多種多樣钝荡，其中較為簡單的一種是快慢指針法
class Solution {
public TreeNode sortedListToBST(ListNode head) {
ListNode h = head;
ListNode t = null;
return linkListToTree(h,t);
}
public TreeNode linkListToTree(ListNode left,ListNode right){
if(left == right){
return null;
}
ListNode mid = getMidleNode(left,right);
TreeNode node = new TreeNode(mid.val);
node.left = linkListToTree(left,mid);
node.right = linkListToTree(mid.next,right);
return node;
}
public ListNode getMidleNode(ListNode left,ListNode right){
ListNode fast = left;
ListNode slow = left;
//注意這里比較關鍵街立，不能通過fast != null && fast.next != null 判斷
while(fast != right && fast.next != right){
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
}
給你二叉樹的根結點 root ，將它展開為一個單鏈表
展開后的單鏈表應該同樣使用 TreeNode 埠通，其中 right 子指針指向鏈表中下一個結點赎离，而左子指針始終為 null 。
展開后的單鏈表應該與二叉樹 先序遍歷 順序相同端辱。
1
/ \
2 5
/ \ \
3 4 6
//將 1 的左子樹插入到右子樹的地方
1
\
2 5
/ \ \
3 4 6
//將原來的右子樹接到左子樹的最右邊節(jié)點
1
\
2
/ \
3 4
\
5
\
6
//將 2 的左子樹插入到右子樹的地方
1
\
2
\
3 4
\
5
\
6
//將原來的右子樹接到左子樹的最右邊節(jié)點
1
\
2
\
3
\
4
\
5
\
6
......
public void flatten(TreeNode root) {
while(root != null){
if(root.left == null){
root = root.right;
}else{
TreeNode temp = root.left;
while(temp.right != null){
temp = temp.right;
}
temp.right = root.right;
root.right = root.left;
root.left = null;
root = root.right;
}
}
}
5.二叉樹的序列化和反序列化
可以先序遍歷這顆二叉樹梁剔，遇到空子樹的時候序列化成 NULL，否則繼續(xù)遞歸序列化舞蔽。那么我們如何反序列化呢荣病？首先我們需要把原先的序列分割開來得到先序遍歷的元素列表，然后從左向右遍歷這個序列：
如果當前的元素為 NULL渗柿，則當前為空樹
否則先解析這棵樹的左子樹个盆，再解析它的右子樹
public static String serialize(TreeNode node) {
return serialize2(node, "");
}
public static String serialize2(TreeNode node, String str) {
if (node == null) {
str += "NULL,";
} else {
str += node.value + ",";
str = serialize2(node.left, str);
str = serialize2(node.right, str);
}
return str;
}
public static TreeNode deserialize(String str) {
String[] split = str.split(",");
List<String> list = new LinkedList<>(Arrays.asList(split));
return deserialize2(list);
}
public static TreeNode deserialize2(List<String> list) {
if ("NULL".equals(list.get(0))) {
list.remove(0);
return null;
}
String s = list.get(0);
TreeNode node = new TreeNode(Integer.parseInt(s));
list.remove(0);
node.left = deserialize2(list);
node.right = deserialize2(list);
return node;
}
時間復雜度：在序列化和反序列化函數中，我們只訪問每個節(jié)點一次朵栖，因此時間復雜度為O(n)颊亮，其中n 是節(jié)點數，即樹的大小陨溅。
空間復雜度：在序列化和反序列化函數中终惑，我們遞歸會使用棧空間门扇，故漸進空間復雜度為O(n)雹有。
給定一個字符串，請你找出其中不含有重復字符的最長字串的長度（字節(jié)跳動）
我們不妨以abcabcbb為例悯嗓，找出從每一個字符開始的件舵，不包含重復字符的最長子串，那么其中最長的那個字符串即為答案脯厨。對于示例一中的字符串铅祸，我們列舉出這些結果，其中括號中表示選中的字符以及最長的字符串：
以(a)bcabcbb 開始的最長字符串為(abc)abcbb合武；
以a(b)cabcbb 開始的最長字符串為a(bca)bcbb
以ab(c)abcbb 開始的最長字符串為ab(cab)cbb
以abc(a)bcbb 開始的最長字符串為abc(abc)bb临梗；
以abca(b)cbb 開始的最長字符串為abca(bc)bb
以abcab(c)bb開始的最長字符串為abcab(cb)b；
以abcabc(b)b開始的最長字符串為abcabc(b)b
以abcabcb(b) 開始的最長字符串為abcabcb(b)稼跳。
發(fā)現(xiàn)了什么盟庞？如果我們依次遞增地枚舉子串的起始位置，那么子串的結束位置也是遞增的汤善！這里的原因在于什猖，假設我們選擇字符串中的第k 個字符作為起始位置票彪，并且得到了不包含重復字符的最長子串的結束位置為rk。那么當我們選擇第k+1 個字符作為起始位置時不狮，首先從k+1到rk
的字符顯然是不重復的降铸，并且由于少了原本的第k 個字符，我們可以嘗試繼續(xù)增大人rk摇零，直到右側出現(xiàn)了重復字符為止推掸。
這樣一來，我們就可以使用「滑動窗口」來解決這個問題了：
我們使用兩個指針表示字符串中的某個子串（或窗口）的左右邊界驻仅，其中左指針代表著上文中枚舉子串的起始位置谅畅，而右指針即為上文中的rk;在每一步的操作中，我們會將左指針向右移動一格噪服，表示 我們開始枚舉下一個字符作為起始位置毡泻，然后我們可以不斷地向右移動右指針，但需要保證這兩個指針對應的子串中沒有重復的字符芯咧。在移動結束后牙捉，這個子串就對應著 以左指針開始的，不包含重復字符的最長子串敬飒。我們記錄下這個子串的長度邪铲；
在循環(huán)結束后，我們找到的最長的子串的長度即為答案无拗。
public static int lengthOfLongestSubstring(String s) {
int left = 0;
HashSet<Character> set = new HashSet();
int max = 0;
for(int i = 0; i < s.length();i++){
if(i != 0){
set.remove(s.charAt(i - 1));
}
while(left < s.length() && !set.contains(s.charAt(left))){
set.add(s.charAt(left));
left++;
}
max = Math.max(max,left-i);
}
return max;
}
7.反轉字符串中的單詞
開辟一個新字符串带到。然后從頭到尾遍歷原字符串，直到找到空格為止英染，此時找到了一個單詞揽惹，并能得到單詞的起止位置。隨后四康，根據單詞的起止位置搪搏，可以將該單詞逆序放到新字符串當中。如此循環(huán)多次闪金，直到遍歷完原字符串疯溺，就能得到翻轉后的結果。
public static String reverseWords(String s) {
int start = 0;
int length = s.length();
StringBuilder builder = new StringBuilder();
while(start < length){
int lastStart = start;
while(start < length && s.charAt(start) != ' '){
start++;
}
for(int i = start -1 ; i >=lastStart;i--){
builder.append(s.charAt(i));
}
while(start < length && s.charAt(start) == ' '){
builder.append(' ');
start++;
}
}
return builder.toString();
}
時間復雜度,O(N)哎垦，其中N 為字符串的長度囱嫩。原字符串中的每個字符都會在O(1) 的時間內放入新字符串中。
空間復雜度,O(N)漏设。我們開辟了與原字符串等大的空間墨闲。
8.動態(tài)規(guī)劃
給定一個整數數組 nums ，找到一個具有最大和的連續(xù)子數組（子數組最少包含一個元素）郑口，返回其最大和鸳碧。
示例 1：
輸入：nums = [-2,1,-3,4,-1,2,1,-5,4]
輸出：6
解釋：連續(xù)子數組 [4,-1,2,1] 的和最大盾鳞，為 6 。
這道題用動態(tài)規(guī)劃的思路并不難解決杆兵，比較難的是后文提出的用分治法求解雁仲，但由于其不是最優(yōu)解法，所以先不列出來
動態(tài)規(guī)劃的是首先對數組進行遍歷琐脏，當前最大連續(xù)子序列和為 sum，結果為 temp
如果 sum > 0缸兔，則說明 sum 對結果有增益效果日裙，則 sum 保留并加上當前遍歷數字
如果 sum <= 0，則說明 sum 對結果無增益效果惰蜜，需要舍棄昂拂，則 sum 直接更新為當前遍歷數字
每次比較 sum 和 temp的大小，將最大值置為temp抛猖，遍歷結束返回結果
時間復雜度:O(n)
public int maxSubArray(int[] nums) {
//優(yōu)化空間前
// int arr[] = new int[nums.length];
// arr[0] = nums[0];
// int max = nums[0];
// for(int i = 1; i < nums.length; i++){
// if(arr[i - 1] > 0){
// arr[i] = arr[i - 1] + nums[i];
// }else{
// arr[i] = nums[i];
// }
// max = Math.max(max,arr[i]);
// }
// return max;
//優(yōu)化空間后
int pre = nums[0];
int max = nums[0];
for(int i = 1; i < nums.length; i++){
pre = Math.max(pre + nums[i],nums[i]);
max = Math.max(pre,max);
}
return max;
9.漢諾塔問題
1.只有一個盤子的時候格侯，只需要從將A塔上的一個盤子移到C塔上。
2.當A塔上有兩個盤子是财著，先將A塔上的1號盤子（編號從上到下）移動到B塔上联四，再將A塔上的2號盤子移動的C塔上，最后將B塔上的小盤子移動到C塔上撑教。
3.當A塔上有3個盤子時朝墩，先將A塔上編號1至2的盤子（共2個）移動到B塔上（需借助C塔），然后將A塔上的3號最大的盤子移動到C塔伟姐，最后將B塔上的兩個盤子借助A塔移動到C塔上收苏。
4.當A塔上有n個盤子是瘾杭，先將A塔上編號1至n-1的盤子（共n-1個）移動到B塔上（借助C塔）聊品，然后將A塔上最大的n號盤子移動到C塔上，最后將B塔上的n-1個盤子借助A塔移動到C塔上秆乳。
5.綜上所述懦鼠，除了只有一個盤子時不需要借助其他塔外，其余情況均一樣（只是事件的復雜程度不一樣）矫夷。
發(fā)現(xiàn)：
中間的一步是把最大的一個盤子由A移到C上去葛闷；
中間一步之上可以看成把A上n-1個盤子通過借助輔助塔（C塔）移到了B上，
中間一步之下可以看成把B上n-1個盤子通過借助輔助塔（A塔）移到了C上双藕；
public static void hannoi(int n, char A, char B, char C) {
if (n == 1) {
move(n, A, C);
} else {
hannoi(n - 1, A, C, B);
move(n, A, C);
hannoi(n - 1, B, A, C);
}
}
private static void move(int n, char a, char c) {
System.out.println("把" + n + "從" + a + "移動到" + c);
}
