Happy everyday!

2016-04-05

3-sum

给定一个数组，求和为0的三个数(a+b+c=0)
• (a, b, c) 非降序 (ie, a ≤ b ≤ c)
• 例如：S = {-1 0 1 2 -1 -4}.
解为：(-1, 0, 1)
(-1, -1, 2)

2016-04-05

OSX安装qemu

sudo brew install qemu

==> Installing dependencies for qemu: jpeg, libpng, libtasn1, gmp, nettle
==> Installing qemu dependency: jpeg
==> Downloading https://homebrew.bintray.com/bottles/jpeg-8d.el_capitan.bottle.2
######################################################################## 100.0%
==> Pouring jpeg-8d.el_capitan.bottle.2.tar.gz
Error: The `brew link` step did not complete successfully
The formula built, but is not symlinked into /usr/local
Could not symlink include/jconfig.h
/usr/local/include is not writable.

You can try again using:
  brew link jpeg
==> Summary
🍺  /usr/local/Cellar/jpeg/8d: 18 files, 712.4K
==> Installing qemu dependency: libpng
==> Downloading https://homebrew.bintray.com/bottles/libpng-1.6.21.el_capitan.bo
######################################################################## 100.0%
==> Pouring libpng-1.6.21.el_capitan.bottle.tar.gz
Error: The `brew link` step did not complete successfully
The formula built, but is not symlinked into /usr/local
Could not symlink include/libpng16
/usr/local/include is not writable.

You can try again using:
  brew link libpng
==> Summary
🍺  /usr/local/Cellar/libpng/1.6.21: 17 files, 1.2M
==> Installing qemu dependency: libtasn1
==> Downloading https://homebrew.bintray.com/bottles/libtasn1-4.7.el_capitan.bot
######################################################################## 100.0%
==> Pouring libtasn1-4.7.el_capitan.bottle.tar.gz
Error: The `brew link` step did not complete successfully
The formula built, but is not symlinked into /usr/local
Could not symlink include/libtasn1.h
/usr/local/include is not writable.

You can try again using:
  brew link libtasn1
==> Summary
🍺  /usr/local/Cellar/libtasn1/4.7: 57 files, 434.1K
==> Installing qemu dependency: gmp
==> Downloading https://homebrew.bintray.com/bottles/gmp-6.1.0.el_capitan.bottle
######################################################################## 100.0%
==> Pouring gmp-6.1.0.el_capitan.bottle.tar.gz
Error: The `brew link` step did not complete successfully
The formula built, but is not symlinked into /usr/local
Could not symlink include/gmp.h
/usr/local/include is not writable.

You can try again using:
  brew link gmp
==> Summary
🍺  /usr/local/Cellar/gmp/6.1.0: 15 files, 3.2M
==> Installing qemu dependency: nettle
==> Downloading https://homebrew.bintray.com/bottles/nettle-3.2.el_capitan.bottl
######################################################################## 100.0%
==> Pouring nettle-3.2.el_capitan.bottle.tar.gz
Error: The `brew link` step did not complete successfully
The formula built, but is not symlinked into /usr/local
Could not symlink include/nettle
/usr/local/include is not writable.

You can try again using:
  brew link nettle
==> Summary
🍺  /usr/local/Cellar/nettle/3.2: 75 files, 1.9M
==> Installing qemu dependency: gnutls
==> Downloading https://homebrew.bintray.com/bottles/gnutls-3.4.10.el_capitan.bo
######################################################################## 100.0%
==> Pouring gnutls-3.4.10.el_capitan.bottle.tar.gz
Error: The `brew link` step did not complete successfully
The formula built, but is not symlinked into /usr/local
Could not symlink include/gnutls
/usr/local/include is not writable.

You can try again using:
  brew link gnutls
