posts - 200, comments - 8, trackbacks - 0, articles - 0

程序员编程艺术-----第五章-----寻找满足和为定值的两个或多个数

                    程序员编程艺术：第五章、寻找和为定值的两个或多个数
 

    作者：July，yansha，zhouzhenren。
    致谢：微软100题实现组，编程艺术室。
    微博：http://weibo.com/julyweibo   。
    出处：http://blog.csdn.net/v_JULY_v  。
    wiki：http://tctop.wikispaces.com/。
------------------------------

前奏

    希望此编程艺术系列能给各位带来的是一种方法，一种创造力，一种举一反三的能力。本章依然同第四章一样，选取比较简单的面试题，恭祝各位旅途愉快。同样，有任何问题，欢迎不吝指正。谢谢。


第一节、寻找和为定值的两个数
第14题（数组）：
题目：输入一个数组和一个数字，在数组中查找两个数，使得它们的和正好是输入的那个数字。
要求时间复杂度是O(n)。如果有多对数字的和等于输入的数字，输出任意一对即可。
例如输入数组1、2、4、7、11、15和数字15。由于4+11=15，因此输出4和11。

分析：

咱们试着一步一步解决这个问题（注意阐述中数列有序无序的区别）：

  1. 直接穷举，从数组中任意选取两个数，判定它们的和是否为输入的那个数字。此举复杂度为O（N^2）。很显然，我们要寻找效率更高的解法。
  2. 题目相当于，对每个a[i]，然后查找判断sum-a[i]是否也在原始序列中，每一次要查找的时间都要花费为O（N），这样下来，最终找到两个数还是需要O（N^2）的复杂度。那如何提高查找判断的速度列?对了，二分查找，将原来O（N）的查找时间提高到O（logN），这样对于N个a[i]，都要花logN的时间去查找相对应的sum-a[i]是否在原始序列中，总的时间复杂度已降为O（N*logN），且空间复杂度为O（1）。（如果有序，直接二分O（N*logN），如果无序，先排序后二分，复杂度同样为O（N*logN+N*logN）=O（N*logN），空间总为O（1））。
  3. 有没有更好的办法列?咱们可以依据上述思路2的思想，a[i]在序列中，如果a[i]+a[k]=sum的话，那么sum-a[i]（a[k]）也必然在序列中，，举个例子，如下：
    原始序列：1、 2、 4、 7、11、15     用输入数字15减一下各个数，得到对应的序列为：
    对应序列：14、13、11、8、4、 0      
    第一个数组以一指针i 从数组最左端开始向右扫描，第二个数组以一指针j 从数组最右端开始向左扫描，如果下面出现了和上面一样的数，即a[*i]=a[*j]，就找出这俩个数来了。如上，i，j最终在第一个，和第二个序列中找到了相同的数4和11，，所以符合条件的两个数，即为4+11=15。怎么样，两端同时查找，时间复杂度瞬间缩短到了O（N），但却同时需要O（N）的空间存储第二个数组（@飞羽：要达到O(N)的复杂度，第一个数组以一指针i 从数组最左端开始向右扫描，第二个数组以一指针j 从数组最右端开始向左扫描，首先初始i指向元素1，j指向元素0，谁指的元素小，谁先移动，由于1（i）>0（j），所以i不动，j向左移动。然后j移动到元素4发现大于元素1，故而停止移动j，开始移动i，直到i指向4，这时,i指向的元素与j指向的元素相等，故而判断4是满足条件的第一个数；然后同时移动i,j再进行判断，直到它们到达边界）。
  4. 当然，你还可以构造hash表，正如编程之美上的所述，给定一个数字，根据hash映射查找另一个数字是否也在数组中，只需用O（1）的时间，这样的话，总体的算法通上述思路3 一样，也能降到O（N），但有个缺陷，就是构造hash额外增加了O（N）的空间，此点同上述思路 3。不过，空间换时间，仍不失为在时间要求较严格的情况下的一种好办法。
  5. 如果数组是无序的，先排序（n*logn），然后用两个指针i，j，各自指向数组的首尾两端，令i=0，j=n-1，然后i++，j--，逐次判断a[i]+a[j]?=sum，如果某一刻a[i]+a[j]>sum，则要想办法让sum的值减小，所以此刻i不动，j--，如果某一刻a[i]+a[j]<sum，则要想办法让sum的值增大，所以此刻i++，j不动。所以，数组无序的时候，时间复杂度最终为O（n*logn+n）=O（n*logn），若原数组是有序的，则不需要事先的排序，直接O（n）搞定，且空间复杂度还是O（1），此思路是相对于上述所有思路的一种改进。（如果有序，直接两个指针两端扫描，时间O（N），如果无序，先排序后两端扫描，时间O（N*logN+N）=O（N*logN），空间始终都为O（1））。（与上述思路2相比，排序后的时间开销由之前的二分的n*logn降到了扫描的O（N））。

总结：

  • 不论原序列是有序还是无序，解决这类题有以下三种办法：1、二分（若无序，先排序后二分），时间复杂度总为O（n*logn），空间复杂度为O（1）；2、扫描一遍X-S[i]  映射到一个数组或构造hash表，时间复杂度为O（n），空间复杂度为O（n）；3、两个指针两端扫描（若无序，先排序后扫描），时间复杂度最后为：有序O（n），无序O（n*logn+n）=O（n*logn），空间复杂度都为O（1）。
  • 所以，要想达到时间O（N），空间O（1）的目标，除非原数组是有序的（指针扫描法），不然，当数组无序的话，就只能先排序，后指针扫描法或二分（时间n*logn，空间O（1）），或映射或hash（时间O（n），空间O（n））。时间或空间，必须牺牲一个，自个权衡吧。
  • 综上，若是数组有序的情况下，优先考虑两个指针两端扫描法，以达到最佳的时（O（N）），空（O（1））效应。否则，如果要排序的话，时间复杂度最快当然是只能达到N*logN，空间O（1）则是不在话下。

