Home

编辑距离

题目源自Leetcode: 编辑距离-leetcode 给定两个单词 word1 和 word2,计算出将 word1 转换成 word2 所使用的最少操作数 。 你可以对一个单词进行如下三种操作: 插入一个字符 删除一个字符 替换一个字符 示例: 输入: word1 = "horse", word2 = "ros" 输出: 3 解释: horse -> rorse (将 'h' 替换为 'r') rorse -> rose (删除 'r') rose -> ros (删除 'e') 解法: 动态规划 这是一道很漂亮的动态规划问题. 我们这样想: 越长的单词求解就越困难, 越短的单词求解就越简单: 长度为1的单词只需比较字母是否相...

Read more

详解寻路算法(1)-图搜索

1. 引言 寻路算法广泛应用在各种游戏中. 寻路算法要解决的问题是, 给定一个 "地图"(定义可行走区域), 一个起点, 和一个目标点, 求起点到目标点的最短路径. 解决寻路问题是一个复杂的过程, 涉及到若干个算法. 大体可以分为两个步骤: 把 地图 抽象成 图. 这里的图指的是数学上的图 $G=(V,E)$; 对图进行搜索. 相比图搜索, 把地图抽象成图通常会比较复杂. 这篇文章先介绍介绍图搜索算法. 在下篇文章中, 我会介绍几种把地图抽象成图的方法. 图搜索算法有很多. 在寻路算法中, 主要用到 A* 算法. 这里我会先介绍 Dijkstra 算法, 然后引出 A* 算法. 稍后会看到, 这两种算法很相似: Dijkstra 算法总是搜索最近的, 适用于求解单源对所...

Read more

牛顿迭代法求平方根

1.先说结论 $\sqrt{a}$ 可这样求得: 令 $x_0$ 为任意实数, 执行以下迭代式: \[x_i = \frac{x_{i-1}+\frac{a}{x_{i-1}}}{2} \tag{1}\] 迭代若干次, 当 $|x_i-x_{i-1}|$ 小于想要的精度时便可停止迭代. 最终的 $x_i$ 便可视为 $\sqrt{a}$. 根据 (1) 式我们可以很快写出求平方根的代码: def sqrt(a): x = 1.0 while True: pre = x x = (x + a / x) / 2 if abs(x - pre) < 1e-6: break retur...

Read more

在Lua中使用装饰器

引言 使用过 Python 的同学都会喜欢上 Python 的装饰器. 它提供一种语法, 对函数进行"声明": def decorator(f): def wrapper(x): print 'call %s' % f.__name__ return "The 2nd power of {0} is {1}".format(x, f(x)) return wrapper @decorator def foo(x): return x ** 2 装饰器本质上只是一种语法糖: 把目标函数作为参数传入装饰器. 巧妙地使用装饰器, 可以让程序变得简洁优雅. 比如说, 声明一个函数是事件, 声明一个函数是远程调用接口, 等等. 在...

Read more

调和级数的渐进表示

令 $H_n$ 为第 n 项调和数 \[H_n=1+\frac{1}{2}+\frac{1}{3}+...+\frac{1}{n}=\sum_{i=1}^{n}\frac{1}{i}\] 证明 $H_n$ 是 $O(\log n)$ 的 证明 如下图所示: $\sum_{i=1}^{n}\frac{1}{i}$可以看作图中蓝色阴影的面积; 而橙色部分的面积则可以看作函数 $y=\frac{1}{x}$ 的积分 $\int_{0}^{n}\frac{1}{x}\mathrm{d}x$. 因此有 \[\sum_{i=2}^{n}\frac{1}{i}\lt \int_{0}^{n}\frac{1}{x}\mathrm{d}x=\ln n\] \[\sum_{i=1}^...

Read more

在Jekyll中使用LaTeX

我准备用 Jekyll + Github page 搭建自己的技术博客. 但是有个问题, 技术文章中不可避免地需要使用到数学公式, Jekyll 原生的 Markdown 解释器总是不能很好地使用 Latex. 通过查阅资料, 我最终解决了这个问题. 下面是我的做法: 禁用 Kramdown 自带的公式解释器: 在 _config.yml 中加入: kramdown: math_engine: null 导入 mathjax 的 javascript 代码: 在 _includes 下新建文件 latex.html, 粘贴上以下内容: <script type="text/x-mathjax-config...

Read more

跳跃游戏

题目源自Leetcode: 跳跃游戏II-leetcode 给定一个非负整数数组, 你最初位于数组的第一个位置. 数组中的每个元素代表你在该位置可以跳跃的最大长度. 你的目标是使用最少的跳跃次数到达数组的最后一个位置. 示例: 输入: [2,3,1,1,4] 输出: 2 解释: 跳到最后一个位置的最小跳跃数是 2.   从下标为 0 跳到下标为 1 的位置, 跳 1 步, 然后跳 3 步到达数组的最后一个位置. 思路1: 动态规划 我们令 dp[i] 为 从第 i 个位置到最后一个位置所需的跳跃次数. 显然, 若数组长度为 n , dp[n] = 0. 对于其他的位置 i, 假设 j 是任意一个 i 能跳到的位置, dp[i] 应为 所有 dp[j] ...

Read more

四元数描述旋转

先看结论: 对于任意坐标 $(a,b,c)$ , 我们希望绕旋转轴 $(x,y,z)$ 旋转 $\theta$ 度, 其中 x, y, z 的平方和为1. 那么: 令四元数 \[q=\cos\frac{\theta}{2}+\sin\frac{\theta}{2}(x\mathrm{i}+y\mathrm{j}+z\mathrm{k})\] \[p=a\mathrm{i}+b\mathrm{j}+c\mathrm{k}\] 得到 \[p'=qpq^{-1}\] 其中 $q^{-1}$ 是 $q$ 的逆, $q^{-1}=\cos\frac{\theta}{2}-\sin\frac{\theta}{2}(x\mathrm{i}+y\mathrm{j}+z\mathrm{k}...

Read more