一周力扣刷題筆記（10月31日）

這周的刷題主要是針對于堆疊的內容進行的，也包括了一些對于鏈表知識的整理與回顧

旋轉鏈表

給你一個鏈表的頭節點 head ，旋轉鏈表，將鏈表每個節點向右移動 k 個位置，

這道題最開始的基本思路是分成兩部分操作，向右移動的話，只要將后面k個位置的節點移動到頭節點，就可以了，但這種方法的邊界條件過多，而且由于要多次操作整個鏈表，因此要定義多個頭指標來遍歷陣列，非常麻煩，最重要的是，當K遠于鏈表長度，這種方式是無法處理的（失敗版本）

var rotateRight = function(head, k) {
let len = 0;
let len2 = 0;
let res = head;
let res2 = head;
if (head == null || head.next == null) { return head }
if (k < 2) { return head }
while (res2.next != null) {
    len2++;
    res2 = res2.next;
}
len2++;
k = k % len2;
while (len != k) {
    len++;
    res = res.next
}
let temp = res.next;
res.next = null;
let tem = temp
while (tem.next != null) {
    tem = tem.next
}
tem.next = head;
return temp
}

更好的做法是采用回圈鏈表的方式，直接重新定義頭節點，利用環形鏈表的特定，直接將已經遍歷到為尾部的指標重新連接到頭部，通過操作指標的方式，找到移動過后的頭節點，再進行分割，就達到了后移的目的，同時，利用環形鏈表的節點數可以取余也有效的解決了K值大于鏈表長的問題

var rotateRight = function(head, k) {
if (k === 0 || !head || !head.next) {
    return head; //除去邊界條件
}
let n = 1;
let cur = head;
// 先遍歷出鏈表的長度
while (cur.next) {
    cur = cur.next;
    n++;
}

let add = n - k % n; //注意環形鏈表
// 移動整數倍直接回傳頭節點
if (add === n) {
    return head;
}
//    使鏈表稱為一個環形鏈表
cur.next = head;
//將節點后移，利用環形鏈表直接后移
while (add) {
    cur = cur.next;
    add--;
}
const ret = cur.next;
// 利用cur.next=null將環形鏈表分割
cur.next = null;
return ret;
};

兩兩交換鏈表中的節點

給定一個鏈表，兩兩交換其中相鄰的節點，并回傳交換后的鏈表，

你不能只是單純的改變節點內部的值，而是需要實際的進行節點交換，

這道題的難度并不大，主要是要理清楚交換兩個節點的順序，對于單向鏈表而言，由于只能訪問大后面的節點，因此操作節點一定要從后往前進行操作，防止出現節點丟失的問題

var swapPairs = function(head) {
let headnode = new ListNode(); //重新定義一個空的頭節點用于輔助
headnode.next = head;
let res = headnode;
console.log(res)
while (res.next != null && res.next.next != null) { //(temp.next && temp.next.next) 條件可以寫成這種形式
    let tmp = res.next.next; //先保存后一位的節點
    res.next.next = res.next.next.next; //將前節點的next連接到后一位節點的next
    tmp.next = res.next;    //將后節點放到前節點之前
    res.next = tmp; //將后一位節點連接到前節點的前一位（輔助節點的下一位）
    res = res.next.next;  //指標往后移動兩位（每次操作了兩位）
}
return headnode.next;
};

洗掉排序鏈表中的重復元素

** 存在一個按升序排列的鏈表，給你這個鏈表的頭節點 head ，請你洗掉所有重復的元素，使每個元素 只出現一次 ，**

這道題目相對比較簡單，基本就是一般的遍歷回圈并判斷，但要注意的一點是，在這道題里如果發生了節點洗掉，指標是不移動到下一位的，否則當出現連續的重復元素時，指標在第一次洗掉元素后跳到了剩余的相同元素的下一位，相當于跳過了一個相同元素，最后就會出現重復元素消除不徹底的情況