代码：

ok，在进入第二节之前，咱们先来实现思路5（这里假定数组已经是有序的），代码可以如下编写（两段代码实现）：

  1. //代码一  
  2. //O（N）  
  3. Pair findSum(int *s,int n,int x)     
  4. {     
  5.     //sort(s,s+n);   如果数组非有序的，那就事先排好序O（N*logN）     
  6.       
  7.     int *begin=s;     
  8.     int *end=s+n-1;     
  9.       
  10.     while(begin<end)    //俩头夹逼，或称两个指针两端扫描法，很经典的方法，O（N）    
  11.     {     
  12.         if(*begin+*end>x)     
  13.         {     
  14.             --end;     
  15.         }     
  16.         else if(*begin+*end<x)     
  17.         {     
  18.             ++begin;     
  19.         }     
  20.         else    
  21.         {     
  22.             return Pair(*begin,*end);     
  23.         }     
  24.     }     
  25.       
  26.     return Pair(-1,-1);     
  27. }     
  28.   
  29. //或者如下编写，  
  30. //代码二  
  31. //copyright@ zhedahht && yansha  
  32. //July、updated，2011.05.14。  
  33. bool find_num(int data[], unsigned int length, int sum, int& first_num, int& second_num)  
  34. {     
  35.     if(length < 1)  
  36.         return true;  
  37.       
  38.     int begin = 0;  
  39.     int end = length - 1;  
  40.       
  41.     while(end > begin)  
  42.     {  
  43.         long current_sum = data[begin] + data[end];  
  44.           
  45.         if(current_sum == sum)  
  46.         {  
  47.             first_num = data[begin];  
  48.             second_num = data[end];  
  49.             return true;  
  50.         }  
  51.         else if(current_sum > sum)  
  52.             end--;  
  53.         else  
  54.             begin++;  
  55.     }  
  56.     return false;  
  57. }  

 

 

扩展：
1、如果在返回找到的两个数的同时，还要求你返回这两个数的位置列?
2、如果把题目中的要你寻找的两个数改为“多个数”，或任意个数列?（请看下面第二节）
3、二分查找时： left <= right，right = middle - 1;left < right，right = middle;

 

//算法所操作的区间,是左闭右开区间,还是左闭右闭区间,这个区间,需要在循环初始化,
//循环体是否终止的判断中,以及每次修改left,right区间值这三个地方保持一致,否则就可能出错.

//二分查找实现一
int search(int array[], int n, int v)
{
    int left, right, middle;
 
    left = 0, right = n - 1;
 
    while (left <= right)
    {
        middle = left + (right-left)/2;   
        if (array[middle] > v)
        {
            right = middle - 1;
        }
        else if (array[middle] < v)
        {
            left = middle + 1;
        }
        else
        {
            return middle;
        }
    }
 
    return -1;
}

//二分查找实现二
int search(int array[], int n, int v)
{
    int left, right, middle;
 
    left = 0, right = n;
 
    while (left < right)
    {
        middle = left + (right-left)/2;    
  
        if (array[middle] > v)
        {
            right = middle;
        }
        else if (array[middle] < v)
        {
            left = middle + 1;
        }
        else
        {
            return middle;
        }
    }
 
    return -1;
}


第二节、寻找和为定值的多个数
第21题（数组）
2010年中兴面试题
编程求解：
输入两个整数 n 和 m，从数列1，2，3.......n 中 随意取几个数,
使其和等于 m ,要求将其中所有的可能组合列出来。

解法一
我想，稍后给出的程序已经足够清楚了，就是要注意到放n，和不放n个区别，即可，代码如下：

  1. // 21题递归方法  
  2. //copyright@ July && yansha  
  3. //July、yansha，updated。  
  4. #include<list>  
  5. #include<iostream>  
  6. using namespace std;  
  7.   
  8. list<int>list1;  
  9. void find_factor(int sum, int n)   
  10. {  
  11.     // 递归出口  
  12.     if(n <= 0 || sum <= 0)  
  13.         return;  
  14.       
  15.     // 输出找到的结果  
  16.     if(sum == n)  
  17.     {  
  18.         // 反转list  
  19.         list1.reverse();  
  20.         for(list<int>::iterator iter = list1.begin(); iter != list1.end(); iter++)  
  21.             cout << *iter << " + ";  
  22.         cout << n << endl;  
  23.         list1.reverse();      
  24.     }  
  25.       
  26.     list1.push_front(n);      //典型的01背包问题  
  27.     find_factor(sum-n, n-1);   //放n，n-1个数填满sum-n  
  28.     list1.pop_front();  
  29.     find_factor(sum, n-1);     //不放n，n-1个数填满sum   
  30. }  
  31.   
  32. int main()  
  33. {  
  34.     int sum, n;  
  35.     cout << "请输入你要等于多少的数值sum:" << endl;  
  36.     cin >> sum;  
  37.     cout << "请输入你要从1.....n数列中取值的n：" << endl;  
  38.     cin >> n;  
  39.     cout << "所有可能的序列，如下：" << endl;  
  40.     find_factor(sum,n);  
  41.     return 0;  
  42. }  

 

解法二
@zhouzhenren：
这个问题属于子集和问题（也是背包问题）。本程序采用 回溯法+剪枝
X数组是解向量，t=∑(1,..,k-1)Wi*Xi, r=∑(k,..,n)Wi
若t+Wk+W(k+1)<=M,则Xk=true，递归左儿子(X1,X2,..,X(k-1),1)；否则剪枝；
若t+r-Wk>=M && t+W(k+1)<=M,则置Xk=0，递归右儿子(X1,X2,..,X(k-1),0)；否则剪枝；
本题中W数组就是(1,2,..,n),所以直接用k代替WK值。

