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];
    }
};

#58##58笔试#
全部评论
佬,你有收到面试通知吗
点赞 回复 分享
发布于 2023-09-18 14:20 湖北
请问第二题的思路是怎么样的啊,我没看明白,求指教!!!!谢谢。我也是暴力做的,不过是借助map统计了每个数的出现次数,然后取最大。
点赞 回复 分享
发布于 2023-09-17 09:56 上海
佬,投的什么方向
点赞 回复 分享
发布于 2023-09-16 22:37 湖北

相关推荐

不愿透露姓名的神秘牛友
06-25 20:45
点赞 评论 收藏
分享
点赞 评论 收藏
分享
评论
1
6
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务