什么样的程序员称得上优秀，根据我所看到，有如下体会：

1、不愿意将就的人

程序设计工作是一项地地道道的脑力劳动，把工作做得很好和做的很差往往只在工作中的一个小小的细节，我发现我身边优秀的程序员都不太喜欢将就，始终把自己的计算机和自己的开发环境调整到最佳状态，原来带我的老员工甚至会自己写一些小工具，来提高工作效率。

2、不喜欢蛮干

脑力劳动与体力劳动不同，很多时候很难通过简单的量的积累达到目的，尤其是处理一些难题的时候。一味的强调蛮干，加班几乎天生与高手无缘。没有思路的时候，换个环境，也许答案就在明天上班的路上想起。

3、愿意思考、专注改进

程序员与其他劳动者相似，熟练了以后都会形成惯性思维，会不自觉的用自己习惯的方式解决问题，但问题的形式与本质总会变化，只有不断的改进才能使工作效率不断提高。而把脑力劳动变成体力劳动的现象在实际工作中比比皆是。

4、良好的基础和不断的学习

良好的基础与不断的学习是天生的一对孪生兄弟，因为基础好所以学的快，因为学得快，所以基本功好。良好学习习惯不是不停的简单追踪新技术，一方面是了解新技术，另一方面需要不断的弥补思维盲区，学习可以有很多种状态，有一种是闻一而知一，技也，有一种是闻一而知三，术也，有一种是闻一而知十，道也。

5、直接切入问题的能力

在解决一个问题的时候，有些人总是能够直接切入问题核心，而有些人总是喜欢关注边缘问题。直入主题是一种核心能力，需要思考，实践，改进，积累，提高，周而复使，螺旋上升。另外我觉得这与思维方式与知识面关系很大，多涉猎一些领域没有坏处。
1、    查找一个字符串中最长的重复子串；
2、    查找一个字符串中重复最多的子串；

查找“重复子串最长的”和“子串出现次数最多的”解决方案相似：
首先、生成一个指针数组，数组的成员依次指向字符串中每一个的字符地址，如

String: “banana”
那么指针数组分别代表字串：

banana
anana
nana
ana
na
a

之后按指针数组指向的字符串值，对数组进行排序，排序结果如下：

a[0]: a
a[1]: ana
a[2]: anana
a[3]: banana
a[4]: na
a[5]: nana

有个这个数组，统计“重复的最长子串”和“重复次数最多子串”就非常容易了。
“重复的最长子串”代码如下：


这个方法出自《编程珠玑》。

介绍的一些字符串处理的问题在日常编程中比较常见，但是在大学读书的时候几乎一个都没有涉及，最近学习了一下在这里介绍给大家，仅供参考。

这些算法与内容包括：

1、    查找一个短串在一个长串中位置；
2、    查找一个字符串中最长的重复子串；
3、    查找一个字符串中重复最多的子串；
4、    两个字符串最长的公共子串（连续）；
5、    两个字符串最长的公共子序列（不连续）；
6、    介绍一种强大的数据结构，Suffix tree.

这里有一个PPT：
http://www.cppblog.com/Files/humanchao/StringAlg.zip

-------------------------------------------------

查找一个短串在一个长串中位置

这个问题传统的解法时间复杂度为O(m*n)，m、n为两个串的长度。有一个Sunday算法，可以最大限度的优化这个比较过程，原理如下：

1、建立一个hash table，依次把search各个字符值作为table索引，为table相应的位置一个值（表示字符存在），如果出现重复，后面的位置会覆盖前面的位置。
例：我们要在"WHICH-FINALLY-HALTS.—AT-THAT-POINT"（简称string）查找" AT-THAT "（简称pat），刚开始时，把pat与string对齐，查看串string中与串pat 相对应的字符（F），在pat的位置，这个查找的过程时间复杂度通过hash table的下标索引为 O(1)： 



