STEP BY STEP

发表于 分类于 阅读次数： Valine：
本文字数： 1.9k 阅读时长 ≈ 2 分钟

这是算法导论习题11.1-4。
具体题目如下：

解决该题目的要点：
1.由于是无穷大的数组，所以无法事先初始化该数组。
2.所提供的方案必须是O（1）。
3.使用的额外空间只能是O（n），这样平均到每一个项上的空间都是O（1）。

一时之间好像没有一点头绪，在几个群里面发问了，网上搜了很久也没有找到答案，后面一群里有个高人给了个链接，里面有解法。链接地址：

http://www.cnblogs.com/flyfy1/archive/2011/03/05/1971502.html

这篇文章里面另外给了个pdf，这个pdf估计是解法的来源。伪代码写得不给力，不过前面的英文描述却很清晰。说实话，这个方法很巧妙。

解法大概的意思如下：
开一个额外的数组A，A[0]表示A数组元素的数目(当然不包括A[0]本身)，A[i]代表插入的第i个元素的key。假设原来的无穷大数组用Huge
表示，如果Hugei有效，则表示其在A数组中的索引。那么如果A[Huge[i]] == i 而且 Huge[i] <= A[0] &&
Huge[i] > 0，则表示i这个位置已经有元素插入了。

插入：A[0]++;A[A[0]] = key; Huge[key] = A[0];
搜索: A[Huge[i]] == i && Huge[i] <= A[0] && Huge[i] > 0 则return true;
删除: 先搜索该位置是否有元素, 如果Search(key)成功，则先把Huge[ A[A[0]] ] = Huge[key]，
然后交换A[A[0]]和A[Huge[key]]，A[0]—即可。
所有操作都是O（1），平均到每一个项，使用的空间都是O（1）。

我用代码实现的模拟如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <stdio.h>
#include <vector>
#include <algorithm>
using std::swap;
using std::vector;
#define INF (100)

int nHuge[INF];//假设这个巨大的数组是无法初始化的
vector<int> vA;

void Init()
{
    vA.push_back(0);//添加A[0]表示元素的数目
}

void Insert(int nKey)
{
    vA[0]++;
    nHuge[nKey] = vA[0];
    vA.push_back(nKey);
}

bool Search(int nKey)
{
    if (nHuge[nKey] > 0 && nHuge[nKey] <= vA[0] && vA[nHuge[nKey]] == nKey)
    {
        return true;
    }

    return false;
}

void Delete(int nKey)
{
    if (Search(nKey))
    {
        nHuge[ vA[vA[0]] ] = nHuge[nKey];//将huge的最后一个元素中存储的A数组的索引改为nHuge[nKey]
        swap(vA[vA[0]], vA[nHuge[nKey]]);//交换key
        --vA[0];
        vA.erase(vA.end() - 1);
    }
}

#define MAX (10)
int main()
{
    Init();
    int i;
    for (i = 0; i < MAX; ++i)
    {
        Insert(i);
    }
    for (i = 0; i < MAX; ++i)
    {
        printf("Search:%d %s\n", i, Search(i) == true? "Success" : "Failure");
    }
    printf("\n");

    Delete(4);
    Delete(9);
    Delete(1);
    for (i = 0; i < MAX * 2; ++i)
    {
        printf("Search:%d %s\n", i, Search(i) == true? "Success" : "Failure");
    }

    return 0;
}

发表于 分类于 ， 阅读次数： Valine：
本文字数： 2k 阅读时长 ≈ 2 分钟

题目意思很简单就是计算含括号的四则运算表达式的值。这个题目很坑爹，刚做的时候，题目描述里面只说里面会有空格，后面居然把题目描述改了。所以，这个题无论怎么改，都是不对。因为，不知道是哪个坑爹的出题人，把数据里面加了\t，难道出题人以为\t也是空格。估计，后面修改题目描述，也是发现这个问题后才改的。这可是还是哥了，改了无数多遍，不处理非法数据就超时，略过非常数据当然直接WA了。好坑爹。
计算表达式的值，以前严蔚敏书上就说用栈构造出来后缀表达式后再计算值。但是这个方法未免太那个了，首先太麻烦了，虽然算法思路不麻烦。我的做法是直接递归计算即可。碰到左括号递归计算新的表达式，右括号作为函数终止条件。否则，按照四则运算的优先级计算当前的表达式。递归算法中需要记录前一个运算符合的优先级，如果前一个运算符的优先级比现在碰到的运算符的优先级高，那么就应该直接返回答案了，当前碰到的运算符的计算交给下一次循环好了。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <stdio.h>
#define MAX (100 + 10)
char szData[MAX];

void TrimSpace(char* pszData)
{
    char* pszRead = pszData;
    char* pszWrite = pszData;
    while (*pszRead)
    {
        //由于数据中有\t,与先前题目描述不符合,不处理掉就直接超时了
        if (*pszRead != ' ' && *pszRead != '\t')
        {
            *pszWrite++ = *pszRead;
        }
        ++pszRead;
    }
    *pszWrite = '\0';
}