代码编写如下：

  1. //copyright@ 2011 zhouzhenren  
  2.   
  3. //输入两个整数 n 和 m，从数列1，2，3.......n 中 随意取几个数,  
  4. //使其和等于 m ,要求将其中所有的可能组合列出来。  
  5.   
  6. #include <stdio.h>  
  7. #include <stdlib.h>  
  8. #include <memory.h>  
  9.   
  10. /**  
  11.  * 输入t， r， 尝试Wk 
  12.  */  
  13. void sumofsub(int t, int k ,int r, int& M, bool& flag, bool* X)  
  14. {  
  15.     X[k] = true;   // 选第k个数  
  16.     if (t + k == M) // 若找到一个和为M，则设置解向量的标志位，输出解  
  17.     {  
  18.         flag = true;  
  19.         for (int i = 1; i <= k; ++i)  
  20.         {  
  21.             if (X[i] == 1)  
  22.             {  
  23.                 printf("%d ", i);  
  24.             }  
  25.         }  
  26.         printf("/n");  
  27.     }  
  28.     else  
  29.     {   // 若第k+1个数满足条件，则递归左子树  
  30.         if (t + k + (k+1) <= M)  
  31.         {  
  32.             sumofsub(t + k, k + 1, r - k, M, flag, X);  
  33.         }  
  34.         // 若不选第k个数，选第k+1个数满足条件，则递归右子树  
  35.         if ((t + r - k >= M) && (t + (k+1) <= M))  
  36.         {  
  37.             X[k] = false;  
  38.             sumofsub(t, k + 1, r - k, M, flag, X);  
  39.         }  
  40.     }  
  41. }  
  42.   
  43. void search(int& N, int& M)  
  44. {  
  45.     // 初始化解空间  
  46.     bool* X = (bool*)malloc(sizeof(bool) * (N+1));  
  47.     memset(X, false, sizeof(bool) * (N+1));  
  48.     int sum = (N + 1) * N * 0.5f;  
  49.     if (1 > M || sum < M) // 预先排除无解情况  
  50.     {  
  51.         printf("not found/n");  
  52.         return;  
  53.     }  
  54.     bool f = false;  
  55.     sumofsub(0, 1, sum, M, f, X);  
  56.     if (!f)  
  57.     {  
  58.         printf("not found/n");  
  59.     }  
  60.     free(X);  
  61. }  
  62.   
  63. int main()  
  64. {  
  65.     int N, M;  
  66.     printf("请输入整数N和M/n");  
  67.     scanf("%d%d", &N, &M);  
  68.     search(N, M);  
  69.     return 0;  
  70. }  

 

扩展：

1、从一列数中筛除尽可能少的数使得从左往右看，这些数是从小到大再从大到小的（网易）。

2、有两个序列a,b，大小都为n,序列元素的值任意整数，无序；
要求：通过交换a,b中的元素，使[序列a元素的和]与[序列b元素的和]之间的差最小。
例如:  
var a=[100,99,98,1,2, 3];
var b=[1, 2, 3, 4,5,40];（微软100题第32题）。

    @well：[fairywell]:
给出扩展问题 1 的一个解法：
1、从一列数中筛除尽可能少的数使得从左往右看，这些数是从小到大再从大到小的（网易）。
双端 LIS 问题，用 DP 的思想可解，目标规划函数 max{ b[i] + c[i] - 1 }, 其中 b[i] 为从左到右， 0 ~ i 个数之间满足递增的数字个数； c[i] 为从右到左， n-1 ~ i 个数之间满足递增的数字个数。最后结果为 n - max + 1。其中 DP 的时候，可以维护一个 inc[] 数组表示递增数字序列，inc[i] 为从小到大第 i 大的数字，然后在计算 b[i] c[i] 的时候使用二分查找在 inc[] 中找出区间 inc[0] ~ inc[i-1] 中小于 a[i] 的元素个数（low）。
源代码如下：

  1. /** 
  2. * The problem: 
  3. * 从一列数中筛除尽可能少的数使得从左往右看，这些数是从小到大再从大到小的（网易）。 
  4. * use binary search, perhaps you should compile it with -std=c99 
  5. * fairywell 2011 
  6. */  
  7. #include <stdio.h>  
  8.   
  9. #define MAX_NUM    (1U<<31)  
  10.   
  11. int  
  12. main()  
  13. {  
  14.     int i, n, low, high, mid, max;  
  15.       
  16.     printf("Input how many numbers there are: ");  
  17.     scanf("%d/n", &n);  
  18.     /* a[] holds the numbers, b[i] holds the number of increasing numbers 
  19.     * from a[0] to a[i], c[i] holds the number of increasing numbers 
  20.     * from a[n-1] to a[i] 
  21.     * inc[] holds the increasing numbers 
  22.     * VLA needs c99 features, compile with -stc=c99 
  23.     */  
  24.     double a[n], b[n], c[n], inc[n];  
  25.       
  26.     printf("Please input the numbers:/n");  
  27.     for (i = 0; i < n; ++i) scanf("%lf", &a[i]);  
  28.       
  29.     // update array b from left to right  
  30.     for (i = 0; i < n; ++i) inc[i] = (unsigned) MAX_NUM;  
  31.     //b[0] = 0;  
  32.     for (i = 0; i < n; ++i) {  
  33.         low = 0; high = i;  
  34.         while (low < high) {  
  35.             mid = low + (high-low)*0.5;  
  36.             if (inc[mid] < a[i]) low = mid + 1;  
  37.             else high = mid;  
  38.         }  
  39.         b[i] = low + 1;  
  40.         inc[low] = a[i];  
  41.     }  
  42.       
  43.     // update array c from right to left  
  44.     for (i = 0; i < n; ++i) inc[i] = (unsigned) MAX_NUM;  
  45.     //c[0] = 0;  
  46.     for (i = n-1; i >= 0; --i) {  
  47.         low = 0; high = i;  
  48.         while (low < high) {  
  49.             mid = low + (high-low)*0.5;  
  50.             if (inc[mid] < a[i]) low = mid + 1;  
  51.             else high = mid;  
  52.         }  
  53.         c[i] = low + 1;  
  54.         inc[low] = a[i];  
  55.     }  
  56.       
  57.     max = 0;  
  58.     for (i = 0; i < n; ++i )  
  59.         if (b[i]+c[i] > max) max = b[i] + c[i];  
  60.         printf("%d number(s) should be erased at least./n", n+1-max);  
  61.         return 0;  
  62. }  

 

