> For the complete documentation index, see [llms.txt](https://vernon97-io.gitbook.io/untitled/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://vernon97-io.gitbook.io/untitled/codingtests/wei-ruan-shu-qi-shi-xi-bi-shi-2021.02.26.md).

# 微软暑期实习笔试2021.02.26

#### 01 - 编程题01

We will call a sequence of integers a *spike* if they first increase (strictly) and then decrease (also strictly, including the last element of the increasing part). For example (4, 5, 7, 6, 3, 2) is a spike, but (1,1, 5, 4, 3) and (1, 4, 3, 5) are not.

Note that the increasing and decreasing parts always intersect, e.g.: for spike (3, 5, 2) sequence (3, 5) isan increasing part and sequence (5, 2) is a decreasing part, and for spike (2) sequence (2) is both an increasing and a decreasing part.

Your are given an array A of N integers. Your task is to calculate the length of the longest possible spike, which can be created from numbers from array A. **Note that you are NOT supposed to find the longest spike as a sub-sequence of Ak, but rather choose some numbers from A and reorder them to create the longest spike.** (不是找子序列 而是可以重新排列)

Write a function:

`class Solution {public int solution(int[] A) }`

which, given an array A of integers of length N, returns the length of the longest spike which can be created from the numbers from A.

Examples:

1. Given A = \[1, 2] your function should return 2, because (1, 2) is already a spike.
2. Given A = \[2, 5, 3, 2, 4, 1] your function should retum 6, because we can create the following spike of length 6: (2, 4, 5, 3, 2, 1).
3. Given A = \[2, 3, 3, 2, 2, 2, 1] your function should return 4, because we can create the following spike of length 4: (2, 3, 2, 1) and we cannot create any longer spike. Note that increasing and decreasing parts should be strictly increasing/decreasing and they always intersect.

Write an efficient algorithm for the following assumptions:

* N is an integer within the range `[1 - 100,000]`
* each element of array A is an integer within the range `[1 - 1,000,000]`

***

还是要好好审题哈 这题要是不可排序就是典型的LIS问题了 前序LIS 后序LDS 然后枚举中间点找最大值

这题感觉就是简单的贪心了 首先统计每个元素出现的次数，然后最大值必在中间只能出现一次 剩下的元素最多出现两次（在左右两边） 好了

```cpp
class Solution
{
public:
int solution(vector<int>& A) // 这是不行的 数组指针传参就没有大小信息了
{
    if(A.empty()) return 0;
    unordered_map<int, int> h;
    int max_val = -0x3f3f3f3f;
    for(int i = 0; i < A.size(); i++)
    {
        h[A[i]]++;
        max_val = max(max_val, A[i]);
    }
    int res = 1;
    for(auto& p : h)
    {
        if(p.first == max_val) continue;
        res += min(2, p.second);
    }
    return res;
}
}
```

#### 02 - 编程题02

You are given an array A of integers. Find the maximum number of non-intersecting segments of length 2 (two adjacent elements), such that segments have an equal sum. For example, given A = \[10,1, 3,1, 2, 2,1, 0, 4] there are three non-intersecting segments, each whose sum is equal to 4: (1, 3), (2, 2), (0,4). Another three non-intersecting segments are (3, 1), (2, 2), (0,4). Write a function: that, given an array A of N integers, returns the maximum number of segments with equal sums. Examples:

1. Given A = \[10,1, 3,1, 2, 2,1, 0, 4], the function should return 3, as explained above.
2. Given A = \[5, 3, 1, 3, 2, 3], the function should return 1. Each sum of two adjacent elements is different from the others.
3. Given A = \[9, 9, 9, 9, 9], the function should return 2.
4. Given A = \[1, 5, 2, 4, 3, 3], the function should return 3. There are three segments: (1, 5), (2,4), (3,3) whose sums are equal to 6.

Write an **efficient** algorithm for the following assumptions:

* N is an integer within the range `[2 - 100,000]`
* each element of array A is an integer within the range `[0 - 1,000,000,000]`

***

我也没有oj哈 但看这个意思得写一个`O(n)`

想了半天的DP 后来发现这个问题可以拆分成 枚举每个和出现的所有区间 然后计算最大不相交区间个数

我们先来回顾一下计算最大不相交区间个数的方法-> 贪心问题：

```cpp
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <unordered_map>
#include <vector>
using namespace std;
using PII = pair<int, int>;
class Solution{
public:
    int solution(vector<int>& A)
    {
        unordered_map<int, vector<PII>> hash;
        for(int i = 1; i < A.size(); i++)
        {
            hash[A[i - 1] + A[i]].emplace_back(i - 1, i);
        }
        // 不必排序了 一定是有序的
        int res = 0;
        for(auto& p : hash)
        {
            res = max(res, find(p.second));
        }
        return res;
    }
    int find(vector<PII>& intervals)
    {
        int res = 0, cur_r = -2e9;
        for(int i = 0; i < intervals.size(); i++)
        {
            int l = intervals[i].l, r = intervals[i].r;
            if(cur_r < l)
            {
                cura_r = r;
                res ++;
            }
        }
        return res;
    }
}
```

***

#### 03 - 编程题03

A non-empty array A consisting of N non-negative integers is given. Its *binarian* is defined as:

`binarian(A)=pow2(A[0]) + pow2(A[1]) + ... + pow2(A[N-1])` `pow2(K) = 2 ^ K`

For example, the binarian of array A such that: `[1, 5, 4]` equals 50:

binarian(A)=pow2(A\[0]) + pow2(A\[1])+ pow2(A\[2]) = pow2(1)+ pow2(5)+ pow2(4) = 2 + 32 + 16 = 50

Write a function:

```java
class Solution{public int solution(int[] A)};
```

that, given an array A consisting of N non-negative integers, returns the length of the shortest array that has the same binarian as array A. For example, given array A such that `[1,0,2,0,0,2]` the function should return 3 because: • the binarian of A is 13

• array B such that B\[0] = 3, B\[1] = 2 and B\[2] = 0 also has a binarian of 13,

• there is no shorter array with a binarian of 13.

Write an efficient algorithm for the following assumptions: • N is an integer within the range \[1..100,000] • each element of array A is an integer within the range\[0..10,000].

***

这题应该就是猛转二进制了吧.. 但是数据太大估计的用bitset

```cpp
const int N = 10100;

class Solution{
public:
    int solution(vector<int>& A)
    {
        bitset<N> f;
        for(int i = 0; i < A.size(); i++)
        {
            int j = A[i];
            bool flag = true;
            while(flag)
            {
                flag = f[j] & flag;
                if(flag)
                    f[j++] = false;
                else
                    f[j++] = true;
            }
        }
        return f.count();
    }
};
```