//nKind代表前一个运算符合的优先级,开始时是0,+-是1,*/是2
double Cal(char*& pszData, int nKind)
{
    double fAns = 0.0;
    while (*pszData && *pszData != ')')//表达式终止的条件是到达'\0'或者碰到右括号
    {
        if (*pszData >= '0' && *pszData <= '9')
        {
            fAns = 10 * fAns + *pszData - '0';
            ++pszData;
        }
        else if (*pszData == '+')
        {
            if (nKind >= 1)
            {
                return fAns;
            }
            ++pszData;
            fAns += Cal(pszData, 1);
        }
        else if (*pszData == '-')
        {
            if (nKind >= 1)
            {
                return fAns;
            }
            ++pszData;
            fAns -= Cal(pszData, 1);
        }
        else if (*pszData == '*')
        {
            if (nKind >= 2)
            {
                return fAns;
            }
            ++pszData;
            fAns *= Cal(pszData, 2);
        }
        else if (*pszData == '/')
        {
            if (nKind >= 2)
            {
                return fAns;
            }
            ++pszData;
            fAns /= Cal(pszData, 2);
        }
        else if (*pszData == '(')
        {
            ++pszData;
            fAns = Cal(pszData, 0);
            ++pszData;//移到')'后面
            return fAns;//一个括号内的是一个完整的表达式,因此直接返回
        }
    }

    return fAns;
}

int main()
{
    while (gets(szData))
    {
        TrimSpace(szData);
        char* pszData = szData;
        printf("%.4f\n", Cal(pszData, 0));
    }
}

一个递归函数能计算出表达式的值，而且能处理优先级和括号，如果是以前的话，我应该是写不出来的。再把算法的实现细节改改，应该也能计算出浮点数的表达式了。

发表于 分类于 ， 阅读次数： Valine：
本文字数： 2.3k 阅读时长 ≈ 2 分钟

这是个简单的字符串处理题目。看题目，数据应该不是很大，直接暴力处理可以过。如果为了加快搜索速度，在中间输入过程中排序，再二分很麻烦，速度也快不了多少，因为只是输入的过程中需要查找。但是，这个题其实很好用map做，代码量可以少很多，也很简洁。
写这篇blog的目的是为了提醒自己，容易题再这样错下去，真的很伤人心，学什么都没必要了，当时打算继续搞ACM的目的之一就是为了提高代码正确率。这个题，不仅细节部分没看清楚，而且写代码时候把比较函数里面的one.nLost写成了one.nGet，查错了1个多小时，还让队友帮忙查错了好久，真的很无语。写程序确实可以debug，但是这也让我养成了很严重的依赖debug的习惯。
人生不可以debug，人生不可以重来。记得以前很多次很多事情就是开始无所谓，后面悲催到底，无限后悔。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include <stdio.h>
#include <string.h>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#define MAX (100)
using std::map;
using std::string;
using std::vector;
using std::sort;

struct INFO
{
    INFO()
    {
        nScore = nGet = nLost = 0;
    }

    string strName;
    int nScore;
    int nGet;
    int nLost;
    bool operator < (const INFO& one) const
    {
        if (nScore != one.nScore)
        {
            return nScore > one.nScore;
        }
        else if (nGet - nLost != one.nGet - one.nLost)//这里把one.nLost写成了one.nGet
        {
            return nGet - nLost > one.nGet - one.nLost;
        }
        else if (nGet != one.nGet)
        {
            return nGet > one.nGet;
        }
        else
        {
            return strName < one.strName;
        }
    }
};

int main()
{
    int nN;

    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    while (scanf("%d", &nN) == 1)
    {
        int nLast = nN * (nN - 1);
        char szOne[MAX];
        char szTwo[MAX];
        int nOne, nTwo;

        map<string, INFO> myMap;
        for (int i = 0; i < nLast; ++i)
        {
            scanf("%s %*s %s %d:%d", szOne, szTwo, &nOne, &nTwo);
            //printf("%s %s %d %d\n", szOne, szTwo, nOne, nTwo);

            string strOne = szOne;
            myMap[strOne].strName = strOne;
            myMap[strOne].nGet += nOne;
            myMap[strOne].nLost += nTwo;

            string strTwo = szTwo;
            myMap[strTwo].strName = strTwo;
            myMap[strTwo].nGet += nTwo;
            myMap[strTwo].nLost += nOne;

            if (nOne > nTwo)
            {
                myMap[strOne].nScore += 3;
            }
            else if (nOne == nTwo)
            {
                myMap[strOne].nScore += 1;
                myMap[strTwo].nScore += 1;
            }
            else
            {
                myMap[strTwo].nScore += 3;
            }
        }

        map<string, INFO>::iterator it;
        vector<INFO> myVt;
        for (it = myMap.begin(); it != myMap.end(); it++)
        {
            myVt.push_back(it->second);
        }

        sort(myVt.begin(), myVt.end());
        for (int i = 0; i < myVt.size(); ++i)
        {
            printf("%s %d\n", myVt[i].strName.c_str(), myVt[i].nScore);
        }
        printf("\n");
    }

    return 0;
}