==> Summary
🍺  /usr/local/Cellar/gnutls/3.4.10: 1,094 files, 6.8M
==> Installing qemu dependency: gettext
==> Downloading https://homebrew.bintray.com/bottles/gettext-0.19.7.el_capitan.b
######################################################################## 100.0%
==> Pouring gettext-0.19.7.el_capitan.bottle.tar.gz
==> Caveats
This formula is keg-only, which means it was not symlinked into /usr/local.

OS X provides the BSD gettext library and some software gets confused if both are in the library path.

Generally there are no consequences of this for you. If you build your
own software and it requires this formula, you'll need to add to your
build variables:

    LDFLAGS:  -L/usr/local/opt/gettext/lib
    CPPFLAGS: -I/usr/local/opt/gettext/include

==> Summary
🍺  /usr/local/Cellar/gettext/0.19.7: 1,929 files, 16.6M
==> Installing qemu dependency: libffi
==> Downloading https://homebrew.bintray.com/bottles/libffi-3.0.13.el_capitan.bo
######################################################################## 100.0%
==> Pouring libffi-3.0.13.el_capitan.bottle.tar.gz
==> Caveats
This formula is keg-only, which means it was not symlinked into /usr/local.

Some formulae require a newer version of libffi.

Generally there are no consequences of this for you. If you build your
own software and it requires this formula, you'll need to add to your
build variables:

    LDFLAGS:  -L/usr/local/opt/libffi/lib

==> Summary
🍺  /usr/local/Cellar/libffi/3.0.13: 14 files, 373.2K
==> Installing qemu dependency: glib
==> Downloading https://homebrew.bintray.com/bottles/glib-2.46.2.el_capitan.bott
######################################################################## 100.0%
==> Pouring glib-2.46.2.el_capitan.bottle.tar.gz
Error: The `brew link` step did not complete successfully
The formula built, but is not symlinked into /usr/local
Could not symlink include/gio-unix-2.0
/usr/local/include is not writable.

You can try again using:
  brew link glib
Warning: The post-install step did not complete successfully
You can try again using `brew postinstall glib`
==> Summary
🍺  /usr/local/Cellar/glib/2.46.2: 421 files, 22.3M
==> Installing qemu dependency: pixman
==> Downloading https://homebrew.bintray.com/bottles/pixman-0.34.0.el_capitan.bo
######################################################################## 100.0%
==> Pouring pixman-0.34.0.el_capitan.bottle.tar.gz
Error: The `brew link` step did not complete successfully
The formula built, but is not symlinked into /usr/local
Could not symlink include/pixman-1
/usr/local/include is not writable.

You can try again using:
  brew link pixman
==> Summary
🍺  /usr/local/Cellar/pixman/0.34.0: 11 files, 1.2M
==> Installing qemu
==> Downloading https://homebrew.bintray.com/bottles/qemu-2.5.0_2.el_capitan.bot
########################################                                  56.1%m######################################################################## 100.0%
==> Pouring qemu-2.5.0_2.el_capitan.bottle.tar.gz
🍺  /usr/local/Cellar/qemu/2.5.0_2: 125 files, 118.3M

使用GDB调试工具

堆栈帧

使用valgrind检查内存使用错误

valgrind your_program

单元测试

使用getenv

#include <stdlib.h> //getenv, atoi
#include <stdio.h>  //printf

int main(){
    char *repstext = getenv("reps");
    int reps = repstext ? atoi(repstext) : 10;

    char *msg = getenv("msg");
    if (!msg) msg = "Hello.";

    for (int i=0; i< reps; i++)
        printf("%s\n", msg);
}

使用reps=10 msg="Ha" ./getenv传递环境变量。

包管理器

编译器

gcc
Clang

调试器

gdb

Valgrind

测试内存使用错误

gprof

代码剖析器

make

pkg-config

