?148. 排序鏈表

題目鏈接：???????148. 排序鏈表

難度：中等

刷題狀態：1刷

新知識：

- `dic.reduceRight((t,c)=>(c.next=t,c),null)`??方法從數組的末尾開始執行

解題過程

思考

示例 1：

輸入：head = [4,2,1,3]
輸出：[1,2,3,4]

當然可以轉成數組排序再生成鏈表，但我感覺這考點應該不是這個

題解分析

參考題解鏈接：240. 搜索二維矩陣 II（貪心，清晰圖解）

好吧，可以這么寫，，而且速度還挺快

詳細分析如下

var sortList = function(head) {let dic=[]while(head){//將當前節點壓入數組中dic.push(head)head=head.next}    dic.sort((a,b)=>a.val-b.val)
//reduceRight 方法從數組的末尾開始執行，逐步向數組的開頭移動。
//reduceRight 的回調函數接受兩個參數：累加器 t 和當前值 c。//t（累加器）：在每次迭代中，t 代表已經連接好的鏈表部分。在第一次迭代時，t 是 null，因為鏈表的最后一個節點的 next 應該是 null。//(c.next = t, c) 是一個使用逗號運算符的表達式。
//c.next = t：將當前節點 c 的 next 指針指向累加器 t。這樣就將當前節點連接到了已經連接好的鏈表部分。
//c：逗號運算符會返回其第二個操作數的結果，因此這里返回的是當前節點 c。這個返回值將成為下一次迭代中的累加器 t。return dic.reduceRight((t,c)=>(c.next=t,c),null)
}

手搓答案（無非廢話版）

/*** Definition for singly-linked list.* function ListNode(val, next) {*     this.val = (val===undefined ? 0 : val)*     this.next = (next===undefined ? null : next)* }*/
/*** @param {ListNode} head* @return {ListNode}*/var sortList = function(head) {let dic=[]while(head){dic.push(head)head=head.next}dic.sort((a,b)=>a.val-b.val)return dic.reduceRight((t,c)=>(c.next=t,c),null)
}

總結

?done

?????????23. 合并 K 個升序鏈表

題目鏈接：???????23. 合并 K 個升序鏈表

難度：困難

刷題狀態：1刷

新知識：

- `lists.flat()`

- `const flatArray = nestedArray.reduce((accumulator, currentValue) => {
? ? return accumulator.concat(currentValue);
}, []);` 拍平數組

解題過程

思考

示例 1：

輸入：lists = [[1,4,5],[1,3,4],[2,6]]
輸出：[1,1,2,3,4,4,5,6]
解釋：鏈表數組如下：
[1->4->5,1->3->4,2->6
]
將它們合并到一個有序鏈表中得到。
1->1->2->3->4->4->5->6

注意這里是鏈表數組

還是轉換成數組處理好了再生成鏈表

題解分析

參考題解鏈接：???????合并K個排序鏈表

手搓答案（無非廢話版）

/*** Definition for singly-linked list.* function ListNode(val, next) {*     this.val = (val===undefined ? 0 : val)*     this.next = (next===undefined ? null : next)* }*/
/*** @param {ListNode[]} lists* @return {ListNode}*/
var mergeKLists = function(lists) {let dic=[]for(let l of lists){while(l){dic.push(l.val)l=l.next}}dic.sort((a,b)=>a-b)let dum=new ListNode(dic[0]),cur=dumif(!dic.length) return dum.nextfor(let i=1;i<dic.length;i++){cur.next=new ListNode(dic[i])cur=cur.next}return dum
};

總結

done

?????????146. LRU 緩存

題目鏈接：???????146. LRU 緩存

難度：中等

刷題狀態：1刷

新知識：

- `this.cache.keys().next().value;`??這行代碼用于獲取?Map?對象中最舊的鍵（即第一個插入的鍵）

解題過程

思考

示例：

輸入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
輸出
[null, null, null, 1, null, -1, null, -1, 3, 4]解釋
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 緩存是 {1=1}
lRUCache.put(2, 2); // 緩存是 {1=1, 2=2}
lRUCache.get(1);    // 返回 1
lRUCache.put(3, 3); // 該操作會使得關鍵字 2 作廢，緩存是 {1=1, 3=3}
lRUCache.get(2);    // 返回 -1 (未找到)
lRUCache.put(4, 4); // 該操作會使得關鍵字 1 作廢，緩存是 {4=4, 3=3}
lRUCache.get(1);    // 返回 -1 (未找到)
lRUCache.get(3);    // 返回 3
lRUCache.get(4);    // 返回 4

一看就沒刷過，直接看答案

題解分析

參考題解鏈接：240. 搜索二維矩陣 II（貪心，清晰圖解）

詳細分析如下

/*** @param {number} capacity*///LRUCache(int capacity) 以 正整數 作為容量 capacity 初始化 LRU 緩存
var LRUCache = function(capacity) {this.capacity = capacity; // 初始化緩存的最大容量this.cache = new Map();   // 使用 Map 對象來存儲緩存的鍵值對
};/** * @param {number} key* @return {number}*///int get(int key) 如果關鍵字 key 存在于緩存中，則返回關鍵字的值，否則返回 -1 。
LRUCache.prototype.get = function(key) {if (!this.cache.has(key)) {return -1; // 如果緩存中沒有這個key，返回-1}// 獲取值，并將該鍵值對移到 Map 的末尾，表示最近使用const value = this.cache.get(key);this.cache.delete(key);this.cache.set(key, value);return value;
};/** * @param {number} key * @param {number} value* @return {void}*///void put(int key, int value) 如果關鍵字 key 已經存在，則變更其數據值 value ；如果不存在，則向緩存中插入該組 key-value 。如果插入操作導致關鍵字數量超過 capacity ，則應該 逐出 最久未使用的關鍵字。
LRUCache.prototype.put = function(key, value) {if (this.cache.has(key)) {// 如果鍵已經存在，刪除舊記錄this.cache.delete(key);} else if (this.cache.size >= this.capacity) {// 如果緩存已滿，刪除最舊的記錄//this.cache 是一個 Map 對象。// keys() 方法返回一個迭代器對象，該迭代器對象按插入順序包含 Map 對象中所有的鍵。// .next():// next() 方法被調用在迭代器對象上，用于獲取迭代器中的下一個值。// next() 返回一個對象，該對象具有兩個屬性：value 和 done。// value 是當前迭代的值（在這個情況下是一個鍵）。const oldestKey = this.cache.keys().next().value;this.cache.delete(oldestKey);}// 插入新記錄this.cache.set(key, value);
};/** * Your LRUCache object will be instantiated and called as such:* var obj = new LRUCache(capacity)* var param_1 = obj.get(key)* obj.put(key,value)*/

手搓答案（無非廢話版）

/*** @param {number[][]} matrix* @param {number} target* @return {boolean}*/var searchMatrix = function(matrix, target) {let tag=matrix[0].length-1for(let i=0;i<matrix.length;i++){if(matrix[i][0]>target) return falseif(matrix[i][matrix[i].length-1]<target) continuefor(let j=tag;j>=0;j--){if(matrix[i][j]==target) return trueif(matrix[i][j]>target){tag--}else{break}}}return false
}

總結

?難死了，不好理解，多看幾遍

?????????94. 二叉樹的中序遍歷

題目鏈接：??????????????94. 二叉樹的中序遍歷

難度：簡單

刷題狀態：1刷

新知識：

解題過程

思考

示例 1：

輸入：root = [1,null,2,3]
輸出：[1,3,2]

二叉樹經典問題，就是我忘了

題解分析

參考題解鏈接：???????二叉樹的中序遍歷

詳細分析如下

var inorderTraversal = function(root) {let res=[]//箭頭函數function inorder(root){if(!root) return //體現了中序遍歷的“先遍歷左子樹”的原則。inorder(root.left)//體現了中序遍歷的“訪問根節點”的步驟。res.push(root.val)//體現了中序遍歷的“再遍歷右子樹”的原則。inorder(root.right)}inorder(root)return res
};

手搓答案（無非廢話版）

/*** @param {TreeNode} root* @return {TreeNode} */var inorderTraversal = function(root) {let res=[]function inorder(root){if(!root) returninorder(root.left)res.push(root.val)inorder(root.right)}inorder(root)return res
}

總結

?拿下

?????????104. 二叉樹的最大深度

題目鏈接：?????????????????????104. 二叉樹的最大深度

難度：簡單

刷題狀態：2刷

新知識：

解題過程

思考

示例 1：

輸入：root = [3,9,20,null,null,15,7]
輸出：3

也是2刷了，放下1刷過程在題解

題解分析

參考題解鏈接：???????畫解算法：104. 二叉樹的最大深度

詳細分析如下

/*** @param {TreeNode} root* @return {number}*/
var maxDepth = function(root) {if(root){// console.log('root.left',root.left)// console.log('root.right',root.right)let left=maxDepth(root.left)let right=maxDepth(root.right)return Math.max(left,right) +1}else{return 0}
};

手搓答案（無非廢話版）

/*** @param {TreeNode} root* @return {number}*/
var maxDepth = function(root) {let res=0,i=0function depth(root){if(!root){res=Math.max(res,i)return }i++let tmp=idepth(root.left)i=tmpdepth(root.right)}depth(root)return res
};

總結

?emm,我用的是套路

?????????101. 對稱二叉樹

題目鏈接：????????????????????????????101. 對稱二叉樹

難度：簡單

刷題狀態：2刷

新知識：

解題過程

思考

示例 1：

輸入：root = [1,2,2,3,4,4,3]
輸出：true

也是2刷了，放下1刷過程在題解

沒寫出來555

題解分析

參考題解鏈接：???????對稱二叉樹

詳細分析如下

/*** Definition for a binary tree node.* function TreeNode(val, left, right) {*     this.val = (val===undefined ? 0 : val)*     this.left = (left===undefined ? null : left)*     this.right = (right===undefined ? null : right)* }*/
/*** @param {TreeNode} root* @return {boolean}*/
function check(L,R){if(!L&&!R) return trueif(!L||!R) return falselet ret=L.val==R.valreturn ret&&check(L.left,R.right)&&check(L.right,R.left)}
var isSymmetric = function(root) {let res=check(root.left,root.right)return !root||res
};

手搓答案（無非廢話版）

/*** Definition for a binary tree node.* function TreeNode(val, left, right) {*     this.val = (val===undefined ? 0 : val)*     this.left = (left===undefined ? null : left)*     this.right = (right===undefined ? null : right)* }*/
/*** @param {TreeNode} root* @return {boolean}*/var isSymmetric = function(root) {function check(l,r){if(!l&&!r) return trueif(!l||!r) return falsereturn l.val==r.val&&check(l.left,r.right)&&check(l.right,r.left)}return root?check(root.left,root.right):true
};

總結

?emm,我用的是套路