Hi，这是我的新站点：https://lawrenceli.me
部署在 Vercel 之上，采用 Next.js（React），TypeScript 构建。文章存储于 Notion（基于私有 API 访问），并加了 CloudFlare 的免费 CDN。
Google 收录了我的几篇文章，这是采用 SSR 的 SEO 的好处。我会在 https://lawrenceli.me/blog 上更新我的博客。你可以通过 https://lawrenceli.me/contact 联系到我。
博客
-
Here’s to the crazy ones.
Here’s to the crazy ones. The cynics. The whistleblowers. The snarkiest of all. The real writers. The ones who see things differently. They’re not fond of UGC. And they have no respect for crowd sourcing. You can quote them, disagree with them, glorify or vilify them, or write lengthy counter-argument on your own fucking blog. About the only thing you can’t do is leave comments on their blogs. Because they change the default setting of WordPress. They push the quality of online content forward. While some may see them as the crazy ones, we see self-respect content creators. Because the people who are crazy enough to disable comment on their blogs, are the ones who do.
by another Lawrence Li.
-
快速幂算法
前几天刷 Leetcode 算法题，有一道求幂的相对容易的题目，常规思路自然是将数字 x 连续相乘 n 次，再考虑 n 的正负，我用 Python 3 去实现，算法大致如下：
def myPow(x, n): s = 1 if n == 0: return 1 if n > 0: while n > 0: n -= 1 s *= x return s else: m = -n while m > 0: m -= 1 s *= x return 1/s看似面面俱到，提交测试一遍，傻眼了。
超出时间限制：291 / 304 个通过测试用例
细节主要卡在了 0.00001 的 2147483647 次方上，指数太大，上述的遍历相乘算法，把 x连续乘 n 次，时间复杂度为 O(n)，随着 n 的增长而线性增长，指数一大，时间自然会超出限制。这时我便开始想方法把时间复杂度降低下来。Python 是通过 C 语言实现的，内置的 pow() 函数的实现原理可以用来参考。我开始找 Cpython 的源码。
里面最核心的部分如下：
if (Py_SIZE(b) <= FIVEARY_CUTOFF) { /* Left-to-right binary exponentiation (HAC Algorithm 14.79) */ /* http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf */ for (i = Py_SIZE(b) - 1; i >= 0; --i) { digit bi = b->ob_digit[i]; for (j = (digit)1 << (PyLong_SHIFT-1); j != 0; j >>= 1) { MULT(z, z, z); if (bi & j) MULT(z, a, z); } }我惊呆了。不是代码本身，而是它给出的注释。Python 作为一款开源语言，成百上千的程序员时时刻刻给它贡献代码，这内置的 pow() 函数参考了 HAC 聚类算法的二进制快速幂，其理论来源是一份 pdf 文献。
至此，我刷 Leetcode 时候的眼界彻底放开，我不在乎题目求解本身，我开始尝试挖掘背后算法的来源。
Keep Coding 