04 November
On
In Data Structures(数据结构), Knowledge Base(心得笔库), Language Tips(语言初试), Mobile Development(移动开发)

之前一篇的文章中已经简单入门了iOS7中新加的JavaScriptCore框架的基本用法，十分的简单方便而且高效，不过也仅限于数值型、布尔型、字符串、数组等这些基础类型。本文将扩展到更复杂的类型，介绍一下该强大的框架是如何让Objective-C对象和JavaScript对象进行直接互通的。

为了方便起见，以下所有代码中的JSContext对象都会添加如下的log方法和eventHandler：

[codesyntax lang=”objc” lines=”normal”]

JSContext *context = [[JSContext alloc] init];
context.exceptionHandler = ^(JSContext *con, JSValue *exception) {
    NSLog(@"%@", exception);
    con.exception = exception;
};

context[@"log"] = ^() {
    NSArray *args = [JSContext currentArguments];
    for (id obj in args) {
        NSLog(@"%@",obj);
    }
};

[/codesyntax]
Read More →

18 July
On
In Algorithm Analysis(算法分析), Data Structures(数据结构), Knowledge Base(心得笔库)

最长公共子串(Longest Common Substring)是一个非常经典的面试题目，在实际的程序中也有很高的实用价值，所以把该问题的解法总结在本文重。不过不单单只是写出该问题的基本解决代码而已，关键还是享受把学习算法一步步的优化，让时间和空间复杂度一步步的减少的惊喜。

概览

最长公共子串问题的基本表述为：

给定两个字符串，求出它们之间最长的相同子字符串的长度。

最直接的解法自然是找出两个字符串的所有子字符串进行比较看他们是否相同，然后取得相同最长的那个。对于一个长度为n的字符串，它有n(n+1)/2 个非空子串。所以假如两个字符串的长度同为n，通过比较各个子串其算法复杂度大致为O(n4)。这还没有考虑字符串比较所需的时间。简单想想其实并不需要取出所有的子串，而只要考虑每个子串的开始位置就可以，这样可以把复杂度减到O(n3)。

但这个问题最好的解决办法是动态规划法，在后边会更加详细介绍这个问题使用动态规划法的契机：有重叠的子问题。进而可以通过空间换时间，让复杂度优化到O(n2)，代价是空间复杂度从O(1)一下子提到了O(n2)。

从时间复杂度的角度讲，对于最长公共子串问题，O(n2)已经是目前我所知最优的了，也是面试时所期望达到的。但是对于空间复杂度O(n2)并不算什么，毕竟算法上时间比空间更重要，但是如果可以省下一些空间那这个算法就会变得更加美好。所以进一步的可以把空间复杂度减少到O(n)，这是相当美好了。但有一天无意间让我发现了一个算法可以让该问题的空间复杂度减少回原来的O(1)，而时间上如果幸运还可以等于O(n)。
Read More →

23 April
On
In Algorithm Analysis(算法分析), Data Structures(数据结构), Mathematical Theory(数学理论), Special Tricks(奇技妙招)

人类有十个手指，所以我们的算数都是10 进制的，而计算机的世界里，所有事物都只由0和1呈现出来，所以数字也只能用2进制表示。因为2进制的表示方式，在计算机里对于数字的运算，除了现实中常用的“加减乘除”，更多了“与非或”这些位运算。

在进行数学运算的过程中，我们经常会总结出一些技巧方法，而这些方法其实跟进制有很大的关系。比如小学老师就告诉我们：检查一个整数能否被3整除，只要派定各个数位上的数字加起来是否能被3；判定一个整数是否能被5整除，只要看最后一位是不是0或5。而这些规律却不能适用到2进制表示的数字上。

不过利用2进制的特殊性，我们也能从位运算上找到很多的技巧。比如一个常见的面试问题：

有一组数包含了1到100的整数，且每个整数只出现一次且随机出现于数组中，现在有一个数被从中删除，请找出被删除的数。

Read More →

14 March
On
In Data Structures(数据结构), Knowledge Base(心得笔库), Language Tips(语言初试)

对于如何给DOM绑定JavaScript的事件，在之前的文章已经比较详细的介绍了三种方式的区别和优缺点。不过，仍然还有一些遗留问题没有详细讲述，比如addEventListener的第三个参数useCapture有何神奇之处；假如HTML元素的自身和其父结点都绑定了相同类型的事件， 这些事件的激发过程又是如何处理的呢。

每一个HTML页面，在被浏览器解析后，都会生成一个树形结构，而每一个结点都是一个对应于标签(Tag)的DOM(Document Object Model)实例。树形数据结构上，其深度体现着父子关系(parent/child)，其广度表现为兄弟关系(sibling)。这些DOM实例首先是用作呈现页面，在页面呈现上(若不指定特殊的布局样式，如z-index、relative position、float)：子结点会被父结点包裹，但是父结点会被子结点全部或部分覆盖，而同层的结点则按从上往下，从左往右的顺序依次排布——（这只是对HTML页面呈现的简单布局流描述，其实根据样式的不同，过程更复杂）。另一方面，它们还是事件目标，用来接收页面上触发的事件。
Read More →

03 May
On
In Algorithm Analysis(算法分析), Data Structures(数据结构), Knowledge Base(心得笔库), Language Tips(语言初试)

古语“画虎画皮难画骨”，是说画老虎时要画它的外表很容易，可要将老虎的气势画出来却很难。

对于现在的程序员来说，似乎也是这样子，可以写出整洁的代码，设计出优异的程序，但却不一定需要知道代码在编译之后的是如何运行的。

但是有时候，能了解表面背后的故事，知道一些程序编译过程，其实对写出一个正确的正确的程序会有很大的帮助，这起源自一段很简单的问题实现：两整数交换。
Read More →

10 April
On
In Data Structures(数据结构), Language Tips(语言初试)

在《C++的头文件和实现文件分别写什么》文章中，我对于的C++的数据成员，逐个分析了可以作用在它们上边的限定符都有哪些，以及它们所对应的进行初始化的位置。可以看出这些修饰符其实就是const和static的两种的组合，但是却有不同的效用。

本文，我想讲关于static的问题，《C++的头文件和实现文件分别写什么》已经指出如果数据成员被声明为static，那么它在编译时就必须被初始化。仅含static的则放在类之外，实现文件之中；同时含有的const的则放在类之内，直接跟在数据的定义之后。

在我实际代码编写中碰到的问题是：static成员的初始化比较的复杂，步骤较多，需要调用另一个函数来完成。此时，简单使用赋值语句就不太能完成那些目的了。
Read More →