ARTS - Week 5

ARTS - Week 5

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

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

Algorithm

LeetCode Problems 50 - Pow(x, n)

Implement pow(x, n), which calculates x raised to the power n (xn).

Difficulty: Medium

Example 1:

Input: 2.00000, 10
Output: 1024.00000

Example 2:

Input: 2.00000, -2
Output: 0.25000
Explanation: 2-2 = 1/22 = 1/4 = 0.25

Solution

第一种解法:使用库函数

可以直接使用库函数完成任务。但在一个面试中,如果只能写出这种解法,那估计凶多吉少~

# Python

import math

class Solution:
    def myPow(self, x, n):
        return math.pow(x, n)
# Ruby

def my_pow(x, n)
  x**n
end

运行结果

Python:
Runtime: 76 ms.
Your runtime beats 9.39 % of python3 submissions.

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

第二种解法:暴力循环

循环 N 次,去把 x 相乘得出结果。

# Python

class Solution:
    def myPow(self, x, n):
        if n < 0:
            n = -n
            x = 1 / x

        pow = 1
        for i in range(1, n+1):
            pow *= x

        return pow
# Ruby

def my_pow(x, n)
  if n < 0
    n = -n
    x = 1 / x
  end

  pow = 1
  i = 1
  while i <= n
    pow *= x
    i += 1
  end

  return pow
end

复杂度

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

运行结果

Python:
Time Limit Exceeded

Ruby:
Time Limit Exceeded

暴力解法太低效暴力了,LeetCode 都不愿意多花时间执行程序……

第三种解法:位运算

将 N 分为奇数和偶数处理,并转为计算(x * x)n/2.

# Python

class Solution:
    def myPow(self, x, n):
    if n < 0:
        x = 1 / x
        n = -n
    pow = 1
    while n:
        if n & 1:
            pow *= x
        x *= x
        n >>= 1
    return pow
# Ruby

def my_pow(x, n)
  if n < 0
    n = -n
    x = 1 / x
  end

  pow = 1
  while n != 0
    pow *= x if n & 1 != 0
    x *= x
    n >>= 1
  end

  return pow
end

复杂度

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

运行结果

Python:
Runtime: 40 ms.
Your runtime beats 89.58 % of python3 submissions.

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

时间复杂度提升后,程序效率提升明显。

第四种解法:递归

思路跟上一种解法类似,不过采用递归的方式。

# Python

class Solution:
    def myPow(self, x, n):
    if not n:
        return 1
    if n < 0:
        return 1 / self.myPow(x, -n)
    if n % 2:
        return x * self.myPow(x, n-1)
    return self.myPow(x*x, n/2)
# Ruby

def my_pow(x, n)
  if n < 0
    n = -n
    x = 1 / x
  elsif n == 0
    return 1
  end

  return x * my_pow(x, n - 1) if n % 2 != 0
  return my_pow(x * x, n / 2)
end

复杂度

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

运行结果

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

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

LeetCode Problems 98 - Binary Tree Level Order Traversal

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

Difficulty: Medium

For example:
Given binary tree [3,9,20,null,null,15,7],
params
return its level order traversal as:
output

Solution

第一种解法 BFS(广度优先算法)

这种思路比较符合人类思考的模式。利用双向队列的数据结构,每一次遍历每一层的所有节点,并把他们的子节点添加到队列中。根据每一层节点数量再进行遍历即可得到结果。

# Python

class Solution:
    def levelOrder(self, root):
        if not root: return []

        result = []
        queue = collections.deque()
        queue.append(root)

        # visited = set(root)

        while queue:
            level_size = len(queue)
            current_level = []

            for _ in range(level_size):
                node = queue.popleft()
                current_level.append(node.val)
                if node.left: queue.append(node.left)
                if node.right: queue.append(node.right)

            result.append(current_level)

        return result
# Ruby

def level_order(root)
  return [] if root.nil?

  queue = []
  queue.push(root)
  result = []

  while !queue.empty?
    level_size = queue.size
    current_level = []

    for _ in (0...level_size) do
      element = queue.shift
      current_level.push(element.val)

      queue.push(element.left) if !element.left.nil?
      queue.push(element.right) if !element.right.nil?
    end

    result.push(current_level)
  end

  return result
end

复杂度

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

运行结果

Python:
Runtime: 40 ms.
Your runtime beats 99.57 % of python3 submissions.

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

第二种解法 DFS(深度优先算法)

这种思路更符合计算机的运行模式。依据节点的所有子节点寻找下去,并把每一个路上的节点放入对应的层级数组里。

# Python

class Solution:
    def levelOrder(self, root):
        if not root: return []

        self.result = []
        self._dfs(root, 0)
        return self.result

    def _dfs(self, node, level):
        if not node: return

        if len(self.result) < level + 1:
            self.result.append([])

        self.result[level].append(node.val)

        self._dfs(node.left, level + 1)
        self._dfs(node.right, level + 1)
# Ruby

def level_order(root)
  return [] if root.nil?

  @result = []
  _dfs(root, 0)
  return @result
end

def _dfs(node, level)
  return if node.nil?

  @result.push([]) if @result.size < level + 1

  @result[level].push(node.val)

  _dfs(node.left, level + 1)
  _dfs(node.right, level + 1)
end

复杂度

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

运行结果

Python:
Runtime: 64 ms.
Your runtime beats 28.86 % of python3 submissions.

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

Review

Regular Expression Matching with a Trigram Index or How Google Code Search Worked

这篇文章出自谷歌代码搜索的作者,介绍了搜索的算法原理。


Tip

本周使用 Rspec、FactoryBot、Faker 这三个 gem 包搭建了基于 Rails 的 API 平台自动化测试框架。


# ARTS 

评论

Your browser is out-of-date!

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

×