现在的位置: 首页 > 综合 > 正文

一道简单的编程题，不过您做对了吗？

2013年01月25日 ⁄ 综合 ⁄ 共 3152字 ⁄ 字号小中大 ⁄ 评论关闭

static void Reverse(int[] array, int begin, int end)
{
   ...
}

　　Reverse方法的作用是将array数组中，从begin下标到end下标之间的元素反序一下，如一个数组初始值是[1, 2, 3, 4, 5, 6]，begin为1，end为4，那么当调用了Reverse之后，array数组中的元素便依次成为[1, 5, 4, 3, 2, 6]，其中从array[1]到array[4]之前的元素被反序了。此外补充一点……其实本不用补充：这个方法需要对传入参数的正确性进行校验，如果用户调用该方法时传入了非法的参数，那么则需要抛出异常，并写清原因。您可以使用您喜欢的语言来实现：C#，VB，Java，Ruby，Python……但是请不要使用内置库中已经有的功能。:)

　　很简单，不是吗？只可惜截止到目前，也只有1人给出了正确答案。如果您没有做过这道题目，那么在查看下面的分析之前，不妨拿张纸拿支笔，写下您的答案，然后再听老赵慢慢讲来……（点此展开）

主体逻辑

　　这道题目的主题逻辑其实非常简单。不就是把数组中的一部分反序吗？不过从这一点上面来说，代码的清晰程度也有较大差距。好的做法和普通的做法，从编程难度和理解上都有一定差距。例如：

许多朋友的做法是：既然是反转数组的一部分元素，那么只要找到中间的位置，然后计算出和begin的偏移量，然后……怎么怎么一搞，就完成了——嗯，似乎还需要根据进行begin和end中间的元素个数是奇数还是偶数分别处理。
另一些朋友的做法是：开一个新数组（长度为end - begin + 1），将begin到end之间的元素放到新数组中去，然后反序，然后再复制回来。
还有一个朋友认为用栈：把begin到end之间的元素给push到栈中，再一个一个pop出来依次赋值给begin到end，这样就反序了……唔！数据结构学的不错！

　　只可惜，这样的做法都复杂了一些。3种做法的时间复杂度均为O(end – begin)，但是只有第一种做法的空间复杂度是O(1)，而后两者也都是线性的空间复杂度。那么老赵眼里最好的做法是什么呢？

static void Reverse(int[] array, int begin, int end)
{
    while (end > begin)
    {
        int temp = array[begin];
        array[begin] = array[end];
        array[end] = temp;

        begin++;
        end--;
    }
}

　　end和begin两个下标从初始值开始依次向中间逼近，每次都交换一下数组中的元素。最终，while在判断的时候会发现end == begin（begin和end之间总共奇数个元素），或end < begin（begin和end之间总共偶数个元素）。无论哪种情况，都表示反序已经完成。

　　是不是很简单？

参数校验

　　上面的做法应该说是最简单的一种，不过实际在评判答案的时候，直接结果正确，老赵都认为是正确的。只可惜，几乎没有朋友在“参数校验”这方面作对。

　　顺便提一下的是，有位朋友给我留言很有意思：“老师只给了一个测试数据，如果要用其它测试数据的话比如比较特殊的，那请老师下次把测试数据列好。”这句话让我木然：测试数据是无穷无尽的，难道需要都列出来？平时写程序，用户会指出他的所有操作步骤吗？给测试数据的目的是为了帮助理解题意，题目的要求都写清楚了，做题才有意义。如果一道题目只要求把给出的测试数据运行，那么又有谁不会做呢？老赵这里就可以立即给出一个万能模板：

if (...)
{
    return ...
}
else if (...)
{
    return ...
}

...

　　按理来说，即使题目中没有写明需要参数校验，一个优秀的实现也应该自带这一点。

　　其实只要仔细一些，把参数所有的错误情况列举出来并不是难事：

array == null
begin < 0;
end < begin
end >= array.Length

　　那么，其他一些情况是否应该一并判断呢？例如end < 0，array.Length == 0或者begin >= length。老赵认为“不判断也没有关系”，因为以上的判断已经确保不会出现额外的错误情况了。那么begin == end是否算是问题呢？老赵认为，这个判断也可以省略。不过……如果begin > end，那么是否应该把两者的数值进行交换？我不知道为什么有些朋友这么做了，不过老赵认为，一般来说一个方法不应该为参数进行额外“调整”——其实各大类库都不会如此画蛇添足。如果哪位朋友有不同看法，我们可以继续讨论。

常见错误

　　在各种答案，以及平时面试过程中，这道题总归会有一些非常典型的错误发生。其中给老赵的感觉也非常有意思，不知其中的“思路”是否如老赵猜测那样。

在方法中进行输入和输出

　　有不少朋友在代码里放置了这样的代码：

static void Reverse(int[] array, int begin, int end)
{
    Console.WriteLine("请输入xxx");
    array[0] = Int32.Parse(Console.ReadLine());
    ...

    for (int i = 0; i < array.Length; i++)
    {
        Console.WriteLine(i);
    }
}

　　为什么会出现这种情况？老赵估计是受到了某些培训机构的影响（观察出现这个问题的朋友们的分布便知）。这些培训一再强调输入、输出，而没有让学员有任何“模块”，“类库”，“辅助方法”的概念。学员的观念中，任何程序都要向用户去索要“输入”，并且要“输出”，否则就不算是程序。

　　为什么会这样？

打印错误，而不是抛出异常

　　代码如下：

static void Reverse(int[] array, int begin, int end)
{
    if (array == null)
    {
        Console.WriteLine("数组为空");
        return;
    }

    ...
}

　　除了和上面类似的“思维”以外，这说明有些朋友还没有形成“抛出异常”的观念。这意味着在过往的编程经验中，可以说完全没有“参数校验”的概念在头脑里面。培训机构只是一味地CRUD，展示，写入，却没有“抛出异常”的想法。同理，即使在题目中已经明确写清了是“抛出”异常，有些朋友的写法是这样的：

static void Reverse(int[] array, int begin, int end)
{
    try
    {
        // 交换数据
    }
    catch (Exception e)
    {
        Console.WriteLine(e.Message);
    }
}

　　很明显，他们只有“捕获”异常的概念——自然是框架本身抛出的异常——而不知“抛出”异常。

参考答案

　　以下是老赵给出的参考答案：

static void Reverse(int[] array, int begin, int end)
{
    if (array == null)
    {
        throw new ArgumentNullException("array", "array不能为空");
    }

    if (begin < 0)
    {
        throw new ArgumentOutOfRangeException("begin", "begin不能小于0");
    }

    if (end < begin)
    {
        throw new ArgumentOutOfRangeException("end不能小于begin", (Exception)null);
    }

    if (end >= array.Length)
    {
        throw new ArgumentOutOfRangeException("end", "end超过array最大下标");
    }

    while (end > begin)
    {
        int temp = array[begin];
        array[begin] = array[end];
        array[end] = temp;

        begin++;
        end--;
    }
}

【上篇】Android驱动之 Linux Input子系统之TP——A/B(Slot)协议
【下篇】command命令模式

作者: wooded

该日志由 wooded 于11年前发表在综合分类下，最后更新于 2013年01月25日.
转载请注明: 一道简单的编程题，不过您做对了吗？ | 学步园 +复制链接

抱歉!评论已关闭.

学步园