2、如果发现没有，说明字符F之前已经无法与pat匹配，直接跳到position(F)+stringlength(pat)


 
3、发现”-”在pat位置3，于是重新定位对齐两串为：

 
4、倒序（从最后一个向前）比较两串，发现无法匹配，继续跳转->查找->定位
因为上面已经有一个T匹配成功，这次要从HALTS的S来查找，于是定位为：



5、上图无法匹配，从”--AT-“中A后的”-”继续查找，重复上过程，最终匹配如图：
 

这个算法关键点：
1、建立为pat建立hash表，以提高查找字符的速度；
2、对齐跳转，快速的后移比较，使比较次数减少。

具体的代码实现可以参考链接：

http://blog.csdn.net/unicode1985/archive/2007/05/30/1631038.aspx


关于：找到两个字符串最长的连续公共子串里无论是表达还是算法本身都是存在一定问题的，查找公共子串的问题在很多资料上都有明确的定义，通过动态规划来解决，算法复杂度为O(M*N)，在此向大家深表歉意。


正确的做法在wikipedia上有所描述，请大家参考：
http://en.wikipedia.org/wiki/Longest_common_substring_problem
与
http://hellobmw.com/archives/dynamic-programming-longest-common-substring.html

将字符串里词顺序倒置，如"Times New Roman"变为"Roman New Times"。以空格为分隔符。

解决方案为：先将整个字串倒置，然后依次把倒置后串中的每一个单词倒置。

这个问题解答的思路很简单，但是要考虑到很多种的情况，比如字符串的头、尾有多余的空格怎么办，如果字符串中只有空格，还有字符串中间可能会有两个以上并列的空格。

程序如下：

 

说实话，如果是突然面对这样一个问题，要在一张纸上写下比较完整的程序是不大可能。能边调试边写程序有的时候也是一件幸事。
中秋节要到了，我要换工作了，告别已经工作两年多熟悉的环境，感觉这两年没有太大的进步，奋斗吧，趁着自己还年轻！

问题：找出整数1~N范围和为M的所有集合，M<=N且M>1，集合里的数不允许重复。

解答：这个问题用递归解决最简单，代码如下：

 1 #define MAX_NUM 20        //要足够大
 2 int log[MAX_NUM];        //记录和数
 3 int index = 0;            //log[]数组的当前指针
 4 
 5 void calc(int start, int n)
 6 {
 7     if (n == 0)  
 8     {
 9         for(int j = 0; j < index; j++)
10             printf("%d ", log[j]);
11         printf("\n");
12     }
13     else
14     {
15         for(int i = start; i<=n; i++)
16         {
17             log[index++] = i;    
18             calc(i + 1, n - i);
19         }
20     }
21 
22     index--;
23 }

如果允许重复只需要将上面第18条代码改为：

calc(i, n - i);

即可。

扩展问题：在数组{5,1,7,9,2,10,11,4,13,14}中找到和为28的所有集合，集合中不允许有重复的数。

解答：第一步要先对数组排序，然后按照上去的思路，对程序略做一些改动。
代码如下：

 1 #define MAX_NUM 20        //要足够大
 2 int log[MAX_NUM];        //记录和数
 3 int index = 0;            //log[]数组的当前指针
 4 
 5 void calc__(int *nArr     //数组, 
 6             int start    //数组起始元素下标, 
 7             int nArrLen    //数组长度, 
 8             int sum)
 9 {
10     if (sum == 0)  
11     {
12         for(int j = 0; j < index; j++)
13             printf("%d ", log[j]);
14         printf("\n");
15     }
16     else
17     {
18         for(int i = start; i < nArrLen; i++)
19         {
20             log[index++] = nArr[i];    
21             calc__(nArr, i+1, nArrLen, sum - nArr[i]);
22         }
23     }
24     
25     index--;
26 }

这个问题的解答思路是相当简单的，但如何把程序写的细致、简捷是除了解答思路以外的另一个关键。就像迷宫最短路径的那个问题，言语描述很简单，但把实现的程序写好确要花一些时间。

已知前序和中序：

struct NODE 
{
    NODE *pLeft;
    NODE *pRight;
    char chValue;
};

