形式语言与自动机

• 未来一定属于语言的胜利。语言将一统天下（未来AI也会用“最优”的语言来思考）。

一直好奇的是，远古巨神们是怎么发明出计算机的？计算机也肯定是遵循某些理论发展出来的。

阿兰·图灵和冯·诺依曼是公认的两位计算机之父。图灵机从理论上证明了计算机这种东西可行，而冯诺依曼结构则从物理上实现了图灵机的理论。即使到现在，几乎所有计算模型和结构也没能脱离这两者而存在。

• 什么是形式语言与自动机？

计算机科学有两个主要的部分: 第一, 构成计算系统基础的一些基本概念和模型; 第二, 设计计算系统 (软件和硬件) 的工程技术。形式语言与自动机理论, 就是作为第一部分, 即构成计算基础的基本概念的引论。

如果你之前接触过开发，有着UI编写经验，这也许是最容易理解的教程。就算之前没接触过开发，也能迅速理解css的盒模型原理。

编写界面，无非是把你想放的元素放到该放的位置上去。

css中的一个基本概念是盒模型，可见元素会在页面中占据一个矩形区域，该区域就是元素的盒子(box)。

gradle上路篇

作为写Android的人（虽然现在重心已经偏向js），当遇上gradle编译时各种各样的错误，，你却不知道怎么办，有时虽然解决了却不知道所以然，我想这样的经历绝不只有我一个。

如果说为什么对gradle始终很糊涂，那么Android Studio将要背很大的锅，因为IDE为你生成好了构建脚本，所以你无需花很多精力去了解它，你的任务更多只是在业务代码本身，事实上，学习gradle你还可以更加地了解android程序整个构建过程，在这一点上，恐怕很多人也跟当初我一样是一知半解的。

为什么是build.gradle?

对呀，为什么是这个文件？其实它没有什么特别的，只不过因为它是默认的构建脚本。所以好事者说，我想执行自己的怎么办？比如a.gradle？ 好，那么其实你可以执行以下命令：

1

$ gradle -b a.gradle yourtask

这样子你可以将构建脚本替换成你想执行的a.gradle。可能对于一直点击

run](/images/run.png)图标的同学来说，`gradle`命令行甚至都没用过，这个`yourtask`是什么鬼？其实在你点击了![run

Groovy语言

gradle脚本其实是基于一个叫Groovy的语言编写的，它的语法相当友好，兼容java语法，有着一些java语言并没有的特性，比如函数传参。但事实上，你并不需要过多了解这门语言，对于gradle脚本来说，掌握部分就够用了。

我并不想在这里介绍Groovy语言，有闲时间我建议直接看Groovy的官方指南：

http://groovy-lang.org/documentation.html

给定整数数组，每个元素出现三次，除了一个出现恰好一次。找到那个单一的。

这道题如果换成“给定整数数组，每个元素出现两次，除了一个出现恰好一次。找到那个单一的。”会简单很多，因为利用异或操作符，可以把两个相同的元素消掉。比如：a^a=0。

但是现在问题是出现了三次,先放上代码：

1
2
3
4
5
6
7

def singleNumber(A):
    ones = 0
    twos = 0
    for i in A:
        ones = (ones ^ i) & ~twos
        twos = (twos ^ i) & ~ones
    return ones

这代码一看就懵逼。而且对于不熟悉位操作的人，简直就是痛苦。WTF？
这段代码看上去很诡异，但其实它是有来头的。

位操作

一道典型的面试题：

给定一个数组，它里面的元素都出现过两次，除了有一个元素，请找出这个元素。

暴力点的，估计就双重循环解决了。。。

但事实上，有一个时间复杂度为O(n)的方法。那就是位操作。

平时码业务逻辑的代码多了，都忘了位操作究竟是啥。

bst

大概从接触到计算机开始算起，就知道计算机中存储都是以补码形式，且认为补码就是“符号位不变，取反加一”，貌似它像一个已有的实体一样, 已经不需再形式的去定义它, 如同几何学中对“点”和“线”的概念不加定义一样。但事实上，它背后还是有点故事的，在教材中也有提及，但是几乎都被我们忽略了。

why two’s complement?

如果你还是第一次听说这个two's complement的，不妨接下来看看。笔者最近在看自动机方面的书籍，涉及到状态机的时候，经常会拿补码举例子，有时看不懂了，就去google。我就寻思这个补码的英文是什么，结果一搜，two's complement, 直接意译过来，就是2的补码。

WTF?当年看计算机组成原理好像没听过这玩意儿啊~

Gulp构建工具

gulp与webpack

• gulp是工具链、构建工具，可以配合各种插件做js压缩，css压缩，sass编译 替代手工实现自动化工作
• webpack是文件打包工具，可以把项目的各种js文、css文件等打包合并成一个或多个文件，主要用于模块化方案，预编译模块的方案

其实webpack很多功能gulp都能做，gulp甚至能够配置webpack，所以这两者之间是没有冲突的。

举个例子，说到js压缩，现在的人都用uglify，如果有多个要压缩的文件，咋办？你总不能一个一个去压缩吧。所以好事者就写脚本，写个.sh或者.bat什么的。幸运的是，gulp有uglify的插件，你就不用重复造轮子了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

// 压缩js
gulp.task('jszip', function (callback) {
    pump(
        [
            gulp.src('app/**/*.js'),
            uglify({
                mangle: true,//类型：Boolean 默认：true 是否修改变量名
                compress: true//类型：Boolean 默认：true 是否完全压缩
            }),
            gulp.dest('dist')
        ],
        callback
    );
});

上面就是一个例子，把app文件夹下的js文件都压缩并打包到dist文件夹里。是不是很方便？

红黑树

• 红黑树（英语：Red–black tree）是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。它是在1972年由鲁道夫·贝尔发明的，他称之为”对称二叉B树”，它现代的名字是在Leo J. Guibas和Robert Sedgewick于1978年写的一篇论文中获得的。它是复杂的，但它的操作有着良好的最坏情况运行时间，并且在实践中是高效的：它可以在O(logn)时间内做查找，插入和删除，这里的n是树中元素的数目。

维基百科上的定义就这么说了。好像你看了之后也不知道它究竟是啥。因为红黑树本身是非常绅士（hentai）的数据结构。

二叉查找树

“自平衡二叉查找树？什么是平衡树？什么是二叉查找树？”
不得不说这由红黑树引发的关于Data Structure知识匮乏的一系列惨案。。。

回顾一下二叉查找树吧（基础好的同学可以略过直接跳往红黑树）。它满足以下性质：

1. 若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
2. 若任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
3. 任意节点的左、右子树也分别为二叉查找树；
4. 没有键值相等的节点。

如何构造一颗二叉查找树？

LRU是什么

说白了就是一种替换策略，在固定容量的缓存中，当存储满了的时候，新的数据插入，该采用何种策略，LRU就是其中一种，LRU(least recently used)，顾名思义就是最近最少使用。当新的插入时，我们要把最近最少使用的给从缓存里拿掉。

实现思路

链表+哈希表

java中可以使用LinkedHashMap来实现，但我这里只给个简单的实现。