有道笔试面试题小结

十分抱歉，最近奔走于各种笔试和面试之间，感觉自己都要荒废了，总结一下最近遇到的一些比较有意思的题目吧：
（1）关于括号匹配的问题：
给你一个字符串，里面只包含"(",")","[","]"四种符号，请问你需要至少添加多少个括号才能使这些括号匹配起来。
如：
[]是匹配的
([])[]是匹配的
((]是不匹配的
([)]是不匹配的

求解给定一个输入的串，需要加入最少多少个括号使得，该输入串合法：

刚看到这个问题，我没有多想就给出了用堆栈匹配的方法，当遇到“（” 或者“[”直接入栈，然后当碰到右括号的时候，判断跟栈顶的元素是否匹配，如果匹配弹出栈定的元素，如果不匹配，将遇到的右括号配对之后，将计数器加一，直至字符串全部遍历完毕，然后用计数器+栈的size。

事后感觉还是想的太简单了些，上面给出的解答可以保证得到一个正确的序列但是不能保证序列是最优的。为什么呢？主要出现在了左右括号不匹配的时候，你是补全左括号，还是补全右括号，这个是不一定的，所以很显然这个用贪心是解决不了的，当用简单的贪心策略解决不了这个问题的时候，我们应该想到用dp去解决这个问题，那么如何定义这个dp的状态呢，简单的dp能够解决这个问题么？

显然不是很容易定义这个问题，因为我们想到括号是成对出现的，一个左括号可以跟位于其后的任何一个右括号匹配，匹配之后将原来的字符串就分成了两段，很自然的我们就想到了这个是一个分区dp的问题。
dp[i][j] = min(dp[i][k] + dp[k + 1][j]) (i <= k < j );
好得到了状态转移方程，我们就来实现这个dp程序，dp程序实现的两个要点：1、找出状态转移方程。2、初始化状态数组：
我们将:dp[i][i] = 1，单个括号的时候需要一个括号令其配对：
下面是实现的代码：

/*************************************************************************
    > File Name: test138.cpp
    > Author: dongdaoxiang
    > Func:
    > Mail: [e-mail]
    > Created Time: 2013年09月27日 星期五 15时28分59秒
 ************************************************************************/
#include<iostream>
using namespace std;

bool compare(const char a, const char b)
{
    if(a == '(' && b == ')' || a == '[' && b == ']')
    {
        return true;
    }
    else
    {
        return false;
    }
}

int get(const string &dest)
{
    if(dest.size() == 0)
        return 0;
    int size = dest.size();
    int dp[size][size];//状态数组
    int min = dest.size();
    for(int i = 0; i < size; i++)
    {
        dp[i][i] = 1;//单个括号置为1
    }
    for(int m = 1; m <= size - 1; m++)
    {
        for(int i = 0; i < size - m; i++)
        {
            int j = i + m;
            if(compare(dest[i], dest[j])) //比较两个端点是否匹配
            {
                if(j - i > 1)
                {
                    dp[i][j] = dp[i + 1][j - 1];
                }
                else
                {
                    dp[i][j] = 0;
                }
            }
            else
            {
                min = dest.size();
                for(int k = i; k < j; k++)
                {
                    int temp = dp[i][k] + dp[k + 1][j];
                    if(temp < min)
                    {
                        min = temp;
                    }
                }
                dp[i][j] = min;//找出区间最优解
            }
        }
    }
    return dp[0][size - 1];
}

int main()
{
    string s("(])](");
    cout << get(s) << endl;
    return 0;
}

（2）给定一个数组B，求得数组中最大差值a - b，在数组B中a在b的左边：

这个题目相对其他来说就比较简单了，好多人一上来就想到了求得每个元素跟其右边所有元素的差，然后找出该最大值，其实这样是没有必要的，我们可以用一个简单的技巧来找出这最大差值：
首先我们来看max[i]等于什么，他应该等于前i - 1个元素中的最大值，减去i的值得到的，所以我们只要在扫描的过程中，用一个变量maxBefore记住前 i - 1中的最大值，然后用另外一个变量记住差的最大值，在O（n）的时间复杂度和O（1）的空间复杂度内就可以解决这个问题。

/*************************************************************************
    > File Name: test139.cpp
    > Author: dongdaoxiang
    > Func:
    > Mail: [e-mail]
    > Created Time: 2013年09月27日 星期五 17时27分43秒
 ************************************************************************/
#include<iostream>
using namespace std;

int getMaxGap(int *arr, const int size)
{
    if(NULL == arr || size <= 0)
        return 0;
    int maxBefore = arr[0];
    int maxGap = 0;

    for(int i = 1; i < size; i++)
    {
        int temp = maxBefore - arr[i];
        if(temp > maxGap)
        {
            maxGap = temp;
        }
        if(arr[i] > maxBefore)
        {
            maxBefore = arr[i];
        }
    }
    return maxGap;
}

int main()
{
    int arr[5] = {2, 4, 1, 3,5};
    cout << getMaxGap(arr, 5) << endl;
    return 0;
}