58同城A卷9/16

t1 数据量很小直接遍历就好了

#include <algorithm>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 计算需要的分数线
     * @param m int整型 晋级和淘汰数量闭区间左值
     * @param n int整型 晋级和淘汰数量闭区间右值
     * @param scores int整型vector 候选项目组分数
     * @return int整型
     */
    int calculate(int m, int n, vector<int>& scores) {
        // write code here
        int k = scores.size();
        sort(scores.begin(), scores.end());
        int i = -1; bool find = false;
        for (i = 0; i <= 1000; i++) {
            int l = upper_bound(scores.begin(), scores.end(), i)-scores.begin();
            int r = k-l;
            if (l >= m && l <= n && r >= m && r <= n) {
                find = true;
                break;
            }
        }
        return find?i:-1;
    }
};

t2 排序后二分，就是在找target，令[target-k, target+k]之间的元素最多，求最多的元素数量，数据量1e5直接爆搜就完事了

#include <algorithm>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @param k int整型 
     * @return int整型
     */
    int maximumScore(vector<int>& nums, int k) {
        // write code here
        int n = nums.size();
        sort(nums.begin(), nums.end());
        int min_num = nums[0];
        int max_num = nums[n-1];
        int res = 1;
        for (int i = min_num; i <= max_num; i++) {
            int l = lower_bound(nums.begin(), nums.end(), i-k)-nums.begin();
            int r = upper_bound(nums.begin(), nums.end(), i+k)-nums.begin();
            res = max(res, r-l);
        } 
        return res;
    }
};

t3 经典dp，对于source每一个位置和pattern每一个位置比较小，如果相等，那就dp[j+1]+=dp[j]，需要注意j=0的时候应该加1，且遍历j的时候应该倒着来，原因同背包dp

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