球谐函数在图形学里最大的应用就是编码压缩irradiance map。

本文将聚焦球谐函数里最复杂的部分，因精力有限，此文打算分成多次更新完成。目前先把大体框架发出来。

https://github.com/Friduric/voxel-cone-tracing 这个demo很适合入门Voxel GI，本文记录下技术细节的学习。

本文简单梳理了实时渲染管线过程。主要参考了《RTR》3rd。

（更新ing）

Note：本文实际绑定的版本是branch5.0（2018-7-25）。

Note：本文实际绑定的版本是branch5.0（2018-7-25）。

Note：本文实际绑定的版本是branch5.0（2018-7-25）。

Note：本文实际绑定的版本是branch5.0（2018-7-25）。

本文将简单介绍rfc5869提出的HKDF。

首先强推大神的文章：

RSA算法原理（一）

RSA算法原理（二）

（Note：里面有些图片要上梯子才能加载，chart.googleapis.com，你懂得）

本文目标是搞清楚zlib库的deflate算法实现。

GJK，全称Gilbert–Johnson–Keerthi distance algorithm，是非常常用的碰撞检测算法。

原始GJK的功能：准确地告诉调用者2个几何体是否碰撞。

GJK的主要特性：

• 只适用于凸体
• GJK算法与维度无关，2D、3D都可以用
• 不要求对顶点数组做排序
• 存在一些技巧可以大大优化GJK的性能

本文将详解原始GJK的来龙去脉。

目录：

• 数学知识点
  • 闵可夫斯基数学 Minkowski Math
  • 单纯形 Simplex
  • 向量混合积 Vector Triple Product
• GJK算法原理
  • GJK伪代码
  • Support函数
  • NearestSimplex函数
• 二维平面的GJK算法实现
  • b2Distance核心逻辑
  • b2Simplex::GetSearchDirection
  • b2Simplex::Solve2
  • b2Simplex::Solve3
  • b2DistanceProxy::GetSupport
• 其他细节
• 参考资料
  • GJK各种实现

最近偶然接触了一下canvas的2D仿射变换。和3D一样，canvas有scale、translate、rotate操作，本质上这3个函数也是矩阵乘法。

canvas应该内置了一套矩阵运算系统，并且canvas内含有一个仿射变换矩阵（大概认为是3x3=9个浮点数变量即可，2D是3x3矩阵，3D是4x4矩阵）。每次调用scale、translate、rotate就是对这个矩阵做矩阵乘法。

另外还有3个函数可以控制canvas的仿射变换：

• resetTransform 重置为单位矩阵
• transform(a,b,c,d,e,f) 以a,b,c,d,e,f构造一个仿射变换矩阵并乘到当前canvas的仿射变换矩阵
• setTransform(a,b,c,d,e,f) 重置为单位矩阵并应用transform(a,b,c,d,e,f)

我遇到的需求是，如果canvas没有提供transform函数，怎么用scale、translate、rotate三个函数的组合，来模拟transform函数？

《Game Engine Architecture》这本书里最让我欣喜的就是动画相关的章节了，非常详细，比中文搜索引擎能搜到的资料都要系统、全面。据说作者以前就是做动画的。其他章节相对的只是抛砖引玉，例如阴影，只写了几页。

通过这本书并结合github上的ozz-animation源码，基本搞懂了骨骼蒙皮动画的核心原理。下面将简单做一份笔记。

HLBVH

上一篇文章介绍了recursiveBuild函数，它对静态场景做了一次自顶向下的BVH构造，且使用了一个叫SAH的切分技术。

recursiveBuild有2个缺点：

1. SAH的计算是\(O(n^{2}) \)的，且几乎每一个节点都要做SAH，性能并不是很理想；

2. 自顶向下地构造BVH，很难应用并行计算来优化性能。

于是作者又发明了更复杂的HLBVHBuild，即 Hierarchical Linear Bounding Volume Hierarchy。

二叉树BVH

BVH是空间切分技术之一，除了BVH之外还有kdtree、octree。

下面先以静态场景为例，讲解BVH的生成算法。Note：演示代码是用pbrt源码改的测试版，这是为了理解代码和方便调试。

要理解方差阴影贴图的来龙去脉，必须先深刻理解概率论中的几个概念：

