Richbabe Blog

立志成为一个游戏开发者.

LeetCode86_Partition List

题目 题目地址:LeetCode 86:Partition List 思路 我们可以将结果链表分成两部分,第一部分是比x小的数组成,第二部分是>=x的数组成。那么我们现在需要做的就是遍历原链表,将元素连接到对应的部分中。 链表的题目可以分四步走: 连过来。把想要的节点链接到你需要的链表上。 指针走。该节点处理完了,在原来的链表上要走一步。 断后路。当前链表不要和原来...

LeetCode300_Longest Increasing Subsequence

题目 题目地址:LeetCode 300:Longest Increasing Subsequence 思路 LIS问题是比较简单的动态规划问题了。设dp[i]为以nums[i]结尾的LIS长度(i∈[0,n-1]),其状态转移方程如下: dp[i] = max(dp[j]) + 1(0 <= j < i && nums[j] < nums[i])...

The summary of silhouette drawing

轮廓线渲染方法总结

中山大学 数据科学与计算机学院 软件工程数字媒体 洪鹏圳 前言 众所周知,在非真实感渲染领域的卡通渲染中,轮廓线的绘制起着至关重要的作用,只有加了轮廓的渲染才称得上是真正的卡通渲染。近20年来,有许多绘制模型轮廓线的方法被先后提出来。在《Real Time Rendering,third edition》[1]一书中,作者把这些方法分成了5种类型。 所用到的测试场景如下: 其...

LeetCode83_Remove Duplicates from Sorted List

题目 题目地址:LeetCode 83:Remove Duplicates from Sorted List 思路 当遍历当前节点时,将其next节点往后移直到next节点的值与当前节点不同为止。然后令当前节点=next节点。重复此操作直到遍历完整个链表。 代码 C++版本代码如下: /** * Definition for singly-linked list. * struc...

基于图像处理的轮廓线渲染

中山大学 数据科学与计算机学院 软件工程数字媒体 洪鹏圳 前言 在大三上学期,我曾经上过一门课叫做数字图像处理,万万没想到在研究NPR的时候他居然能够派上用场,看来DIP和CV还是有所交集的。众所周知,图像处理是对一张图像进行像素级的处理,那么我们如何在游戏开发中应用图像处理的方法呢?那就要引入屏幕后处理技术了。 屏幕后处理 屏幕后处理简介 屏幕后处理效果(screen po...

LeetCode79_Word Search

题目 题目地址:LeetCode 79:Word Search 思路 看到这种搜索类题目,第一反应就是DFS和BFS,在这里我使用DFS。在遍历完矩阵一个元素时,我将其置为’\0’,以防下次再次遍历到,这样做可以避免用一个二维数组存储遍历状态,减小空间复杂度。 代码 C++版本如下: class Solution { public: bool exist(vector<...

Cel Shading

一种卡通着色技术

中山大学 数据科学与计算机学院 软件工程数字媒体 洪鹏圳 前言 在非真实感渲染中,有两种经典的NPR着色方法,一种即是我们上次讲过的Tone Based Shading。另一种则是我们这次要讲的Cel Shading(Wiki介绍)。由于Cel Shading对于美术来说更好控制渲染的效果,因此在现实中往往会采用Cel Shading来模拟卡通风格的渲染。 最原始的Cel S...

ToneBasedShading

基于色调的光照模型

中山大学 数据科学与计算机学院 软件工程数字媒体 洪鹏圳 参考论文 A Non-Photorealistic Lighting Model For Automatic Technical illustration Abstract 在1998年,Gooch等人发了一篇论文中提出并实现了基于色调的光照模型。基于色调的光照模型主要是通过亮度和色调的变化来指示物体表面方向:...

LeetCode78_Subsets

题目 题目地址:LeetCode 78:Subsets 思路 当我们遍历nums中的每一个数时,我们需要将这个数插入到我们的子集中的每个集合中。因此我们可以先声明一个空子集,每遍历一个数我们便把子集中的每个集合复制一份,加入该数再压入到子集中。 代码 C++版本如下: class Solution { public: vector<vector<int>&g...

LeetCode76_Minimum Window Substring

题目 题目地址:LeetCode 76:Minimum Window Substring 思路 我们可以使用双指针实现滑动窗口来在O(n)的时间复杂度解决这道题。 具体做法如下: 先扫描一边T,把对应的字符及其出现的次数存到哈希表中 用一个count来记录当前T中还有多少个字母未匹配,用start和end分别表示滑动窗口的左边界和右边界 开始遍历S,先向右移动窗口的右边界...