共计 2340 个字符,预计需要花费 6 分钟才能阅读完成。
【160】相交链表
又是要求要空间复杂度为 O(1)
第一种解法:时间复杂度和空间复杂度都是 O(n)
给 headA 循环添加一个标记,然后去循环 headB 判断 headB 是否有被标记过的节点,如果有则为相交节点,没有则返回 NULL
function getIntersectionNode
(headA, headB) {while(headA) {
headA.flag = true
headA = headA.next
}
while(headB) {if (headB.flag) return headB
headB = headB.next
}
return null
};
第二种解法:本题主要是考察双指针的用法吧。如果 A、B 相交,那么 A、B 自相交节点往后的链表是一致的。
我们可以尝试消除 A、B 链表的长度差,从数量相等的位置开始,判断是否有相同节点,若有相同则是两链表相交,返回第一个相同节点 即可。否则返回 null,两链表不相交。
时间复杂度:O(n)
空间复杂度:O(1)
var getIntersectionNode = function(headA, headB) {
// 清除高度差
let pA = headA, pB = headB
while(pA || pB) {if(pA === pB) return pA
pA = pA === null ? headB : pA.next
pB = pB === null ? headA : pB.next
}
return null
};
【206】反转一个单链表
要求用递归和迭代两种方法来处理
第一种方法迭代法:
时间复杂度:O(n)
空间复杂度:O(1)
function reverseList(head) {if(!head || !head.next) return head
var prev = null, curr = head
while(curr) {
// 用于临时存储 curr 后继节点
var next = curr.next
// 反转 curr 的后继指针
curr.next = prev
// 变更 prev、curr
// 待反转节点指向下一个节点
prev = curr
curr = next
}
head = prev
return head
};
第二种方法:递归法
时间复杂度:O(n)
空间复杂度:O(n)
function reverseList(head) {if(!head || !head.next) return head
var next = head.next
// 递归反转
var reverseHead = reverseList(next)
// 变更指针
next.next = head
head.next = null
return reverseHead
};
[217]给定一个整数数组,判断是否存在重复元素
本题主要考察的应该是 Set 吧
方法一:
最开始想了一个最笨的方法,暴力法,两层循环挨个比较,超级没有技术含量,其实还可以先排序,但也不是最简单的解法。
/**
* @param {number[]} nums
* @return {boolean}
*/
var containsDuplicate = function(nums) {for(var i = 0; i < nums.length; i++){for(var j = 0; j < nums.length; j++){if(nums[i] == nums[j] && i != j){return true;}
}
}
return false;
};
方法二:参考了题解用一行代码搞定
set 去重 然后比较大小
var containsDuplicate = function(nums) {return !(nums.length === new Set(nums).size);
};
【235】二叉搜索树的最近公共祖先:给定一个二叉搜索树,找到该树中两个指定节点的最近公共祖先。
然后第一个疑问点就是对最近公共祖先的定义:百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”
题解:利用二叉搜索树的特点。大小规律可以采用递归法解题
var lowestCommonAncestor = function(root, p, q) {if(root == null){return root}
if(p.val < root.val && root.val > q.val){return lowestCommonAncestor(root.left, p, q);
}
if(p.val > root.val && root.val < q.val){return lowestCommonAncestor(root.right, p, q);
}
return root;
};
[2]两数相加
给的是两个非空的链表,且按照逆序方式存储,相加后返回一个链表也是逆序存储。
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} l1
* @param {ListNode} l2
* @return {ListNode}
*/
var addTwoNumbers = function(l1, l2) {var node = new ListNode();
let temp = node , sum , n = 0
while(l1 || l2){
const n1 = l1 ? l1.val : 0
const n2 = l2 ? l2.val : 0
sum = n1 + n2 + n
temp.next = new ListNode(sum % 10)
temp = temp.next
n = parseInt(sum / 10)
if(l1) l1 = l1.next
if(l2) l2 = l2.next
}
if(n > 0) temp.next = new ListNode(n)
return node.next
};
正文完
发表至: javascript
2020-05-27