微软笔试简易题解

这次还是挺简单的，比上次实习笔试简单多了。。上次实习笔试简直就在做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]=min\{min(dp[i][k]+dp[k+1][j]),st(s[i],s[j])+dp[i+1][j-1]\}$

并且

$dp[i][i+1]=st(s[i],s[i+1])$

$st(a,b)= \begin{cases} 1& \text{a==b}\\ 2& \text{a=='J'}\\ 0& \text{a=='K'} \end{cases}$

大概解释一下，就是 dp[i][j] 要么是从两段 dp[i][k] 和 dp[k+1][j] 转移而来，要么就是去掉头尾 s[i] 和 s[j]，然后转移到 dp[i+1][j-1]

#微软##笔试题目#

全部评论

推荐最新楼层

点儿点儿7

算法工程师

第一题题目写错了吧，应该是a[0]+a[n-1] = a[1]+a[n-2]...另外能具体说下怎么做吗

1 回复

发布于 2020-09-22 12:55

狗傻

算法工程师

为何你们都有笔试

点赞回复

发布于 2020-09-22 10:54

滴滴

校招火热招聘中

官网直投

Duodenum

PHP

第三题可以用栈

点赞回复

发布于 2020-09-22 12:57

傅明老人找工作

算法工程师

不是，想不明白第一题那个原始的序列保证 a[1] = a[n], a[2] = a[n-1], ..., a[i] = a[n-i] 怎么还能做到序列递增

点赞回复

发布于 2020-09-22 16:23

钱多多钱

C++

楼主被通知笔试了吗？

点赞回复

发布于 2020-09-24 11:49

牛客51186656号

算法工程师

// 第一题，用差序列做，希望有dl指正 bool isSymmetric(vector<int> &diff, int begin, int end) { for(int i = begin; i < (begin + end)/2; i++) { if(diff[i] != diff[begin + end - i]) { return false; } } return true; } int solution(vector<int>& A) { int n = A.size(); vector<int> diff(n-1, 0); for(int i = 0; i < n-1; i++) { diff[i] = A[i+1] - A[i]; } int ret = A[0]; for(int i = 0; i < (n-1)/2; i++) { if(diff[i] != diff[n-2-i]) { if(i == 0 && isSymmetric(diff, 1, n-2) || isSymmetric(diff, 0, n-3)) { if(isSymmetric(diff, 1, n-2)) { ret = A[n-1] + diff[0]; } else if(isSymmetric(diff, 0, n-3)) { ret = A[0] - diff[n-2]; } } else { if(diff[i] > diff[n-2-i]) { ret = A[i] + diff[i+1]; } else { ret = A[n-1-i] - diff[i]; } } break; } } return ret; }

点赞回复

发布于 2021-04-10 17:32