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;
};
Comments