C

在编译例子的时候用到了 pkg-config 。例如 :::c $ gcc -o example example.c `pkg-config alsaplayer --cflags --libs` 这个 example 使用了 libalsaplayer.so ，只要运行上述命令，编译就可以通过。gcc 的使用已经熟悉了，但是 pkg-config 却不知道是什么东西。 最后通过 wiki 明白了这个家伙究竟是什么东西了。 pkg-config 和 ls 一样，是 可执行程序。作用是查询已安装库的各种信息。例如如果我们在终端输入 :::c pkg-config alsaplayer --cflags --libs 就会输出下面的字符串 :::c -I/usr/local/include/alsaplayer -L/usr/local/lib -lalsaplayer -ldl 打印出了头文件的位置和连接库的位置和需要的链接库，再拼接之前的 gcc -o example example.c ，难怪能够编译了。 但是究竟 pkg-config 是如何得到这些信息的？ wiki 上面说了，在安装 alsaplayer 的时候，有一个 叫做 alsaplayer.pc 的文件被放到了 /usr/local/lib/pkgconfig 这个目录里面，打开这个 pc 后缀的文件，内容如下 :::c prefix=/usr/local exec_prefix=${prefix} libdir=${exec_prefix}/lib includedir=${prefix}/include plugindir=${exec_prefix}/lib/alsaplayer alsaplayer_includedir=${prefix}/include/alsaplayer inputplugindir=${plugindir}/input outputplugindir=${plugindir}/output scopeplugindir=${plugindir}/scopes interfaceplugindir=${plugindir}/interface Name: AlsaPlayer Description: AlsaPlayer audio player with plugin support Version: 0.99.82 Libs: -L${libdir} -lalsaplayer -ldl Cflags: -I${alsaplayer_includedir} 其中记录着各种信息，我们需要的 Libs 和 CFlags 就是在这里获得的。 ...

在编写 c/c++ 程序的时候需要随时提防内存泄漏的问题。而且有时候内存泄漏了却不知道是哪里的问题。这些多是对内存管理不熟悉导致的。 直接开炮，从四道面试题开始 在解答之前先补了一下内存分配的知识。 一个程序通常分为三个区域存储数据。 静态存储区，存储全局变量和static变量，程序退出自动释放内存。 栈存储区，存储临时变量，函数结束自动释放内存。 堆存储区，向系统调用 malloc 和 new 将在这里划分存储空间，需要手动释放。 第一题 :::c void GetMemory(char *p) { p = (char *)malloc(100); } void Test(void) { char *str = NULL; GetMemory(str); strcpy(str, "hello world"); printf(str); } 这题的意图是想在子函数里面分配堆空间。但是程序运行却奔溃了。根据预期效果，即使没有写 free 程序也不会奔溃的吧。除非 strcpy 的时候 str 还是NULL。 调试验证了 str 还是NULL 的问题。问题出在调用函数的值传递问题。 在 c/c++ 中 值传递的意思是分配一个栈空间来存储传入子函数的值，函数结束的时候释放其空间。 知道了值传递后我们分析一下程序 首先 *str 指向 NULL 然后执行GetMemory(str)，系统就开辟了一个栈 *p 来存储这个NULL(值传递) 然后 p 分配到了一段堆内存 退出子函数， 释放存储 p 地址的栈(内存泄漏，因为指向p的堆内存不可能释放了)。这个时候 str 还是 NULL ，因为 p 和 str 是两个地址完全不同的指针，p 分配的内存跟 str 无关。 运行strcpy 直接奔溃了。 :::c char *GetMemory(void) { char p[] = "hello world"; return p; } void Test(void) { char *str = NULL; str = GetMemory(); printf(str); } p 可视为指向栈内存 hello world 的指针。 返回 p 但是其栈内存已被回收，会输出不确定的内容。 :::c Void GetMemory2(char **p, int num) { *p = (char *)malloc(num); } void Test(void) { char *str = NULL; GetMemory(&str, 100); strcpy(str, "hello"); printf(str); } 比起第一题好像是改善了，能打印 hello 出来，但是最后忘记 free 了。 ...

基础水题，插入排序第一部分 Input Format There will be two lines of input: s - the size of the array ar - the sorted array of integers Output Format On each line, output the entire array every time an item is shifted in it. Constraints 1<=s<=1000 -10000<=x<= 10000, x ∈ ar Sample Input 5 2 4 6 8 3 Sample Output 2 4 6 8 8 2 4 6 6 8 2 4 4 6 8 2 3 4 6 8 Explanation 3 is removed from the end of the array. In the 1st line 8 > 3, 8 is shifted one cell right. In the 2nd line 6 > 3, 6 is shifted one cell right. In the 3rd line 4 > 3, 4 is shifted one cell right. In the 4th line 2 < 3, 3 is placed at position 2. Task Complete the method insertionSort which takes in 1 parameter: ar - an array with the value V in the right-most cell. 本节讲解如何移动元素并插入元素。 ...

刚注册上 Hacker Rank ，出现了一条练手的题目，竟然不是著名的 Hello World ，而是这题 Pairs 。 连接 题目是这样的 Given N integers [N<=10^5], count the total pairs of integers that have a difference of K. [K>0 and K<1e9]. Each of the N integers will be greater than 0 and at least K away from 2^31-1 (Everything can be done with 32 bit integers). Input Format 1st line contains N & K (integers). 2nd line contains N numbers of the set. All the N numbers are assured to be distinct. ...

在比较算法中，快速排序可以算是明星算法了，因为他的常系数小，使得其总体性能比其他比较算法优秀。其性能基本上可以达到$\theta (n\lg n)$ ，但在某些极端情况其时间复杂度却是$\theta ({n}^{2})$。 快速排序的基本思想是遵循分而治之的思想的，其基本思路是： 分：在待排序的数据中选取一个数作为中心点，大于这个数的数统统放到右边，小于这个数的统统放在左边。这样就形成了左右两个子串。 治：两个子串重复1的动作 合并：无 ##分 所以最重要的是分这一步，这一步的伪代码如下 :::c Partition(A,p,q) // A[p,q] x<-A[p] i<-p for j<-p+1 to q do if A[j] <= x // <= 是小于等于的意思 then i<-i+1 exhange A[i]<->A[j] exchange A[p]<->A[i] return i 时间复杂度为$\theta(n)$ 下面给出一个例子，看如何分。 Ex. :::java 6 10 13 5 8 3 2 11 选取 pivot＝6 i=0 j=1 :::java 6 10 13 5 8 3 2 11 pivot=6 i=0 j=3 i=i+1 -> i=1 exchange A[i]<->A[j] so: :::java 6 5 13 10 8 3 2 11 此时 i=1,j=3, 继续 :::java 6 5 13 10 8 3 2 11 i=1,j=5 i=2 exchange A[i]<->A[j] :::java 6 5 3 10 8 13 2 11 i=2,j=5 j继续自增 :::java 6 5 3 10 8 13 2 11 i=2,j=6 i=3 exchange A[i]<->A[j] :::java 6 5 3 2 8 13 10 11 i=3,j=6 直到结束，然后 exchange A[p]<->A[i] : A[0] <-> A[3] , 最后结果为 :::java 2 5 3 6 8 13 10 11 这样以6为轴，比6小的都在左边，比6大的都在右边，分结束。 ...