Tags:

Graphics Pipeline

Written on August 5, 2018

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

(更新ing)

Read More

碰撞检测算法(二):原始GJK详解

Written on March 20, 2018

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

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

GJK的主要特性:

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

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

目录:

Read More

Canvas的transform函数与2D仿射变换矩阵分解

Written on February 7, 2018

最近偶然接触了一下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函数?

Read More

骨骼动画与蒙皮矩阵

Written on January 4, 2018

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

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

Read More

Bounding Volume Hierachy of pbrt 解析(2) HLBVH

Written on December 21, 2017

HLBVH

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

recursiveBuild有2个缺点:

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

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

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

Read More

Bounding Volume Hierachy of pbrt 解析(1)

Written on December 20, 2017

二叉树BVH

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

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

Read More

方差阴影贴图与切比雪夫不等式

Written on November 17, 2017

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

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

现代抗锯齿技术——PPAA中的新星SMAA

Written on October 22, 2017

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。

Read More

法向量矩阵

Written on October 15, 2017

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

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

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

Read More

ssao介绍

Written on September 28, 2017

AO,ambient occlusion

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

SSAO,screen-space ambient occlusion

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

Read More

PBR渲染原理

Written on September 23, 2017

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

Read More

错误使用四元数依然会出现Gimble Lock

Written on May 30, 2017

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

Read More

碰撞检测算法

Written on May 10, 2017

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

Read More

forwarder概况

Written on March 18, 2017

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

Read More

细说红黑树(1)-核心定理

Written on October 7, 2016

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

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

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

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

Read More

立体角(Solid Angle)详解

Written on July 9, 2016

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

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

Read More

线性代数之主成分分析(PCA)算法

Written on May 30, 2016

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

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

Read More

线性代数之伪逆矩阵(pseudoinverse matrix)

Written on May 29, 2016

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

Read More

矩阵微分(一)

Written on May 8, 2016

基本认识

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} \]

Read More

最小二乘估计(Least Squares Estimator)的公式的推导

Written on May 6, 2016

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

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

\[ y = ax + e \]

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

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

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

Read More

线性代数之视角矩阵Lookat Matrix

Written on March 20, 2016

引言

(下文的讨论基于右手坐标系,以及矩阵左乘顺序。)

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

Read More

曲线数学之B样条曲线B-Spline

Written on December 29, 2015

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

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

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

Read More

线性代数之Cholesky分解

Written on December 19, 2015

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

算法原理

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

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

\[ A = LL^{T} \]

L是下三角矩阵。

Read More

线性代数之逆矩阵

Written on December 19, 2015

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

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

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

Read More

《Effective Modern C++》读书笔记

Written on November 8, 2015

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

Read More

线性代数之奇异值(SVD)分解

Written on October 27, 2015

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

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

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

Read More

理解卷积 Convolution

Written on October 18, 2015

数学中的卷积

卷积的wiki:Convolution

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

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

写成积分形式是:

Read More

gcc-4.9.3 编译过程笔记

Written on October 15, 2015

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

唠叨几句

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

Read More

复数和三角函数

Written on October 10, 2015

欧拉公式

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

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

Read More

线性代数之TRS分解

Written on October 5, 2015

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] \]

Read More

线性代数之各种各样的矩阵

Written on October 5, 2015

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

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

Read More

Understanding Quaternions 中文翻译《理解四元数》

Written on September 30, 2015

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

正文

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

内容结构

Read More

矩阵的特征值、特征向量、特征矩阵、迹、特征值分解

Written on September 26, 2015

定义

设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} \]

Read More

线性代数之正交矩阵与QR分解

Written on September 26, 2015

基础知识

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

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

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

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

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

Read More

线性代数之投影矩阵

Written on September 26, 2015

投影矩阵是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,于是有:

Read More

More Effective C++ 笔记

Written on September 6, 2015

基础议题(basics)

条款1:仔细区别pointers和references

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

线性代数之PLU分解

Written on August 31, 2015

行列式的求解

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

PLU的LU

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

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

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

Read More

线性代数之矩阵与行列式(2)

Written on August 29, 2015

行列式的意义

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

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

一阶行列式

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

\[ |x| = x \]

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

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

Read More

线性代数之矩阵与行列式(1)

Written on August 25, 2015

矩阵的基本性质

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

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

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

Read More

leetcode题解 problem87 Scramble String

Written on July 24, 2015

题解:

设s1,s2是两个长度都为len的字符串(把s1、s2当做字符数组理解)

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

Read More

leetcode题解 problem213 House Robber II

Written on July 24, 2015

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"的变种(尼玛又改需求了摔)。改动的地方是,房子分布从一条线变成了一个环,首尾相接了。依然是求最大值。

Read More

《数学之美》读后小结

Written on July 24, 2015

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

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

大概记录下读书笔记吧。

Read More

leetcode题解 problem 45 Jump Game II

Written on July 20, 2015

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 的升级版,问到达最后一个位置时,至少要跳跃多少步。

Read More

我是这样用jekyll搭建个人博客的

Written on July 18, 2015

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

Read More

leetcode题解 problem 134 Gas Station

Written on July 15, 2015

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。

Read More

leetcode题解 problem 142 Linked List Cycle II

Written on July 8, 2015

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。

Read More

leetcode题解 problem 152 Maximum Product Subarray

Written on July 6, 2015

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.

题意:

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

Read More

leetcode题解 problem 221 Maximal Square

Written on July 5, 2015

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字正方形的面积

Read More

leetcode题解 problem 222 Count Complete Tree Nodes

Written on July 3, 2015

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.

题意:

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

Read More

leetcode题解 problem 11 Container With Most Water

Written on June 30, 2015

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.

Read More

leetcode题解 problem 62 63 Unique Paths I & II

Written on June 27, 2015

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?

Read More

leetcode题解 problem53 Maximum Subarray

Written on June 26, 2015

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.

Read More

leetcode题解 problem120 Triangle

Written on June 25, 2015

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.

Read More

leetcode题解 problem198 House Robber

Written on June 24, 2015

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.

Read More