京东8.12笔试

我是100 97 100.感觉这次运气爆棚。开个帖子分享下思路吧

只分享第一题和第三题的思路，不一定是最优的。但是反正a了。

第一题回文：双指针
看字符串长度为1000，感觉用o(n^2)的复杂度肯定能解。于是就考虑一个一个遍历。
因为移动字符串再改和改了再移动字符串实际上没有本质区别，顺序是无所谓的。所以就直接开始从移动0 - (n-1)的字符串来开始，然后用双指针判断如果要成为回文字符串需要改动多少字符，总的次数就是改动的字符加上之前移动的次数。然后遍历取最小就行了

第三题正方形：暴力遍历
从每一个"x"的位置开始，然后判断它所有的右上（包括正右边）的临界点是否是"x"，这样可以避免重复。如果是X，那就判断含这两点作为右下底边是否能组成正方形，能就可以 + 1