算法小日常02

4次阅读

共计 2340 个字符，预计需要花费 6 分钟才能阅读完成。

又是要求要空间复杂度为 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
};

要求用递归和迭代两种方法来处理
第一种方法迭代法：
时间复杂度：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
};

本题主要考察的应该是 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);
};

然后第一个疑问点就是对最近公共祖先的定义：百度百科中最近公共祖先的定义为：“对于有根树 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;
};

给的是两个非空的链表，且按照逆序方式存储，相加后返回一个链表也是逆序存储。


/**
 * 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
};

正文完