总结
- 没写过函数式编程,十分不习惯
- ( exttt{C})题的( exttt{vector})不会用,像傻子一样看着屏幕不知道该咋办
- 罚时罚了五次,还都是傻逼错误
最后成了一个小小的白银……我真是太菜了!
题解
A 移动字母
题意
给出一个字符串,让你把这个字符串中的小写字母(a)移到字符串的最后
思路
众所周知( exttt{string})是具有可加性的,所以可以新建一个字符串(t)储存新的字符串,并用(cnt)记录(a)的个数,将(s)循环一遍如果(s[i]=='a')就累积到计数器(cnt)中,否则加入(t)串中,然后循环一遍将(cnt)个(a)加到(t)串中,最后输出即可
代码
class Solution {
public:
string change(string s) {
// write code here
int n = s.length();
int cnt = 0;
string t;
for (int i = 0; i < n; i++)
if (s[i] == 'a') cnt++;
else t += s[i];
for (int i = 1; i <= cnt; i++)
t += 'a';
return t;
}
};
B 魔法数字
题意
给出两个数(n,m),有三种操作:
- 当前数加(1)
- 当前数(-1)
- 当前数平方
问(n)最少操作多少次可以变成(m)
思路
广搜
用一个(pair)型的队列,第一维是当前数,第二维是所用的步数
根据题目条件设置三个变量分别为加之后的结果、减之后的结果、平方之后的结果,按照常规广搜思路入队列,根据广搜的性质,最先搜到(m)的次数就是答案,返回即可
代码
class Solution {
public:
int solve(int n, int m) {
queue <pair<int, int> > Q;
int vis[10001], x, y;
memset(vis, 0, sizeof(vis));
Q.push({n, 0}), vis[n] = 1;
while (Q.size()) {
x = Q.front().first, y = Q.front().second;
Q.pop();
if (x == m) return y;
//a加之后的结果,b减之后的结果,c平方之后的结果
int a = x + 1, b = x - 1, c = x * x;
if (a < 1000 && !vis[a]) Q.push({a, y + 1}), vis[a] = 1;
if (b >= 0 && !vis[b]) Q.push({b, y + 1}), vis[b] = 1;
if (c < 1000000 && !vis[c]) Q.push({c, y + 1}), vis[c] = 1;
}
}
};
C 牛妹的春游
题意
给出需要的面包数(n)和饮料数(m)
给出(?)个背包,每个背包中有(p_1)个面包,(p_2)瓶饮料,花费为(p_3)
求最小花费
思路
二维费用背包问题
比赛的时候不会用( exttt{vector})。。。。结束之后发现和数组没啥两样
在题解里看到一个大佬说函数参数是可以改名的……于是改成了(a,b,v)
其实背包的数量就是(v.size())
然后就和(01)背包类似了,选或不选这个背包,优化也一样
但是其实是可以买多的,可能会出现减出负数的情况,这个时候只要对负数体积取(0)即可,表示即使当前需要的饮料/面包小于袋子中的饮料/面包数量依然可以购买
最后返回(f[a][b])即可
代码
class Solution {
public:
int f[2000][2000];
int minCost(int a, int b, vector<vector<int> >& v) {
memset(f, 0x3f, sizeof(f));
f[0][0] = 0;
for (int i = 0; i < v.size(); i++)
for (int j = a; j >= 0; j--)
for (int k = b; k >= 0; k--)
f[j][k] = min(f[j][k], f[max(j - v[i][0], 0)][max(k - v[i][1], 0)] + v[i][2]);
return f[a][b];
}
};