解决字符串回文与大写字母移位问题的算法

"这是腾讯2017年暑期实习生笔试题的一部分，包含了两道编程题目。第一题是关于找到一个字符串中能形成最长回文串所需的最少删除字符数，第二题则要求在不额外申请空间的情况下，将字符串中的大写字母移到后面，保持原有顺序不变。" 在这份笔试题中，我们首先遇到的是一个与回文串相关的算法问题。回文串是指正读反读都能读通的字符串，如"abcba"。问题要求找出一个字符串中最少需要删除多少个字符，才能使剩下的字符串形成一个回文串。解决这个问题的一种方法是使用动态规划。代码中定义了一个二维数组`dp`，其中`dp[i][j]`表示字符串从索引`i`到`j`的子串是否是回文串，以及如果不是，需要删除的字符数。初始化时，如果相邻的两个字符相同，则`dp[j-1][j]`为0，否则为1。接着，通过双重循环更新`dp`数组，对于每个子串，如果首尾字符相同，则可以继承上一个子串的性质，即`dp[i][j] = dp[i+1][j-1]`；否则，`dp[i][j]`等于删除末尾字符或删除首字符后的较小值加1。 第二题是一个位操作的问题，要求在不使用额外空间的情况下，将字符串中的所有大写字母移动到字符串的末尾。这个问题可以通过位操作的交换技巧实现。首先定义一个函数`isCap()`来判断字符是否为大写字母。然后，使用位操作的异或(XOR)技巧`mSwap()`来无额外空间地交换两个字符的值。在主函数`main()`中，通过循环读取字符串，每次遇到大写字母，就将其与后面的字符进行位操作交换，从而实现大写字母向后移动。这个方法巧妙地利用了位操作的性质，可以在不额外分配内存的情况下完成字符的交换。 这两道题都是对编程思维和算法能力的测试，涉及到字符串处理、动态规划和位操作等核心概念，对于想要进入IT行业，尤其是互联网大厂实习的学生来说，是很好的练习题目。