var deleteDuplicates = function(head) {
let res = head;
while (1) {
    if (!res || !res.next) { break; }
    if (res.next.val == res.val) {
        res.next = res.next.next;
    } else { //注意這里要有else，否則多個連續的重復數字無法去重
        res = res.next;
    }
}
return head;
}

洗掉排序鏈表中的重復元素2

存在一個按升序排列的鏈表，給你這個鏈表的頭節點 head ，請你洗掉鏈表中所有存在數字重復情況的節點，只保留原始鏈表中 沒有重復出現 的數字， 回傳同樣按升序排列的結果鏈表，

跟前面的題目類似，但難度明顯大了很多，這道題要求去掉所有鏈表中發生過重復的元素，這里不僅僅是要多考慮后面一個節點，還要考慮連續重復的節點需要一直舍棄的問題，因此當出現重復元素時先保存這個值，然后一直往后遍歷直到后面的值與這個保存的值不相等為止，在這個程序中迭代指標去掉所有重復的元素（指標最后指向的是不重復的元素）

  var deleteDuplicates = function(head) {
    let headnode = new ListNode();
    headnode.next = head;
    let res = headnode;
    let las = res;
    let temp;
    if (!res.next) { return res.next }
    while (true) {
        if (!res.next.next) { break; } //后面只有一個元素必不可能重復
        // 這里要跟下面對應起來，會進行貪婪去重，當回圈結束時指標以及指標前面一定沒有重復元素
        if (res.next.val == res.next.next.val) {
            temp = res.next.val;
            while (res.next.val == temp) {
                res.next = res.next.next;
                // 回圈指標直到沒有重復元素為止，注意此時最后最后一次去完后，后面哪一項一定不與前面的重復
                if (!res.next) { return las.next }
            }
        } else {
            res = res.next;
            // 繼續指向下一個節點
        }
    }
    return las.next;
	};

分割鏈表

給你一個鏈表的頭節點 head 和一個特定值 x ，請你對鏈表進行分隔，使得所有 小于 x 的節點都出現在 大于或等于 x 的節點之前， 你應當 保留 兩個磁區中每個節點的初始相對位置，

這道題我最開始的基本思路是，由于只要讓所有小的出現在一邊，大的出現在另一邊，那么在一次遍歷時，定義兩個鏈表，一個存放比x小的所有節點，另一個存放比x大的所有節點，最后將兩個鏈表和x拼接起來就可以了，

   var partition = function(head, x) {
    let onehead = new ListNode(0);
    onehead.next = head;
    head = onehead;
    let res = head;
    let lastnode = new ListNode(0);
    let last = lastnode;
    let headnode = new ListNode(0);
    let bef = headnode;
    while (1) {
        if (res.val == x) {
            last.next = null;
            break;
        }
        if (res.next.val > x) {
            last.next = res.next;
            last = last.next;
            res.next = res.next.next;
        }
        res = res.next
    }
    while (1) {
        if (!res.next) { break; }
        if (res.next.val < x) {
            bef.next = res.next;
            bef = bef.next;
            res.next = res.next.next;
        } else {
            res = res.next
        }
    }
    head = head.next;
    lastnode = lastnode.next;
    bef.next = head;
    res.next = lastnode;
    return headnode.next
	};

這種方式是能夠在多數情況符合要求的，但少數情況下會由于這個代碼保留了x兩邊的節點，導致一些時候沒有保留相對位置，其實正確的解法跟我的思路基本是一樣的，但他僅僅拆分成立小于x和大于等于x的部分，在簡化代碼的同時也保留了相對位置，防止了邊界條件，同時，下面這個程式巧妙地運用了=從右往左計算的性質，只用一個指標遍歷了一遍鏈表，效率更高

var partition = function(head, x) {
let pA = a = new ListNode(0),
    pB = b = new ListNode(0)		//利用等號處理簡化代碼
while (head) {
    head.val < x ? a = a.next = head : b = b.next = head
        //利用等號的處理順序簡化代碼
    head = head.next
}
a.next = pB.next
b.next = null //注意將后面鏈表的next置空
return pA.next
};