int  CharInStrFirstPos(char ch, char *str, int nLen)
{
    char *pOrgStr = str;
    while (nLen > 0 && ch != *str)
    {
        str++;
        nLen--;
    }
    
    return (nLen > 0) ? (str - pOrgStr) : -1;
}

void ReBuild_PreIn(char *pPreOrder, char *pInOrder, int nTreeLen, NODE **pRoot)
{
    if (pPreOrder == NULL || pInOrder == NULL)
    {
        return;
    }

    NODE *pTemp = new NODE;
    pTemp->chValue = *pPreOrder;
    pTemp->pLeft = NULL;
    pTemp->pRight = NULL;

    if (*pRoot == NULL)
    {
        *pRoot = pTemp;
    }

    if (nTreeLen == 1)
    {
        return;
    }

    int nLeftLen = CharInStrFirstPos(*pPreOrder, pInOrder, nTreeLen);
    assert(nLeftLen != -1);
    int nRightLen = nTreeLen - nLeftLen -1;

    if (nLeftLen > 0)
    {
        ReBuild_PreIn(pPreOrder + 1, pInOrder, nLeftLen, &((*pRoot)->pLeft));
    }

    if (nRightLen > 0)
    {
        ReBuild_PreIn(pPreOrder + nLeftLen + 1, pInOrder + nLeftLen + 1,
            nRightLen, &((*pRoot)->pRight));
    }
}

已知后序和中序：

void ReBuild_AftIn(char *pAftOrder, char *pInOrder, int nTreeLen, NODE **pRoot)
{
    if (pAftOrder == NULL || pInOrder == NULL)
    {
        return;
    }
    
    NODE *pTemp = new NODE;
    pTemp->chValue = *pAftOrder;
    pTemp->pLeft   = NULL;
    pTemp->pRight  = NULL;
    
    if (*pRoot == NULL)
    {
        *pRoot = pTemp;
    }
    
    if (nTreeLen == 1)
    {
        return;
    }
    
    int nLeftLen = CharInStrFirstPos(*pAftOrder, pInOrder, nTreeLen);
    assert(nLeftLen != -1);
    int nRightLen = nTreeLen - nLeftLen -1;
    
    if (nLeftLen > 0)
    {
        ReBuild_AftIn(pAftOrder + nRightLen + 1, pInOrder, nLeftLen, &((*pRoot)->pLeft));
    }
    
    if (nRightLen > 0)
    {
        ReBuild_AftIn(pAftOrder + 1, pInOrder + nLeftLen + 1,
            nRightLen, &((*pRoot)->pRight));
    }
}

我上传了一个工VC的工程，有兴趣的朋友点此下载。代码参考于《编程之美》。

我们先看一个函数：函数的功能完成1~10的加法。

int Add1to10(int a, int b)
{
   return a +b;
}

但是一般我们还需要加上几条代码：

int Add1to10(int a, int b)
{
    assert(a >= 1 && a <= 10);
    assert(b >= 1 && b < =10);

    if ( a < 1 || a > 10 || b < 1 || b > 10)
        return -1;

    return a +b;
}

加上上面几条代码的作用是检查函数的输入参数，当参数不正确的时候不光要在返回值上得到体现，而且会触发assert断言，提醒我们参数有误。

断言式编程体现一个编程的思想，在我们的程序执行偏离预想的路线时给出提醒。当程序执行偏离预想的路线时一般会出现两种可能：即断言以上的程序没有理解下面程序的调用条件、或断言以下的程序需要接受更为宽泛输入条件。以下分别讨论修改方法：

1、如果函数的输入参数是我们编程的一个疏漏，我们认为根本就不应该出现或产生这样的值，那我们应该修改调用函数处的代码，避免非预想的值出现。

2、如果无法避免出现或者产生一个非法输入值，那我们要么在函数调用处加入判断，产生符合条件的值时调用函数，不符合参数条件else处理；要么修改函数，使函数可以接受更为宽泛输入条件，并调整断言内容和参数判断逻辑。