@yansha：fairywell的程序很赞，时间复杂度O(nlogn)，这也是我能想到的时间复杂度最优值了。不知能不能达到O(n)。

扩展题第2题

当前数组a和数组b的和之差为
    A = sum(a) - sum(b)

a的第i个元素和b的第j个元素交换后，a和b的和之差为
    A' = sum(a) - a[i] + b[j] - （sum(b) - b[j] + a[i])
           = sum(a) - sum(b) - 2 (a[i] - b[j])
           = A - 2 (a[i] - b[j])

设x = a[i] - b[j]，得
    |A| - |A'| = |A| - |A-2x|

    假设A > 0,

    当x 在 (0,A)之间时，做这样的交换才能使得交换后的a和b的和之差变小，x越接近A/2效果越好,
    如果找不到在(0,A)之间的x，则当前的a和b就是答案。

所以算法大概如下：
    在a和b中寻找使得x在(0,A)之间并且最接近A/2的i和j，交换相应的i和j元素，重新计算A后，重复前面的步骤直至找不到(0,A)之间的x为止。 

接上，@yuan：
a[i]-b[j]要接近A/2，则可以这样想，
我们可以对于a数组的任意一个a[k],在数组b中找出与a[k]-C最接近的数（C就是常数，也就是0.5*A）
这个数要么就是a[k]-C，要么就是比他稍大，要么比他稍小，所以可以要二分查找。

查找最后一个小于等于a[k]-C的数和第一个大于等于a[k]-C的数，
然后看哪一个与a[k]-C更加接近，所以T(n) = nlogn。

除此之外，受本文读者xiafei1987128启示，有朋友在stacoverflow上也问过一个类似的题，:-)，见此：http://stackoverflow.com/questions/9047908/swap-the-elements-of-two-sequences-such-that-the-difference-of-the-element-sums。感兴趣的可以看看。

本章完。

 

程序员面试题狂想曲-tctop（the crazy thinking of programers）的修订wiki（http://tctop.wikispaces.com/）已建立，我们急切的想得到读者的反馈，意见，建议，以及更好的思路，算法，和代码优化的建议。所以，

•如果你发现了狂想曲系列中的任何一题，任何一章（http://t.cn/hgVPmH）中的错误，问题，与漏洞，欢迎告知给我们，我们将感激不尽，同时，免费赠送本blog内的全部博文集锦的CHM文件1期；
•如果你能对狂想曲系列的创作提供任何建设性意见，或指导，欢迎反馈给我们，并真诚邀请您加入到狂想曲的wiki修订工作中；
•如果你是编程高手，对狂想曲的任何一章有自己更好的思路，或算法，欢迎加入狂想曲的创作组，以为千千万万的读者创造更多的价值，更好的服务。
Ps：狂想曲tctop的wiki修订地址为：http://tctop.wikispaces.com/。欢迎围观，更欢迎您加入到狂想曲的创作或wiki修订中。 

版权所有，本人对本blog内所有任何内容享有版权及著作权。实要转载，请以链接形式注明出处。

posted @ 2012-11-30 21:09 鑫龙 阅读(163) | 评论 (0) | 编辑 收藏

最长上升子序列 O(nlogn)解法 (转)

最近在做单调队列，发现了最长上升子序列O(nlogn)的求法也有利用单调队列的思想。

    最长递增子序列问题：在一列数中寻找一些数，这些数满足：任意两个数a[i]和a[j]，若i<j，必有a[i]<a[j]，这样最长的子序列称为最长递增子序列。

   设dp[i]表示以i为结尾的最长递增子序列的长度，则状态转移方程为：

dp[i] = max{dp[j]+1}, 1<=j<i,a[j]<a[i].

   这样简单的复杂度为O(n^2)，其实还有更好的方法。

   考虑两个数a[x]和a[y]，x<y且a[x]<a[y],且dp[x]=dp[y]，当a[t]要选择时，到底取哪一个构成最优的呢？显然选取a[x]更有潜力，因为可能存在a[x]<a[z]<a[y]，这样a[t]可以获得更优的值。在这里给我们一个启示，当dp[t]一样时，尽量选择更小的a[x].

    按dp[t]=k来分类，只需保留dp[t]=k的所有a[t]中的最小值，设d[k]记录这个值，d[k]=min{a[t],dp[t]=k}。

    这时注意到d的两个特点（重要）：

1. d[k]在计算过程中单调不升；           

2. d数组是有序的，d[1]<d[2]<..d[n]。

    利用这两个性质，可以很方便的求解：

1. 设当前已求出的最长上升子序列的长度为len（初始时为1），每次读入一个新元素x：