发表于 分类于 阅读次数： Valine：
本文字数： 3.3k 阅读时长 ≈ 3 分钟

两个栈实现一个队列
要求：只能使用栈的pop和push，以及测试栈是否为空三个操作。
实现思路：
队列里面使用stack one 和 stack two。
进队列时，直接进入栈one即可。
出队列时，从two弹出一个元素，如果two里面的元素为空，则将one里面的元素依次弹出并压入two中，再从two弹出一个元素返回。

用STL里面的stack模拟实现queue的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <stack>
using std::stack;

template<class T> class CQueue
{
public:
    CQueue()
    {
        nSize = 0;
    }

    void clear()
    {
        while (!one.empty())
        {
            one.pop();
        }
        while (!two.empty())
        {
            two.pop();
        }
    }

    void push(const T& t)
    {
        one.push(t);
        ++nSize;
    }

    void pop()
    {
        if (two.empty())
        {
            while (!one.empty())
            {
                two.push(one.top());
                one.pop();
            }
        }
        two.pop();
        --nSize;
    }

    T& front()
    {
        if (two.empty())
        {
            while (!one.empty())
            {
                two.push(one.top());
                one.pop();
            }
        }
        return two.top();
    }

    T& back()
    {
        return one.top();
    }

    bool empty()
    {
        return nSize == 0;
    }

private:
    stack<T> one;
    stack<T> two;
    int nSize;
};

#define MAX 20

int main()
{
    CQueue<int> q;

    srand(time(NULL));
    for (int i = 0; i < MAX; ++i)
    {
        q.push(i);

        if (rand() % 2)
        {
            printf("front: %d\n", q.front());
            q.pop();
        }
    }

    while (!q.empty())
    {
        printf("front: %d\n", q.front());
        q.pop();
    }

    return 0;
}

两个队列实现一个栈
要求：只能使用从队列的尾部入和头部出，以及测试队列是否为空三个操作。
实现思路：
队列里面使用queue one 和 stack two。
进栈时，根据当前元素是全部存储在哪个队列而选择从one或者two的尾部进入。
出栈时，假设当前元素都存储在one里面，则不断出队列，直到队列为空之前的所有元素一次进入队列two，而one里面的最后一个元素作为栈弹出的值返回。
对于当前元素是存储在哪个队列里面，可以设置变量标记，初始化时候存储在one里面，操作一次，由于元素要倒转，则存储位置会变一次。

用STL里面的queue模拟实现的stack代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142

#include <stdio.h>
#include <queue>
using std::queue;

template<class T> class CStack
{
public:
    CStack()
    {
        nSize = 0;
        nTime = 1;
    }

    void clear()
    {
        while (!one.empty())
        {
            one.pop();
        }
        while (!two.empty())
        {
            two.pop();
        }
    }

    void push(const T& t)
    {
        if (nTime % 2)
        {
            one.push(t);
        }
        else
        {
            two.push(t);
        }
        ++nSize;
    }

    void pop()
    {
        if (nTime % 2)
        {
            while (!one.empty())
            {
                T t = one.front();
                one.pop();
                if (!one.empty())
                {
                    two.push(t);
                }
            }
        }
        else
        {
            while (!two.empty())
            {
                T t = two.front();
                two.pop();
                if (!two.empty())
                {
                    one.push(t);
                }
            }
        }

        nTime = (nTime + 1) % 2;
        --nSize;
    }

    T& top()
    {
        if (nTime % 2)
        {
            while (!one.empty())
            {
                T t = one.front();
                one.pop();
                if (!one.empty())
                {
                    two.push(t);
                }
                else
                {
                    two.push(t);
                    nTime = (nTime + 1) % 2;
                    return two.back();
                }
            }
        }
        else
        {
            while (!two.empty())
            {
                T t = two.front();
                two.pop();
                if (!two.empty())
                {
                    one.push(t);
                }
                else
                {
                    one.push(t);
                    nTime = (nTime + 1) % 2;
                    return one.back();
                }
            }
        }
    }

    bool empty()
    {
        return nSize == 0;
    }

private:
    queue<T> one;
    queue<T> two;
    int nSize;
    int nTime;
};

#define MAX 20

int main()
{
    CStack<int> stack;

    for (int i = 0; i < MAX; ++i)
    {
        stack.push(i);
    }

    while (!stack.empty())
    {
        printf("top: %d\n", stack.top());
        stack.pop();
    }

    return 0;
}