断言不仅可以出现在函数的参数检查的场合，也可以出现在其他的上下文调用的场合。而且它还会随着程序的开发进程逐渐的增加、删除和调整。它可以验证程序是按照我们预想的思路在执行，当出现意外时及时的给出提醒，提醒我们修正程序或者自己的思路。

void QuickSort(int* pData,int left,int right)
{
    int i = left, j = right;
    int middle = pData[(left+right)/2];        // midlle value
    int iTemp;
    do
    {    
        while (pData[i] < middle && i < right)            i++;
        while (pData[j] > middle && j > left)            j--;
        if (i < j)                            // swap
        {
            iTemp    = pData[i];
            pData[i] = pData[j];
            pData[j] = iTemp;
            i++;            j--;
        } 
        else if (i == j)
        {
            i++;            j--;
        }
    } while (i < j);

    if (left  < j)        QuickSort(pData,left,j);
    if (right > i)        QuickSort(pData,i,right);
}

没的说，理解不了就是背也得把这段代码背下来。

学习数据结构和算法的好东西，非常形象，制作水平比较高，向制作者致敬！里面包含以下算法的过程演示：

B树的删除
B树的生长过程
三元组表的转置
中序线索化二叉树
串的顺序存储
二分查找
二叉排序树的删除
二叉排序树的生成
二叉树的建立
克鲁斯卡尔算法构造最小生成树
冒泡排序
分块查找
单链表结点的删除
单链表结点的插入
图的深度优先遍历
基数排序
堆排序
头插法建单链表
寻找中序线索化二叉树指定结点的前驱
寻找中序线索化二叉树指定结点的后继
尾插法建表
希儿排序
开放定址法建立散列表
循环队列操作演示
快速排序
拉链法创建散列表
拓扑排序
数据结构和算法Flash动画演示.rar
最短路径
朴素串匹配算法过程示意
构造哈夫曼树的算法模拟
构造哈夫曼树过程
栈与递归
...更多

点击下载

如果BAT不带参数，脚本内容如下：

SetOutPath '$INSTDIR'
ExecWait '$INSTDIR\A.bat'

如果BAT需要参数时，要把带参数的命令写入另外一个新的BAT中，执行新BAT：

B.bat内容：
CALL A.bat install

NSIS 脚本：
SetOutPath '$INSTDIR'
ExecWait '$INSTDIR\B.bat'

#import   "scrrun.dll"   raw_interfaces_only

// 参数格式："c:\" 或 "c:\test"
ULONGLONG GetPathUseSpace(const char *szPath)
{
    ASSERT(szPath != NULL);

    int nLen = strlen(szPath);
    if (nLen == 0)
        return 0;

    ULONGLONG result = 0;

    if (nLen == 3)      // c:\
    {
        ULARGE_INTEGER nFreeBytesAvailable;
        ULARGE_INTEGER nTotalNumberOfBytes;
        ULARGE_INTEGER nTotalNumberOfFreeBytes;
        //
        if (GetDiskFreeSpaceEx(szPath,
              &nFreeBytesAvailable,
              &nTotalNumberOfBytes,
              &nTotalNumberOfFreeBytes))
        {
            result = nTotalNumberOfBytes.QuadPart - nFreeBytesAvailable.QuadPart;
        }
    }
    else
    {
        CoInitialize(NULL);  
        {  
            try  
            {  
                Scripting::IFileSystem3Ptr   fs;  
                fs.CreateInstance(__uuidof(Scripting::FileSystemObject)); 
                
                Scripting::IFolderPtr   folder;  
                fs->GetFolder(_bstr_t(szPath),&folder);
                
                _variant_t vsize;
                folder->get_Size(&vsize);
                result = (double)vsize;
            }  
            catch(_com_error &e)  
            {  
                result = -1;
            }  
        }  

        CoUninitialize();   
    }

    return result;
}

