2012腾讯笔试：Hadoop2算法题-字符串大写字母后置无额外空间

在2012年腾讯笔试中，一道关于Hadoop2的算法题要求设计一个函数来处理字符串，将其中的大写字母移动到字符串的末尾，同时保持原有字符的相对位置不变，且不能申请额外的空间。这个问题考察了对字符串操作的理解、循环控制和空间复杂度的优化。 该题目给出的代码实现主要包含以下关键步骤： 1. 判断字符是否为大写字母的函数`isUpperAlpha`：这个函数接受一个字符`c`作为输入，通过ASCII码范围判断是否在大写字母'A'到'Z'之间，如果满足条件则返回1，否则返回0。 2. 交换字符的函数`swap`：这是一个简单的字符指针交换函数，用于在不改变原始数组的情况下，将两个字符的位置互换。 3. 主要处理函数`mySort`：函数接收一个字符串`arr`和其长度`len`作为参数。首先检查输入是否有效，然后通过三层嵌套循环来实现目标。外部循环控制遍历字符串，中间循环用于查找大写字母，内部循环则用来交换大写字母与非大写字母之间的位置。当找到大写字母后，会立即从当前位置向后移动，并跳过已处理的部分。若遍历结束仍未发现大写字母，则直接返回原数组，表示无需进一步操作。 4. `main`函数中的示例：给出了一个字符串`"aaaaaaaaaaaaaaaaaaaaaaaAbcAdeBbDc"`，调用`mySort`函数并打印处理后的结果，结果为`"aaaaaaaaaaaaaaaaaaaaaaabcdebcAABD"`，可以看到大写字母被移动到了字符串的末尾。 然而，这段代码并非最优解，因为每次找到大写字母后都需要进行一次全数组的内层循环，这会导致不必要的重复操作。实际上，可以通过一个变量记录上次发现大写字母的位置，然后只在该位置之后的区域进行交换，这样可以减少不必要的比较和交换操作，提高效率。优化后的代码虽然没有在给出的部分体现，但理解这一点对于实际解决此类问题至关重要。 这个题目考察了考生对字符串处理的熟练程度，对算法的优化意识，以及如何在有限空间和条件下解决问题的能力。在实际面试中，除了正确实现功能，还要能讨论优化思路和复杂度分析，这对于评估候选人的编程技能和思维能力非常有帮助。