• 矩(Moment)
• 数学期望(Mean)
• 方差(Variance)
• 马可夫不等式 (Markov's Inequality)
• 切比雪夫不等式 (Chebyshev's inequality)
• 切比雪夫不等式的one-tailed版本 (one-tailed version of Chebyshev's inequality)

PPAA

所谓PPAA（Post Process Antialiasing)，也叫FBAA（Filter-Based Antialiasing），是基于后处理的各种抗锯齿技术的统称。在PPAA之前，主流AA技术是MSAA（MultiSamples AA）、SSAA（SuperSamples AA）。SSAA是AA中最暴力也是最完美的解决方案，而MSAA是与硬件紧密结合的built-in AA。对于forward rendering来说，MSAA几乎是唯一的选择。

然而，MSAA这种古老的、built-in的技术，已经不太能满足现代渲染器的需求了。它有两大问题，一是MSAA会有多余的AA计算，二是MSAA不适用于deferred rendering。

鉴于MSAA的不足，PPAA就蓬勃发展起来了。PPAA强大之处在于可以自定义、且硬件无关、兼容forward／defer，所以基于PPAA的算法非常多。而其中的翘楚，SMAA(Subpixel Morphological Antialiasing)，性能以及AA质量都很不错。本文将着重介绍SMAA。

在对vertex做model、view、projection计算过程中，还有一个要同时考虑的东西是法向量的矩阵变换。

normal的变换并不能直接使用vertex的变换。如果直接使用的话，就会放了一个定时炸弹在你的shader里面，当哪天你的object做了一个不uniform的缩放变换时，例如x、y轴放大1.5倍，而z轴放大3倍，输出的normal就会出错，进而导致光照计算出错。

下面开始推导正确的只属于normal的变换矩阵。

AO，ambient occlusion

环境光遮蔽，大致上指的是几何物体的拐角处，因为受光不全面（被相邻的面挡光／遮蔽），导致变暗。

SSAO，screen-space ambient occlusion

屏幕空间环境光遮蔽，简称SSAO，是一种让画面更‘真实’的后处理技术。该方法较为简单实用，但需要先获得view space的场景的几何信息，因此比较适合在defer rendering框架下应用。除了SSAO之外，还存在voxel based 的world space的AO技术。

基于PBR做渲染，需要涉及到很多物理学、几何学、热辐射学概念，本文将逐一介绍每个关键概念，并给出相关重要公式。

最近在做的东西涉及到四元数的知识，做的过程中发现四元数有一些很容易让人迷惑的点，现写这篇文章备忘。

一直都说用欧拉角做旋转会出现万向节锁Bug（Gimble Lock），而用四元数就不会。其实这样的说法是不准确的，当用四元数做旋转，如果使用姿势错误，依然会出现Gimble Lock。

碰撞检测算法，暴力解决是一个\( O(n^{2}) \)的过程：对于场景中的每一个obj都和所有其他的obj做相交测试。2个for循环解决问题，所以时间复杂度是\( O(n^{2}) \)，这是最坏情况了。于是可以说，现在流传的各种碰撞检测算法的存在意义都是为了降低这个复杂度\( O(n^{2}) \)。

5个月没更新博客，是因为这段时间主要用在开发forwarder。forwarder是因为工作需要而开发的一个工具，它统一了游戏前后端之间、后端各个服务之间的通信，目前forwarder不仅已经通过了初步的压力和稳定性测试，并且已经在项目中发挥了实际作用。

项目地址：https://github.com/voyagingmk/forwarder

我一直觉得那些著名的数据结构，都是工程设计和数学的完美结合。

所有的数据结构都是被精心设计出来的，此所谓工程设计。但是，既然叫精心设计，就意味着有一套准则，这个准则就是数学。

没有数学基础的数据结构都是耍流氓。

红黑树拥有精巧的结构设计和强大的数学基础，但我总觉得有点过于复杂，故写本文来回顾总结下。

理解立体角之前要先理解圆心角。在二维平面上，一个圆的圆弧的微分记为ds(也叫弧微分)，半径为r，则圆心角指的是弧微分与半径的比值:

\[ d\theta = \frac {ds}{r} \]

PCA(Principal Component Analysis)的主要应用场景是：在大数据集中找出关键的信息并剔除冗余的信息。根据这个特性，PCA也可以用来做信息压缩(有损)、特征提取。不过在本文中，只会对PCA的数学原理进行阐述。

另外，PCA可以说是Machine Learning领域的自编码机(AutoEncoder,AE)的基础。主要区别在于，PCA是线性算法，而AE则不一定。所以在学习AutoEncoder之前，有必要先将PCA搞清楚。

众所周知只有方阵才有逆矩阵，非方阵没有逆矩阵。这个不和谐的问题已在20世纪初被数学家E. H. Moore等人解决掉了，因为他们发明了一般化的逆矩阵(generalized inverse)，也称为伪逆矩阵(Moore–Penrose pseudoinverse)。

基本认识

3种标准导数(梯度)公式

1) 自变量是一个标量(Scalar)时：

\[ Df(x) = \lim _{t\to 0} \frac {f(x+t)-f(x)}{t} \]

2) 自变量是一个向量(Vector)时：

