趁空閑時間刷一遍極客時間上王爭的《數(shù)據(jù)結構與算法之美》課程，個人覺得寫的很好，每章節(jié)由淺入深且從基礎到引入設計類問題，如果寫過很多代碼想要進行架構設計轉型時再回頭看這些基礎知識還蠻有趣的，以下紀錄下隨著課程走的部分實現(xiàn)代碼和思考；
內(nèi)容主要是筆記和代碼，注：手寫一遍代碼是有必要的；

鏈表反轉

單鏈表反轉

class ListNode {  int val;  ListNode next;  ListNode(int val) {  this.val = val;  this.next = null;  }  
public ListNode reverseList(ListNode head) {  ListNode prev = null;  ListNode curr = head;  while (curr != null) {  ListNode nextTemp = curr.next;  // 臨時保存下一個節(jié)點  curr.next = prev;               // 反轉當前節(jié)點的指針  prev = curr;                    // 將前一個節(jié)點移動到當前節(jié)點  curr = nextTemp;                // 將當前節(jié)點移動到下一個節(jié)點  }  return prev;  // prev 最后會指向新的頭節(jié)點  }  
}

鏈表合并

兩個有序的鏈表合并，用到了哨兵dummy這個指針記錄

class ListNode {  int val;  ListNode next;  ListNode(int val) {  this.val = val;  this.next = null;  }  public ListNode mergeTwoLists(ListNode l1, ListNode l2) {  // 創(chuàng)建一個哨兵節(jié)點，方便處理邊界情況  ListNode dummy = new ListNode(0);  ListNode curr = dummy;  // 使用兩個指針分別遍歷兩個鏈表  while (l1 != null && l2 != null) {  if (l1.val <= l2.val) {  curr.next = l1;  l1 = l1.next;  } else {  curr.next = l2;  l2 = l2.next;  }  curr = curr.next;  }  // 處理剩余節(jié)點（只能有一個鏈表還有剩余節(jié)點）  if (l1 != null) {  curr.next = l1;  } else {  curr.next = l2;  }  }
}

刪除鏈表倒數(shù)第 n 個結點

使用快慢指針，快慢指針在解很多鏈表題目中都有體現(xiàn)

class ListNode {  int val;  ListNode next;    ListNode(int val) {  this.val = val;  this.next = null;  }  public ListNode removeNthFromEnd(ListNode head, int n) {  // 創(chuàng)建一個哨兵節(jié)點，簡化頭節(jié)點被刪除的情況  ListNode dummy = new ListNode(0);  dummy.next = head;// 初始化快慢指針  ListNode fast = dummy;  ListNode slow = dummy;  // 先將快指針向前移動 n+1 步  for (int i = 0; i <= n; i++) {  fast = fast.next;  }    // 然后同時移動快慢指針，直到快指針到達鏈表末尾  while (fast != null) {  fast = fast.next;  slow = slow.next;  }    // 此時慢指針指向的節(jié)點的下一個節(jié)點就是要刪除的節(jié)點  slow.next = slow.next.next;    // 返回頭節(jié)點（注意是哨兵節(jié)點的下一個節(jié)點）  return dummy.next;  }    
}

找鏈表的中間結點

使用快慢指針來實現(xiàn)，快指針每次移動2步，而慢指針每次移動1步。當快指針到達鏈表末尾時，慢指針將恰好位于鏈表的中間。

class ListNode {  int val;  ListNode next;  ListNode(int val) {  this.val = val;  this.next = null;  }  public ListNode findMiddle(ListNode head) {  // 初始化快慢指針  ListNode slow = head;  ListNode fast = head;  // 快指針每次移動兩步，慢指針每次移動一步  while (fast != null && fast.next != null) {  slow = slow.next;  // 慢指針移動一步  fast = fast.next.next;  // 快指針移動兩步  }  // 當快指針到達鏈表末尾時，慢指針指向中間節(jié)點  return slow;  } 
}

鏈表中環(huán)的檢測

快慢指針進行遍歷，如果快慢指針不相遇說明沒有環(huán)

class ListNode {  int val;  ListNode next;ListNode(int val) {  this.val = val;  this.next = null;  }  public boolean hasCycle(ListNode head) {  if (head == null || head.next == null) {  // 如果鏈表為空或只有一個節(jié)點，則不可能有環(huán)  return false;  }   ListNode slow = head;  ListNode fast = head;// 快慢指針開始移動，直到它們相遇或快指針到達鏈表末尾  while (fast != null && fast.next != null) {  slow = slow.next;          // 慢指針每次移動一步  fast = fast.next.next;     // 快指針每次移動兩步  // 如果快慢指針相遇，說明鏈表中存在環(huán)  if (slow == fast) {  return true;  }  }// 快指針到達鏈表末尾，說明鏈表中沒有環(huán)  return false;  }  
}

排序算法

常用的冒泡、選擇、插入、歸并、快速算法，手寫很重要，寫出來會發(fā)現(xiàn)即使是一個小的改動對于程序的消耗來說都有所差別；
關于排序的算法還可以參照：https://mp.weixin.qq.com/s/HQg3BzzQfJXcWyltsgOfCQ
在要求高效的很多基礎框架代碼中都是用了快速排序（遞歸思路）

// 冒泡排序  
void bubbleSort(int[] arr) {  int n = arr.length;  for (int i = 0; i < n - 1; i++) {  for (int j = 0; j < n - i - 1; j++) {  if (arr[j] > arr[j + 1]) {  // 交換arr[j]和arr[j + 1]  int temp = arr[j];  arr[j] = arr[j + 1];  arr[j + 1] = temp;  }  }  }  
}  // 選擇排序  
void selectionSort(int[] arr) {  int n = arr.length;  for (int i = 0; i < n - 1; i++) {  int minIdx = i;  for (int j = i + 1; j < n; j++) {  if (arr[j] < arr[minIdx]) {  minIdx = j;  }  }  // 交換arr[i]和arr[minIdx]  int temp = arr[minIdx];  arr[minIdx] = arr[i];  arr[i] = temp;  }  
}  // 插入排序  
void insertionSort(int[] arr) {  int n = arr.length;  for (int i = 1; i < n; i++) {  int key = arr[i];  int j = i - 1;  // 將arr[i]插入到已排序部分arr[0..i-1]  while (j >= 0 && arr[j] > key) {  arr[j + 1] = arr[j];  j = j - 1;  }  arr[j + 1] = key;  }  
} 
// 歸并排序  
void mergeSort(int[] arr, int left, int right) {  if (left < right) {  int mid = left + (right - left) / 2;  // 遞歸排序兩個子數(shù)組  mergeSort(arr, left, mid);  mergeSort(arr, mid + 1, right);  // 合并兩個已排序的子數(shù)組  merge(arr, left, mid, right);  }  
}  
void merge(int[] arr, int left, int mid, int right) {  int n1 = mid - left + 1;  int n2 = right - mid;  int[] L = new int[n1];  int[] R = new int[n2];  for (int i = 0; i < n1; i++) L[i] = arr[left + i];  for (int j = 0; j < n2; j++) R[j] = arr[mid + 1 + j];  int i = 0, j = 0;  int k = left;  while (i < n1 && j < n2) {  if (L[i] <= R[j]) {  arr[k] = L[i];  i++;  } else {  arr[k] = R[j];  j++;  }  k++;  }  while (i < n1) {  arr[k] = L[i];  i++;  k++;  }  while (j < n2) {  arr[k] = R[j];  j++;  k++;  }  
}    
// 快速排序  
void quickSort(int[] arr, int low, int high) {  if (low < high) {  int pi = partition(arr, low, high);  // 遞歸排序兩個子數(shù)組  quickSort(arr, low, pi - 1);  quickSort(arr, pi + 1, high);  }  
}  
int partition(int[] arr, int low, int high) {  int pivot = arr[high];  int i = (low - 1);  for (int j = low; j < high; j++) {  if (arr[j] < pivot) {  i++;  // 交換arr[i]和arr[j]  int temp = arr[i];  arr[i] = arr[j];  arr[j] = temp;  }  }  // 交換arr[i + 1]和arr[high] (或pivot)  int temp = arr[i + 1];  arr[i + 1] = arr[high];  arr[high] = temp;  return i + 1;  
}

遞歸

遞歸是一種分治的思維，不適合人類大腦但天然是計算機的處理方式，人類大腦總是想把事情的步驟想的很清晰，12345每一步驟做什么，但是計算機不是這樣的；
遞歸也存在堆棧溢出和重復計算的問題，專欄中也給了對應的方式，重復計算可以通過緩存來解決；

// 上樓梯問題中可以適當增加緩存來消除重復計算
public int f(int n) {if (n == 1) return 1;if (n == 2) return 2;// hasSolvedList 可以理解成一個 Map，key 是 n，value 是 f(n)if (hasSolvedList.containsKey(n)) {return hasSovledList.get(n);}int ret = f(n-1) + f(n-2);hasSovledList.put(n, ret);return ret;
}