南宁网络公司网站建设,wordpress配置资源,汉川网站开发,网站建设公司网站模板文章目录 41 排序链表42 合并k个升序链表43 LRU缓存44 二叉树的中序遍历45 二叉树的最大深度 41 排序链表 递归 归并排序找到链表中心点#xff0c;从中心点将链表一分为二。奇数个节点找中心点#xff0c;偶数个节点找中心左边的点作为中心点。快慢指针找中心点#xff0c… 文章目录 41 排序链表42 合并k个升序链表43 LRU缓存44 二叉树的中序遍历45 二叉树的最大深度 41 排序链表 递归 归并排序找到链表中心点从中心点将链表一分为二。奇数个节点找中心点偶数个节点找中心左边的点作为中心点。快慢指针找中心点当快指针移动到该段链表的最后一个元素时慢指针所指向的节点为中心点。找到中心点后中心点.next null将链表从中间断开。分别将前一半链表的头节点head和后一半链表的头节点中心点.next进行下一次划分。注意快慢指针初始化时快指针比慢指针快一步方便链表只有2个节点时划分链表。合并有序链表 (1) 建立新节点作为新链表的哨兵节点。 (2) leftright 分别指向两个链表的头部比较两个指针处节点值的大小从小到大插入到有序链表中指针交替前进直至其中一个链表为空。将剩余的链表直接插入到有序链表的尾部。 (3) 返回哨兵节点.next。
/*** Definition for singly-linked list.* function ListNode(val, next) {* this.val (valundefined ? 0 : val)* this.next (nextundefined ? null : next)* }*/
/*** param {ListNode} head* return {ListNode}*/
var sortList function(head) {if(head null || head.next null){ // 1个节点或0个节点return head;}let slow head, fast head.next;while(fast ! null fast.next ! null){ // 奇数个节点fast null停止偶数个节点fast.next null停止slow slow.next;fast fast.next.next;}let tmp slow.next;slow.next null;let left sortList(head);let right sortList(tmp);let dummy new ListNode();let res dummy;while(left ! null right ! null){if(left.val right.val){dummy.next left;left left.next;}else{dummy.next right;right right.next;}dummy dummy.next;} dummy.next left? left: right;return res.next;
};42 合并k个升序链表 方法1最小堆。将头节点放入堆中弹出最小值node此时将node.next放入堆中一直取到堆为空为止每次取出最小值时都将最小值的下一个节点放入堆中。方法2分治。这里给出该方法的代码。将链表数组lists一分为二先合并前一半链表再合并后一半链表最后完成全部链表的合并。中心点为mid前一半链表的区域为[左mid]后一半链表的区域为[mid 1右]。
/*** Definition for singly-linked list.* function ListNode(val, next) {* this.val (valundefined ? 0 : val)* this.next (nextundefined ? null : next)* }*/var merge function(left, right){let dummy new ListNode();let cur dummy;while(left ! null right ! null){if(left.val right.val){cur.next left;left left.next;}else{cur.next right;right right.next;}cur cur.next;}cur.next left? left: right;return dummy.next;
}/*** param {ListNode[]} lists* return {ListNode}*/
var mergeKLists function(lists) {function partition(i, j){if(i j){ // 区域内只有1个值return lists[i];}if(i j){ // 非法区域return null;}let mid Math.floor((i j) / 2);let left partition(i, mid);let right partition(mid 1, j);return merge(left, right);}return partition(0, lists.length - 1)
};43 LRU缓存 哈希表 双向链表put ① key不存在创建新节点添加进哈希表添加到链表头部。如果当前容量 capacity删除链表尾部节点删除哈希表中对应的项。 ② key存在通过哈希表找到key所在的节点改变value移动到链表头部。get ① key不存在返回 -1。 ② key存在通过哈希表找到key所在的节点移动到链表头部返回value。这里给出的代码直接使用哈希表实现各类操作。this.map.delete(key); this.map.set(key, value);先删除再将该节点添加到最后。this.map.keys().next().value;哈希表中第一个键值。
/*** param {number} capacity*/
var LRUCache function(capacity) {this.capacity capacity;this.map new Map();
};/** * param {number} key* return {number}*/
LRUCache.prototype.get function(key) {if(this.map.has(key)){let value this.map.get(key);this.map.delete(key);this.map.set(key, value);return value;}else{return -1;}
};/** * param {number} key * param {number} value* return {void}*/
LRUCache.prototype.put function(key, value) {if(this.map.has(key)){let value this.map.get(key);this.map.delete(key);}this.map.set(key, value);if(this.map.size this.capacity){this.map.delete(this.map.keys().next().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)*/44 二叉树的中序遍历 方法1递归法。
/*** Definition for a binary tree node.* function TreeNode(val, left, right) {* this.val (valundefined ? 0 : val)* this.left (leftundefined ? null : left)* this.right (rightundefined ? null : right)* }*/
/*** param {TreeNode} root* return {number[]}*/
var inorderTraversal function(root) {var res [];var traversal function(root){if(root null){return;}traversal(root.left); // 左res.push(root.val); // 根traversal(root.right); // 右}traversal(root);return res;
};方法2迭代法。遍历顺序与处理顺序不同。
/*** Definition for a binary tree node.* function TreeNode(val, left, right) {* this.val (valundefined ? 0 : val)* this.left (leftundefined ? null : left)* this.right (rightundefined ? null : right)* }*/
/*** param {TreeNode} root* return {number[]}*/
var inorderTraversal function(root) {var res []; // 存放结果var vis []; // 模拟遍历队列存放访问过的元素while(root ! null || vis.length ! 0){if(root ! null){vis.push(root);root root.left; // 左}else{root vis.pop();res.push(root.val); // 根root root.right; // 右}}return res;
};45 二叉树的最大深度 深度任意节点到根节点的距离使用前序遍历。高度任意节点到叶子节点的距离使用后序遍历。根节点的高度就是二叉树的最大深度。这里使用后序遍历即通过求根节点高度得出二叉树的最大深度。
/*** Definition for a binary tree node.* function TreeNode(val, left, right) {* this.val (valundefined ? 0 : val)* this.left (leftundefined ? null : left)* this.right (rightundefined ? null : right)* }*/
/*** param {TreeNode} root* return {number}*/
var maxDepth function(root) {if(root null){return 0;}var leftheight maxDepth(root.left);var rightheight maxDepth(root.right);var height Math.max(leftheight, rightheight) 1;return height;
};