\[ D_{\textbf {w}}f(\textbf {x}) = \lim _{t\to 0} \frac {f(\textbf {x} + t\textbf {w}) - f(\textbf {x})}{t} \]

最近在学习ML(Machine Learning)，注意到了一个有趣的东西：Least Squares Estimator。

先从简单说起吧。看下面的式子：

\[ y = ax + e \]

这是一个非常简单的直线方程。如果赋予y、a、x、b具体的意义，这个式子就有意思了：

1. 假设x是一个统计变量（预先就知道的），譬如，x代表人的年龄。

2. 假设y是关于x的一个label量（预先就知道的），譬如，y代表的是年龄为x时的人的智商。

本文可认为是《PBRT》3.6节的公式推导笔记。

引言

（下文的讨论基于右手坐标系，以及矩阵左乘顺序。）

我对视角矩阵的理解是这样子的，假设3维空间有一个观察者（摄像机），这个观察者必然有它的坐标位置、视角、焦点，根据这3个参数，可以建立一个正交化、规范化的坐标系（一个正交化、单位化的3x3矩阵），这个坐标系对应的矩阵就是Lookat矩阵。

本文部分内容翻译自：Tutorial 12: Perspective Projection

本文介绍的是OpenGL中的透视矩阵。

介绍

所谓的透视矩阵，指的是一个“降维”的转换过程。

上一篇文章已经介绍了贝塞尔曲线。本篇文章接着介绍B样条曲线。

B样条曲线，简单来说，它是对贝塞尔曲线的一个补充。为什么这样说呢？是因为贝塞尔曲线某些情况下不实用：曲线上每个点受所有控制点影响，这会给调整曲线工作带来麻烦。可以想到的第一个优化是，把整个贝塞尔曲线变成多段贝塞尔子曲线的拼接。然而，这个方案也不好用，因为拼接工作很难做好，因为要拼接曲线显得“光滑”前提是保证相邻曲线之间的连续性。

于是，老外发明了一个算法:De Boor's algorithm，基于这个算法的曲线也被称为贝塞尔曲线的变种：B-Spline(B样条)曲线。

本文主要关注的是公式的推导。

在讲贝塞尔曲线之前先复习下组合数学。

又到了矩阵分解时间。这次介绍的是Cholesky分解。这个方法只适用于符合厄米特矩阵、正定矩阵定义的矩阵。

算法原理

设A是一个n阶厄米特正定矩阵(Hermitian positive-definite matrix)。

Cholesky分解的目标是把A变成:

\[ A = LL^{T} \]

L是下三角矩阵。

逆矩阵是一个很基本的概念，这里就不说定义了。本文只介绍求解方法。

初等变换求逆法——高斯消元法(Gauss-Jordan elimination)

先在要求解逆矩阵的A的右边增加一个临时的单位矩阵（阶数显然和A一致）。那么A就变成了一个n行、2n列的矩阵A'。 然后对A'进行高斯消元，也就是通过row operation不断对A'做变换，直到A'的左边的A变成单位矩阵时，A'的右边部分就是A的逆矩阵了。 要注意的是，A不一定有逆矩阵，当A没有逆矩阵时，这个高斯消元过程中肯定会出现A的某row全是0的情况。

Note：为避免各种侵权问题，本文并没有复制原书任意文字(代码除外，作者已经声明代码可以被使用)。需要原书完整中文翻译的读者请等待官方译本的发布。

首先看下这3个不同版本的Get函数：

本文测试环境:

系统：Linux ubuntu 4.2.0-16-generic #19-Ubuntu SMP x86_64 GNU/Linux

gcc版本: gcc version 5.2.1 20151010 (Ubuntu 5.2.1-22ubuntu2)

先贴一段代码(在vs2015编译通过):

在线性代数中，SVD(Singular Value Decomposition)是对实数矩阵(甚至复数矩阵)的一种因式分解。在信号、统计、图像图形学中都有应用。