VC取得目录的大小可以用COM方式，但是在某些操作系统上使用COM方式取根目录大小（即某一个盘已用空间）会出现问题，可以用GetDiskFreeSpaceEx，上面是我写了一个小函数。

有一个单链表，其中可能有一个环，也就是某个节点的next指向的是链表中在它之前的节点，这样在链表的尾部形成一环。

问题：

1、如何判断一个链表是不是这类链表？
2、如果链表为存在环，如果找到环的入口点？

解答：

一、判断链表是否存在环，办法为：

设置两个指针(fast, slow)，初始值都指向头，slow每次前进一步，fast每次前进二步，如果链表存在环，则fast必定先进入环，而slow后进入环，两个指针必定相遇。(当然，fast先行头到尾部为NULL，则为无环链表)程序如下：

bool IsExitsLoop(slist *head)
{
    slist *slow = head, *fast = head;

    while ( fast && fast->next ) 
    {
        slow = slow->next;
        fast = fast->next->next;
        if ( slow == fast ) break;
    }

    return !(fast == NULL || fast->next == NULL);
}

二、找到环的入口点

当fast若与slow相遇时，slow肯定没有走遍历完链表，而fast已经在环内循环了n圈(1<=n)。假设slow走了s步，则fast走了2s步（fast步数还等于s 加上在环上多转的n圈），设环长为r，则：

2s = s + nr
s= nr

设整个链表长L，入口环与相遇点距离为x，起点到环入口点的距离为a。
a + x = nr
a + x = (n – 1)r +r = (n-1)r + L - a
a = (n-1)r + (L – a – x)

(L – a – x)为相遇点到环入口点的距离，由此可知，从链表头到环入口点等于(n-1)循环内环+相遇点到环入口点，于是我们从链表头、与相遇点分别设一个指针，每次各走一步，两个指针必定相遇，且相遇第一点为环入口点。程序描述如下：

slist* FindLoopPort(slist *head)
{
    slist *slow = head, *fast = head;

    while ( fast && fast->next ) 
    {
        slow = slow->next;
        fast = fast->next->next;
        if ( slow == fast ) break;
    }

    if (fast == NULL || fast->next == NULL)
        return NULL;

    slow = head;
    while (slow != fast)
    {
         slow = slow->next;
         fast = fast->next;
    }

    return slow;
}

扩展问题：

判断两个单链表是否相交，如果相交，给出相交的第一个点（两个链表都不存在环）。

比较好的方法有两个：

一、将其中一个链表首尾相连，检测另外一个链表是否存在环，如果存在，则两个链表相交，而检测出来的依赖环入口即为相交的第一个点。

二、如果两个链表相交，那个两个链表从相交点到链表结束都是相同的节点，我们可以先遍历一个链表，直到尾部，再遍历另外一个链表，如果也可以走到同样的结尾点，则两个链表相交。

这时我们记下两个链表length，再遍历一次，长链表节点先出发前进(lengthMax-lengthMin)步，之后两个链表同时前进，每次一步，相遇的第一点即为两个链表相交的第一个点。

     摘要: 有一个二维数组，0表示路，-1表示墙，求其中任意两点的最短路径。 我们先看，怎么求一条路径：求两点路径是一个数据结构上的典型的迷宫问题，很多数据结构的书上都有介绍，解决办法如下： 从一点开始出发，向四个方向查找，每走一步，把走过的点的值+1(即本节点值+1)，防止重复行走，并把走过的点压入堆栈(表示路径)，如果遇到墙、或者已走过的点则不能前进，如果前方已经无路可走，则返回，路径退栈，这样递归调...  阅读全文

曾经遇到一个为二维数组循环赋值的问题，即赋值后的二维数组为如下情形：



当时在网上找了一下答案，基本上都是1层大循环套4层小循环还实现的，感觉不够优雅。最近翻了一下数据结构的书，看到迷宫问题受到了一点启发，感觉同样是实现这个功能，如下代码要优雅一些：

const int ROW__ = 10;
const int COL__ = 10;
int mat[ROW__][COL__];

