虾皮4.6笔试情况
单选题主要考察智商了，多选题还好。
编程题AC了2.7，不过不抱有希望，虾皮只是走流程而已。
第一题，互斥字符串：相邻两个字符不同。给你一个字符串，只包含AB两种字符，你可以对任何一个字符改变，比如A改为B，B改为A，问把这个字符串改为互斥字符串的最小次数。
比如ABB，只需要将最后一个B改为A即可。
这道题直接暴力，分别看凑出ABAB。。。和BABA。。。的最小次数就行了。挺像动态规划的，因为状态和选择都有，求的也是字符串的最大或者最小，但是我做过的题一般是两个字符串多，比如编辑距离，所以这个没想到用dp怎么做。
第二题，n皇后问题，坑的就是虾皮的编辑器提示我不通过，我以为我算法问题，浪费了40分钟后发现原来我的全局函数res没放上去，发现这个错误还是我重新将代码cv上突然ac，惊呆了我。
第三题，给你4个数，a，b，A，B，可以有两种操作，对a和b同时加一，对a和b同时乘2，问转化为A，B的最小操作次数，不能转换输出-1.
第二题浪费了很多时间，第三题时间也够，不过是在没思路，投机取巧下发现输出-1，通过30%，输出0，通过10%，输出2，给30%，输出5，给10%，这种情况应该给80%，但是最后只凑出了70%，几个if else而已，有时间好好思考下。
附上第三题凑数code
public long GetMinCalculateCount(long sourceX, long sourceY, long targetX, long targetY) {
// write code here
if (targetX == sourceX && targetY == sourceY) return 0;
if (targetX <= sourceX || targetY <= sourceY) return -1;
if (sourceX + 2 == targetX && sourceY + 2 == targetY ||
sourceX * 4 == targetX && sourceY * 4 == targetY ||
(sourceX + 1) * 2 == targetX && (sourceY + 1) * 2 == targetY ||
sourceX * 2 + 1 == targetX && sourceY * 2 + 1 == targetY) return 2;
return targetX % sourceX == 0 ? 5 : -1;
} 来一个回溯暴力破解，时间复杂度最坏2的n次方，可以用dp，应该可以控制在n2，明天试下 int res = Integer.MAX_VALUE;
public long GetMinCalculateCount(long sourceX, long sourceY, long targetX, long targetY) {
// write code here
traverse(sourceX, sourceY, targetX, targetY, 0);
return res == Integer.MAX_VALUE ? -1 : res;
}
private void traverse(long sourceX, long sourceY, long targetX, long targetY, int step) {
if (sourceX > targetX || sourceY > targetY) return;
if (sourceX == targetX && sourceY == targetY) {
res = Math.min(res, step);
return;
} else if (sourceX == targetX && sourceY == targetY || sourceX != targetX && sourceY == targetY) return;
traverse(sourceX + 1, sourceY + 1, targetX, targetY, step + 1);
traverse(sourceX * 2, sourceY * 2, targetX, targetY, step + 1);
} 
投递比亚迪等公司10个岗位 >
查看3道真题和解析