SVD非常强大且实用，因为数学界前辈已经证明任意的一个矩阵都可以做SVD分解。这一点特别重要，因为相比SVD分解，和SVD相近的特征值分解只能应用于方阵。

第二个重要的点是：SVD分解可用来解决非方阵不能计算逆矩阵的问题。

狄拉克δ函数(Dirac delta)

在卷积那篇文章中，已经提到了狄拉克δ函数的定义:

\[ delta (t) = \begin {cases} +\infty , t=0 \\ 0, t\neq 0 \end {cases} \]

\[ \int _{-\infty }^{\infty }\delta (t)dt = 1 \]

数学中的卷积

卷积的wiki：Convolution。

卷积和(convolution sum)的公式是:

\[ y(t) = x(t)*h(t) = \sum _{\tau =-\infty }^{\infty }x(\tau )h(t-\tau )\]

写成积分形式是:

官方的编译指南：https://gcc.gnu.org/install/

唠叨几句

之前升级了我的阿里云的gcc，记得是费了些功夫的，有些坑。可惜忘了记笔记。今天编译node.js时发现我编译的gcc有些问题，要重新编译下，悲催的是gcc的编译目录都删掉了。全部得重来过。

本文主要写的是公式层面的推导，关于傅里叶变换的应用，请到知乎搜索'傅里叶'，能找到很多不错的文章。

本文主要参考了斯坦福大学Brad Osgood的公开课:

http://open.163.com/special/opencourse/fouriertransforms.html

youtube的比较高清:

https://www.youtube.com/watch?v=gZNm7L96pfY

欧拉公式

复数和三角函数有密切的联系，因为大神欧拉发现了这样的公式：

\[ e^{ix} = \cos x + i\sin x\]

第三章介绍各种特殊几何体。

Ray与Sphere的相交判断

pbrt的TRS分解

设矩阵A，假设A可以分解成T、R、S，则有A=TRS，设A:

\[ A = \left[ \begin{matrix} A_{11}&A_{12}&A_{13}&A_{14}\\ A_{21}&A_{22}&A_{23}&A_{24}\\ A_{31}&A_{32}&A_{33}&A_{34}\\ A_{41}&A_{42}&A_{43}&A_{44}\\ \end{matrix} \right] \]

再设T、R、S分别为：

\[ T = \left[ \begin{matrix} 1&0&0&t_{x}\\ 0&1&0&t_{y}\\ 0&0&1&t_{z}\\ 0&0&0&1\\ \end{matrix} \right] \]

\[ R = \left[ \begin{matrix} r_{11}&r_{12}&r_{13}&0\\ r_{21}&r_{22}&r_{23}&0\\ r_{31}&r_{32}&r_{33}&0\\ 0&0&0&1\\ \end{matrix} \right] \]

\[ S = \left[ \begin{matrix} s_{x}&0&0&0\\ 0&s_{y}&0&0\\ 0&0&t_{y}&0\\ 0&0&0&1\\ \end{matrix} \right] \]

矩阵家族成员非常多，本文主要记录了我遇到过的矩阵(前面的文章所提到的矩阵，在这里就不重复列举了)。以后见识了新的矩阵时，会继续扩充本文。

(以下知识均查阅了wikipedia。单词的中文翻译查的是有道词典。)

原文地址:http://www.3dgep.com/understanding-quaternions/

正文

在这篇文章中我会尝试用简单的方式去解释四元数的概念，即用可视化的方式解释四元数以及几种对四元数的操作。我将把矩阵、欧拉角和四元数放在一起比较，并解释什么时候该用四元数、什么时候该用欧拉角或矩阵。

内容结构

• 介绍
• 复数
  • 复数的加减
  • 复数的系数缩放
  • 复数的积
  • 复数的平方
  • 共轭复数
  • 复数的绝对值
  • 两复数的商
• i的幂
• 复数平面
  • 旋转数（Rotors)
• 四元数
  • 作为有序数的四元数
  • 四元数的加减
  • 四元数的积
  • 实四元数
  • 四元数的系数缩放
  • 纯四元数
  • 四元数的加法形式
  • 单位四元数
  • 四元数的二元形式
  • 共轭四元数
  • 四元数范数
  • 四元数规范化
  • 四元数的逆
  • 四元数的点积
• 旋转
• 四元数插值
  • SLERP
    • 四元数的差
    • 四元数的幂运算
    • 2个四元数的分数差
    • 注意事项
  • SQUARD
• 总结
• 下载Demo

最近在看线代的公开课，顺便也把PBRT这个坑开了，合在一起学。

