微软0825笔试
第一题：去除数字中的一个5，使得数字最大。
样例：
- n = 15958, return 1958
- n = -5859, return -589
- n = -5000, return 0
数据范围[-999995, 999995]，且一定含有至少一个5。评估只看正确性，不看性能。
思路：暴力枚举，n最大才10万， 枚举也才5个数。先记录符号，然后枚举去除5的所有可能。
虽然是暴力枚举，但时间和空间复杂度O(lg(n))。随着n的位数增长。
第二题，leetcode560，k为0的情况。
思路：前缀和，然后求和。时间和空间复杂度都是O(n)。
第三题，求等差数列的个数，最少连续三个。
样例：
- A = [-1, 1, 3, 3, 3, 2, 3, 2, 1, 0]，return 5。有五个区间是等差
- (1) [-1, 1, 3] 差为2
- (2) [3, 3, 3] 差为0
- (3) [3, 2, 1, 0] 差为1
- (4) [3, 2, 1]
- (5) [2, 1, 0]
思路：双指针确定等差区间，区间长度为3，则区间个数为1； 区间长度为4，则区间个数为（4 - 1）*（4 - 2）/2 == 3；可知区间长度为k时， 区间个数为（k - 1)*(k - 2)/2。
时间复杂度O(n)，空间复杂度O(1)。
求求大家的点赞和收藏了。
想要原题截图的可以私信我。
#校招##秋招##微软#
投递牛客等公司9个岗位 >
