目录
1.最大差值
因为b >= a,所以可以在遍历数组的时候更新所遍历到的最小值以及返回值即可
class Solution {
public:
int getDis(vector<int>& A, int n) {
int ret = -0x3f3f3f3f;
int l = 0, r = l + 1;
while (r < n) {
ret = max(A[r] - A[l], ret);
if (A[r] < A[l]) {
l = r;
}
r++;
}
return ret < 0 ? 0 : ret;
}
};
2.兑换零钱
链接https://www.nowcoder.com/practice/67b93e5d5b85442eb950b89c8b77bc72?tpId=230&tqId=40432&ru=/exam/oj
每个值代表一种面值的货币,每种面值的货币可以使用任意张
根据题意,可以分析出这是一道完全背包类型的题目:
直接分析状态转移方程和注意初始化的细节即可
#include <cstring>
#include <iostream>
using namespace std;
const int N = 10010;
int w[N];
int dp[5010];
int n, aim;
int main()
{
cin >> n >> aim;
for(int i = 1; i <= n; ++i)
cin >> w[i];
memset(dp, 0x3f3f3f3f, sizeof dp);
dp[0] = 0;
for(int i = 1; i <= n; ++i)
{
for(int j = w[i]; j <= aim; ++j)
{
dp[j] = min(dp[j], dp[j - w[i]] + 1);
}
}
cout << (dp[aim] == 0x3f3f3f3f ? -1 : dp[aim]) << endl;
return 0;
}
3.小红的子串
链接https://ac.nowcoder.com/acm/problem/260770
若种类的范围为 【1,x】的话,则满足条件的数组区间内方案数则为 right - left + 1,因此可以将种类范围想办法变为【1,x】,最后用【1,r】 - 【1,l】即可
滑动窗口遍历数组:(数据范围过大,注意开long long)
#include <iostream>
#include <cstring>
#define int long long
using namespace std;
int n, l, r;
char s[200010];
int find(int x)
{
if(x == 0)
return 0;
int cnt[26] = { 0 };
int kind = 0, ret = 0;
int L = 1, R = 1;
while(R <= n)
{
if(cnt[s[R] - 'a']++ == 0)
kind++;
while(kind > x)
{
if(cnt[s[L++] - 'a']-- == 1)
kind--;
}
ret += R - L + 1;
R++;
}
return ret;
}
signed main()
{
cin >> n >> l >> r;
for(int i = 1; i <= n; ++i)
cin >> s[i];
cout << find(r) - find(l - 1) << endl;
return 0;
}