0918携程秋招笔试复盘

1.
题目大意：判断一个三位数是否等于其各位数字的立方和。

思路：通过取模和整除运算分离出百、十、个位，计算立方和后与原数比较。

2.
题目大意：
对一个字符串先进行字符循环移位，再从右至左消除相邻的同字母异大小写字符对。

思路：
第一步是字符模拟。第二步从右向左遍历，使用栈结构进行配对消除：若当前字符与栈顶字符能配对，则跳过；否则将当前字符入栈。

3.
题目大意：给定一个数组，可任选数组中一个元素x，将整个数组所有元素异或x，此操作可进行任意次。求操作后数组元素和的最大值。

思路：
任意次操作等价于将原数组与0或某个初始元素异或一次。因此，遍历所有初始元素和0作为候选异或值，计算每种情况下的数组和，取最大值。为加速求和，可预先按位统计原数组中1的个数，再根据异或值计算每位的贡献。

4.
题目大意：对一个序列，通过至多一次的区间反转操作，求能达到的最小逆序对数量。

解题思路：先计算原序列的总逆序对数。反转区间[l, r]带来的逆序对减少量为：区间内原有的逆序对数 - 区间内原有的顺序对数。暴力枚举所有可能的区间[l, r]，计算每个区间反转带来的逆序对减少量，找出最大减少值，从初始逆序对数中减去即可。
#发面经攒人品##携程##秋招##携程秋招##牛客AI配图神器#