目錄
- 前言
- 0. *經驗總結
- 0.1 程式員面試金典 P79
- 0.2 需要詢問面試官的點
- 0.3 快慢指標
- 0.4 遞回
- 1. 移除重復節點 [easy]
- 1.1 考慮點
- 1.2 解法
- 1.2.1 集合法
- 1.2.2 兩回圈法
- 2. 回傳倒數第 k 個節點 [easy]
- 2.1 考慮點
- 2.2 解法
- 2.2.1 雙指標同步運動法（快慢指標）（優）
- 2.2.2 使用堆疊法
- 2.2.3 遞回
- 3. 洗掉中間節點 [easy]
- 3.1 考慮點
- 3.2 解法
- 3.2.1 復制自己法
- 4. 分割鏈表 [medium]
- 4.1 考慮點
- 4.2 解法
- 4.2.1 雙指標逐個處理法
- 4.2.2 排序法
- 4.2.3 頭插法
- 4.2.4 原地洗掉
- 5. 鏈表求和 [medium]
- 5.1 考慮點
- 5.2 解法
- 5.2.1 反向存放法
- 5.2.2 遞回法
- 6. 回文鏈表 [easy]
- 6.1 考慮點
- 6.2 解法
- 6.2.1 改變方向雙向遍歷法（優）
- 6.2.2 將值復制到陣列中后用雙指標法
- 6.2.3 遞回
- 7. 鏈表相交 [easy]
- 7.1 考慮點
- 7.2 解法
- 7.2.1 長度對齊雙指標法
- 7.2.2 雙指標（優）
- 8. 環路檢測 [medium]
- 8.1 考慮點
- 8.2 解法
- 8.2.1 快慢指標法（優）
- 8.2.2 哈希表
- 最后
前言
本系列筆記主要記錄筆者刷《程式員面試金典》演算法的一些想法與經驗總結，按專題分類，主要由兩部分構成：經驗值點和經典題目，其中重點放在經典題目上；
0. *經驗總結
0.1 程式員面試金典 P79
- 鏈表的特點：無法在常數時間復雜度內訪問鏈表的特定元素；可以在引數事件復雜度內加入和洗掉元素；
- 如果鏈表被多個物件參考，當鏈表頭結點變了，可能會有一些物件仍然指向原頭結點；解決方法：可以用LinkedList封裝Node類，該類只包含一個成員變數：頭結點；
- 鏈表問題可以關注“快慢指標”和遞回；
0.2 需要詢問面試官的點
- 是否可以修改原鏈表；
- 是否可以開辟額外空間；
- 時間優先還是空間優先；
- 在面試中要弄清單向鏈表和雙向鏈表；
0.3 快慢指標
- 快慢指標又稱雙指標，是一個廣泛的概念，只要涉及兩個指標遍歷鏈表，并且一前一后，都可以稱為快慢指標；
- 快慢指標在不同題目有不同的作用，常見型別有：
- 找到中點：慢指標每走n步時，快指標走2n步，當快指標達到尾部時；
- 找到三分之一點：慢指標走n步，快指標走3n步；
- 找到倒數第x個節點：快指標先走x步后，慢指標從頭出發，與快指標速度一樣，當快指標達到尾部時，慢指標到倒數第k個節點；【詳情見 2. 回傳倒數第 k 個節點】
- 測驗環形鏈表：慢指標每走n步時，快指標走2n步，能相遇說明環形；
- 測驗鏈表是否成環并找到第一個成環節點：【詳情見 8. 環路檢測】
- ……
0.4 遞回
- 實際上所有遞回演算法都可以轉換成迭代法，只是后者可能要復雜得多；
- 一般來說，遞回解法更簡潔，但效率低下；
1. 移除重復節點 [easy]
1.1 考慮點
- 需要問清楚面試官是否可以開辟額外空間；
- 需要詢問面試官時間優先還是空間優先；
1.2 解法
1.2.1 集合法
public ListNode removeDuplicateNodes(ListNode head) {
if(head == null || head.next == null){
return head;
}
ListNode cur = head;
ListNode index = head;
Set<Integer> set = new HashSet<>();
set.add(head.val);
while( cur.next != null){
cur = cur.next;
if( !set.contains(cur.val) ){
index.next = cur;
index = cur;
set.add(cur.val);
} else {
index.next = null;
}
}
return head;
}
- 執行時間：66.09%；記憶體消耗：51.20%；
- 也可以用哈希表；
- 時間復雜度：O(N)，其中 N 是給定鏈表中節點的數目；
- 空間復雜度：O(N)，在最壞情況下，給定鏈表中每個節點都不相同，哈希表中需要存盤所有的 N個值；
1.2.2 兩回圈法
public ListNode removeDuplicateNodes(ListNode head) {
ListNode ob = head;
while (ob != null) {
ListNode oc = ob;
while (oc.next != null) {
if (oc.next.val == ob.val) {
oc.next = oc.next.next;
} else {
oc = oc.next;
}
}
ob = ob.next;
}
return head;
}
- 執行時間：93.52%；記憶體消耗：93.52%；
- 時間復雜度：O(N2)，其中 N 是給定鏈表中節點的數目；
- 空間復雜度：O(1)；
2. 回傳倒數第 k 個節點 [easy]
2.1 考慮點
- 需要問清楚面試官是否可以開辟額外空間；
2.2 解法
2.2.1 雙指標同步運動法（快慢指標）（優）
public int kthToLast(ListNode head, int k) {
if(head == null || head.next == null){
return head.val;
}
ListNode cur = head;
ListNode index = head;
//cur先走k-1個步長
for(int i = 0; i < k - 1; i++ ){
cur = cur.next;
}
//index上鏈表，跟cur同步運動，當cur到達鏈表尾時，cur為倒數第k個
while(cur.next != null){
cur = cur.next;
index = index.next;
}
return index.val;
}
- 執行時間：100.00%；記憶體消耗：30.78%；
- 第一個指標先移動k步，然后第二個指標再從頭開始，這個時候這兩個指標同時移動，當第一個指標到鏈表的末尾的時候，回傳第二個指標即可；
2.2.2 使用堆疊法
public int kthToLast(ListNode head, int k) {
Stack<ListNode> stack = new Stack<>();
//鏈表節點壓堆疊
while (head != null) {
stack.push(head);
head = head.next;
}
//在出堆疊串成新的鏈表
ListNode firstNode = stack.pop();
while (--k > 0) {
ListNode temp = stack.pop();
temp.next = firstNode;
firstNode = temp;
}
return firstNode.val;
}
- 執行時間：9.00%；記憶體消耗：58.84%；
- 把原鏈表的結點全部壓堆疊，然后再把堆疊中最上面的k個節點出堆疊，出堆疊的結點重新串成一個新的鏈表即可；
2.2.3 遞回
int size;
public int kthToLast(ListNode head, int k) {
if (head == null){
return 0;
}
int value = https://www.cnblogs.com/dlhjw/p/kthToLast(head.next, k);
if (++size == k){
return head.val;
}
return value;
}
- 執行時間：100.00%；記憶體消耗：24.44%；
- 遞回訪問整個鏈表，到達尾部時，回傳一個設定為0的size計數器，后續呼叫每次都會將計數器加1，當計數器為k是，即為倒數第k個，value為暫存的結果值；
3. 洗掉中間節點 [easy]
3.1 考慮點
- 題目有點“腦筋急轉彎”的意思，注意給出的是當前要洗掉的節點；
- 面試官期待的是：當待洗掉的節點為鏈表尾節點時的情況：
- 因為不能訪問前一個節點，要從其他方面考慮解決方法；
- 可以考慮將該節點標記為假節點，即物理上存在，邏輯上不在；
3.2 解法
3.2.1 復制自己法
public void deleteNode(ListNode node) {
if(node == null || node.next == null){
return;
}
ListNode nextNode = node.next;
node.val = nextNode.val;
node.next = nextNode.next;
}
- 執行時間：100.00%；記憶體消耗：72.05%；
- 如果只能訪問當前節點，那么該題的解題思路就是，將自己變成其他節點；
- 舉個例子：A->B->C->D；
- 如果要刪掉 B 節點，那么只需要將 B 變為 C，再把 B 的指標指向 D，即可完成；
4. 分割鏈表 [medium]
4.1 考慮點
- 注意題目意思，可以排序，但不一定是排序；
- 如果本題描述的是陣列，對于如何移動元素要謹慎，陣列元素的移動通常開銷很大，但鏈表相對比較簡單；
4.2 解法
4.2.1 雙指標逐個處理法
public ListNode partition(ListNode head, int x) {
if(head == null || head.next == null ){
return head;
}
//找到比x小的節點，該節點離x節點最近
ListNode index = head;
while(index.val < x && index.next != null){
index = index.next;
}
//用2個指標完成移位操作
//index為首個大于等于x的節點
//cur為index2的next
ListNode cur = index.next;
while(index.next != null){
if(cur.val >= x){
//繼續
index = index.next;
cur = cur.next;
} else {
//移位
index.next = cur.next;
if( head.val < x){
cur.next = head.next;
head.next = cur;
} else {
cur.next = head;
head = cur;
}
cur = index.next;
}
}
return head;
}
- 執行時間：100.00%；記憶體消耗：64.81%；
4.2.2 排序法
public ListNode partition(ListNode head, int x) {
return sortList(head, null);
}
private ListNode sortList(ListNode head, ListNode tail) {
//無法繼續拆分的情況
if (head == null) {
return null;
}
//無法繼續拆分的情況
if (head.next == tail) {
head.next = null;
return head;
}
//快慢指標找到中間節點
ListNode slow = head, fast = head;
while (fast != tail && fast.next != tail) {
slow = slow.next;
fast = fast.next.next;
}
ListNode mid = slow;
//左邊繼續拆分
ListNode left = sortList(head, mid);
//右邊繼續拆分
ListNode right = sortList(mid, tail);
//有序鏈表合并
return merge(left, right);
}
private ListNode merge(ListNode left, ListNode right) {
ListNode mergeNode = new ListNode();
ListNode help = mergeNode;
//比較兩個鏈表當前的值，值小的鏈表就把參考賦給mergeNode，并向后移動一位重新賦值給自己，同時help指向值小的那個節點
while (left != null && right != null) {
if (left.val < right.val) {
help.next = left;
left = left.next;
} else {
help.next = right;
right = right.next;
}
help = help.next;
}
//最后如果有剩余的節點，就一次性鏈上去
help.next = left == null ? right : left;
return mergeNode.next;
}
- 執行時間：100.00%；記憶體消耗：83.65%；
- 最無腦的做法是排序，這題不管x給什么，只需要對鏈表進行一次排序，既能滿足題目要求，之前的題目中有練習過插入排序、歸并排序，隨便哪一種都可以，當然歸并的效率更高一點；
4.2.3 頭插法
public ListNode partition(ListNode head, int x) {
ListNode dummy = new ListNode();
dummy.next = head;
while (head != null && head.next != null) {
int nextVal = head.next.val;
if (nextVal < x) {
ListNode next = head.next;
head.next = head.next.next;
next.next = dummy.next;
dummy.next = next;
} else {
head = head.next;
}
}
return dummy.next;
}
- 執行時間：100.00%；記憶體消耗：20.44%；
- 逐個遍歷，遇到小于x值的節點，就插到頭部；
- PS：Java中HashMap，jdk1.8之前，擴容時鏈表采用的就是頭插法（存在死回圈的問題，1.8改了）；
4.2.4 原地洗掉
public ListNode partition(ListNode head, int x) {
ListNode dummy = new ListNode();
dummy.next = head;
ListNode smallDummy = new ListNode();
ListNode small = smallDummy;
//和洗掉節點的套路一樣，先處理頭節點滿足條件的情況
while (head != null) {
if (head.val >= x) {
break;
}
small.next = new ListNode(head.val);
small = small.next;
head = head.next;
}
//洗掉
ListNode cur = head;
ListNode pre = null;
while (cur != null) {
if (cur.val < x) {
pre.next = cur.next;
small.next = new ListNode(cur.val);
small = small.next;
} else {
pre = cur;
}
cur = cur.next;
}
small.next = head;
return smallDummy.next;
}
- 執行時間：100.00%；記憶體消耗：56.22%；
- 按照洗掉節點的方式，遇到小于x值的節點，就從原鏈表中洗掉，并添加到新的鏈表中，這樣一次遍歷結束后，只要把新的鏈表連上原鏈表即可；
5. 鏈表求和 [medium]
5.1 考慮點
- 需要考慮鏈表長度不一導致的空指標例外問題；
- 進階的思考：
- 鏈表長度不一時的對位問題，如（1 -> 2 -> 3 -> 4）和（5 -> 6 -> 7），這里5對2而不是1；
- 上述問題可以遍歷鏈表，用0占位解決；
5.2 解法
5.2.1 反向存放法
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
if( l1 == null && l2 == null){
return null;
}
ListNode cur1 = l1;
ListNode cur2 = l2;
int cache = 0;
boolean isFirst = true;
ListNode head = null;
ListNode index = null;
while( cur1 != null || cur2 != null){
//加法
int value = https://www.cnblogs.com/dlhjw/p/0;
if( cur1 == null){
value = cur2.val + cache;
cur2 = cur2.next;
} else if ( cur2 == null){
value = cur1.val + cache;
cur1 = cur1.next;
} else {
value = cur1.val + cur2.val + cache;
cur1 = cur1.next;
cur2 = cur2.next;
}
//進位在cache儲存
cache = value / 10;
//構造新節點，新節點指向新節點
ListNode node = new ListNode(value%10);
if(isFirst){
head = node;
index = node;
isFirst = false;
} else {
index.next = node;
index = node;
}
}
//判斷cache
if(cache != 0){
ListNode node = new ListNode(cache);
index.next = node;
}
return head;
}
- 執行時間：97.51%；記憶體消耗：33.72%；
- 通常做法：逐個遍歷，進位，構建新節點；
5.2.2 遞回法
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode head = new ListNode(0);
helper(head, l1, l2, 0);
return head.next;
}
private void helper(ListNode result, ListNode l1, ListNode l2, int carry) {
if (l1 == null && l2 == null && carry == 0){
return;
}
int sum = (l1 != null ? l1.val : 0) + (l2 != null ? l2.val : 0) + carry;
result.next = new ListNode(0);
result.next.val = sum % 10;
carry = sum / 10;
helper(result.next, l1 != null ? l1.next : null, l2 != null ? l2.next : null, carry);
}
- 執行時間：100.00%；記憶體消耗：26.25%；
6. 回文鏈表 [easy]
6.1 考慮點
- 對于鏈表，可以思考的角度有：改變鏈表方向、拼接、成環等；
- 需要問清楚面試官是否可以開辟額外空間；
- 需要問清楚面試官是否可以修改鏈表；
6.2 解法
6.2.1 改變方向雙向遍歷法（優）
public boolean isPalindrome(ListNode head) {
if(head == null){
return true;
}
//統計鏈表長度
ListNode cur = head;
int count = 0;
while( cur != null ){
count++;
cur = cur.next;
}
if( count < 2){
return true;
}
//改變前 count/2-1 個節點指向，分奇偶討論
ListNode right = head;
//定位right指標
if( count % 2 == 1 ){
//奇數情況
for( int i = 0; i < count/2+1; i++){
right = right.next;
}
} else {
//偶數情況
for( int i = 0; i < count/2; i++){
right = right.next;
}
}
//改變前count/2-1個節點方向
ListNode left = head;
cur = head.next;
ListNode mid = cur.next;
//判斷對只有2~3個節點單獨判斷
if(count < 4){
return left.val == right.val;
}
for( int i = 0; i < count/2-1; i++){
cur.next = left;
left = cur;
cur = mid;
mid = mid.next;
}
//遍歷比較left和right
while(right != null){
if(left.val != right.val){
return false;
}
right = right.next;
left = left.next;
}
return true;
}
- 執行時間：96.85%；記憶體消耗：80.19%；
- 不使用額外空間；
- 需要注意，是否可以改變原鏈表；
6.2.2 將值復制到陣列中后用雙指標法
public boolean isPalindrome(ListNode head) {
List<Integer> vals = new ArrayList<Integer>();
// 將鏈表的值復制到陣列中
ListNode currentNode = head;
while (currentNode != null) {
vals.add(currentNode.val);
currentNode = currentNode.next;
}
// 使用雙指標判斷是否回文
int front = 0;
int back = vals.size() - 1;
while (front < back) {
if (!vals.get(front).equals(vals.get(back))) {
return false;
}
front++;
back--;
}
return true;
}
- 執行時間：32.69%；記憶體消耗：24.77%；
- 時間復雜度：O(n)，其中 n 指的是鏈表的元素個數；
- 第一步： 遍歷鏈表并將值復制到陣列中，O(n)，
- 第二步：雙指標判斷是否為回文，執行了 O(n/2) 次的判斷，即 O(n)，
- 總的時間復雜度：O(2n) = O(n)，
- 空間復雜度：O(n)，其中 n 指的是鏈表的元素個數，我們使用了一個陣列串列存放鏈表的元素值；
- 需要開辟額外空間；
6.2.3 遞回
private ListNode frontPointer;
private boolean recursivelyCheck(ListNode currentNode) {
if (currentNode != null) {
if (!recursivelyCheck(currentNode.next)) {
return false;
}
if (currentNode.val != frontPointer.val) {
return false;
}
frontPointer = frontPointer.next;
}
return true;
}
public boolean isPalindrome(ListNode head) {
frontPointer = head;
return recursivelyCheck(head);
}
- 執行時間：56.10%；記憶體消耗：5.05%；
- 時間復雜度：O(n)，其中 n 指的是鏈表的大小；
- 空間復雜度：O(n)，其中 n 指的是鏈表的大小， 這種方法不僅使用了 O(n)的空間，且比第一種方法更差，因為在許多語言中，堆疊幀的開銷很大（如 Python），并且最大的運行時堆疊深度為 1000（可以增加，但是有可能導致 底層解釋程式記憶體出錯），為每個節點創建堆疊幀極大的限制了演算法能夠處理的最大鏈表大小；
7. 鏈表相交 [easy]
7.1 考慮點
- 這里不能使用鏈表反轉，題目要求不能破壞原有結構；
- 對于兩條長度不同的鏈表而言，可以先遍歷求出各自的長度再做計算，也可以使用；兩個指標走完兩條鏈表，最后必然能重合，因為指標的速度（步長）的一樣的；
- 需要問清楚面試官是否可以開辟額外空間；
7.2 解法
7.2.1 長度對齊雙指標法
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if( headA == null || headB == null ){
return null;
}
ListNode cur = headA;
int countA = 0;
while( cur != null ){
countA++;
cur = cur.next;
}
cur = headB;
int countB = 0;
while( cur != null){
countB++;
cur = cur.next;
}
//保證headA長于headB
if( countA < countB){
return getIntersectionNode(headB,headA);
}
ListNode curA = headA;
ListNode curB = headB;
for( int i = 0; i < countA-countB; i++){
curA = curA.next;
}
while( curA != null ){
if( curA.equals(curB) ){
return curA;
}
curA = curA.next;
curB = curB.next;
}
return null;
}
- 執行時間：100.00%；記憶體消耗：57.18%；
- 時間復雜度：O(A+B)，A和B是兩個鏈表的長度；
- 空間復雜度：O(1)；
7.2.2 雙指標（優）
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode h1 = headA;
ListNode h2 = headB;
while(h1 != h2){
h1 = (h1 == null ? headB : h1.next);
h2 = (h2 == null ? headA : h2.next);
}
return h1;
}
- 執行時間：100.00%；記憶體消耗：57.18%；
- 對于h1來說，走到末尾（或相交點）時，走了兩段鏈表（兩段鏈表不同部分）的路徑；
- 對于h2來說，走到末尾（或相交點）時，走了兩段鏈表（兩段鏈表不同部分）的路徑；
- h1和h2走過的路徑相同，因此第二輪就能匹配到；
8. 環路檢測 [medium]
8.1 考慮點
- 處理環形鏈表可以試試快慢指標；
8.2 解法
8.2.1 快慢指標法（優）
public ListNode detectCycle(ListNode head) {
if( head == null ){
return null;
}
if(head.next == null){
return null;
}
if(head.next.next == null){
return null;
}
//使用快慢指標找到有count個環成圈;
ListNode fast = head.next.next;
ListNode slow = head.next;
int count = 1; //count變數不是必要的
while( fast != slow ){
if(fast == null || slow == null){
return null;
}
slow = slow.next;
if(fast.next != null){
fast = fast.next.next;
} else {
return null;
}
count++;
}
// cur 和 slow 一起走，走n步到環路開頭節點
ListNode cur = head;
while( cur != slow ){
cur = cur.next;
slow = slow.next;
}
return cur;
}
- 執行時間：100.00%；記憶體消耗：53.71%；
- 時間復雜度：O(n)，n為不成環的節點和成環節點的較大值；
- 空間復雜度：O(1)，不開辟額外空間，演算法中的count不是必要的；
- 演算法解釋：演算法主要分為兩個部分，如下：
- 使用快慢指標找到有count個環成圈：走x步到達下標為x的節點，可以通過快慢指標獲得count（或count的質因數）個節點成圈，同時慢指標走了count步（此時快慢指標所指節點下標為count），假設環路開頭節點的下標為 n（n<=count），從鏈表頭走要走n步到環路開頭節點；
- 走n步到環路開頭節點：從鏈表頭到快慢指標處走count步，從鏈表頭到環路開頭節點要n步，如果要從環路開頭節點走到快慢指標處要走count-n步；如果要從環路開頭節點再一次回到開頭節點必須走完一個圈（或n圈），即走count步，那么從快慢指標處走到開頭節點至少就要count-(count-n)=n步，而我們從鏈表頭走到環路開頭節點也是要走n步；
8.2.2 哈希表
public ListNode detectCycle(ListNode head) {
ListNode pos = head;
Set<ListNode> visited = new HashSet<ListNode>();
while (pos != null) {
if (visited.contains(pos)) {
return pos;
} else {
visited.add(pos);
}
pos = pos.next;
}
return null;
}
- 執行時間：30.58%；記憶體消耗：24.80%；
- 時間復雜度：O(N)，其中 N 為鏈表中節點的數目，我們恰好需要訪問鏈表中的每一個節點；
- 空間復雜度：O(N)，其中 N 為鏈表中節點的數目，我們需要將鏈表中的每個節點都保存在哈希表當中；
最后
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/315940.html
標籤：其他
上一篇：關于對碎紙片拼接復原的理解