发表于 分类于 阅读次数： Valine：
本文字数： 498 阅读时长 ≈ 1 分钟

带权中位数定义如下：

邮局位置问题定义如下：

上一篇文章输油管道问题里面证明了，当权值Wi都为1的时候，中位数就是最佳的解。但是，现在Wi已经不一定是1了。所以，现在
需要证明在任意Wi的取值情况下，带权中位数能够成为邮局位置的最佳解。假设，所有Wi都是1的倍数，如果是小数的话，可以所有的
Wi都乘以一定的倍数。那么wid(p,pi) = Σ(p,pi)(i从1到wi)，这个意思是把距离乘以了wi倍。
但是，现在可以换一种看法，换成了pi位置有wi个重合的点，且每一个点的权值都是1，那么其和也是wid(p,pi)。那么对所有的pi
都这样分解，就把问题重新转换成了输油管道问题了。输油管道问题的最优解就是中位数，那么邮局问题的最优解就是转换之后的
这些点的中位数点。而这个点一定存在于带权中位数那个点分解出的一堆点中。
二维邮局问题的解法是把x和y分开求2次一维邮局问题，然后把解组和起来，得到答案。

求带权中位数的算法比较简单，直接的做法是，先把n个点按照位置排序，然后按点的位置从小到大遍历，找到满足要求的点即可。
不算排序点位置的预处理，因为很多时候点应该就是按顺序给出的，所以其时间复杂度是O(n)。
要求：

发表于 分类于 ， 阅读次数： Valine：
本文字数： 2k 阅读时长 ≈ 2 分钟

先看算导上输油管道问题的描述：

这个题，虽然说给出了井的x,y坐标，但是要修建的主管道却只是一条横向的，而且其余管道也只是到这条管道的竖向距离。那么，就转换为确定一条直线 y = m，使得其它个点到这条直线的距离最多。也许不需要多的提示，大家的直觉就会想到应该所有y值的中点。但是，这个的证明却不是那么的明显。

证明如下：
设所有的y值系列为y1,y2,…,yn，并且假设这个是按递增排列的。我们要求的是Sum = Σ|yi-m|(1<=i<=n),

1）显然假如选小于y1或者大于yn的y=m都不会比选y1或者yn更好。
2）如果选y1或者yn，那么|y1-m|+|yn-m| = |yn-y1|都是一样的结果，甚至选y1和yn之间的任意一个值。
3）如此继续下去，对于y2和yn，也有2）所描述的性质
4）继续到最后，只需要取最中间一对点之间的值即可，如果n是奇数，那么就是中间的点，如果n是偶数，取任意一个中间点都可以。

通过上面证明，我们可以选取第y(n/2 + 1)作为修建主管道的地方。当然这可能是唯一的最优选择，或者无数个最优选择中的一个。那么现在已经转换为求中位数了，求中位数的办法最简单的是对序列排序然后取中间的即可。算法导论上有一种平均代价O(n)的办法，思路类似于快速排序，快排的每一次操作都是划分数组，前小后大，如果我们也这一次次去划分数组，刚好轴元素处于我们要求的那个位置上那么就达到我们的目的了，下面的代码中Select函数就是求一个数组的中位数。

对于POJ 1723题，很显然y的选择是中位数即可，x的选择需要转换一下也变成求中位数了。题目中描述，最后要达到的效果是每个士兵都占成一横排，而且彼此相邻，也就是y相同，但是x系列k,k+1,k+2,…,k+n-1。那么如何从原来的x0,x1,x2,…,x(n-1)移动过去了。可以简单的考虑下，将最左边的士兵移动到k,次左的移动到k+1,…,最右边的移动到k+n-1，所需要的移动之和一定是最小的。那么我们可以将原来的x0-x(n-1)排序，得到x’0,x’1,…,x’(n-1),要求的Sum = **Σ|x’i - (k + i)| = Σ|(x’i - i) - k|**,那么要使Sum最小，只需要求序列X’i - i的中位数即可了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <stdio.h>
#include <algorithm>
using std::sort;
using std::swap;
#define MAX (10000 + 10)
int Partion(int* pnA, int nLen)
{
    int i, j;
    for (i = j = 0; i < nLen - 1; ++i)
    {
        if (pnA[i] < pnA[nLen - 1]) { swap(pnA[i], pnA[j++]); } } swap(pnA[j], pnA[nLen - 1]); return j; } int Select(int* pnA, int nLen, int nIndex) { if (nLen > 1)
    {
        int nP = Partion(pnA, nLen);
        if (nP + 1 == nIndex)
        {
            return pnA[nP];
        }
        else if (nP + 1 > nIndex)
        {
            return  Select(pnA, nP, nIndex);
        }
        else
        {
            return Select(pnA + nP + 1, nLen - nP - 1, nIndex - nP - 1);
        }
    }
    else
    {
        return pnA[0];
    }
}
int main()
{
    int nX[MAX];
    int nY[MAX];
    int nN;
    int i;
    while (scanf("%d", &nN) == 1)
    {
        for (i = 0; i < nN; ++i)
        {
            scanf("%d%d", &nX[i], &nY[i]);
        }
        int nMY = Select(nY, nN, nN / 2 + 1);
        sort(nX, nX + nN);
        for (i = 0; i < nN; ++i)
        {
            nX[i] = nX[i] - i;
        }
        int nMX = Select(nX, nN, nN / 2 + 1);
        int nSum = 0;
        for (i = 0; i < nN; ++i)
        {
            nSum += abs(nX[i] - nMX);
            nSum += abs(nY[i] - nMY);
        }
        printf("%d\n", nSum);
    }

    return 0;
}

