Ahri-珊

day21将分享LeetCode算法题235,237,242。

LeetCode

今天的三道题涉及到二叉树、字符串还有链表。

235. Lowest Common Ancestor of a Binary Search Tree

求二叉查找树中两个子节点的最小公共祖先。

心路历程

1.由于二叉树的特性,最小公共祖先的值在p,q两个节点值之间。

2.当前根节点的值大于p,q两个节点值,公共祖先在左子树找。

3.当前根节点的值小于p,q两个节点值,公共祖先在右子树找。

4,当前根节点的值在p,q之间,那我们就找到啦。

代码:

var lowestCommonAncestor = function(root, p, q) {
    if(root.val > p.val && root.val > q.val)
        return lowestCommonAncestor(root.left, p, q);
    if(root.val < p.val && root.val < q.val)
        return lowestCommonAncestor(root.right, p, q);
    return root;
};

237. Delete Node in a Linked List

删除当前节点。

心路历程

删除首节点,我们可以把下一个节点的值赋给当前节点,删除下一节点

代码:

var deleteNode = function(node) {
    if(node&&node.next)
        {
            node.val = node.next.val;
            node.next = node.next.next;
        }
};

242. Valid Anagram

判断一个字符串是否是由另一个字符串打乱顺序得到的

心路历程

1.两个字符串长度不同,直接返回false

2.创建两个hash对象,记录两个字符串中每个字母出现的次数

3.比较两个hash对象中记录的每个字母出现的次数,相同返回true,不同返回false;

代码:

var isAnagram = function(s, t) {
    if(s.length!=t.length)
        return false;
    var hashS = {},hashT = {};
    for(let i=0;i<s.length;i++)
        {
            if(!hashS[s[i]])
                {
                    hashS[s[i]] = 1;
                }
            if(hashS[s[i]])
                hashS[s[i]] += 1;
            if(!hashT[t[i]])
                {
                    hashT[t[i]] = 1;
                }
            if(hashT[t[i]])
                hashT[t[i]] += 1;
        }
    for(var key in hashS)
        {
            if(hashS[key]!=hashT[key])
                return false;
        }
    return true;
};

END