pkg-config是向程序提供相应库的路径、版本号等信息的程序。
如：
$pkg-config –libs –cflags opencv
会显示如下信息：
-I/usr/include/opencv -lcxcore -lcv -lhighgui -lcvaux
得到的是用gcc编译连接时CFLAGS的参数。因此当我们需要编译连接某个库时，我们只需要把上面那行加入gcc 的参数里面即可。这也是configure的作用，它会检查你需要的包，产生相应的信息。
那pkg-config从哪儿知道这些信息的呢？它是从包名为xxx.pc这个文件中查找到的。拿上面那个例子说，它是从opencv.pc这个文件中查知的。
那pkg-config 又怎么会知道opencv.pc这个文件呢？下面我们看一下pkg-config是怎样工作的。
缺省情况下，pkg-config首先在prefix/lib/pkgconfig/中查找相关包（譬如opencv）对应的相应的文件（opencv.pc）。在linux上上述路径名为 /usr/lib/pkconfig/。若是没有找到，它也会到PKG_CONFIG_PATH这个环境变量所指定的路径下去找。若是没有找到，它就会报错，例如：
Package opencv was not found in the pkg-config search path. Perhaps you should add the directory containingopencv.pc’
to the PKG_CONFIG_PATH environment variable
No package ‘opencv’ found
`

寻找库的工具，使用见下面库文件的路径。

产生文档的工具

编辑器的选择

Emacs
vim
Kate
nano

一些IDE的选择

Autotools

Git

shell的替代品

常用的编译器选项

-g - 加入调试符号
-std=gnu11 - C11标准
-O2 - 优化等级
-Wall - 添加编译器警告

库的路径

C程序设计时，常常遇到找不到路径的问题。
对路径的理解，有助于问题的排查。

库文件在哪里

典型的情况下，库存放的地方至少有三个：
1、操作系统预定义的安装库文件的目录
2、本地系统管理员的库安装目录，不会被操作系统的更新覆盖
3、通常情况下用户没有访问一些位置的权利，所以将一些库文件存放着用户主目录下
例子：
假如名为Libuseful的库安装在/usr/local/目录下，代码里已经包含了头文件#include <useful.h>。则可以用以下命令：
gcc -I/usr/local/include use_useful.c -o use_useful -L/usr/local/lib -luseful
• -I 指定搜索头文件的路径
• -L 指定库的搜索范围
• 注意库的顺序：如果specific.o依赖于Libbroad库，Libbroad依赖于Libgeneral，则库的顺序通常为gcc specific.o -lbroad -lgeneral才会成功。

库文件的查找

搜索库的命令：（POSIX环境）
find /usr -name 'libuseful*'
一般情况下，如果库的目标文件在/somepath/lib，那么对应的头文件一定在/somepath/include
查找库的工具pkg-config
pkg-config --libs libxml-2.0 得到输出：-lxml2
pkg-config --cflags libxml-2.0 得到输出：-I/usr/include/libxml2
即得到的是编译LibXML2所需要的所有选项。
在shell中，当把命令行用反引号包围时，这个命令行的反引号部分会被其自身的输出代替。
故输入：

1	gcc `pkg-config --cflags --libs libxml-2.0` -o specific specific.c

等价于：

1	gcc -I/usr/include/libxml2 -lxml2 -o specific specific.c

在命令行里包含头文件

gcc -include stdio.h
可以自己设置统一的头文件，包含通用的一些头文件，供编译时使用。（偷懒的做法）

Makefile的使用

一个基本的makefile：

P=program_name
OBJECTS=
CFLAGS = -g -Wall -O3
LDLIBS=
CC=c99
$(P): $(OBJECTS)

$(var) 设置变量
$@ 返回完整的目标文件名
$* 不带文件名后缀的输出文件
$< 当前目标的文件名称

1 2	target: dependencies script

…关于make的使用有待补充

Here Documents & Compiling from stdin

setjmp()/longjmp()

非局部跳转语句: setjmp和longjmp函数。
非局部指不像普通C语言goto，语句在一个函数内实施的跳转，而是在栈上跳过若干调用帧，返回到当前函数调用路径上的某一个函数中。

1
2
3

#include <setjmp.h>
int setjmp(jmp_buf  env);   //返回值：若直接调用则返回0，
void longjmp(jmp_buf env,int val);  //若从longjmp调用返回则返回非0值

·在希望返回到的位置调用setjmp，此位置在main函数中，因为直接调用该函数，所以其返回值为0
setjmp参数evn的类型是一个特殊的类型jmp_buf，这一数据类型是某种形式的数组，其中存放在调用longjmp时能用来恢复栈状态的所有信息。因为需要在另一个函数中引用env变量，所以规范的处理方式是将env变量定义为全局变量。
·当检查到一个错误时,则以两个参数调用longjmp函数，第一个就是在调用setjmp时所用的env，第二个参数是具有非0值的val，它将成为从setjmp处返回的值。使用第二个参数的原因是对于一个setjmp可以有多个longjmp。

问题

Input：numbers={2, 7, 11, 15}, target=9 Output: index1=1, index2=2

方案

用一个哈希表，存储每个数对应的下标，复杂度O(n)

代码

class Solution {
public:
    vector<int> twoSum(vector<int> &nums, int target) {
        unordered_map<int, int> mapping;
        vector<int> result;
        for (int i = 0; i < nums.size(); i++) {
            mapping[nums[i]] = i;
        }
        
        for (int i = 0; i < nums.size(); i++) {
           const int gap = target - nums[i];
           if (mapping.find(gap) != mapping.end() && mapping[gap] > i) {
                result.push_back(i + 1);
                result.push_back(mapping[gap] + 1);
                break;
           }
        }
        return result;
    }
};

2016-03-12

通过解释器执行程序

若通过语法分析得到语法分析树，解释器只需要从抽象语法树的根节点开始遍历该树直到叶节点，并计算各节点的内容便可得到结果。

eval方法

eval方法将计算以该节点为根的子树对应的语句、表达式及子表达式，并返回执行结果。

环境对象

环境对象是一种用于记录变量名称与值的对应关系的数据结构，常以哈希表的形式实现。
1、当程序中出现新变量时，由该变量的名称与初始值构成的键值对添加到哈希表；
2、之后遇到这一变量时，程序将搜索哈希表并取得它的值；
3、值的更新将更新键值对。

作用域与生存周期

scope
extent

要知道的高级C数据类型

指针通常的用法

创建链式数据结构

数据结构的动态分配

实现引用调用

访问和遍历数据集合

传递数组参数

作为函数的引用

作为其他值的别名

表示字符串

直接访问系统内存

结构体

问题：

[100, 4, 200, 1, 3, 2] 最长连续序列：[1, 2, 3, 4]。
复杂度：O(n)

方法一

先排序，复杂度O(nlogn)。
要求O(n)，用哈希表。用一个哈希表记录每个元素是否使用，对每个元素，已该元素为中心，向左右扩张，直到不连续为止，记录下最长的长度。
[unordered_map](http://www.cplusplus.com/reference/unordered_map/unordered_map/)

class Solution {
public:
	int longestConsecutive(const vector<int> &nums) {
		unordered_map<int, bool> used;
		for (auto i : nums) used[i] = false;

		int longest = 0;

		for (auto i : nums) {
			if (nums[i]) continue;

			int length = 1;
			used[i] = true;

			for (int j = i + 1; used.find(j) != used.end(); ++j) {
				used[j] = true;
				++length;
			}
			for (int j = i - 1; used.find(j) != used.end(); --j) {
				used[j] = true;
				++length;
			}

			longest = max(longest, length);
		}

		return longest;
	}
};

方法二：聚类操作

·待补充

God is in the details. ---Mies van der Rohe

2016-04-05 3-sum

2016-04-05 OSX安装qemu

2016-03-21 调试的技巧