2. 若x>d[len]，则直接加入到d的末尾，且len++；（利用性质2）

   否则，在d中二分查找，找到第一个比x小的数d[k]，并d[k+1]=x，在这里x<=d[k+1]一定成立（性质1,2）。

 

  1. /** 
  2. 最长递增子序列O(nlogn)算法： 
  3. 状态转移方程：f[i] = max{f[i],f[j]+1},1<=j<i,a[j]<a[i]. 
  4. 分析：加入x<y,f[x]>=f[y],则x相对于y更有潜力。 
  5. 首先根据f[]值分类，记录满足f[t]=k的最小的值a[t],记d[k]=min{a[t]},f[t]=k. 
  6.     1.发现d[k]在计算过程中单调不上升 
  7.     2.d[1]<d[2]<...<d[k] (反证) 1 2 3 8 4 7 
  8. 解法： 
  9. 1. 设当前最长递增子序列为len,考虑元素a[i]; 
  10. 2. 若d[len]<a[i],则len++，并将d[len]=a[i]; 
  11.    否则,在d[0-len]中二分查找,找到第一个比它小的元素d[k],并d[k+1]=a[i].() 
  12. */  
  13. #include <iostream>  
  14. #include <cstdio>  
  15. #include <cstring>  
  16. using namespace std;  
  17. const int N = 41000;  
  18. int a[N];       //a[i] 原始数据  
  19. int d[N];       //d[i] 长度为i的递增子序列的最小值  
  20.   
  21. int BinSearch(int key, int* d, int low, int high)  
  22. {  
  23.     while(low<=high)  
  24.     {  
  25.         int mid = (low+high)>>1;  
  26.         if(key>d[mid] && key<=d[mid+1])  
  27.             return mid;  
  28.         else if(key>d[mid])  
  29.             low = mid+1;  
  30.         else  
  31.             high = mid-1;  
  32.     }  
  33.     return 0;  
  34. }  
  35.   
  36. int LIS(int* a, int n, int* d)  
  37. {  
  38.     int i,j;  
  39.     d[1] = a[1];  
  40.     int len = 1;        //递增子序列长度  
  41.     for(i = 2; i <= n; i++)  
  42.     {  
  43.         if(d[len]<a[i])  
  44.             j = ++len;  
  45.         else  
  46.             j = BinSearch(a[i],d,1,len) + 1;  
  47.         d[j] = a[i];  
  48.     }  
  49.     return len;  
  50. }  
  51.   
  52. int main()  
  53. {  
  54.     int t;  
  55.     int p;  
  56.     scanf("%d",&t);  
  57.     while(t--)  
  58.     {  
  59.         scanf("%d",&p);  
  60.         for(int i = 1; i <= p; i++)  
  61.             scanf("%d",&a[i]);  
  62.         printf("%d\n",LIS(a,p,d));  
  63.     }  
  64.     return 0;  
  65. }  

 

posted @ 2012-11-30 17:44 鑫龙 阅读(14762) | 评论 (1) | 编辑 收藏

《UNIX环境高级编程》单个源码编译方法(转)

对于很多初学《UNIX环境高级编程》（AdvancedProgramming in the UNIX Environment,简称APUE，以下使用简称）的朋友，第一个遇到的问题可能就是该书中的源代码编译的问题。此书中差不多每个例程中，都会有这样一行源码：
＃include "ourhdr.h"


在第二版中改为：
＃include "apue.h"

   这个头文件是作者把把每个例程中常用的标准头文件，一些常用的出错处理函数（err_**（）之类的函数）和一些常用的宏定义给整理在一个头文件中。这个可以省去在每个例程中录入较多的重复代码，这样可以减少每个例程的长度。但是，这样就给读者带来了不少麻烦。因为我们还要去搞明白如和把这个头文件编译，然后做成库文件，添加到我们的系统中。特别读于初学者，本来满怀信心的，结果在编译第一个程序的时候就出现了问题。我也没有搞明白如何把"ourhdr.h"静态的编译到系统中。

   不过，不明白如何使用"ourhdr.h"这个头文件，并不会影响我们学习APUE，也不会影响我们编译和运行每一个例程。其实，简单的想一下，如果一个C程序要能顺利的编译和运行，除了我们要语法正确等方面外，最根本的是要保证我们程序中所调用的函数以及宏等等都要有完整的来源，也就是必须包含所有调用函数和宏所在的头文件。对于一个具体的源程序，如果我们正确的包含了头文件，那么剩下的就是程序本生语法方面应该注意的事项。

   如何确定系统调用函数包含在那个头文件中呢？这在Unix/Linux系统下并非一件难事。Unix/Linux下命令man可以帮助我们找到。man命令不仅可以帮助我们查找一般命令的用法，同时提供不同层次的帮助诸如系统调用或者管理员级别的命令等等（譬如FreeBSD6.1中，man1是用户专用手册，man 2是系统调用，man 3是库函数查询等等）。

   下面我们就以APUE书中程序1-1（实现ls命令部分功能）为例，来说明如何将书中的程序改编成全部使用标准头文件的程序。其中，操作系统用的是FreeBSD6.1，经过相应的修改可以在书中所说的几个Unix系统及Linux系统中运行，我也曾在Debian Linux下成功编译和运行该程序。书中1-1.c的原始代码如下：

#include <sys/types.h>
#include <dirent.h>
#include "ourhdr.h"

int
main(int argc, char *argv[])
{
    DIR                *dp;
    struct dirent    *dirp;

    if (argc != 2)
        err_quit("usage: ls directory_name");

    if ((dp = opendir(argv[1])) == NULL)
        err_sys("can't open %s", argv[1]);
    while ((dirp = readdir(dp)) != NULL)
        printf("%s\n", dirp->d_name);

    closedir(dp);
    exit(0);
}


  从书后面的附录中可以看到"ourhdr.h"的内容比较多，包含了比较多的常用头文件，一些宏定义和一些常用函数和出错函数的定义。其实，对于每一个具体的程序，我们只需要找到该程序中用到的头文件即可。

    该1-1.c中所用到的系统函数调用有：opnedir()，readdir()，printf()，closedir()和exit()。
其中，对于常用的函数prinft()和exit()，它们所在的头文件一般都知道，分别是<stdio.h>和<stdlib.h>。而对于opnedir()，readdir()和closedir()，我们可以通过man opendir，man readdir，manclosedir得到这三个关于目录操作的函数所在的头文件都是：<sys/types.h>和<dirent.h>。这两个头文件在源程序中也已经列出。

   其次，1-1.c中还用到了作者自定义的两个函数：err_quit()和err_sys()。这两个函数主要使用来进行出错处理的。当然，使用这两个函数对错误信息的处理是比较完善的。但是，作为我们学习来讲，了解程序的核心功能是首要的，我们可以将出错处理简化一点，即当遇到错误的时候，我们只简单的使用printf()函数来提示一下有错误发生。当然，用printf()来进行出错处理并不是一种很合理的方法，而且往往我们看不到更关键的错误信息，但对于我们仅仅作为学习来用还是可以接受的。毕竟我们要理解的核心部分是程序的功能实现，出错处理在于其次。

   通过以上的说明，我们可以将1-1.c修改为如下内容：
