微软2021春招实习生笔试

发表于 更新于 分类于 ，

两个小时，三道题，第二题实在是粗心了，正确率应该能提到100%的，忘记对结果进行特判。

结果

A题

第一题可以选择中文或者英文题面，不过题目好像不太一样，我做的中文题。

题面

给一个数组，求其中元素大于等于3的等差数列子串的数量。只评测正确率，不评测运行时间。

题解

因为不评测运行时间，所以直接暴力枚举即可，判断是否等差数列可以直接求差分是否相等，复杂度o(n)，枚举子串复杂度C(n,m)，因为每个长度都枚举，总之这个复杂度是挺炸裂的，不过它不评测时间，所以没问题，这题如果认真做的话应该可以优化到o(n)。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
bool isArti(vector<int>::iterator begin, vector<int>::iterator end) {
    auto itr = begin + 1;
    int diff = *itr - *begin;
    for (; itr < end; itr++) {
        if (*itr - *(itr - 1) != diff) {
            return false;
        }
    }
    return true;
}

int artiSeq(vector<int> &A) {
    int ans = 0;
    for (int i = 0; i + 3 <= A.size(); i++) {
        for (int len = 3; i + len <= A.size(); len++) {
            if (isArti(A.begin() + i, A.begin() + i + len)) {
                ans += 1;
            }
        }
    }
    return ans;
}

B题

题面

给一个长度N的数组，其中数字范围是[1,N]，每次变化可以对一个元素+1或者-1，求最少多少次变化可以让数组中每个数字唯一。N的范围是2e5。如果结果大于1e9则返回-1。

题解

直接排序，然后遍历每个元素求它本身与它的下标的差再加起来即可。复杂度o(nlogn)。

代码

在做这题的时候忘了判断结果是否大于1e9，所以正确率只有90%，裂开。

而且这题其实我搞复杂了，完全不需要那个order数组的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int moveNumber(vector<int> &A) {
    int ans = 0;
    sort(A.begin(), A.end());
    vector<int> order(A.size());
    for (int i = 0; i < order.size(); i++) {
        order[i] = i + 1;
    }
    for (int i = 0; i < A.size(); i++) {
        ans += abs(order[i] - A[i]);
    }
    if (ans > 1000000000) {
        return -1;
    }
    return ans;
}

C题

题面

给一组平面上的点，求三个点共线的组合有多少个。点的数量范围是1e3，如果结果大于1e9则输出-1。

题解

这题没想到好的方法，直接暴力枚举来做的，全部都超时了，好在都是对的。

判断三个点是否共线可以用斜率，具体来说就是
$$
\frac{x_a-x_b}{y_a-y_b}=\frac{x_c-x_b}{y_c-y_b}
$$
考虑到除法可能导致精度问题以及除0（垂直线）错误，我们只需要把它改成乘法来判断就好了。复杂度$O(n^3)$。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
struct Point2D {
    int x;
    int y;
};

bool isCollinear(Point2D &a, Point2D &b, Point2D &c) {
    return (a.x - b.x) * (c.y - b.y) == (c.x - b.x) * (a.y - b.y);
}

int numOfCollinear(vector<Point2D> &A) {
    int ans = 0;
    for (int i1 = 0; i1 + 2 < A.size(); i1++) {
        for (int i2 = i1 + 1; i2 + 1 < A.size(); i2++) {
            for (int i3 = i2 + 1; i3 < A.size(); i3++) {
                if (isCollinear(A[i1], A[i2], A[i3])) {
                    ans += 1;
                }
            }
        }
    }
    return ans > 1000000000 ? -1 : ans;
}