Luyu Huang's Tech Blog

跳跃游戏

题目源自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

从分治策略到动态规划,再到贪心算法

引言 分治, 动态规划和贪心算法, 是算法设计中非常重要的三种思想, 它们各不相同, 却又息息相关. 本文会介绍三种思想之间的共同点和不同之处, 并且列举一些典型算法的例子, 试图探索算法设计的一般思路. 分治策略 我们先来看比较熟悉的快速排序. 快速排序是一个非常典型的分治策略算法. 它采取的方法是把数组中的某一个数移动到数组中的某一个位置, 使得它前面的数都小于它, 它后面的数都大于它. 然后, 对前面的数组和后面的数组做同样的操作. 直到数组全部有序. 下面是快速排序的代码 function qsort(a, l, r) if l >= r then return end local x = a[r] local p = l - 1 ...

Read more

避免使用无符号数

考察这样一段代码: int a = -1; unsigned int b = 1; if (a < b) printf("a < b\n"); else printf("a > b\n"); a是有符号整数,b是无符号整数。C语言在比较他们的大小时会进行隐式类型转换。如果执行的是 if ((unsigned int)a < b) 则-1被转换成4294967295,结果是 a > b;如果执行的是 if (a < (int)b) 则结果是 a < b。采取哪种方式依赖于编译器。 在g++中,输出的结果是a > b。当然,也会打出警告:warning: comparison between signed and u...

Read more