前言
这里记录每日随机刷的错题
两个数组的交集(模拟)
题目描述
题目解析
题目要求返回指定的两个字符串之间的距离,容易想到的一种解法就是暴力遍历,来个双循环,但时间复杂度就为N^2,不符合题意
for()
{ for{}
}
可以借助两个变量来优化暴力解法,prev1来标记str1,prev2来标记str2的下标
for(int i = 0; i < strs.size(); i++)
{遍历到str1就更新prev1,遍历到str2就更新prev2同时求下标之差的最小值
}
这样一个循环就可以搞定
代码如下
#include <iostream>
#include <vector>
#include <limits.h>
using namespace std;int main()
{int prev1 = -1, prev2 = -1;int ret = INT_MAX;int n = 0;string str1, str2;vector<string> strs(n);cin >> n;cin >> str1 >> str2;for(int i = 0; i < n; i++){cin >> strs[i];}for(int i = 0; i < n; i++){if(strs[i] == str1) {prev1 = i;if(prev2 != -1) ret = min(ret, abs(prev2 - prev1));}if(strs[i] == str2) {prev2 = i;if(prev1 != -1) ret = min(ret, abs(prev2 - prev1));}}if(prev1 == -1 || prev2 == -1) cout << -1 << endl;else cout << ret << endl;return 0;
}
最小花费爬楼梯(小动态规划)
题目描述
题目解析
很典型的一道动态规划的题目,但是要注意理解题意
cost[i] 是爬第 i 个台阶所需要的费用
可以选择从第 0 个台阶 或 第 1 个台阶开始(dp[0] = 0,dp[1] = 0)
楼顶:根据示例的说明来看(你将从下标为1的台阶开始,向上爬两个台阶走到楼顶)
[2, 5(下标为1), 20,楼顶]
代码如下
#include <iostream>
#include <vector>
using namespace std;int main()
{int n = 0;cin >> n;vector<int> cost(n);vector<int> dp(n + 1, 0); //开辟n + 1,下标索引0 ~ nfor(int i = 0; i <= n; i++){cin >> cost[i];}for(int i = 2; i <= n; i++){dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);}cout << dp[n] << endl;return 0;
}
数字统计(数学、模拟)
题目描述
题目解析
利用取模求尾部数字
while(tmp)
{if(tmp % 10 == 2) ret++;tmp /= 10;
}
代码如下
#include <iostream>
using namespace std;int main()
{int L, R;int ret;cin >> L >> R;for(int i = L; i <= R; i++){int tmp = i;while(tmp){if(tmp % 10 == 2) ret++;tmp /= 10;}}cout << ret << endl;return 0;
}
// 64 位输出请用 printf("%lld")