前言

题目比较简单，dp也是最常规的那种，所以要争取ak啦

第一题

公司正在进行优秀项目组评比的初选工作，评委会已经根据K个项目组提交的材料完成打分，各项目组分数为s1,s2,s3 ......sk。评委组希望设定一个初选晋级分数线x，使得所有得分大于x的项目组晋级，其他淘汰，同时，希望晋级和淘汰的项目组数量都在[m,n]区间。

显然x可能不存在，也可能存在多个x。若不存在则输出-1，若存在多个，则输出满足条件的所有分数线的最小值。

参数取值范围：1<k<30000,1<m<=n<k，0<si<=1000，且k、m、n、si为正整数。

示例1

输入

2,3,[1,2,3,5,6,4]

输出

3

思路与代码

模拟题，如果分数数量不在【m+m，n+n】直接输出-1。将分数排序，根据分数数量输出结果：

1、m+n>=s，证明不及格的人数可以为m人，由于数组是排好序的，所以输出scores[m-1]是及格线最小值

2、n+n>=s，证明不及格的人数不可以为m人，不知道不及格的人数应该为多少，那么就让及格的人数为n，输出scores[s-n-1]就是及格线最小值

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 计算需要的分数线
     * @param m int整型 晋级和淘汰数量闭区间左值
     * @param n int整型 晋级和淘汰数量闭区间右值
     * @param scores int整型vector 候选项目组分数
     * @return int整型
     */
    int calculate(int m, int n, vector<int>& scores) {
        int s=scores.size();
        if(n+n<s || s<m+m) return -1;
        sort(scores.begin(),scores.end());
        if(m+n>=s) return scores[m-1];
        else if(n+n>=s) return scores[s-n-1];
        return -1;
    }
};

第二题

给定一个从0开始的数组nums和一个非负整数k.

在一次操作中，你可以做以下操作:

选择一个之前未选择过的下标i，范围为[0nums.length - 1]。

将nums[i]替换为范围[nums[i] -k,nums[i]+k]内的任意整数 (包含两端)。

在应用任意次数的操作后，返回数组nums的最大可能分数。

数组分数是“数组中最多的重复元素个数”

注意，你只能对每个下标应用一次操作。

示例1

输入

[4,6,1,2],2

输出

3

说明

在这个示例中，我们进行了以下操作:
#选择下标1，将其替换为4(范围为[4,8])，nums =[4,4,12]
#选择下标3，将其替换为4(范国为[0,4])，nums=[4,4,1,4].
应用这些操作后，数组nums的得分为3(由下标0、1和3组成的子序列)。可以证明，3是我们可以达到的最大可能长度。

思路和代码可以替换的数想成区间+1，因此维护一个查分数组，最后看看哪个位置的结果最大，输出即可

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @param k int整型 
     * @return int整型
     */
    int maximumScore(vector<int>& nums, int k) {
        int m=1e5+10;
        vector<int> cha(3*m);
        for(auto &i:nums){
            i+=m;
            int left=i-k;
            int right=i+k+1;
            cha[left]+=1;
            cha[right]-=1;
        }
        int res=0;
        int s=0;
        for(auto &i:cha){
            s+=i;
            res=max(res,s);
        }
        return res;
    }
};

第三题

网络黑色产业链(简称黑产)，是指利用互联网技术实施网络攻击窃取信息、勒索诈骗、盗窃钱财、黄赌毒等的网络违法行为。58同城几乎每时每刻都在遭受黑产攻击，给平台和用户带来巨大的损失。平台在治理黑产中有一环就是对黑产行为序列进行识别。

例如，一个序列可抽象为“AABCCD”，识别模式为“CCD”，由于“CCD”是序“AABCCD”的子序列，则表示模式匹配，即可对黑产账号进行处置。

现在，给你一些序列和识别模式，请你找出该序列有多少个这样的子序列。如果子序列不存在则返回0。

示例1

输入

"ABC""A"

输出

1

思路与代码

这个是比较常见的dp方式，dp[i][j]表示source[0:i]和pattern[0:j]的答案

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param source string字符串 
     * @param pattern string字符串 
     * @return int整型
     */
    int subsequence(string source, string pattern) {
        int n=source.length();
        int m=pattern.length();
        int dp[n+1][m+1];
        memset(dp,0,sizeof dp);
        for(int i=0;i<=n;i++)  dp[i][0]=1;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                dp[i][j]=dp[i-1][j];
                if(source[i-1]==pattern[j-1]){
                    dp[i][j]+=dp[i-1][j-1];
                }
            }
        }
        return dp[n][m];
    }
};