发表于 分类于 阅读次数： Valine：
本文字数： 1.3k 阅读时长 ≈ 1 分钟

虽然简易二字，因人而异。不过，写一个快排确实并不需要过20行，超过几分钟时间的代码。面试的时候，面试官确实会经常问起快排什么的。但是，大家上的入门课基本是使用严蔚敏老奶奶的教材，上面对于快排的讲解我是不敢恭维的。至少上面关于快排的写法，我是写过好几次之后都是没掌握好的。后面，应该是看K&R的c语言程序设计时候，发现一种更简便的partion方法，但是当时我也没怎么掌握。这一切直到，寒假认真阅读算法导论的时候。

不用算法牛人，算法学得好或者对快排理解深刻的，不用把这篇文章看完了，相信你们都能在10分钟之内写一个正确的快排了。
废话少说，还是来讲讲如何保证10分钟之内写一个正确的快排，而且以后都能10分钟之内写出来，而不是此刻看了我说的这些胡言之后。

快排的主函数大家都会，现在我给个简易点的样子：

1
2
3
4
5
6
7
8
9
void QuickSort(int* pnA, int nLen)
{
    if (nLen > 1)
    {
        int nP = Partion(pnA, nLen);
        QuickSort(pnA, nP);//排序第nP+1个元素前面的nP个元素
        QuickSort(pnA + nP + 1, nLen - nP - 1);//排序第nP+1个元素后面的元素
    }
}