#include <sys/types.h>
#include <dirent.h>
#include <stdio.h>
#include <stdlib.h>
int main(int argc, char* argv[])
{
    DIR *dp;
    struct dirent *dirp;
   
    if(argc != 2)
    {
        printf("You need input the directory name.\n");
        exit(1);  
    }
   
    if((dp = opendir(argv[1])) == NULL)
    {
        printf("cannot open %s\n", argv[1]);
        exit(1);   
    }

    while ((dirp = readdir(dp)) != NULL)
        printf("%s\n", dirp->d_name);


    closedir(dp);

    exit(0);
}


  这样修改后的程序已经与作者的头文件"ourhdr.h"没有关系，可以单独的进行编译。我使用的是root用户，执行命令：

# gcc 1-1.c  //生成目标文件a.out
或者
＃ gcc -o 1-1 1-1.c  //生成目标文件1-1

    没有任何错误和警告，说明编译成功。这时我们执行生成的目标文件：

＃ ./a.out /home
或者
＃ ./1-1 /home

    则会列出/home路径下的所有文件，包括目录(.)和(..)。

   通过这样的方法，基本上我们可以将该书中所有的例程修改成不包含"ourhdr.h"的程序。这样，我们就可以单独的编译每一个例程，而不用顾及作者所给的杂凑的头文件。同时这种比较笨的方法，反而有利于帮助我们了解不同系统调用所对应的头文件，对于学习来说，这应该是一件好事。

欢迎交流，欢迎自由转载，但请注明CU链接或本人CU Blog链接：
http://blog.chinaunix.net/u/33048/showart_343553.html

posted @ 2012-11-28 23:36 鑫龙 阅读(176) | 评论 (0) | 编辑 收藏

POJ题目分类(转)

转贴 ACM的算法（觉得很好，有层次感）
OJ上的一些水题(可用来练手和增加自信) 
(poj3299,poj2159,poj2739,poj1083,poj2262,poj1503,poj3006,poj2255,poj3094)


初期:

一.基本算法: 
     (1)枚举. (poj1753,poj2965) 
     (2)贪心(poj1328,poj2109,poj2586) 
     (3)递归和分治法. 
     (4)递推. 
     (5)构造法.(poj3295) 
     (6)模拟法.(poj1068,poj2632,poj1573,poj2993,poj2996) 
二.图算法: 
     (1)图的深度优先遍历和广度优先遍历. 
     (2)最短路径算法(dijkstra,bellman-ford,floyd,heap+dijkstra) 
        (poj1860,poj3259,poj1062,poj2253,poj1125,poj2240) 
     (3)最小生成树算法(prim,kruskal) 
        (poj1789,poj2485,poj1258,poj3026) 
     (4)拓扑排序 (poj1094) 
     (5)二分图的最大匹配 (匈牙利算法) (poj3041,poj3020) 
     (6)最大流的增广路算法(KM算法). (poj1459,poj3436) 
三.数据结构. 
     (1)串 (poj1035,poj3080,poj1936) 
     (2)排序(快排、归并排(与逆序数有关)、堆排) (poj2388,poj2299) 
     (3)简单并查集的应用. 
     (4)哈希表和二分查找等高效查找法(数的Hash,串的Hash)    
        (poj3349,poj3274,POJ2151,poj1840,poj2002,poj2503) 
     (5)哈夫曼树(poj3253) 
     (6)堆 
     (7)trie树(静态建树、动态建树) (poj2513) 
四.简单搜索 
     (1)深度优先搜索 (poj2488,poj3083,poj3009,poj1321,poj2251) 
     (2)广度优先搜索(poj3278,poj1426,poj3126,poj3087.poj3414) 
     (3)简单搜索技巧和剪枝(poj2531,poj1416,poj2676,1129) 
五.动态规划 
     (1)背包问题. (poj1837,poj1276) 
     (2)型如下表的简单DP(可参考lrj的书 page149): 
       1.E[j]=opt{D+w(i,j)} (poj3267,poj1836,poj1260,poj2533) 
       2.E[i,j]=opt{D[i-1,j]+xi,D[i,j-1]+yj,D[i-1][j-1]+zij} (最长公共子序列) 
    
         (poj3176,poj1080,poj1159) 
       3.C[i,j]=w[i,j]+opt{C[i,k-1]+C[k,j]}.(最优二分检索树问题) 
六.数学 
     (1)组合数学: 
        1.加法原理和乘法原理. 
        2.排列组合. 
        3.递推关系. 
          (POJ3252,poj1850,poj1019,poj1942) 
     (2)数论. 
        1.素数与整除问题 
        2.进制位. 
        3.同余模运算. 
          (poj2635, poj3292,poj1845,poj2115) 
     (3)计算方法. 
        1.二分法求解单调函数相关知识.(poj3273,poj3258,poj1905,poj3122) 
七.计算几何学. 
     (1)几何公式. 
     (2)叉积和点积的运用(如线段相交的判定,点到线段的距离等). (poj2031,poj1039)

     (3)多边型的简单算法(求面积)和相关判定(点在多边型内,多边型是否相交) 
         (poj1408,poj1584) 
     (4)凸包. (poj2187,poj1113)


中级:

一.基本算法: 
     (1)C++的标准模版库的应用. (poj3096,poj3007) 
     (2)较为复杂的模拟题的训练(poj3393,poj1472,poj3371,poj1027,poj2706) 
二.图算法: 
     (1)差分约束系统的建立和求解. (poj1201,poj2983) 
     (2)最小费用最大流(poj2516,poj2195) 
     (3)双连通分量(poj2942) 
     (4)强连通分支及其缩点.(poj2186) 
     (5)图的割边和割点(poj3352) 
     (6)最小割模型、网络流规约(poj3308, ) 
