ARTS - Week 4

ARTS - Week 4

ARTS 是耗叔发起的一项活动,每周完成以下内容:

Algorithm - 至少做一个 LeetCode 上的算法题
Review - 阅读并点评至少一篇英文技术文章
Tip - 学习至少一个技术技巧
Share - 至少分享一篇有观点和思考的技术文章

Algorithm

LeetCode Problems 236 - Lowest Common Ancestor of a Binary Tree

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Given the following binary tree: root = [3,5,1,6,2,0,8,null,null,7,4]
二叉树

Difficulty: Medium

Example:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.

Solution

递归

定义一个方法,在 root 的二叉树中找到 p 或者 q,然后递归的去解决。

# Python

class Solution:
    def lowestCommonAncestor(self, root, p, q):
        if root is None or root == p or root == q:
            return root
        left = lowestCommonAncestor(self, root.left, p, q)
        right = lowestCommonAncestor(self, root.right, p, q)

        if left is None:
            return right
        else:
            if right is None:
                return left
            else:
                return root
# Ruby

def lowest_common_ancestor(root, p, q)
  return root if root.nil? || root == p || root == q

  left = lowest_common_ancestor(root.left, p, q)
  right = lowest_common_ancestor(root.right, p, q)

  return left.nil? ? right : (right.nil? ? left : root)
end

复杂度

  • Time complexity: O(N);
  • Space complexity: O(N);

运行结果

Python:
Runtime: 100 ms.
Your runtime beats 47.34 % of python3 submissions.

Ruby:
Runtime: 64 ms.
Your runtime beats 97.22 % of ruby submissions.

LeetCode Problems 235 - Lowest Common Ancestor of a Binary Search Tree

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Given binary search tree: root = [6,2,8,0,4,7,9,null,null,3,5]
BST

Difficulty: Easy
Example:

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6
Explanation: The LCA of nodes 2 and 8 is 6.

Solution

第一种解法:递归

二叉搜索树是有序的,所有可以在上一题的基础上优化算法。

# Python

class Solution:
    def lowestCommonAncestor(self, root, p, q):
        if p.val < root.val > q.val:
            return self.lowestCommonAncestor(root.left, p, q)
        if p.val > root.val < q.val:
            return self.lowestCommonAncestor(root.right, p, q)
        return root
# Ruby

def is_valid_bst(root)
  return lowest_common_ancestor(root.left, p, q) if p.val < root.val && root.val > q.val
  return lowest_common_ancestor(root.right, p, q) if p.val > root.val && root.val < q.val

  return root
end

复杂度

  • Time complexity: O(N);
  • Space complexity: O(N);

运行结果

Python:
Runtime: 80 ms.
Your runtime beats 99.93 % of python3 submissions.

Ruby:
Runtime: 68 ms.
Your runtime beats 100.00 % of ruby submissions.

第二种解法:循环

解法思路和递归类似,不过使用循环完成。

# Python

class Solution:
    def lowestCommonAncestor(self, root, p, q):
        while root:
            if p.val < root.val > q.val:
                root = root.left
            elif p.val > root.val < q.val:
                root = root.right
            else:
                return root
# Ruby

def lowest_common_ancestor(root, p, q)
  while root
    if p.val < root.val && root.val > q.val
      root = root.left
    elsif p.val > root.val && root.val < q.val
      root = root.right
    else
      return root
    end
  end
end

复杂度

  • Time complexity: O(N);
  • Space complexity: O(1);

运行结果

Python:
Runtime: 140 ms.
Your runtime beats 19.84 % of python3 submissions.

Ruby:
Runtime: 68 ms.
Your runtime beats 100.00 % of ruby submissions.


Review

Advanced web security topics

这篇文章中介绍了一些黑客攻击网站的方式以及相应的解决预防方式。总结如下:

  1. 黑客在图片中嵌套 HTML 代码,并在目标网站中执行这些嵌套的代码;
  2. 当点击target=_blank属性的链接时,会打开一个新的标签页。而通过window.opener可以修改新打开网页的前述网页,进而导致使用者进入了页面一样的钓鱼网站,从而窃取使用者信息。解决方法是禁用掉window.opener或者不使用target=_blank
  3. 很多网页的表单有储存用户填写信息,以方便使用者下次填写时直接自动填写。但这样也会保存很多被隐藏起来的表单信息,例如信用卡号码,手机号码,家庭住址等,这样会造成用户的信息泄露;
  4. 有很多使用第三方登录的网站。在某些网站会隐藏一些插件,当用户授权后,黑客就可以利用用户登录信息去使用另一些网站。

HelloGitHub

这个网站中每一期会介绍一些有趣、入门级的开源项目,适合去寻找编程的乐趣。


Tip

本周学习了 Python 和 Ruby 中构建二叉树的类。
链表就是特殊化的树,树就是特殊化的图。

# Python

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
# Ruby

class TreeNode
  attr_accessor :val, :left, :right
  
  def initialize(val)
    @val = val
    @left, @right = nil, nil
  end
end
# ARTS 

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×