本文的cpp代码均来自https://github.com/mmp/pbrt-v2，木有修改。只为方便读者阅读。

定义

设A是数域F上的n阶矩阵，如果存在数域F中的一个数\(\lambda \)与数域上F的非零向量\(\vec \alpha \)，使得： \[ A\vec \alpha = \lambda \vec \alpha \] 则称\(\lambda \)为A的一个特征值(根)(eigenvalue)，称\(\vec \alpha \)为A的属于特征值\(\lambda \)的特征向量(eigenvector)。

显然从上式可以看出，\( A\vec \alpha \)和\(\vec \alpha \)平行。

将上式做一下变换：

\[ A\vec \alpha = \lambda \vec \alpha \]

\[ A\vec \alpha - \lambda \vec \alpha = \vec 0 \]

\[ A\vec \alpha - \lambda E\vec \alpha = \vec 0 \]

\[ (A - \lambda E)\vec \alpha = \vec 0 \]

\[ (\lambda E - A)\vec \alpha = \vec 0 \]

称：

• \(\lambda E - A\)为A的特征矩阵

• 行列式\(f(\lambda ) = |\lambda E - A|\)为A的特征多项式

• \(|\lambda E - A| = 0\)为A的特征方程

• \((\lambda E - A)\vec x = \vec 0\)是A关于该\(\lambda \)的齐次线性方程组

A的主对角线上元素之和称为A的迹(trace)，记为tr(A)，即

\[ tr(A) = a_{11} + a_{11} + \cdots + a_{nn} \]

迹和特征值有很重要的联系：

\[ tr(A) = \lambda _{1} + \lambda _{2} + \cdots + \lambda _{n} \]

特征值还和A的行列式有关系：

\[ |A| = \lambda _{1}\lambda _{2}\cdots \lambda _{n} \]

基础知识

标准正交向量组（Orthonormal vectors）的点积(内积)性质：

\( q_{i}^{T}q_{j} = 0 \) if \( i\neq j \)

\( q_{i}^{T}q_{j} = 1 \) if \( i = j \)

其中每个正交向量的长度\(||q_{i}||=1\)。

标准正交向量组成的矩阵是：

投影矩阵是what？

先给出结论：投影矩阵P（projection），可以把一个向量b，投影到一个“空间”上，投影点称为p，从p到b的向量称为e，e = b - p，e的含义是误差向量（error）。

再举例子帮助读者理解：

上述的“空间”为一维时

一个向量b，投影到一个一维的空间，显然，这个空间是一条直线，设直线为单位向量a，那么这个投影其实就是找到这个直线上离b最近的点p，误差向量e就是b到p的距离。因为p在a上，所以有：

p = ax（p和a都是向量，x是一个值）【式子1】

然后，因为p是b在a上的投影，那么意味着，a与e成90度角，当2个向量互相垂直时，他们的点积（或 内积、 dot product）等于0，于是有：

基础议题(basics)

条款1：仔细区别pointers和references

• 使用引用，可以不做null判断
• 当需要考虑“不指向任何对象”的可能性时，或是考虑“在不同时间指向不同对象”的能力时，你就应该采用pointer，前一种情况可以将pointer设为null，后一种情况可以改变pointer所指对象。
• 当确定“总是会代表某个对象”，而且“一旦代表了该对象就不能够再改变”，那么应该选用reference。
• 总是令operator[]返回一个reference。

行列式的求解

从行列式的定义出发去求行列式，是一个简单但低效的方法。而实际上，解决数学问题的途径往往有多种。这里，我将介绍其中一种比较常见的快速解法：PLU分解。

PLU的LU

要理解PLU，得先搞懂LU分解。（这里分享一个外教的讲解视频，简单好理解：https://www.youtube.com/watch?v=UlWcofkUDDU 能翻墙的同学就直接看吧。)

LU分别代表：Lower Triangular Matrix 和 Upper Triangular Matrix，即下三角矩阵和上三角矩阵。

下面手动演示下LU分解过程：

行列式的意义

貌似一般的线性代数教科书并没有告诉读者行列式的实际意义，只是教会了读者行列式的定义和计算方法。（起码我所阅读的线性代数课本没有提及）

那么在这里我简单地介绍一下。

一阶行列式

要说行列式的意义，得先从行列式的"|"符号谈起。下面是一阶方阵的行列式：

\[ |x| = x \]

是不是想到什么？一阶方阵，其实就是一个数，且它的行列式等于这个数。且，一阶方列式的写法，恰好就是高中数学里的绝对值写法！