三.数据结构. 
     (1)线段树. (poj2528,poj2828,poj2777,poj2886,poj2750) 
     (2)静态二叉检索树. (poj2482,poj2352) 
     (3)树状树组(poj1195,poj3321) 
     (4)RMQ. (poj3264,poj3368) 
     (5)并查集的高级应用. (poj1703,2492) 
     (6)KMP算法. (poj1961,poj2406) 
四.搜索 
     (1)最优化剪枝和可行性剪枝 
     (2)搜索的技巧和优化 (poj3411,poj1724) 
     (3)记忆化搜索(poj3373,poj1691) 
      
五.动态规划 
     (1)较为复杂的动态规划(如动态规划解特别的施行商问题等) 
         (poj1191,poj1054,poj3280,poj2029,poj2948,poj1925,poj3034) 
     (2)记录状态的动态规划. (POJ3254,poj2411,poj1185) 
     (3)树型动态规划(poj2057,poj1947,poj2486,poj3140) 
六.数学 
     (1)组合数学: 
        1.容斥原理. 
        2.抽屉原理. 
        3.置换群与Polya定理(poj1286,poj2409,poj3270,poj1026). 
        4.递推关系和母函数. 
         
     (2)数学. 
        1.高斯消元法(poj2947,poj1487, poj2065,poj1166,poj1222) 
        2.概率问题. (poj3071,poj3440) 
        3.GCD、扩展的欧几里德(中国剩余定理) (poj3101) 
     (3)计算方法. 
        1.0/1分数规划. (poj2976) 
        2.三分法求解单峰(单谷)的极值. 
        3.矩阵法(poj3150,poj3422,poj3070) 
        4.迭代逼近(poj3301) 
     (4)随机化算法(poj3318,poj2454) 
     (5)杂题. 
         (poj1870,poj3296,poj3286,poj1095) 
七.计算几何学. 
        (1)坐标离散化. 
        (2)扫描线算法(例如求矩形的面积和周长并,常和线段树或堆一起使用). 
            (poj1765,poj1177,poj1151,poj3277,poj2280,poj3004) 
        (3)多边形的内核(半平面交)(poj3130,poj3335) 
        (4)几何工具的综合应用.(poj1819,poj1066,poj2043,poj3227,poj2165,poj3429
)


高级: 
一.基本算法要求:   
      (1)代码快速写成,精简但不失风格   
          (poj2525,poj1684,poj1421,poj1048,poj2050,poj3306) 
      (2)保证正确性和高效性. poj3434 