所有顯然我考慮問題還不夠周全，差了一點點
##簡化路徑
給你一個字串 path ，表示指向某一檔案或目錄的 Unix 風格 絕對路徑 （以 ‘/’ 開頭），請你將其轉化為更加簡潔的規范路徑，

• 在 Unix 風格的檔案系統中，一個點（.）表示當前目錄本身；此外，兩個點 （…） 表示將目錄切換到上一級（指向父目錄）；兩者都可以是復雜相對路徑的組成部分，任意多個連續的斜杠（即，’//’）都被視為單個斜杠 ‘/’ ， 對于此問題，任何其他格式的點（例如，’…’）均被視為檔案/目錄名稱，

• 請注意，回傳的 規范路徑 必須遵循下述格式：

• 始終以斜杠 ‘/’ 開頭，

• 兩個目錄名之間必須只有一個斜杠 ‘/’ ，

• 最后一個目錄名（如果存在）不能 以 ‘/’ 結尾，
  *此外，路徑僅包含從根目錄到目標檔案或目錄的路徑上的目錄（即，不含 ‘.’ 或 ‘…’），

• 回傳簡化后得到的 規范路徑 ，

這道題明顯是要我們使用堆疊進行解題，按照linux的規則，遇到檔案名進堆疊；遇到’…/‘出堆疊，遇到’./'直接繼續遍歷，注意檔案名是多個字串，要先對字串陣列做一些處理，轉化為檔案名和特殊符號的形式，最后還有對邊界條件進行處理

var simplifyPath = function(path) {
path = path.split("");
if (path[path.length - 1] != '/') { path.push('/') }
let arr = [];
let stk = [];
let str = '';
// 先對陣列進行處理,將其轉變為/與檔案名/特殊符號的形式
for (let i = 0; i < path.length; i++) {
    if (path[i] == '/') {
        if (str != '') { //注意檔案名是多個字符,需要先保存再一并 加入
            arr.push(str);
            str = '';
        }
        continue;
    } else {
        str += path[i];
    }
}
console.log(arr)
for (let i = 0; i < arr.length; i++) {
    if (arr[i] != "." && arr[i] != '..') {
        stk.push(arr[i]); //不等于特殊符號默認檔案名,直接進堆疊
    } else if (arr[i] == ".") {
        continue; //遇到'./'同級檔案,跳過
    }
    if (arr[i] == '..' && stk != []) {
        stk.pop(); //遇到../出堆疊,注意判斷非空條件
    }
}
// 最后加入/并對邊界條件做一些處理
let las = stk.join("/").split("");
if (las[0] != '/') { las.unshift("/") }
return las.join("")
};	

這個演算法還可以優化，比如處理字串的那一步，我們可以直接通過split這個API進行處理，對回圈和邊界條件的處理的寫法也可以化簡

   const dir = path.split('/'),
    stack = []
	for (const i of dir) {
    // 特殊情況直接跳過
    if (i === '.' || i === '') continue
        // 遇到'..'入堆疊
    if (i === '..') {
        stack.length > 0 ? stack.pop() : null
        continue
    }
    //其他情況直接進堆疊
    stack.push(i)
	}
	// 直接在return處處理結果
	return '/' + stack.join('/')

有效的括號

** 給定一個只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字串 s ，判斷字串是否有效，**

• 有效字串需滿足：

• 左括號必須用相同型別的右括號閉合，

• 左括號必須以正確的順序閉合，

還是經典的堆疊的運用，不管我們右多少括號，處理的時候只要處理堆疊頂就可以了，如果匹配到左括號就入堆疊，匹配到右括號就跟堆疊頂進行比較，如果跟堆疊頂的左括號無法匹配，就說明匹配失敗，這組括號是非法的，否則就將堆疊頂出堆疊，如果最后堆疊空，說明一一匹配完畢，括號組合法，