struct Position
{
    int    nRow;
    int nCol;
};

void printMat(int mat[ROW__][COL__]);

int main(int argc, char* argv[])
{
    Position offset[4];
    offset[0].nRow = 0;        offset[0].nCol = 1;
    offset[1].nRow = 1;        offset[1].nCol = 0;
    offset[2].nRow = 0;        offset[2].nCol = -1;
    offset[3].nRow = -1;    offset[3].nCol = 0;

    Position curPos;
    curPos.nRow = 0;
    curPos.nCol = 0;
    mat[0][0] = 1;

    int nOffset = 0;

    Position tempPos;
    for (int i = 1; i < ROW__*COL__; i++)
    {
        // nOffset % 4 ------> 右->下->左->上 循环
        tempPos.nRow = curPos.nRow + offset[nOffset % 4].nRow;
        tempPos.nCol = curPos.nCol + offset[nOffset % 4].nCol;

        if (   tempPos.nRow >= ROW__ || tempPos.nRow < 0
            || tempPos.nCol >= COL__ || tempPos.nCol < 0    // 不超过边界
            || mat[tempPos.nRow][tempPos.nCol] > 0)         // 已经有值
        {
            i--;        
            nOffset++;
            continue;
        }

        curPos = tempPos;
        mat[curPos.nRow][curPos.nCol] = i+1;
    }

    printMat(mat);

    return 0;
}

printMat函数这些就不提供了，它的功能是打印出这个数组。我上传了一下工程，有兴趣的朋友点此下载。

刚刚有人考了我一道题，逆序输出单链表：
我是这样答的（下面的代码为伪代码，不能通过编译）：

void printSList(slist *pList)
{
    assert(pList);
    if (pList == NULL)
        return;

    string str;
    while (pList)
    {
        str = string(*pList) + str;
        pList = pList->next;
    }

    printf("%s", str.c_str());
}

后来他让我想一想还有没有更为简单的方法了，当时允许我上网，我用了几分钟到网上找了一下，没有找到更好的办法，如果先把链表逆序，再顺序输出时间复杂度更高。

我走出大楼以后，忽然想到，是递归呀，对是递归：

void printSList(slist *pList)
{
    assert(pList);
    if (pList == NULL)
        return;
    
    if (pList->next == NULL)
        printf("%s", *pList);
    else
    {
        printSList(pList->next);
        printf("%s", *pList);
    }
}

哎，人生中机会就是一瞬之间，错过不知道下一次又是什么时候。但只要做了就会收获，会一次比一次做的好。吃饭去了...

1000毫秒为一秒，毫秒可能是能够取到的最小的时间单位了，代码如下：

看到楼下两们仁兄的发言，我找了一下资料，如下的代码可以取得更为精确的时间值：

一年半之前，我遇到一个问题：把一堆数平均分成N份，保证每一份的和接近于所有数之和除以N，不要求平分以后的每份数据个数相等。这是有现实的程序设计需求的，当时是3份。首先想到要先进行排序，再依次从已排序的数列中抽取，如何进行抽取方法有很多，我大概想了3种左右，感觉要拿一些数据去测试一下这几种方法哪一种可以逼近最优解。

当时经理要求算法一定能够得出最优解，但测试多组数据，没有发现哪一种实现能得到最优解。后来翻了一下《数据结构、算法与应用--C++语言描述》，忽然想到，原来这个是一个典型贪婪算法问题，这个问题没有最优解，用贪婪算法来解决这个问题可以让每一次结果逼近最优。实现如下(注：代码是我今天写的)：


我上传了一个VC的测试工程，有兴趣的朋友点此下载。

理论的依据不仅指导了实践的选择，同时给选择以有力的支撑。

2007年就要结束了，在此预祝大家在新的一年里：身体健康，平安如意！

假设需要执行的程序如下：

执行它，并取得其返回值，我写了一个函数如下：


我上传了两个工程，希望对大家有所帮助！

http://www.cppblog.com/Files/humanchao/ExecExe.rar