想一下绝对值的几何意义：指明了一个实数（这里不提虚数）距离数轴原点的大小。

矩阵的基本性质

我对矩阵的定义：一个含有x个元素的数组(x>=1)，以n个数为一段，将把这个数组按顺序分成m段，并按顺序排成m行，就构成了一个矩阵。数组和分段是构成一个矩阵的充分必要条件。

这个定义是从程序实现角度考虑的。一个矩阵可以用二维数组Array[m][n]来存放，也可以用一维数组Array[m*n]来存放，在不考虑实现语言之前，我更倾向于使用一维数组。

矩阵的定义虽然不复杂，但是聪明的数学家对矩阵进行了各种研究，导致产生了非常多的概念、术语、定理、推论：

题解：

设s1，s2是两个长度都为len的字符串（把s1、s2当做字符数组理解）

设状态量res[n][i][j]，(n < len, i <= n, j <= n), 元素是bool值

After robbing those houses on that street, the thief has found himself a new place for his thievery so that he will not get too much attention. This time, all houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, the security system for these houses remain the same as for those in the previous street.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

题意：

"House Robber"的变种（尼玛又改需求了摔)。改动的地方是，房子分布从一条线变成了一个环，首尾相接了。依然是求最大值。

大学时候读过吴军博士的《浪潮之巅》，从中了解到了IT行业的近代史，形形色色的传奇人物和大事件，非常震撼，读完的同时也对作者的才华感到佩服，不仅是一名一流的计算机科学家，更是一位难得的历史研究者。

最近又拜读了吴博士的《数学之美》。入手前以为是一本和《编程之美》类似的书，无非讲讲算法、数学之类的。但等到开始读的时候才发现，这本书的特别之处，他将IT发展史和数学、算法一起介绍，却一点也不显乱，甚至是让枯燥的数学变得生动，读完的感觉就像读了一本小说。

大概记录下读书笔记吧。

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

For example: Given array A = [2,3,1,1,4]

The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)

题意：

Jump Game I 的升级版，问到达最后一个位置时，至少要跳跃多少步。

好几年前就尝试用github pages服务来搭建github博客，当时也已经用了jekyll，不过由于那时候主要是在windows下工作学习（学图形学），手头也只有一台电脑，在win环境弄jekyll实在是不方便，要装ruby啊gem啊，都感觉没有linux环境顺手，最后还是转去了csdn博客。不过csdn博客在我毕业后也是荒废了。

There are N gas stations along a circular route, where the amount of gas at station i is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.

Return the starting gas station's index if you can travel around the circuit once, otherwise return -1.

Note: The solution is guaranteed to be unique.

题意：

有N个加油站，连成环形，每个加油站有gas[i]的油，从第i个加油站到第i+1个加油站需要消耗cost[i]的油。现在有一辆车，它有无限大的油箱，但是是空的。求问这辆车应该从哪个加油站出发，才可以跑一遍所有的加油站，返回该加油站的序号，如果不存在这样的起点，返回-1。

游戏试玩地址：http://wanga.me/45512

技术架构：

平台：web、mobile

引擎：cocos2d

语言：js

使用的插件：chipmunk(物理引擎) underscore(js增强函数库）

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Follow up:

Can you solve it without using extra space?

题意：

判断一个链表是否有环，有环的话返回环的起始节点，无环的话返回NULL。

Find the contiguous subarray within an array (containing at least one number) which has the largest product.

For example, given the array [2,3,-2,4],

the contiguous subarray [2,3] has the largest product = 6.

题意：

求数组里最大的连续子序列的乘积。

Given a 2D binary matrix filled with 0's and 1's, find the largest square containing all 1's and return its area.

For example, given the following matrix:

1 0 1 0 0

1 0 1 1 1

1 1 1 1 1

1 0 0 1 0

Return 4.

题意：

给定一个01矩阵，求矩阵里最大的1字正方形的面积

Given a complete binary tree, count the number of nodes.

Definition of a complete binary tree from Wikipedia: In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.

题意：

求一颗完全二叉树得节点的数量。

Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container.

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).

How many possible unique paths are there?

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [−2,1,−3,4,−1,2,1,−5,4], the contiguous subarray [4,−1,2,1] has the largest sum = 6.

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

For example, given the following triangle

• [
• ........[2],
• .......[3,4],
• .....[6,5,7],
• ....[4,1,8,3]
• ]

The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

Note:

Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.