對于代碼的撰寫，我們可以選擇使用map進行匹配，或者暴力else if進行配對判斷，但這里我們可以靈活使用堆疊，但匹配到左括號時，讓對應的右括號入堆疊，這樣當匹配到右括號時只需要比較右括號跟堆疊頂的元素是否相等，這種寫法大大減少了我們的代碼量

var isValid = function(s) {
const stack = [];
for (let val of s) {
    console.log(stack)
    if (val === '(') stack.push(')');
    else if (val === '[') stack.push(']');
    else if (val === '{') stack.push('}');
    else if (stack.length === 0 || val !== stack.pop()) return false;
}
return stack.length === 0;
};

最長有效括號

給你一個只包含 ‘(’ 和 ‘)’ 的字串，找出最長有效（格式正確且連續）括號子串的長度，

跟上一道題很相似，但這里要回傳最長的字串長度，最開始我的思路是設定兩個堆疊，當匹配到左括號時不斷入其中一個堆疊（常堆疊），當匹配到右括號時，常堆疊出堆疊并將出堆疊的元素push進另一個堆疊（臨時堆疊），記錄臨時堆疊的長度，當常堆疊匹配的程序種發現無法匹配到有效括號時，臨時堆疊清，重新添加并挑戰最大長度，代碼實作如下：

var longestValidParentheses = function(s) {
    let stk = [];
    let max = 0;
    let temp = [];
    s = s.split("");
    for (let i = 0; i < s.length; i++) {
        if (stk.length == 0 && s[i] == ")") {
            console.log(temp)
            temp = [];
            continue;
        }
        if (s[i] == "(") {
            stk.push(s[i]);
        }
        if (stk.length != 0 && s[i] == ")") {
            temp.push(stk[stk.length - 1]);
            temp.push(s[i]);
            stk.pop();
            if (temp.length > max) {
                max = temp.length;
            }
        }
    }
    return max;
}

但這種演算法存在問題，先不考慮開辟兩個堆疊的記憶體消耗，如果出現像"(()"這種"最長有效括號在無效括號中"的情況，這種方法會匹配失敗，

正確的解決方法是，通過保存下標并與起始下標相減來獲得最大長度，基本原則是匹配到左括號進堆疊，匹配到右括號時，先出堆疊，如果堆疊非空，就通過下標計算長度并挑戰最大長度，如果堆疊空，說明之前已經匹配完一組合法的括號，且新push進來的這個是不合法的，所有可以將他push進堆疊的第一項作為新的初始項，這里要注意一下初始項，由于下標是從0開始的，而且可能出現上面這種堆疊空進右括號的情況，所有我們需要定義一個初始值（-1）作為下標的第一位，之后出現上面的情況，就通過讓右括號下標進堆疊的方式重置這個下標

var longestValidParentheses = function(s) {
let stk = [];
let max = 0;
stk.push(-1);
for (let i = 0; i < s.length; i++) {
    if (s[i] == "(") {
        stk.push(i);
    } else {
        stk.pop();
        if (stk.length != 0) {
            max = Math.max(max, i - stk[stk.length - 1]);
        } else {
            stk.push(i)
        }
    }
}
return max;
};

二叉樹的中序遍歷

給定一個二叉樹的根節點 root ，回傳它的 中序 遍歷，

基礎題，不做過多解釋

  var inorderTraversal = function(root) {
    if (!root) { return [] }
    let res = [];
    allTree(root);

    function allTree(node) {
        if (node.left) {
            allTree(node.left);
        }
        res.push(node.val);
        if (node.right) {
            allTree(node.right);
        }
    }
    return res;
	};

二叉樹遍歷為鏈表

展開后的單鏈表應該同樣使用 TreeNode ，其中 right 子指標指向鏈表中下一個結點，而左子指標始終為 null ， 展開后的單鏈表應該與二叉樹 先序遍歷 順序相同，