二.图算法: 
      (1)度限制最小生成树和第K最短路. (poj1639) 
      (2)最短路,最小生成树,二分图,最大流问题的相关理论(主要是模型建立和求解)

         (poj3155, poj2112,poj1966,poj3281,poj1087,poj2289,poj3216,poj2446 
      (3)最优比率生成树. (poj2728) 
      (4)最小树形图(poj3164) 
      (5)次小生成树. 
      (6)无向图、有向图的最小环    
三.数据结构.   
      (1)trie图的建立和应用. (poj2778) 
      (2)LCA和RMQ问题(LCA(最近公共祖先问题) 有离线算法(并查集+dfs) 和 在线算法

          (RMQ+dfs)).(poj1330) 
      (3)双端队列和它的应用(维护一个单调的队列,常常在动态规划中起到优化状态转移
的 
          目的). (poj2823) 
      (4)左偏树(可合并堆).   
      (5)后缀树(非常有用的数据结构,也是赛区考题的热点). 
         (poj3415,poj3294) 
四.搜索   
      (1)较麻烦的搜索题目训练(poj1069,poj3322,poj1475,poj1924,poj2049,poj3426)

      (2)广搜的状态优化:利用M进制数存储状态、转化为串用hash表判重、按位压缩存储
状态、双向广搜、A*算法. (poj1768,poj1184,poj1872,poj1324,poj2046,poj1482) 
      (3)深搜的优化:尽量用位运算、一定要加剪枝、函数参数尽可能少、层数不易过大
、可以考虑双向搜索或者是轮换搜索、IDA*算法. (poj3131,poj2870,poj2286) 
五.动态规划   
      (1)需要用数据结构优化的动态规划. 
         (poj2754,poj3378,poj3017) 
      (2)四边形不等式理论. 
      (3)较难的状态DP(poj3133) 
六.数学   
      (1)组合数学. 
        1.MoBius反演(poj2888,poj2154) 
        2.偏序关系理论. 
      (2)博奕论. 
        1.极大极小过程(poj3317,poj1085) 
        2.Nim问题. 
七.计算几何学.   
      (1)半平面求交(poj3384,poj2540) 
      (2)可视图的建立(poj2966) 
      (3)点集最小圆覆盖. 
      (4)对踵点(poj2079) 
      八.综合题. 
      (poj3109,poj1478,poj1462,poj2729,poj2048,poj3336,poj3315,poj2148,poj1263
)

posted @ 2012-11-26 13:00 鑫龙 阅读(149) | 评论 (0) | 编辑 收藏

C++类型转换总结(转)

C风格的强制类型转换(Type Cast)很简单，不管什么类型的转换统统是：
TYPE b = (TYPE)a。
C++风格的类型转换提供了4种类型转换操作符来应对不同场合的应用。

const_cast，字面上理解就是去const属性。
static_cast，命名上理解是静态类型转换。如int转换成char。
dynamic_cast，命名上理解是动态类型转换。如子类和父类之间的多态类型转换。
reinterpret_cast，仅仅重新解释类型，但没有进行二进制的转换。
4种类型转换的格式，如：TYPE B = static_cast(TYPE)(a)。

const_cast
去掉类型的const或volatile属性。

1 struct SA {
2  int i;
3 };
4 const SA ra;
5 //ra.i = 10; //直接修改const类型，编译错误
6 SA &rb = const_cast<SA&>(ra);
7 rb.i = 10;

static_cast

类似于C风格的强制转换。无条件转换，静态类型转换。用于：
1. 基类和子类之间转换：其中子类指针转换成父类指针是安全的；但父类指针转换成子类指针是不安全的。(基类和子类之间的动态类型转换建议用dynamic_cast)
2. 基本数据类型转换。enum, struct, int, char, float等。static_cast不能进行无关类型（如非基类和子类）指针之间的转换。
3. 把空指针转换成目标类型的空指针。
4. 把任何类型的表达式转换成void类型。
5. static_cast不能去掉类型的const、volitale属性(用const_cast)。

1 int n = 6;
2 double d = static_cast<double>(n); // 基本类型转换
3 int *pn = &n;
4 double *d = static_cast<double *>(&n) //无关类型指针转换，编译错误
5 void *p = static_cast<void *>(pn); //任意类型转换成void类型

dynamic_cast
有条件转换，动态类型转换，运行时类型安全检查(转换失败返回NULL)：
1. 安全的基类和子类之间转换。
2. 必须要有虚函数。
3. 相同基类不同子类之间的交叉转换。但结果是NULL。

 1 class BaseClass {
 2 public:
 3 int m_iNum;
 4 virtual void foo(){}; //基类必须有虚函数。保持多台特性才能使用dynamic_cast
 5 };
 6 
 7 class DerivedClass: public BaseClass {
 8 public:
 9 char *m_szName[100];
10 void bar(){};
11 };
12 
13 BaseClass* pb = new DerivedClass();
14 DerivedClass *pd1 = static_cast<DerivedClass *>(pb); //子类->父类，静态类型转换，正确但不推荐
15 DerivedClass *pd2 = dynamic_cast<DerivedClass *>(pb); //子类->父类，动态类型转换，正确
16 
17 BaseClass* pb2 = new BaseClass();
18 DerivedClass *pd21 = static_cast<DerivedClass *>(pb2); //父类->子类，静态类型转换，危险！访问子类m_szName成员越界
19 DerivedClass *pd22 = dynamic_cast<DerivedClass *>(pb2); //父类->子类，动态类型转换，安全的。结果是NULL

reinterpret_cast
仅仅重新解释类型，但没有进行二进制的转换：
1. 转换的类型必须是一个指针、引用、算术类型、函数指针或者成员指针。
2. 在比特位级别上进行转换。它可以把一个指针转换成一个整数，也可以把一个整数转换成一个指针（先把一个指针转换成一个整数，在把该整数转换成原类型的指针，还可以得到原先的指针值）。但不能将非32bit的实例转成指针。
3. 最普通的用途就是在函数指针类型之间进行转换。
4. 很难保证移植性。

1 int doSomething(){return 0;};
2 typedef void(*FuncPtr)(); //FuncPtr is 一个指向函数的指针，该函数没有参数，返回值类型为 void
3 FuncPtr funcPtrArray[10]; //10个FuncPtrs指针的数组 让我们假设你希望（因为某些莫名其妙的原因）把一个指向下面函数的指针存入funcPtrArray数组：
4 
5 funcPtrArray[0] = &doSomething;// 编译错误！类型不匹配，reinterpret_cast可以让编译器以你的方法去看待它们：funcPtrArray
6 funcPtrArray[0] = reinterpret_cast<FuncPtr>(&doSomething); //不同函数指针类型之间进行转换

总结
去const属性用const_cast。
基本类型转换用static_cast。
多态类之间的类型转换用daynamic_cast。
不同类型的指针类型转换用reinterpret_cast。

posted @ 2012-11-25 17:33 鑫龙 阅读(193) | 评论 (0) | 编辑 收藏

memcpy与memmove(转)

     摘要: memcpy与memmove的目的都是将N个字节的源内存地址的内容拷贝到目标内存地址中。但当源内存和目标内存存在重叠时，memcpy会出现错误，而memmove能正确地实施拷贝，但这也增加了一点点开销。memmove的处理措施：（1）当源内存的首地址等于目标内存的首地址时，不进行任何拷贝（2）当源内存的首地址大于目标内存的首地址时，实行正向拷贝（3）当源内存的首地址小于目标内存的首地址时，实行反向...  阅读全文

posted @ 2012-11-25 16:55 鑫龙 阅读(274) | 评论 (0) | 编辑 收藏

程序员编程艺术-----第四章-----现场编写类似strstr/strcpy/strpbrk的函数

     摘要:                第四章、现场编写类似strstr/strcpy/strpbrk的函数    作者：July。    说明： 如果在博客中代码使用了\n，csdn blog系统将会自动回给我变成/n。据后续验证，可能是原来旧bl...  阅读全文

posted @ 2012-11-21 19:04 鑫龙 阅读(259) | 评论 (0) | 编辑 收藏

程序员编程艺术-----第三章续-----Top K算法问题的实现

     摘要:                      程序员编程艺术：第三章续、Top K算法问题的实现    作者：July，zhouzhenren，yansha。    致谢：微软100题实现组，狂想曲创作组。 &nb...  阅读全文

posted @ 2012-11-21 17:21 鑫龙 阅读(228) | 评论 (0) | 编辑 收藏

程序员编程艺术-----第三章-----寻找最小的k个数

     摘要:                     程序员编程艺术：第三章、寻找最小的k个数作者：July。时间：二零一一年四月二十八日。致谢：litaoye， strugglever，yansha，luuillu，Sorehead，及狂想曲创作组。微博：http://weibo.com/j...  阅读全文

posted @ 2012-11-20 21:56 鑫龙 阅读(3303) | 评论 (0) | 编辑 收藏

最小堆&&最大堆的实现(c++)(转)

     摘要: 最小堆：Code highlighting produced by Actipro CodeHighlighter (freeware)http://www.CodeHighlighter.com/-->template<class T>class MinHeap {public:    MinHeap(int&nb...  阅读全文

posted @ 2012-11-19 21:09 鑫龙 阅读(1167) | 评论 (1) | 编辑 收藏

仅列出标题
共20页: First 11 12 13 14 15 16 17 18 19 Last