CodingTour —

ARTS #105

Algorithm

本周选择的算法题是：Pow(x, n)。

规则

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

Example 1:

Input: x = 2.00000, n = 10
Output: 1024.00000

Example 2:

Input: x = 2.10000, n = 3
Output: 9.26100

Example 3:

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

Constraints:

• -100.0 < x < 100.0
• -231 <= n <= 231-1
• -104 <= xn <= 104

Solution

Exponentiation by squaring using recursion:

class Solution:
    def myPow(self, x: float, n: int) -> float:
        def pow(n):
            if n == 0: return 1
            ans = pow(n // 2)
            return ans * ans * (1 if n % 2 == 0 else x)
        return pow(n) if n > 0 else 1 / pow(-n)

Exponentiation by squaring using iteration:

class Solution:
    def myPow(self, x: float, n: int) -> float:
        def pow(n):
            ans = 1
            x_contribute = x
            while n:
                if n % 2 == 1:
                    ans *= x_contribute
                x_contribute *= x_contribute
                n //= 2
            return ans
        return pow(n) if n > 0 else 1 / pow(-n)

Review

HTTP/2 Push is dead

网上关于 HTTP/2 push cache 相关的内容很少，一定程度上和 Push 已“死”有关，Chrome 团队在去年移除了 HTTP/2、HTTP/3 的 Push 实现，主要原因是该功能没有表现出明显的性能优势，算是没达到设计时的预期吧；至于如何减少获取小而多的文件带来的延迟，未来还需要其他探索，比如这个还未完成的提案: 103 Early Hints。

Tip

Python 3.3+ 有一个显示错误堆栈的标准库 faulthandler，启用方式为：

import faulthandler
faulthandler.enable()

或者以 python3 -X faulthandler 执行脚本。这样当 Python 异常终止时就能自动显示丰富的堆栈信息了，如：

Fatal Python error: Segmentation fault

Current thread 0x00007fb899f39700 (most recent call first):
  File "/home/python/cpython/Lib/ctypes/__init__.py", line 486 in string_at
  File "<stdin>", line 1 in <module>
Segmentation fault

Learn more: https://docs.python.org/3/library/faulthandler.html。

另外 XMind 的 Distinctive 模板适合画基建蓝图。

Share

浏览器缓存策略.xmind。