C/C++每日一练11

1.买卖股票的最好时机二给定数组prices代表每日股价可以多次买卖股票规则不能同时持有多只股票必须卖出后才能再次买入同一天可以先卖再买求能获得最大利润示例 1plaintextprices [7,1,5,3,6,4] 收益(5-1)(6-3) 43 7示例 2plaintextprices[1,2,3,4,5] 收益(2-1)(3-2)(4-3)(5-4)4 等价 5-1核心思路贪心只要后一天股价 前一天就进行一次交易累加差价。 原理上涨区间拆分成连续小段买卖总收益不变。 例如1,3,5(3-1)(5-3) 5-1公式\(ans\sum_{i1}^{n-1}\max(0,\ prices[i]-prices[i-1])\)C AC 代码cpp运行#include iostream #include vector #include algorithm using namespace std; int maxProfit(vectorint prices) { int profit 0; for(int i 1; i prices.size(); i){ profit max(0, prices[i] - prices[i-1]); } return profit; } int main() { int n; cin n; vectorint p(n); for(int i 0; i n; i){ cin p[i]; } cout maxProfit(p) endl; return 0; }复杂度时间 \(O(n)\)空间 \(O(1)\)补充动态规划写法拓展面试常问dp [i][0]第 i 天不持有股票最大利润 dp [i][1]第 i 天持有股票最大利润 转移方程plaintextdp[i][0] max(dp[i-1][0], dp[i-1][1] prices[i]); dp[i][1] max(dp[i-1][1], dp[i-1][0] - prices[i]);DP 完整代码cpp运行int maxProfit(vectorint prices) { int n prices.size(); int dp0 0; // 不持有 int dp1 -prices[0]; // 持有 for(int i 1; i n; i){ int new_dp0 max(dp0, dp1 prices[i]); int new_dp1 max(dp1, dp0 - prices[i]); dp0 new_dp0; dp1 new_dp1; } return dp0; }⚠️区分两道股票题买卖股票最好时机一最多交易 1 次→ 维护最小值买卖股票最好时机二无限次交易→ 贪心累加正向差价2.倒置字符串题意将一句话的单词进行倒置标点不倒置。 例如输入I like beijing.输出beijing. like I注意是单词逆序不是每个单词内部字母翻转思路两种写法方法 1利用栈 /vector 存单词最简单笔试首选持续读取单词存入容器倒序输出空格隔开方法 2原地字符串翻转面试进阶考点整个字符串全部反转逐个单词内部再反转I like beijing.整体翻转 →.gnijieb ekil I单词逐个翻转 →beijing. like I写法 1 简易 AC 代码牛客直接过cpp运行#include iostream #include vector #include string using namespace std; int main() { string s; vectorstring vec; // 循环读取单词自动以空格分割 while (cin s) { vec.push_back(s); } // 倒序输出 for (int i vec.size() - 1; i 0; i--) { if(i ! vec.size()-1) cout ; cout vec[i]; } return 0; }写法 2 原地翻转面试常考不使用额外容器cpp运行#include iostream #include algorithm #include string using namespace std; int main() { string str; // getline读取整行包含空格 getline(cin, str); reverse(str.begin(), str.end()); int l 0; int n str.size(); for (int r 0; r n; r) { // 遇到空格或者末尾翻转[l,r)区间单词 if (r n || str[r] ) { reverse(str.begin() l, str.begin() r); l r 1; } } cout str endl; return 0; }⚠️重要坑点cin 字符串遇到空格停止读取 ** 整行带空格字符串必须用 getline如果混用 cin 和 getline需要吸收换行符cin.ignore()区分两种题型倒置字符串单词I am cat→cat am I本题反转整个字符串字符abc→cba另一简单题测试样例 输入plaintextI like beijing.输出plaintextbeijing. like I3.删除公共字符题目描述输入两个字符串从第一字符串中删除第二个字符串中所有的字符。 示例 输入plaintextThey are students. aeiou输出plaintextThy r stdnts.思路使用哈希数组ASCII 0~127标记第二个字符串出现过的字符遍历第一个字符串如果字符没有被标记保留否则丢弃优势时间复杂度 O (nm)不用嵌套循环效率高C AC 代码笔试推荐cpp运行#include iostream #include string using namespace std; int main() { string s1, s2; getline(cin, s1); getline(cin, s2); bool vis[128] {false}; // 标记s2所有字符 for (char c : s2) { vis[(unsigned char)c] true; } string ans; for (char c : s1) { if (!vis[(unsigned char)c]) { ans c; } } cout ans endl; return 0; }⚠️关键易错点必须用 getline字符串包含空格不要混用cin 和 getline会遗留换行导致读空大小写区分A和a视为不同字符题目默认区分数组开 128 覆盖全部标准 ASCII 字符简易逻辑流程演示s1 They are students.s2 aeiou标记 a,e,i,o,u 遍历 s1遇到这五个字符直接跳过其余拼接输出拓展低效写法不推荐双层循环会超时cpp运行// 暴力O(n*m)大数据不建议 for(auto c : s1){ bool flag true; for(auto ch : s2){ if(c ch) flag false; } if(flag) ans c; }谢谢