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笔试#