leetcode题解141.Linked list cycle，给定一个单链表，判断该单链表是否有环问题，这个问题蛮简单的，但是在面试中也是经常被问到的，所以要注意一下。解决这道题的思路就是使用两个指针，一个一次走两步，一个一次走一步，如果有环两者必定在某个位置处相遇，只要快的走到了NULL节点，则说明此链表无环。这就是快慢指针找环法，是比较经典的问题。 c++代码如下： class Soluti …Continue reading
对单链表的排序，前几天写过一篇文章使用o(nlog(n))的时间复杂度进行排序，当时说可选的方法是利用归并或者快排对单链表进行排序，这个题目同样给定一个单链表，只不过这里要求用插入排序对其进行排序。在数组中我们使用插入排序的时候通常在寻找插入位置的时候是从后向前，这样可以同时查找并把较大的元素后移一位，然后腾出要插入的位置，但是在单链表中就不行了，首先，单链表不能逆向遍历，第二，单链表无需移动，可 …Continue reading
pat 1005.spell it right. 题目给定一个非负的整数，要求把每一位上的数字相加，得到一个和，然后把这个和从高位到低位翻译成英文单词，1对应one，2对应two，3对three，0对应zero，这样依次将每一位表示成一个单词，输出。 给定的这个整数小于等于10^100次方，所以超出了数据类型int的表示范围，所以注意处理，另外题目中说明是非负整数，所以这就要考虑到临界条件0的处理 …Continue reading
leetcode第148题，sort list，题目给定一个单链表，要求用o(nlogn)的时间复杂度对链表进行排序，其实对于单链表的排序可以使用快排，也可以使用归并排序，对于已排序链表的合并由于比较简单，所以这里就使用归并排序实现一下。 设计了一个找链表中间节点的方法halfList，找到中间节点后将链表一分为二，左右各进行归并排序就好了，最后一个合并两个已排序链表的操作就可以了。 下面使用c+ …Continue reading
pat 1004题。 每个家族结构通常表示为一棵家谱树，家谱树种每一带偶尔会有一些人没有后代。也就是树种每一层偶尔会有无子节点的情况。 题目给定一个家谱树，要求统计每一代，也就是树中每一层有多少个节点没有子节点。 家谱树的输入为按标号输入，输入某个节点，然后后面跟着其所有子节点，一次类推。 做法是逐层遍历，累死与层序遍历，统计每一层中的无子节点的节点个数即可，即每层的叶子节点个数，记录层的方法很多 …Continue reading
pat第二题，给定两个多项式，计算两个多项式相加后的多项式，多项式的给出示例，指数+对应的系数，计算规则是相同指数的系数相加作为新的系数，例如2x^2 + 3x和-x^2 + 3则得到x^2 + 3x + 3。这里需要注意的点有三个，第一要求按指数降序排列，第二精确到小数点后一位，如果计算中出现系数为0，则该项不应该出现在结果中。尤其是第三点如果忘记过滤掉的话，最后一个case会过不去，所以要记得 …Continue reading
PAT的1003题，题目告诉了一张图，图中有很多城市，给出不同城市之间的通路情况，以及路的距离，每个城市中有一定数量的救援队，现在给定一个源城市和一个目的城市，找一条最短路，是的两城市之间的距离最短，同时保证经过的城市中的救援队总和最大。 所以题目就是个双重条件的最短路问题，第一重条件是距离，第二重条件是救援队的数量，首先保证距离最短，在距离相同的情况下选择救援队数量多的路径。所以可以直接使用df …Continue reading
重新开始刷PAT，第一题，最简单的A + B，要求输入两个数A和B，求A+B的值，并对该值做千位分割，即从个位开始，每三位加一个逗号进行隔开，比如10000->10,000,这种格式，因为python中有直接的千位分割的format可用，所以直接用python做了。 python代码： import re if __name__ == '__main__': str = input …Continue reading
程序中经常要对字符串进行处理，处理用户的输入，对文本的编辑等等，都是对字符串的操作，对字符串的操作可以使用正则表达式来进行，正则表达式的使用会使得字符串的处理很方便。 这里就总结下python中的正则表达式，以及主要的用法。 首先\d,\s,\w,. 这四个表达式可以匹配单个字符，其中\d可以匹配任意一个数字0-9,\s可以匹配任意的空白字符，比如空格，tab键等等，\w可以匹配一个数字或者字母, …Continue reading
leetcode第160题，给定两个链表的头节点，求两个链表是否相交，如果相交则返回相交的首节点，否则返回NULL。 思路是两个指针分别从头开始走，直到一个指针为NULL，这说明另一个链表比较长，而且长的这个链表剩下的节点个数正好是长度超出的节点数。这个时候把长的从头开始走，走的步数为整下的节点个数，这样短的节点从头开始，就能保证两者要走的节点数相同，也就是如果相交，那么两者分别走下去一定会在交点 …Continue reading
leetcode第203题，remove linked list elements，题目给定一个单链表和一个值，要求将该单链表中所有val与该给定值相等的节点删除，结果返回删除后的链表，原链表中的元素相对位置不变。 例如： Given: 1 –> 2 –> 6 –> 3 –> 4 –> 5 –> 6, val = 6 Return: 1 –> 2 –> 3 –> 4 –> 5 …Continue reading
简单链表逆置，这个在面试中多次要求被写，是在搞不懂这么简单的问题为什么要放在面试中，直接用头插法就可以了，下面是c++和python代码 c++代码: class Solution { public: ListNode* reverseList(ListNode* head) { ListNode *pre = new ListNode(-1); ListNode *p = head; while …Continue reading
leetcode第234题，简单链表操作的题目，题目要求判断给定的单链表是否是回文的，是返回true，否则返回false。 题目比较简单，直接暴力解，通过快慢指针找到中点，然后把前半部分逆置一下，最后把前后向部分判断元素是否依次相等即可，全相等则回文，否则就不是回文。下面用了c++和python同时实现，两者的思路是完全一样的。 c++代码： class Solution { public: bo …Continue reading
python中的多线程执行可以使用threading模块，导入该模块然后可以利用模块中的多线程类来编写多线程程序，一般涉及到多线程程序的话就避不开锁，因为线程一般是共享进程的资源，所以当多线程要访问进程的资源时，为了保证一致性就要加锁。 在python中多线程实现主要是两种方式：1.直接生成threading.Thread的实例；2.以对象的方式(OOP)实现 1.直接生成threading.Th …Continue reading
leetcode第237题，题目要求写一个函数实现删除链表中的一个节点，该节点以指针给出。一般链表中删除某个节点的时候我们通常是找到要删除节点的前一个节点，然后把当前节点删除掉，但是这里直接给了要删除节点的指针，题目中也说了，该节点不会是尾节点，这样我们就可以把当前节点的内容与当前节点的下一个节点的内容交换，然后删掉下一个节点就可以了。 所以代码比较简单，可以用不同的方法，以下是python和c+ …Continue reading
python的内建函数eval能对四则运算的表达式进行求解，这里简单实现下模拟eval，当然没有实现的向eval那么复杂，现在只能处理所有数字均为个位数的四则运算表达式，表达式包括+，-，*，/,(,)和数字(0-9)。实现的过程很简单，就是借助了逆波兰表达式，先把四则运算表达式转换成逆波兰表达式，然后根据逆波兰表达式求解结果。 程序代码如下，代码中已经实现写了文档测试，可以多测几个： #!/us …Continue reading
python中类似java和c++中一样，建立了一套异常体系，这样允许程序员能够捕获程序中出现的异常，然后简单处理或者继续抛出异常，从而保证程序的健壮性。 异常的语法比较简单，大体框架如下： try: express except oneException: solve exception except twoException solve exception finally: some post …Continue reading
题目给定一个包含数字的链表，要求把链表进行修改，保证奇数位置的元素按顺序排在前面，然后是偶数位置的元素一次排在后面。返回修改后的链表即可。 简单的思路就是把所有奇数位的元素摘出来按原有顺序组成一个链表even然后把所有偶数位置的元素摘出来组成一个新的链表odd，然后把odd链表链在even链表之后就可以了。这样能保证空间复杂度o(1),时间复杂度o(n)。如下为c++和python两个版本的代码。 …Continue reading
leetcode 445题，题目如下： You are given two linked lists representing two non-negative numbers. The most significant digit comes first and each of their nodes contain a single digit. Add the two numbers and …Continue reading
如果把示例数据的顺序改一下，就可以看出规律了。 1 1 2 3 3 \ \ / \ / / 3 2 1 3 2 1 / \ / \ 2 3 1 2 比如，以 1 为根的树的个数，等于左子树的个数乘以右子树的个数，左子树是 0 个元素的树， 右子树是 2 个元素的树。以 2 为根的树的个数，等于左子树的个数乘以右子树的个数，左子树是 1 个元素的树，右子树也是 1 个元素的树。依此类推。 当数组为 …Continue reading
wordpress自从3.0开始是自动添加robots.txt(虚拟的)，这样包括所有爬虫已经正常访问都可以访问到根目录下的robots.txt，但是其实这个文件本身并不存在。而且这个虚拟的robots.txt太过简单了，并没有达到想要的效果，所以一般情况下要自己写一个robots.txt然后上传到网站根目录。 一般自己上传的robots.txt在访问的时候却报404，即文件找不到。这事因为虚拟r …Continue reading
双向反射分布函数（BRDF），能够基于真实世界物理模型来计算给定的入射方向上的光在经过某个表面之后如何在各个出射方向上分布的。这比以往基于经验的模型如phong模型blinn-phong模型能更好的渲染出符合现实世界的真实效果。 基于物理的BRDF种类繁多，但是都要至少满足一下两点要求：1.可逆性，即交换入射和出射方向并不会影响到BRDF的值；2.能量守恒，即出射的各方向能量总和不应该大于入射能量 …Continue reading
题目描述 下图是一个4阶的螺旋数阵： 1 2 3 4 12 13 14 5 11 16 15 6 10 9 8 7 数字从1开始，沿着顺时针方向依次填满整个矩阵。 现在给你矩阵的规模n，请你输出n阶螺旋数阵。 输入描述: 输入包含多组数据，每组数据包含一个正整数n（1≤n≤20）。 输出描述: 对应每组数据，输出相应的螺旋数阵。 每组数据之后输出一个空行作为分隔。 输入例子: 3 4 输出例子: …Continue reading
2016校招互联网公司薪资大全（网上以及群里收集的信息，非个人意见） 华为深圳 ： 14k 16k 18k * 16个月，部分20k，22k正常16k，好多18k，其他地方也都差不多 百度北京 ： 本科12k，硕士14k * 14.6个月 IDL 有的18k，多的有20k，special offer 本科14k， 前端和测试少1k Indeed : 58w人民币 京东 : (16k 18k 22k …Continue reading
lambda函数实际就是匿名函数，现在C++中也支持lambda表达式了，说白了就是一个小的lambda函数。 匿名函数主要是用在某个函数只是使用一下，而且比较轻小，每笔要显示定义时使用，一般用在把函数作为参数传递时非常方便。 python中支持lambda函数，但是一般只支持一行的lambda函数，因为python中希望lambda函数不要太大，太大的话对代码的可读性不是很友好。 举个栗子，使用 …Continue reading
当使用vim编辑一个文件，要从文件中复制大量代码到另一个文件时，通常使用N yy，即 使用yy命令复制大量的行到缓存中，然后到另一个文件中p命令粘贴，但是当代码行数很 多时，会发现虽然成功复制了，但是在粘贴的时候，代码不完整，可能之粘贴了50行等等。 这时候可以在vim中输入命令 set viminfo=’1000,<800 这种命令，选项’用与规定你为多少个文件保存标记(a-z …Continue reading
今天中午照常打开博客后台看一下，发现出现了两万多条评论待审，然后打开一看，发现都是垃圾评论，这么多待审评论，不可能手工删除，于是先记下垃圾评论的IP地址，然后进入后台登陆mysql，使用sql命令直接清除掉所有的待审评论和垃圾评论，命令如下： delete from wp_comments where comment_approved = ‘评论类型’ 这里wp_comments是wordpres …Continue reading
wordpress文章底部可以自动添加版权信息，这里主要是两种方式，一种是在single.php页中的合适位置直接添加，另一种则是在functions.php中通过钩子将版权信息添加在文章内容末尾。题目虽然说基于twenty-twelve主题，其实对任何主题都一样。这里主要介绍第二种方式： function copyright($content) { if(is_single()||is_feed …Continue reading
wordpress博客经常会遇到有人暴力破解密码的问题，也就是有人频繁访问wp-login.php页面，这时候要采取一定的措施解决此问题。 我现在采取的主要是两个方法：1.限制每秒每个IP访问总次数；2.wp-login.php传入参数验证 1.限制每秒每个IP一段时间内访问总次数 http{ … #定义一个名为allips的limit_req_zone用来存储session，大小是10M内存 …Continue reading
python中的函数定义比较简单，但是由于参数的形式多样就导致可以定义非常灵活的函数，下面主要总结下python中函数的知识点。 1.定义 通过 1 def funcName(args): 2 funcBody 就可以定义一个python函数。 比如 1 def maxx(a, b): 2 if a < b: 3 return b 4 else: 5 return a 这样就定义了一个简单的 …Continue reading
一.纹理映射 简单说纹理映射就是将一张或者多张纹理粘贴在mesh的表面，为mesh进行着色的过程，就是纹理映射。 我们在使用opengl进行纹理映射的时候，通常的步骤是： 1.创建纹理对象，加载纹素数据。 2.为mesh上的每个点增加一个uv坐标也就是纹理坐标。 3.将纹理对象与纹理单元进行绑定，即将纹理对象与着色器中纹理采样器相关联。 4.在着色器中直接使用纹理采样器来得到特定纹理坐标出的颜色值 …Continue reading
gravatar 头像确实不错，但是速度也确实慢，虽然现在gravatar已经解锁，但是偶尔总是抽风一下，所以，有的时候还是会导致速度变慢，甚至头像请求不到，所以，最终决定将头像更改为本地头像，也就是完全本地化。 1.首先在网站根目录下建一个avatar文件夹，里面放入一个自定义的头像 2.在主题文件下修改functions.php，添加如下代码，但是src=”http://www.i …Continue reading
这几天发现blog的访问速度偶尔还是有点慢，F12后发现还是fonts.googleapis.com链接拖慢速度，google字体其实已经解封了，但是偶尔访问速度还是差强人意，这次决定彻底解决这个问题。 网上有很多不同的方法，有的是禁用google字体，有的是换成360的cdn，我觉着这些方法都不靠谱，如果禁用，势必导致某些格式出错，虽然不影响，只是可能看起来字体不是很舒服而已。用360的也不放心 …Continue reading
python的控制语句主要是条件判断和循环 1.条件判断 1 #单if形式 2 if state： 3 express 4 5 #if and else形式 6 if stateA： 7 expressA 8 else: 9 expressB 10 11 #多重条件判断形式 12 if stateA: 13 expressA 14 elif stateB 15 expressB 16 . 17 . …Continue reading
文章中有时候会用到少量代码，在文章中为了方便阅读代码，一般会高亮的形式显示代码，类似编译器中的格式，以前使用了几款不同的代码高亮插件来实现，但是发现经常就是这些插件会拖慢加载速度，或者插件一崩溃就会导致原来的文章代码部分无法正常查看。 现在可以使用sublime来产生相应的带格式的代码，然后直接把这些代码插入到文章中即可（以html格式插入）。这样就不会有拖慢速度的现象，而且因为没有使用插件，也不 …Continue reading
python内置了不少容器，主要有list，tuple，dict和set等几种。 1.list 在python中list就类似于一个链表，或者说列表，从来从出大量数据 list.append(x); #在list的末尾添加元素x，尾部插入 list.extend(L); #L也是一个list，extend就是说在当前list后面插入整个L list.insert(index, x); #在list …Continue reading
经典的hello， world 1.python的输入输出主要是input和print从标准输入输出进行内容读取打印 print(‘hello, world!’); 这句可以在屏幕上打印hello, world！ input()函数可以接受标准输入的输入内容，同时可以赋给一个相应的变量，var = input(); 当然也可以加入提示语，比如var=input(‘ …Continue reading
做全局光照的时候，要用到每个点发射射线然后跟mesh的相交检测，检测量非常大，效率是很大的瓶颈，考虑使用CGAL中的快速求交模型，内部会建立kdtree，从而加速求交检测的过程。 简单记录下配置CGAL库的过程： CGAL库依赖于boost库，所以配置CGAL要首先配置boost库，如果只是使用CGAL的快速求交相应的函数的话就不需要使用期demo了，因为CGAL的demo用到QT，要是运行dem …Continue reading