今日学习记录
1. 跳跃游戏 9leetcode.3660
关键词：动态规划
问题分析：
- i<j,大换小
- j<i,小换大
- 要尽量换大,可以大换小之后换更大
核心思路
- 有两种换法,首先从后面开始小换大,都是符合题目的,其次从前面开始大换小再换大,感觉操作好麻烦,要换两次,那么我能不能先从后面开始,把小的都换成大的呢,换成大的之后,前面大的再跟小的一换不就直接成最大的了吗.
- 可能最麻烦的就是大换小再换大这部分麻烦,但我们想想以下例子,数据一定是按照我给出例子分成三部分,一部分是让我们烦恼的要进行二次交换的,第二部分是最大值,第三部分是最小值,除此分布之外就只需要交换一次,非常容易
- {2,3,1,1,1,1,1,1},后面的 1 可以全换成 3,只要是小于 3 的都可以换成最大值,而且只要有一个数满足小于我们要换的 2,那么就可以把 2 换成 1 再换 3,这里任意数,那么肯定取最小的数喽
- {2,1,1,1,1,1,3},只要这个最大值不在后面的最小值到前面的目标值中间,那么就无法换,只能是 2
- 那么答案显然易见了,首先先预处理每个位子前的最大值(pre_max),从后面开始遍历,求后缀的最小值(suf_min),你想想既然按照我给出的分布,那么当要换的时候 2 是不是就等于 3,也就是 ans{i} == ans{i+1},所以状态方程为
- ans(i) = pre_max(i)当 pre_max<=suf_min;ans(i) = ans(i+1),当 pre_max>suf_min;
**最终代码：
vector<int> maxValue(vector<int>& nums) {
int n = nums.size();
vector<int> pre_max(n);
pre_max[0] = nums[0];
for(int i = 1;i<n;i++){
pre_max[i] = max(pre_max[i-1],nums[i]);
}
vector<int> ans(n);
int suf_min = INT_MAX;
for(int i = n-1;i>=0;i--){
ans[i] = pre_max[i]<=suf_min?pre_max[i]:ans[i+1];
suf_min = min(suf_min,nums[i]);
}
return ans;
}学到的点：
- 感觉就是个思维题
今周收获
进步还是挺明显的,不过系统性的学习的效率比我想的慢多了,因为比我想象中要难要繁琐,手写几遍不同版本的数据结构真的好累,加油把,还有练习时间太长了,题目太多了,我不应该集中时间做,应该以后有时间分散做,这样有利用我复习,回忆
竞赛当队长了!
说实话我挺想当队长的,不是因为得奖获益最大,而是我感觉我也想培养团队合作能力,我之前总想着提升个人能力,但个人能力固然重要,可后续的比赛都是团队比赛,个人的力量终究不行,所以我还是要刻意历练一下自己,虽然但是,我还是希望有人能带我打比赛,这样不知道轻松多少,下半年要做的事太多了,四级,算法竞赛,人工智能算法大赛,离散数学,统计概率,我还是挺忙的,我们队三个人都是小白,T-T