微软笔试简易题解
这次还是挺简单的，比上次实习笔试简单多了。。上次实习笔试简直就在做acm金牌题。。
1.
题意：给你一个长度为偶数的递增的序列 a ，原始的序列保证 a[1] = a[n], a[2] = a[n-1], ..., a[i] = a[n-i]，现在拿掉其中一个元素，问你拿掉的那个元素是多少。
解：拿前半部分二分就好了
2.
题意：有一个空格分割的若干个单词组成的字符串，现在有一个n表示对每个单词做n次顺时针旋转，现在给你旋转之后的的字符串，问有多少个单词在原来的字符串和旋转之后的字符串中一致。比如n=2, 字符串="ba def adad"，那么显然旋转之前的字符串是"ba fde adad"，所以有2个单词和原来一致。
解：模拟一下就好了，用python写特别简单。
3.
题意：给你一个J和K组成的字符串，要求改变其中的若干个字符，使得：1) J和K的数量一致 2) 从左到右，K的数量始终多余J的数量。问你最少需要改变几个字符。比如KKJJ、KJKJ、KKJJKJ都是合法的，但JK、KJJK、KKJ都是不合法的。
解：显而易见的dp。设 dp[i][j] 表示从 i 到 j 的答案，那么
并且
大概解释一下，就是 dp[i][j] 要么是从两段 dp[i][k] 和 dp[k+1][j] 转移而来，要么就是去掉头尾 s[i] 和 s[j]，然后转移到 dp[i+1][j-1]
查看26道真题和解析
