ARTS - Week 6

ARTS - Week 6

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

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

Algorithm

LeetCode Problems 50 - Maximum Depth of Binary Tree

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Difficulty: Easy

Example:

Given binary tree [3,9,20,null,null,15,7]
二叉树示例

return its depth = 3.

Solution

深度优先

采用深度优先递归的方式解决

# Python

class Solution:
    def maxDepth(self, root):
    if not root: return 0
    
    return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))
# Ruby

def max_depth(root)
  return 0 if root.nil?

  return 1 + [max_depth(root.left), max_depth(root.right)].max
end

复杂度

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

运行结果

Python:
Runtime: 68 ms.
Your runtime beats 44.03 % of python3 submissions.

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

LeetCode Problems 111 - Minimum Depth of Binary Tree

Given a binary tree, find its minimum depth.

Difficulty: Easy

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

For example:
Given binary tree [3,9,20,null,null,15,7]

二叉树示例
return its minimum depth = 2.

Solution

深度优先

依然采用深度优先的加递归的思想。只不过比上一题需要多做一些判断。

# Python

class Solution:
    def minDepth(self, root):
    if not root: return 0;
    if not root.left: return 1 + self.minDepth(root.right);
    if not root.right: return 1 + self.minDepth(root.left);

    return 1 + min(self.minDepth(root.left), self.minDepth(root.right))
# Ruby

def min_depth(root)
  return 0 if root.nil?
  return 1 + min_depth(root.right) if root.left.nil?
  return 1 + min_depth(root.left) if root.right.nil?

  return 1 + [min_depth(root.left), min_depth(root.right)].min
end

复杂度

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

运行结果

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

Ruby:
Runtime: 52 ms.
Your runtime beats 95.65 % of ruby submissions.

LeetCode Problems 22 - Generate Parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

Difficulty: Medium

For example, given n = 3, a solution set is:

生成括号示例

Solution

递归

通过设置一些判断条件来降低时间复杂度

# Python

class Solution:
    def generateParenthesis(self, n):
        self.list = []
        self._gen(0, 0, n, "")
        return self.list

    def _gen(self, left, right, n, result):
        if left == n and right == n:
            self.list.append(result)
            return
        if left < n:
            self._gen(left + 1, right, n, result + "(")
        if left > right and right < n:
            self._gen(left, right + 1, n, result + ")")
# Ruby

def generate_parenthesis(n)
  @list = []
  _gen(0, 0, n, "")
  return @list
end

def _gen(left, right, n, result)
  @list.push(result) and return if left == n && right == n

  _gen(left + 1, right, n, result + "(") if left < n

  _gen(left, right + 1, n, result + ")") if left > right && right < n
end

运行结果

Python:
Runtime: 60 ms.
Your runtime beats 40.54 % of python3 submissions.

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

Review

Hardening Website Security – Part 1: HTTP Security Headers

这篇文章介绍了怎么设置 HTTP Headers能使网站更加健壮,以避免被黑客攻击。主要包括以下几个参数的设定:X-Frame-Options; X-XSS-Protection; X-Content-Type-Options; Strict-Transport-Security; Content-Security-Policy


Tip

本周使用 simple_token_authentication 搭配 Devise搭建 Private API 的认证体系。


# ARTS 

评论

Your browser is out-of-date!

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

×