笔试——Day42

第一题

题目

最大差值

思路

模拟
遍历数组，维护a[i]之前的最小值

代码

class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param A int整型vector * @param n int整型 * @return int整型*/int getDis(vector<int>& a, int n) {// write code hereint minPrev = a[0];int res = 0;for(int i = 1; i < n; i++){minPrev = min(minPrev, a[i]);res = max(res, a[i] - minPrev);}return res;}
};

第二题

题目

兑换零钱

思路

动态规划

代码

// https://www.nowcoder.com/practice/67b93e5d5b85442eb950b89c8b77bc72?tpId=230&tqId=40432&ru=/exam/oj
#include <iostream>
#include <cstring>
using namespace std;const int N = 10010;
const int M = 5010;int a[N];
int dp[M];
int n, aim;int main()
{cin >> n >> aim;for(int i = 1; i <= n; i++) cin >> a[i];memset(dp, 0x3f, sizeof dp);// dp[i][j]：从前i个纸币中挑选，正好总和为j，此时的最少张数  // 不选a[i]：dp[i][j] = dp[i - 1][j]// 选1个a[i]  ：dp[i][j] = dp[i - 1][j - a[i]] + 1// 选2个a[i]  : dp[i][j] = dp[i - 1][j - 2 * a[i]] + 2// ...// dp[i][j] = dp[i][j - a[i]] + 1// dp[i][j] = min(dp[i - 1][j], dp[i][j - a[i]] + 1)dp[0] = 0; // 0张纸币凑成0元for(int i = 1; i <= n; i++){for(int j = a[i]; j <= aim; j++){dp[j] = min(dp[j], dp[j - a[i]] + 1);}}if(dp[aim] >= 0x3f) cout << -1 << endl;else cout << dp[aim] << endl;return 0;
}

第三题

题目

小红的子串

思路

滑动窗口

代码

// https://ac.nowcoder.com/acm/problem/260770
#include <iostream>using namespace std;int n, l, r;
string s;long long find(int x)
{if(x == 0) return 0;int hash[26] = {0};int left = 0, right = 0;long long res = 0;int kind = 0;while(right < n){if(hash[s[right] - 'a']++ == 0) kind++;while(kind > x){hash[s[left] - 'a']--;if(hash[s[left] - 'a'] == 0) kind--;left++;}res += right - left + 1;right++;}return res;
}int main()
{cin >> n >> l >> r >> s;cout << find(r) - find(l - 1) << endl;return 0;
}