那么现在就剩下Partion函数了。
我记得严蔚敏书上的写法中Partion 函数里面是有几个循环的。而且即使大概写出来了，也很难处理正确边界。
现在，我要说的就是算法导论上，作为教材内容出现的Partion函数。还是看代码吧。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int Partion(int* pnA, int nLen)
{
//这里选择最后一个元素作为轴元素
    int i, j;
    for (i = j = 0; i < nLen - 1; ++i)
    {
        if (pnA[i] < pnA[nLen - 1])
        {
            swap(pnA[i], pnA[j];//交换2个数的函数，大家都能写吧，stl中也有
            ++j;
        }
    }
    swap(pnA[j], pnA[nLen - 1]);
    return j;
}

为了公平起见，上面的代码我都是在blog上面直接敲的，写这10多行代码是绝对用不了10分钟的。主递归函数大家都会写，Partion函数里面只有一个for循环，所以只要明确了for循环的意思，快排的速写就迎刃而解了。其实，按照算导的说法，这个for一直在划分区间。区间[0,j-1]是小于最后一个元素的区间，[j,nLen - 2]是大于等于最后一个元素的区间，所以最后将第nLen-1个元素与第j个元素交换即可，Partion应该返回的值也应该是j。
我不知道大家理解上面那句黑体字的话没，如果理解了，随便写个快排是没问题了。至少，可能的下次面试时候，可以潇洒地写个快排给面试官看看了，虽然这也许并不是什么值得庆幸的事情。

算法导论里面的快速排序那章后面还有思考题，其中第一个思考题，提出的另外一种叫做Hoare划分的partion写法，意思就和严蔚敏书上的partion函数一致的。理解的关键是，轴元素一直处于被交换中。只要发现了这点，写一两次后，这种partion方法也能掌握好了，不过写起来是循环嵌循环了，没那么舒服。

发表于 分类于 阅读次数： Valine：
本文字数： 1.6k 阅读时长 ≈ 1 分钟

这个算法的应用，比如洗牌，这个大家都非常熟悉。很久以前用的是最原始的方法，就是一直rand()未出现的牌，直至生成所有的牌。这当然是一个while(1)循环，很烂的算法吧。后面听说直接交换牌，打乱即可了。但是打乱后生成的排列是随机的么，是等可能随机的么。
其实，这个问题上算法导论上早已经有了答案了，看过算法导论之后觉得没看之前真的是算法修养太差了。
算法的伪代码如下图所示：

具体c++实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <time.h>
// void Swap(int& nOne, int& nTwo)
// {
//  nOne = nOne + nTwo;
//  nTwo = nOne – nTwo;
//  nOne = nOne – nTwo;
// }
void Swap(int&  nOne, int&  nTwo)
{
    int nTemp;
    nTemp = nOne;
    nOne = nTwo;
    nTwo = nTemp;
}
//返回一个在区间[nBeg, nEnd]内的随机数
int Random(int nBeg, int nEnd)
{
    assert(nEnd >= nBeg);
    if (nBeg == nEnd)
    {
        return nBeg;
    }
    else
    {
        return rand() % (nEnd – nBeg + 1) + nBeg;
    }
}
void RandomizeInPlace(int* pnA, int nLen)
{
    static bool s_bFirst = false;
    if (!s_bFirst)
    {
        srand(time(NULL));
        s_bFirst = true;
    }
    for (int i = 0; i < nLen; ++i)
    {
        Swap(pnA[i], pnA[Random(i, nLen - 1)]);
    }
}
int main()
{
    int nArray[20];
    int i, j;
    for (i = 1; i <= 20; ++i)
    {
        int nCnt = i;
        while (nCnt–)
        {
            for (j = 0; j < i; ++j)
            {
                nArray[j] = j;
            }
            RandomizeInPlace(nArray, i);
            for (j = 0; j < i; ++j)
            {
                printf("%d", nArray[j]);
            }
            printf("\n");
        }
        printf("\n");
    }
    return 0;
}

运行效果图片如下：

根据运行结果大致就可以感觉到，生成的排列都是随机的。
这里要多说一句那就是我注释的那个交换函数其实是有bug的，也许这才是不提倡使用这个交换方法的真正原因，而不仅仅是难以理解。用同一个变量去调用该函数，会将该变量置0，而不是保持原来的值！！！至于如何证明这个算法生成的均匀随机的排列，可以参考算法导论5.3节最后一部分。
证明的大致思路是利用循环不变式的证明方法：证明i次循环后得到某个排列的概论是(n -i)! / n!，那么n次循环后得到最终那个排列的
概论就是1/n!，这样就证明了该算法能够得到均匀随机排列。
这个算法其实就是随机化算法的一种，其实快排也有所谓的随机化版本，改动的地方只是随机选择了中轴元素而已，这个在算法导论上也有介绍。

发表于 分类于 阅读次数： Valine：
本文字数： 4k 阅读时长 ≈ 4 分钟

今天在做课设，由于想给程序加上删除以前的配置文件的功能，由于某种原因，同类型的文件比较多，加上暑假实习的时候，做了个用dir命令实现的批量文件修改器，所以决定用del命令，一下子写好后，发现以前由于没有要求做界面，而现在课设我用的是MFC里面的CFormView做的界面，所以会闪烁而过一个console窗口，实在不爽之，所以，找方法去掉它。
网上找来找去，只找到启动cmd，传参数的都很少，传参数时候组合参数的更加少，加上我对dos命令不熟悉，所以实在悲催，浪费了不少时间。
这种东西，一直窃以为有人做好之后，提供比较合格的接口，大家以后都方便，所以贴出来，大家雅俗共赏，批评下。还发现网上的代码有个问题，居然大多把直接cmd路径写上去，其实大家都知道，系统路径是不确定的，所以特定修正了这个bug，而且我也实验了下，无论参数是绝对路径还是相对路径这个函数都是有效的。
大家用这个函数的时候，记得cmd命令都是可以匹配通配符的哦。

函数代码如下:

//批量删除指定格式文件,不显示console窗口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
void BatchDelFile(char* pszFile)
{
    char szDelCmd[MAX_INFO_LEN];
    char szCurDir[MAX_PATH];
    char szCmdPath[MAX_PATH];
    SHELLEXECUTEINFO shExecInfo = {0};

    GetCurrentDirectory(MAX_PATH, szCurDir);//获取当前路径
    GetSystemDirectory(szCmdPath, MAX_PATH);//获取cmd路径
    strcat(szCmdPath, "\\cmd.exe");
    sprintf(szDelCmd, "%s /c del /f /q /s %s",
    szCmdPath, pszFile);//格式化出命令字符串, 注意加上/c, 还有那2个""

    shExecInfo.cbSize = sizeof(SHELLEXECUTEINFO);
    shExecInfo.fMask = SEE_MASK_NOCLOSEPROCESS;
    shExecInfo.hwnd = NULL;
    shExecInfo.lpVerb = NULL;
    shExecInfo.lpFile = szCmdPath;//cmd的路径
    shExecInfo.lpParameters = szDelCmd;//程序参数,参数格式必须保证正确
    shExecInfo.lpDirectory = szCurDir;//如果szFile是相对路径,那个这个参数就会起作用
    shExecInfo.nShow = SW_HIDE;//隐藏cmd窗口
    shExecInfo.hInstApp = NULL;
    ShellExecuteEx(&shExecInfo);
    WaitForSingleObject(shExecInfo.hProcess, INFINITE);//无限等待cmd窗口执行完毕
}

以下是我在一个消息出来函数的调用：
char szDelFiles[MAX_PATH];
sprintf(szDelFiles, “\”.tcp.txt\” + \”.udp.txt\””);
BatchDelFile(szDelFiles);

为了调用方便，我还实现了一个可变参数列表的版本，以及一个传一个文件名数组的版本。

可变参数版本代码如下：
//批量删除指定格式文件,不显示console窗口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
void BatchDelFile(int nNum, ...)
{
    va_list argPtr;
    int i;
    char* pszDelCmd;
    char szCurDir[MAX_PATH];
    char szCmdPath[MAX_PATH];
    SHELLEXECUTEINFO shExecInfo = {0};

    pszDelCmd = (char*)malloc((nNum + 2)* MAX_PATH);
    GetCurrentDirectory(MAX_PATH, szCurDir);//获取当前路径
    GetSystemDirectory(szCmdPath, MAX_PATH);//获取cmd路径
    strcat(szCmdPath, "\\cmd.exe");
    sprintf(pszDelCmd, "%s /c del /f /q /s ", szCmdPath);//格式化出命令字符串, 注意加上/c
    va_start(argPtr, nNum);
    for(i = 0; i < nNum; ++i)
    {
        strcat(pszDelCmd, "\"");
        strcat(pszDelCmd, *(char**)argPtr);
        strcat(pszDelCmd, "\"");
        if (i != nNum - 1)
        {
            strcat(pszDelCmd, " + ");
        }
        va_arg(argPtr, char**);
    }
    va_end(argPtr);
    shExecInfo.cbSize = sizeof(SHELLEXECUTEINFO);
    shExecInfo.fMask = SEE_MASK_NOCLOSEPROCESS;
    shExecInfo.hwnd = NULL;
    shExecInfo.lpVerb = NULL;
    shExecInfo.lpFile = szCmdPath;//cmd的路径
    shExecInfo.lpParameters = pszDelCmd;//程序参数,参数格式必须保证正确
    shExecInfo.lpDirectory = szCurDir;//如果szFile是相对路径,那个这个参数就会起作用
    shExecInfo.nShow = SW_HIDE;//隐藏cmd窗口
    shExecInfo.hInstApp = NULL;
    ShellExecuteEx(&shExecInfo);
    WaitForSingleObject(shExecInfo.hProcess, INFINITE);//无限等待cmd窗口执行完毕
    free(pszDelCmd);
}

调用方法：
BatchDelFile(2, “.tcp.txt”, “.udp.txt”);//第一个是文件个数，后面依次是文件路径，文件路径可以是相对路径也可以是绝对路径。

文件名数组的版本代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
void BatchDelFile(int nNum, char** pszFiles)
{
    int i;
    char* pszDelCmd;
    char szCurDir[MAX_PATH];
    char szCmdPath[MAX_PATH];
    SHELLEXECUTEINFO shExecInfo = {0};

    pszDelCmd = (char*)malloc((nNum + 2)* MAX_PATH);
    GetCurrentDirectory(MAX_PATH, szCurDir);//获取当前路径
    GetSystemDirectory(szCmdPath, MAX_PATH);//获取cmd路径
    strcat(szCmdPath, "\\cmd.exe");
    sprintf(pszDelCmd, "%s /c del /f /q /s ", szCmdPath);//格式化出命令字符串, 注意加上/c

    for(i = 0; i < nNum; ++i)
    {
        strcat(pszDelCmd, "\"");
        strcat(pszDelCmd, *(pszFiles + i));
        strcat(pszDelCmd, "\"");
        if (i != nNum - 1)
        {
            strcat(pszDelCmd, " + ");
        }
    }
    shExecInfo.cbSize = sizeof(SHELLEXECUTEINFO);
    shExecInfo.fMask = SEE_MASK_NOCLOSEPROCESS;
    shExecInfo.hwnd = NULL;
    shExecInfo.lpVerb = NULL;
    shExecInfo.lpFile = szCmdPath;//cmd的路径
    shExecInfo.lpParameters = pszDelCmd;//程序参数,参数格式必须保证正确
    shExecInfo.lpDirectory = szCurDir;//如果szFile是相对路径,那个这个参数就会起作用
    shExecInfo.nShow = SW_HIDE;//隐藏cmd窗口
    shExecInfo.hInstApp = NULL;
    ShellExecuteEx(& shExecInfo);
    WaitForSingleObject(shExecInfo.hProcess, INFINITE);//无限等待cmd窗口执行完毕
    free(pszDelCmd);
}

调用方法：

1
2
3
4
char* szFiles[2];
szFiles[0] = "*.tcp.txt";
szFiles[1] = "*.udp.txt";
BatchDelFile(2, szFiles);

发表于 分类于 ， 阅读次数： Valine：
本文字数： 3.1k 阅读时长 ≈ 3 分钟

题目1描述:
输入:一个序列s,该序列里面可能会有同样的字符,不一定有序
输出:打乱输入中的序列,可能产生的所有新的序列
题目2描述:

输入:一个序列s,该序列里面可能会有同样的字符,不一定有序 和 一个整数k
输出:该序列往后计算第k个序列,所有序列是以字典序排序的如果会有序搜索的童鞋自然而然能立刻做出来第一个题目,可是第二个题目在s较长的情况下,却需要用模拟而不是搜索…
大家都知道STL里面有个泛函模版, prev_permutation和next_permutation,用法也很简单,实现的就是题目2的功能…
但是算法最好得靠自己想出来,自己想出来的才是自己的,碰到新的问题才能产生思想的火花…废话少说,题目1的解法就是深搜,不过需要加上一个bool数组标记和一个函数确定不同字符之间的大小(有可能这个大小还不是Ascii码就能决定的),
大致描述下搜索过程,比如输入序列是12345,那么我搜索的过程大致是第一层按顺序选取1-5,进入第二层的时候也是按顺序选取1-5,
以此类推,但是每一层里面都只能选前面的层次没有选过的数,而且因为有重复字符,算法还必须保证每一层里面按顺序选取的字符必须是升序的,
熟悉顺序搜索和回溯的同学,很自然就会产生这样的想法…
POJ - 1256的代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <stdlib.h>
#include <algorithm>
#define MAX (13 + 10)
using namespace std;
bool bUsed[MAX];
char szAns[MAX];
char szInput[MAX];
bool CmpChar(char chOne, char chTwo)
{
    if (abs(chOne - chTwo) != 'a' - 'A')
    {
        return tolower(chOne) - tolower(chTwo) < 0;
    }
    return chOne - chTwo < 0;
} 

bool Greater(char chOne, char chTwo) 
{ 
    if (abs(chOne - chTwo) != 'a' - 'A') 
    { 
        return tolower(chOne) - tolower(chTwo) > 0;
    }
    return chOne - chTwo > 0;
}

void Gen(int nDepth, int nLen)
{
    if (nDepth == nLen)
    {
        szAns[nLen] = '\0';
        printf("%s\n", szAns);
        return;
    }

    char chLast = '\0';
    for (int i = 0; i < nLen; ++i)
    {
        if (!bUsed[i] && Greater(szInput[i], chLast))
        {
            bUsed[i] = true;
            szAns[nDepth] = szInput[i];
            Gen(nDepth + 1, nLen);
            bUsed[i] = false;
            chLast = szInput[i];
        }
    }
}
int main()
{
    int nCases;

    scanf("%d", &nCases);
    while (nCases--)
    {
        scanf("%s", szInput);
        int nLen = strlen(szInput);
        sort(szInput, szInput + nLen, CmpChar);
        Gen(0, nLen);
    }

    return 0;
}

题目2的解法是模拟,功能类似与STL的那2个泛型模版函数,算法的大致过程是想办法从当前序列进入下一个刚好比其大或者刚好比其小的序列…很自然我们想到要把序列后面大的字符交和前面小的字符交换就会使序列变大,为了使其刚好变大,可以把交换后的字符从交换位置起至最后都排序一下,现在的问题是我们如何选取2个字符交换…正确的想法是,我们从最后面开始往前面看,寻找一个最长的递增序列,找到之后,我们只需要选取递增序列前面的那个字符chBefore和递增序列里面的一个最小的比chBefore大的字符交换即可…交换之后,将新的递增序列排序一下即可…
为什么这样做了,因为从后往前看的递增序列,是不能交换2个字符让当前序列变大的,所以必须选取最长递增序列前面的那个字符交换…

POJ百练 - 1833 的代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define MAX (1024 + 10)
using namespace std;
int nInput[MAX];
void GetNext(int* nInput, int nLen)
{
    int i = nLen - 2;
    while (i >= 0)
    {
        if (nInput[i] >= nInput[i + 1])
        {
            --i;
        }
        else
        {
            int k = i + 1;
            for (int j = nLen - 1; j > i; --j)
            {
                if (nInput[j] > nInput[i] && nInput[j] < nInput[k])
                {
                    k = j;
                }
            }
            swap(nInput[i], nInput[k]);
            sort(nInput + i + 1, nInput + nLen);
            return;
        }
    }

    sort(nInput, nInput + nLen);
}
int main()
{
    int nCases;
    scanf("%d", &nCases);
    while (nCases--)
    {
        int nLen;
        int nK;
        scanf("%d%d", &nLen, &nK);
        for (int i = 0; i < nLen; ++i)
        {
            scanf("%d", &nInput[i]);
        }
        for (int i = 0; i < nK; ++i)
        {
            GetNext(nInput, nLen);
        }
        for (int i = 0; i < nLen; ++i)
        {
            printf("%d%s", nInput[i], i == nLen - 1 ? "\n" : " ");
        }
    }
    return 0;
}