腾讯2017暑期实习生编程挑战：回文串优化与大写字母移动

在腾讯2017暑期实习生的编程题目中，我们遇到了两个有趣的问题。第一个问题是关于字符串操作和动态规划的回文序列问题。给定一个字符串`s`，目标是通过删除某些字符使其成为最长的回文子串。这个问题可以通过动态规划方法解决。算法的核心在于创建一个二维数组`dp`，其中`dp[i][j]`表示从索引`i`到`j`的子串是否为回文串。初始化时，如果子串包含相同字符则`dp[i][j] = 0`（即回文），否则为`1`。然后遍历字符串，对于每个长度，检查左右字符是否相等，若相等则`dp[i][j]`保持不变，否则更新为左右子串的回文状态中的较小值加一。最后，通过`dp`数组找到最长回文子串的边界，计算出需要删除的字符个数。 第二个问题是字符移动问题，具体是将一个字符串中所有大写字母移到字符串的末尾，同时保持原始字符顺序不变，且不使用额外空间。这里可以利用位操作技巧来实现，题目给出了`isCap()`函数用于判断字符是否为大写字母。`mSwap()`函数则是关键，通过异或操作实现字符交换。当`a`和`b`不相等时，执行三次异或操作`a ^= b`, `b ^= a`, `a ^= b`，这样可以在原地完成字符交换，无需额外空间。在`main()`函数中，读取输入字符串，不断处理大写字母并调用`mSwap()`函数进行交换，直到字符串中的所有大写字母都移到了末尾。 这两个题目不仅考察了基础的编程技能，如字符串处理、动态规划和位操作，还涉及到了数据结构和算法优化，对于实习生来说，是非常实用且考验思维能力的练习题。理解和解决这些问题，可以帮助实习生提升算法理解、逻辑思考以及实际编程能力。