阿里云上怎么做网页网站,整站优化关键词排名,网站备案座机,郑州最好的男科医院哪家好C日常刷题积累 今日刷题汇总 - day0181、压缩字符串(一)1.1、题目1.2、思路1.3、程序实现 2、chika和蜜柑2.1、题目2.2、思路2.3、程序实现 3、 01背包3.1、题目3.2、思路3.3、程序实现 -- dp 4、题目链接 今日刷题汇总 - day018
1、压缩字符串(一)
1.1、题目 1.2、思路
读完… C日常刷题积累 今日刷题汇总 - day0181、压缩字符串(一)1.1、题目1.2、思路1.3、程序实现 2、chika和蜜柑2.1、题目2.2、思路2.3、程序实现 3、 01背包3.1、题目3.2、思路3.3、程序实现 -- dp 4、题目链接 今日刷题汇总 - day018
1、压缩字符串(一)
1.1、题目 1.2、思路
读完题知道让处理一组英文字符串完成压缩功能压缩规则满足保持字符串的顺序将多余相邻的字符压缩以数字字符表示当前被压缩的字母个数其中注意如果只有一个字符1不用写。通过分析示例和题目规则想到蛮力法遍历字符串利用一个新字符串retstr接收遇到的字母进行尾插统计相邻字母的个数到count中然后转字符串尾插在字母后然后处理重复的字母直接count次不作任何处理知道遇见下一个不同字母即可然后count小于1也不用管直到遍历结束即可。接下来就是程序实现。
1.3、程序实现
按照思路分析完成程序即可。主要在于处理一些细节如边界控制相同的直接统计个数和让遍历的下标然后处理大于1的个数尾插使用to_string(count)另外需要重置计数器为1才进入下次循环。
class Solution {
public: string compressString(string param) { string retstr; int count 1; for (int i 0; i param.size(); i){ while (i 1 param.size() param[i 1] param[i]){ count; i; } retstr param[i]; if (count 1) { retstr to_string(count); } count 1; // 重置计数器 } return retstr; }
};2、chika和蜜柑
2.1、题目 2.2、思路
读完题想到跟上次比那名居的桃子类似但是这里并没有限制持续时间等条件这里是任意挑选k不使用滑动窗口所以利用排序的思想将每个橘⼦按照甜度由⾼到低排序相同甜度的橘⼦按照酸度由低到⾼排序。满足尽可能地甜度高。然后提取排序后的前k个橘⼦就得到最好地选择方案了。那么接下来就是程序实现。
2.3、程序实现
首先按照题目要求完成输入n,k代表蜜柑总数和chika吃的蜜柑数量然后这里为了方便描述甜度和酸度这里使用pair然后就可以输入数组arr中即可。
#include iostream
#include algorithmusing namespace std;
const int N 2e5 10;
typedef pairint, int PII; // 酸度甜度
PII arr[N];int main()
{int n, k;cin n k;for(int i 0; i n; i) cin arr[i].first;for(int i 0; i n; i) cin arr[i].second;//sort//求前k个蜜柑甜度和酸度和return 0;
}接下来就是排序地思路需要满足题目中尽可能地甜和不酸那么这里可以采用lambda表达式与sort结合的方式处理即可。lambda实际上可以理解为仿函数使其sort的执行逻辑更加方便了。 [] 表示捕获列表这里使用 表示捕获外部作用域中所有变量的引用。但在这个 lambda 表达式中实际并没有使用到外部变量所以 []不捕获任何变量或 [] 都是可以的。 (const PII a, const PII b) 是 lambda 表达式的参数列表表示这个函数对象接受两个 PII 类型的常量引用作为参数。 函数体 {} 中定义了比较逻辑首先比较两个元素的甜度a.second 和 b.second如果甜度不同则甜度较大的元素被认为更大这里使用了 意味着排序后甜度是降序的。如果甜度相同则比较酸度酸度较小的元素被认为更大这里使用了 但注意这是为了保持甜度相同时的稳定性实际上排序的主要依据是甜度。 sort(arr, arr n, [](const PII a, const PII b){if(a.second ! b.second) return a.second b.second;else return a.first b.first;});否则不然就自己单独再封装一个比较逻辑的函数回调到sort也行一样的所以综合考虑lambda这里会更好。也是处理类似逻辑比较常用的方法之一。
// 自定义比较函数
bool compare(const PII a, const PII b) { if (a.second ! b.second) { return a.second b.second; // 甜度降序 } else { return a.first b.first; // 甜度相同时酸度升序 }
} // 使用自定义比较函数进行排序
sort(arr, arr n, compare);除此之外对于自定义封装的函数又恰好是比较元组类型的值可以使用tie的逻辑实现但是要清楚比较对象之间的关系。 注意包含头文件#include tuple // 对于 std::tie // 自定义比较函数
bool compare(const PII a, const PII b) { return tie(b.second, a.first) tie(a.second, b.first); // 注意这里的 b.second 和 a.first 是为了得到甜度降序酸度相同则酸度升序的效果 // 但实际上对于这种情况更直观的方式直接比较定义更具有阅读性
}
// 使用自定义比较函数进行排序
sort(arr, arr n, compare);最后遍历前k个蜜柑获取甜度和酸度和然后按照题目要求的格式输出即可。
#include iostream
#include algorithmusing namespace std;
const int N 2e5 10;
typedef pairint, int PII; // 酸度甜度
PII arr[N];int main()
{int n, k;cin n k;for(int i 0; i n; i) cin arr[i].first;for(int i 0; i n; i) cin arr[i].second;sort(arr, arr n, [](const PII a, const PII b){if(a.second ! b.second) return a.second b.second;else return a.first b.first;});long long s 0, t 0;for(int i 0; i k; i){s arr[i].first;t arr[i].second;}cout s t endl;return 0;
}3、 01背包
0/1背包详解参考
3.1、题目 3.2、思路
读完题知道0/1背包问题是算法课的经典题型了通常涉及贪心和dp动态规划法简单说就是尽可能让包不超重情况下装最多的物品。所以这里分析题目和示例得知采用动态规划法分析状态表示和状态转移方程。 状态表示dp[i][j]表示从前 i 个物品中挑选总体积不超过 j 的情况下最⼤重量是多少。 推导状态转移方程根据「最后⼀步」的状况需要分情况讨论 (1)、当第i个物品不被选时就是i-1个物品中挑选且体积不超过j此时满足dp[i][j] d[i-1][j]; (2)、当选择第i 个物品时那么就只能去前i - 1 个物品中挑选总体积不超过j - v[i]的物品。此时dp[i][j] dp[i - 1][j - v[i]] w[i] 。但是这种状态不⼀定存在因此需要特判⼀下。 综上所述 状态转移⽅程为 dp[i][j] max(dp[i - 1][j], dp[i - 1][j - v[i]] w[i]) 那么接下来就是程序实现。
3.3、程序实现 – dp
首先题目已经给了几个参数 int V 表示背包的最大容量。 int n 表示物品的数量。 vectorvector vw 是一个二维向量其中vw[i][0]表示第i个物品的重量vw[i][1]表示第i个物品的价值。 然后按照思路分析的需求定义dp数组然后在内层循环中依次放入物品对于每个容量j如果当前容量j大于等于当前物品的重量vw[i][0]则有两种选择 1.不装入当前物品此时背包的价值为dp[j]即前i-1个物品在容量j下的最大价值。 2.装入当前物品此时背包的价值为dp[j - vw[i][0]] vw[i][1]即前i-1个物品在容量j - vw[i][0]下的最大价值加上当前物品的价值。 使用max函数比较这两种选择取较大值作为dp[j]的值即dp[j] max(dp[j], dp[j - vw[i][0]] vw[i][1]);。 最终dp[V]存储的就是在背包容量为V时能够装载的最大价值将其作为函数的返回值。
class Solution {public:int dp[1010] { 0 };int knapsack(int V, int n, vectorvectorint vw) {for (int i 0; i n; i){for (int j V; j vw[i][0]; j--){dp[j] max(dp[j], dp[j - vw[i][0]] vw[i][1]);}}return dp[V];}
};4、题目链接
压缩字符串(一) chika和蜜柑 01背包
