rapheal
- 浏览: 171055 次
- 性别:
- 来自: 广州
-
最新评论
-
donkeydoney：
为什么不在每次递归时把当前节点的visited设置为true？ ...
【算法入门】深度优先搜索(DFS) -
zy416548283：
忍不住给楼主顶一个～
【算法入门】深度优先搜索(DFS) -
被淹死的鱼鱼：
写的不错 支持下
PHP-Zend引擎剖析之词法分析（一） -
rapheal：
jordan_micle 写道双显示器真是必需的。。。。个人觉 ...
浏览器处理“盒子” -
jordan_micle：
双显示器真是必需的。。。。
浏览器处理“盒子”
文章列表
前言
UglifyJS会对JS文件的变量名进行混淆处理，要理解Javascript变量混淆的细节，我们需要回答以下几个问题：1.遇到一个变量myName，我们怎么知道这个myName变量要不要混淆2.混淆名字怎么生成才合适，新的名字替换旧的名字时有 ...
前言
这一次，我围绕Hello World来展开Zend虚拟机的执行过程。Hello World的PHP版本:
<?php
echo 'Hello World';
?>
前一篇文章聊到的词法分析阶段就会把上边的脚本分析出一个Token序列：
我们得到一个Token序列：T_OPEN_TAG, T_ECHO, T_CONSTANT_ENCAPSED_STRING, ';', T_CLOSE_TAG。但在Zend虚拟机执行的过程中，是怎么去分析这个Token序列的？
<!--more-->
跟踪运行轨迹
我们还是从 ...
前言
闲来研究一下PHP底层的Zend引擎源码，Zend引擎是PHP脚本的虚拟机。
在PHP上层有SAPI接口，负责对各个接入层的抽象，例如PHP在Apache模块里边的实现，Fast-CGI的实现，命令行的实现。在PHP底层便是Zend虚拟机，Zend虚拟机负 ...
jQuery源码剖析
- 博客分类：
- Web前端
博客移到SAE上，域名暂时没买。
最近写了一系列jQuery1.9.0源码分析http://rapheal.sinaapp.com/category/js/jquery/，欢迎交流。
【算法入门】深度优先搜索(DFS)
- 博客分类：
- 算法
深度优先搜索(DFS)
【算法入门】
郭志伟@SYSU：raphealguo(at)qq.com
2012/05/12
1.前言
深度优先搜索（缩写DFS）有点类似广度优先搜索，也是对一个连通图进行遍历的算法。它的思想是从一个顶点V0开始，沿着一条路一直走到底，如果发现不能到达目标解，那就返回到上一个节点，然后从另一条路开始走到底，这种尽量往深处走的概念即是深度优先的概念。
广度/宽度优先搜索(BFS)
【算法入门】
郭志伟@SYSU：raphealguo(at)qq.com
2012/04/27
1.前言
广度优先搜索（也称宽度优先搜索，缩写BFS，以下采用广度来描述）是连通图的一种遍历策略。因为它的思想是从一个顶点V0开始，辐射状地优先遍历其周围较广的区域，故得名。
一般可以用它做什么呢？一个最直观经典的例子就是走迷宫，我们从起点开始，找出到终点的最短路程，很多最短路径算法就是基于广度优先的思想成立的。
算法导论里边会给出不少严格的证明，我想尽量写得通
这篇文章写得太好了，瞬间把虚表的一些细节弄懂了。
有必要转一下，以后可以翻看。
转自陈皓老师的《C++ 虚函数表解析》
前言
C++中的虚函数的作用主要是实现了多态的机制。关于多态，简而言之就是用父类型别的指针指向其子类的实例，然后通过父类的指针调用实际子类的成员函数。这种技术可以让父类的指针有“多种形态”，这是一种泛型技术。所谓泛型技术，说白了就是试图使用不变的代码来实现可变的算法。比如：模板技术，RTTI技术，虚函数技术，要么是试图做到在编译时决议，要么试图做到运行时决议。
1163. Tour
题目大意：
就是一个双调旅程问题，从最左边的点走到最右边的点，然后从最右边走回最左边，问这段旅程的最短距离。
解题思路：
题目已经告诉我们，所有的点已经按照左到右的顺序输入了。
题目可以转换成，从第一个点出发，分两路A，B走，最后汇集到第n个点。
用动态规划：
dp[i][j]表示A到达i点，B到达j点时的最短路径。我们始终考虑i>=j，根据对称性可以得出其余解
于是dp[n][n]表示最终解。
当前的状态为dp[i][j]，分情况：
j != i - 1 时：此时dp[i-1][j]再通过从点i-1到i即可。
...
1221. 数字游戏
解题思路：
题目有个地方，我理解错了，导致WA很多次，问题是当你擦除a[i]时，你要将它对应的b[i]去减剩余的序列，之前一直以为第i轮就减去b[i]，ORZ。
简单的动态，dp[i]表示去到第i轮时的最大擦出和。
按照我们直观的思路，肯定是最大消费的（也就是b[i]比较大的）应该先拿掉，因此我们先按照cost排序。
dp[j] = min{dp[j-1] + nodes[i].v - nodes[i].cost*(j-1)};
源码如下：
/*
* main.cpp
*
* Created on: Sep 23, 2011
...
1001. Alphacode
题目大意：
将一串字符串（只有A-Z）转化成数字0-9，转换的规则：A->1，B->2 ......Z->26。
那么从这段数字再转换回去字符串就会发生一些歧义，题目要求求出一段数字转换成字符串的最多数量。
解题思路：
如果说用dp[i]表示当前的前i个数字能够转化的字符串数量，当str[i+1]加进来时，如果说跟前面的一个字符能够构成26以下的数字，那说明这个状态至少有两种组合选择：
跟第i个数字一起翻译，那么前i-1个就是一个子状态了；
单独翻译，那前i个作为一个整体；
于是状态的转 ...
1011. Lenny's Lucky Lotto
题目大意：
给定正整数n, m，构建的列表满足下列条件：
列表长度为n
列表的第i个数不能超过2的i次方
列表的最后一个数不能超过m
求出这样的列表的最大数目。
解题思路：
一般遇到需要求最优解的，应该立马想到动态规划；
影响列表的数目的应该是有两个状态，一个是列表的长度，一个是列表的末尾值。因此采用两个状态，申请表dp[11][2001]。其中dp[i][j]表示：当长度为i，末尾为j的列表的数目。
状态转移方程：
dp[i][j] = dp[i][j-1] + dp[i-1 ...
刚刚装了Linux系统，要连上校内网，得用到华为的H3C iNode。
刚刚开始使用Linux，很多不熟悉的地方。
不过这两天在搞Linux，有种很兴奋的感觉，对它突然很感兴趣。
记录一下在我的Fedora下安装iNode的过程，纯粹是无技术性的文章。
1.解压
tar -zxvf iNode.tar.gz
2.进目录iNodeClient
cd iNodeClient
3.执行install.sh
bash install.sh 或者 ./install.sh
在这个过程提示了缺少so等文件时，使用yum install xxx.so下载安装即 ...
前言
Web2.0发展的迅猛，个人觉得很大程度依托于Ajax的出现。然而，我们分享一个网页给好友一般都是直接把URL复制给他，但是Ajax的特点导致了同样一个URL，有可能你跟你的好友看到的内容是完全不一样的，这个真的很头疼。
于是我发现了如果从URL的HASH入手（也就是URL后边#的部分）可以跟踪这个浏览记录的历史，在此记录一下。
Ajax
既然出现了Ajax这个词，我想就稍微解释一下。
Ajax:“Asynchronous JavaScript and XML”（异步JavaScript和XML)。
有点抽象！
想想一般访问一个网站是通过什么方式，输入地址，浏览器向服务 ...
前言
记得long long ago，刚刚开始写JS的时候，我喜欢写一些函数在JS文件里边，然后通过script标签引进来，在DOM节点上绑定onclick等事件，看了很多人写的代码，也大多是这样。
后来会发现，当项目小的时候这么做为了快速开发是 ...