了解了二叉數前序遍歷的話，這個題的思路還是很容易想到的，但要注意一些問題，一方面是這道題中涉及大量的節點修改，這種情況下，如果直接修改鏈表的話，我們需要定義大量的指標，而且程式也會比較臃腫，合理的方式是用陣列去保存所有節點，然后按順序處理成鏈表，這樣更有利于我們的處理，另外，力扣的console對于鏈表來說是不完整的!只會列印一部分，導致我在這道題上花費了大量的時間debug，以后要注意一下，

var flatten = function(root) {
const list = [];
preorderTraversal(root, list);
const size = list.length;
for (let i = 1; i < size; i++) {
    const prev = list[i - 1],
        curr = list[i];
    prev.left = null;
    prev.right = curr;
}
};

const preorderTraversal = (root, list) => {
if (root != null) {
    list.push(root);
    preorderTraversal(root.left, list);
    preorderTraversal(root.right, list);
}
}

柱狀圖中的最大矩形

給定 n 個非負整數，用來表示柱狀圖中各個柱子的高度，每個柱子彼此相鄰，且寬度為 1 ，求在該柱狀圖中，能夠勾勒出來的矩形的最大面積，

這道題的難度還是比較高的，需要發現一個規律：當新的柱子的高度小于堆疊頂的元素時，需要進行判斷，獲取到當前矩形的最大值并挑戰總的最大值，第一次自己寫代碼的時候，忽略了可能在新元素加入后，柱狀圖中間出現最大塊的情況

// 邊界條件考慮不足

var largestRectangleArea = function(heights) {
let stk = [];
let max = 0;
heights.unshift(0);
heights.push(0);
for (let i = 0; i < heights.length; i++) {
    console.log(stk, max);
    if (stk.length == 0 || (heights[i] >= stk[stk.length - 1])) {
        stk.push(heights[i]);
    }
    if (heights[i] < stk[stk.length - 1]) {
        let k = 0;
        while (stk[stk.length - 1] > heights[i]) {
            stk.pop();
            k++;
        }
        max = k * heights[i - k] > max ? k * heights[i - k] : max;
    }
}
return max;
};

正確答案對于這種情況的解決方案是：在每次判斷時，進行逐次回圈判斷，保證遍歷到每一種情況

  const largestRectangleArea = (heights) => {
    let maxArea = 0
    const stack = []
    heights = [0, ...heights, 0]
    for (let i = 0; i < heights.length; i++) { //只有小于才回圈，將相等的部分一并入堆疊
        while (heights[i] < heights[stack[stack.length - 1]]) { // 當前bar比堆疊頂bar矮
            const stackTopIndex = stack.pop() // 堆疊頂元素出堆疊，并保存堆疊頂bar的索引
            maxArea = Math.max( // 計算面積，并挑戰最大面積
                maxArea, // 計算出堆疊的bar形成的長方形面積
                //這里中間逐次比較，防止出現某幾項過高的邊界條件
                heights[stackTopIndex] * (i - stack[stack.length - 1] - 1)
            )
        }
        stack.push(i) // 當前bar比堆疊頂bar高了，入堆疊
    }
    return maxArea
	}

小結

• 處理鏈表時，如果出現需要大量移動鏈表元素的情況時，可以考慮使用回圈鏈表（基本的位置順序不變）或者使用陣列暫時存放節點（鏈表的整體順序會出現比較大的改變）來取代大量修改節點的操作，注意用陣列暫時存放節點時，要將next置為null清空，重新組織時再重新連接否則容易出現節點回圈，對于回圈鏈表，也要注意拆開節點的方法是將拆分點的next置為null
• 對鏈表的洗掉活修改注意從后往前進行，防止出現節點丟失的情況
• 注意邊界條件，當出現類似二分法的處理時，可以以小于和大于等于為一組，更便于處理
• 使用堆疊時，push進堆疊的不一定是元素本身，元素的下標，元素對應的部分，甚至與其不相干的部分都可以，很多時候對入堆疊出堆疊的元素的合理選擇能簡化我們的思路和操作
• 可以根據情況再堆疊的兩邊添加參照物，方便我們處理，這個參照物可以是動態更改的