2.28场

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 然后枚举中间点找最大值

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

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 后来发现这个问题可以拆分成 枚举每个和出现的所有区间 然后计算最大不相交区间个数

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

#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:

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

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();
    }
};

3.05场

01 - 编程题01

这题还有中文哈哈哈 还是看看英文吧

You are a programmer in a scientific team doing research into particles. As an experiment, you have measured the position of a single particle in N equally distributed moments of time.
The measurement made in moment K is recorded in array A as A[K].

Now, your job is to count all the periods of time when the movement of the particle was stable.

Those are the periods during which the particle doesn’t change its velocity: i.e. the difference between any two consecutive position measurements remains the same. Note that you need at least three measurements to be sure that the particle didn’t change its velocity. For example:

• 1, 3, 5, 7, 9 is stable (velocity is 2)
• 7, 7, 7, 7 is stable (particle stays in place)
• 3, -1, -5, -9 is stable (velocity is -4)
• 0, 1 is not stable (you need at least three measurements)
• 1, 1, 2, 5, 7 is not stable (velocity changes between measurements)

More formally, your task is to find all the periods of time A[P],A[P+1], …,A[Q] (of length at least 3) during which the movement of the particle is stable. Note that some periods of time might be contained in others (see example test).

Write a function:
class Solution { public int solution(int[] A};

that, given array A consisting of N integers representing the results of the measurements, returns the number of periods of time when the movement of the particle was stable. The function should return -1 if the result exceeds 1,000,000,000.
Examples: Given array A = [-1, 1, 3, 3, 3, 2, 3, 2, 1, 0] the function should return 5, because there are five periods during which the movement of the particle is stable, namely: (0, 2), (2, 4), (6, 9), (6, 8) and (7, 9). Note that the last two periods are contained by (6, 9).

Assume that
• N is an integer within the range [0..100];

• each element of array A is an integer within the range [-1,000,000,000..1,000,000,000].

In your solution, focus on correctness. The performance of your solution will not be the focus of the assessment.

这题我以为是签到题了 看来后面还有更签到的

这题解法多啦 总的来说就是计数DP 找到等差数列的数量

状态：f[i]表示以A[i]结尾的等差数列个数

f[i] = f[i - 1] + 1; f[i - 1] 就是之前接上A[i]的个数 1就是（A[i-2], A[i-1], A[i])

举个例子： 1 2 3 4 -> 5; f[4] = 2([2,3,4], [1,2,3,4]) , f[5] = 3([3,4,5], [2,3,4,5],[1,2,3,4,5])

当然空间可以优化成o(1)

class Solution
{
public:
    int solution(vector<int>& A)
    {
        int n = A.size();
        vector<int> A(n + 1);
        int res = 0, f = 0;
        for(int i = 2; i < n; i++)
        {
            if(A[i] - A[i - 1] == A[i - 1] - A[i - 2])
                f = f + 1;
            else f = 0;
            res += f;
        }
        return res;
    }
};

02 - 编程题02

You are given an array A consisting of N integers within the range [1..N].
In one move, you can increase or decrease the value of anyone by 1. After each move, all numbers should remain within the range [1..N].

our task is to find the smallest required number of moves to make all elements in the array pairwise distinct (i.e. no value can appear in the array more than once).
Write a function:

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

That, given an array A consisting of N integers, returns the smallest number of moves required to make all elements in the array •airwise distinct. If the result is greater than 1,000,000,000, the function should return -1.

examples:

1. Given A = [1, 2, 1], the function should return 2, because you can increase A[2] twice: [1, 2, 1] -> [1, 2, 2] -> [1, 2, 3].
   In this example, ou could also change the array to the following values in two moves: [3, 2, 1], [1, 3, 2], [2, 3, 1].
2. Given A = [2, 1, 4, 4], the function should return 1, as it is sufficient to decrease A[2] or A[3] by 1, resulting in [2, 1, 3, 4] or [2, 1, 4, 3].
3. Given A = [6, 2, 3, 5, 6, 3], the function should return 4, because you can achieve the following array in four moves: [6, 2, 1, 5, 4, 3].

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

这题想不明白有一个测试点过不去🆘

很直接了 从小到大排序 计算到 [1,2,3,4, ... N]的距离就好了

class Solution
{
public:
    int solution(vector<int>& A)
    {
        sort(A.begin(), A.end());
        int res = 0;
        for(int i = 1; i <= A.size(); i++)
            res += abs(A[i] - i);
        return res;
    }
}

03 - 编程题03

You are given N fractions. Fractions are represented as two arrays, X and Y of length N, containing the fraction numerators and denominators respectively.
Write a function solution that, given such arrays X and Y of length N, returns the number of possible ways to choose a pair of ractions that sum up to 1.

Since the answer can be large, provide it modold 10^9 + 7 (1,000,000,007). Note that a single fraction can orm multiple pairs.

Examples:

1. Given X = [1, 1, 2], Y = [3, 2, 3], the function should return 1. The input represents fractions 1/3,1/2, 2/3, and the only pair that sums up to 1 is (1/3, 2/3)
2. Given X = [1, 1,1], Y = [2, 2, 2], the function should return 3. The input represents 1/2,1/2,1/2. There are three ways to choose a pair hat sums up to 1.
3. Given X = [1, 2, 3, 1, 2, 12, 8, 4], Y = [5, 10, 15, 2, 4, 15, 10, 5], the function should return 10.

Write an efficient algorithm for the following assumptions

• N is an integer within the range [0..100,000];
• each element of arrays X, Y is an integer within the range [1..1,000,000,000].

这题Leetcode第一题的化身啊哈哈哈 用哈希表存target - A[i]出现的次数即可

这里难一点的地方无非在分数的化简和pair不能哈希上面，都比较好解决；

using ULL = unsigned long long;
const int mod = 1e9 + 7;
class Solution{
public:
    int gcd(int a, int b)
    {
        return b ? gcd(b, a % b) : a;
    }
    ULL hash_func(int a, int b)
    {
        return a * 1000000001 + b;
    }
    int solution(vector<int>& X, vector<int>& Y)
    {
        unordered_map<ULL, int> hash;
        int res = 0;
        for(int i = 0; i < X.size(); i++)
        {
            int a = X[i], b = Y[i], ab = gcd(a, b);
            ULL query = hash_func(b / ab - a / ab, b / ab), cur = hash_func(a / ab, b / ab);
            if(hash.count(query))
                res = (res + hash[query]) % mod;
            hash[cur]++;
        }
        return res;
    }
}