每日一题 | 42接雨水 和 1218最长定差子序列
2021/11/5 23:12:59
本文主要是介绍每日一题 | 42接雨水 和 1218最长定差子序列,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
42. 接雨水(I、II。掌握这种思想)
思路:暴力(超时)
- 能接到的雨水总量
sum
,是每一列雨水f(i)
的和 - 而
f(i)
又是每一列最多能接的雨水capable
, 与 该列的柱子高度height[i]
的差 capable
根据短板效应,属于 i 左边的最大值lheight
与 右边的最大值rheight
的最小值
所以综合一下得到 sum( min(lheght, rheight) - height[i] ) (1 < i < height.size()-1)
class Solution { public: int trap(vector<int>& height) { int sum = 0; // 遍历每一列 for(int i = 0; i < height.size(); i++) { // 跳过第一列和最后一列 if(i == 0 || i == height.size()-1) continue; // 用两个变量分别记录左右两侧的最大值 int lheight = 0; int rheight = 0; // 求左侧最大值 for(int j = 0; j < i; j++) { if(height[j] > lheight) lheight = height[j]; } // 求右侧最大值 for(int j = i+1; j < height.size(); j++) { if(height[j] > rheight) rheight = height[j]; } // 得到当前i列能接到的雨水 int cur = min(lheight, rheight) - height[i]; // 累加到sum中 if(cur > 0) sum += cur; } return sum; } };
思路:动态规划
与上种解法有所不同,此处利用两个 vector 容器记录对应每个 i 值的 lheight 和 rheight ,最后累积相加即可。
class Solution { public: int trap(vector<int>& height) { // 处理边界 if(height.size() <= 2) return 0; // 两个维护左右侧最大柱高的容器 vector<int> lmax(height.size(), 0); vector<int> rmax(height.size(), 0); int len = rmax.size(); // 先遍历一次记录左侧最大柱高的容器 lmax[0] = height[0]; for(int i = 1; i < len; i++) { lmax[i] = max(height[i], lmax[i-1]); } // 先遍历一次记录右侧最大柱高的容器 rmax[len - 1] = height[len - 1]; for(int i = len-2; i >= 0; i--) { rmax[i] = max(height[i], rmax[i+1]); } // 遍历全部,累计相加 int sum = 0; for(int i = 0; i < len; i++) { int cur = min(lmax[i], rmax[i]) - height[i]; if(cur > 0) sum += cur; } return sum; } };
- 76.05%
- 11.97%
1218. 最长定差子序列(这题很绝,代码短而精)
思路:动态规划
参考了官方题解,解法非常巧妙。首先利用了动态规划的思想,从左往右遍历整个数组,并建立一个辅助数组v。
- 当遍历到 i 时,就根据
v[i - difference]
的内容来更新v[i]
的值。
arr = [ 1,2,4,3,5,8,7,5,1 ],difference = 2 可以手动测试一下,就知道这一句话实现了什么内容
class Solution { public: int longestSubsequence(vector<int> &arr, int difference) { int res = 0; // 此处辅助数组的建立要多加注意! unordered_map<int, int> map; for(auto i : arr) { map[i] = map[i-difference] + 1; res = max(res, map[i]); } return res; } };
- 88.68%
- 52.83%
关于辅助数组的建立:
由于上述代码的关键句会涉及到访问未初始化的数组成员,因此如果用:
vector<int> v
来接收和计算此题,一定会报错!
而 map 使用 [] 符号取值时,当 key 不存在时,c++ 会利用该 key 及默认构造的 value,组成一个{key, value}
对,插入 map 中,即将该 key 对应的 value 初始化为 0,所以访问不存在的元素时不会出错。
这篇关于每日一题 | 42接雨水 和 1218最长定差子序列的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-02springboot项目无法注册到nacos-icode9专业技术文章分享
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)