想做一个网站平台怎么做的,网站百度排名优化,做网站好看的旅行背景图片,网站ico图标放在哪里文章目录 引言复习单调队列优化——最大子序列和思路分析实现代码参考实现 背包问题——宠物小精灵的收服问题个人实现参考实现 新作两两交换链表中的节点个人实现参考实现 删除有序数组中的重复项个人实现知识补全迭代器的访问和控制vector删除特定的元素erasevector底层删除元… 文章目录 引言复习单调队列优化——最大子序列和思路分析实现代码参考实现 背包问题——宠物小精灵的收服问题个人实现参考实现 新作两两交换链表中的节点个人实现参考实现 删除有序数组中的重复项个人实现知识补全迭代器的访问和控制vector删除特定的元素erasevector底层删除元素的原理是什么 实现思路 总结 引言
今天早上起的刚好挺早的书也背了继续开始复习。动态规划的章节继续完成。
复习
单调队列优化——最大子序列和
第一次的理论推理第二次代码推理
思路分析
这个题目是在长度为n的整数序列找出长度不超过m的连续子序列最直白的做法就是的枚举起点然后在遍历终点。现在转换为找在范围m内移动坐标点使得该坐标点的累加和最小为了一个单调递增队列实现。
下面分析知道问题转换部分都是确定的但是后续部分就有点不确定了参考一下就行感觉有点硬往单调队列上车扯 实现代码
#include iostreamusing namespace std;
const int N 300010,M 300010;
int s[N],q[N];
int n,m; // n是队列元素个数m是维系的m个队列int main(){cinnm;// 维系累加和队列for (int i 1; i n; i) {cins[i];s[i] s[i - 1];}// 计算单调最优队列int res INT_MIN;int l 0,r 0;for (int i 1; i n; i) {// 判定队列是否超过了当前的边界只if (l i i - q[l] m) l ;res max(res,s[i] - s[q[l]]);// 更新最右端队列的边界值// 右指针移动的时候是如何进行比较的int t q[r] 1;// 保证队列的右指针始终在左指针旁边while (r l s[q[r]] s[t]) r--;q[r] t;}coutres;}问题
在实现中不知道单调递增队列应该如何和右指针进行比较所以迭代的细节不是很清楚。我以为的迭代过程是在i-m到i之内结果不对或者说过程不对如果抛开的m这个边界不说那就是直接找s[i]的最小值的也就是的往后遍历即可。我这里是遍历到的q[r]右边的一个元素和那个差不多。因为在i不断增加的过程中实际上就已经控制了边界每一次都是遍历到i那么在i为i-1的时候其实就已经遍历过对应的值了。
参考实现
#include iostream
#include limits.h
using namespace std;typedef long long LL;
const int N 300010;
int q[N],s[N];
int n,m;int main(){cinnm;for (int i 1; i n ; i) {cins[i];s[i] s[i - 1];}// 创建对应的队列int hh 0,tt 0,res INT_MIN;q[hh] 0;for (int i 1; i n; i) {// 保证队列的长度不变if (i - q[hh] m) hh;// 计算最值res max(res , s[i] - s[q[hh]]);// 更新的队列尾部// 队列可为空也就是tt hh// 然后就是保证队列是单调递增的,如果出现新的值小于后续的值// 就要将所有比之大的数据排除因为是一个序列一定会选中这个数据while(tt hh s[q[tt]] s[i]) tt --;// 移动到一个小于或者等于的数字之后tt再往后移动一个即将新的排序值加入其中。q[tt] i;}coutres;
}背包问题——宠物小精灵的收服问题
第一次做的链接上一次大概看了一遍是一个二维背包问题但是二维背包问题怎么做还有点不清楚的。应该是两个维度基本上所有的状态分析都是对的。
个人实现
#include iostreamusing namespace std;const int N 10010,M 510,K 110; // N精灵球的数量M皮卡丘的初始体力值K是野生小精灵的数量
int n,m,k;
int f[K][N][M];
int mt[K],nt[K];int main(){cinnmk;for (int i 0; i k; i) {cinnt[i]mt[i];// 分别记录收服每一个小精灵的数量、损耗的体力值}// 动态规划方程// 初始值的问题for (int i 0; i k; i) {for (int j 0; j m; j) {// 遍历对应皮神的体力值for (int l 0; l n; l) {// 遍历手上剩余的精灵球的数量// 主要是两种情况分别是抓或者不抓if (i - 1 0 j - mt[i] 0 l - nt[i] 0)f[i][j][l] max(f[i - 1][j][l],f[i - 1][j - mt[i]][l - nt[i]] 1);}}}// 现在是遍历右下角然后遍历精灵球用光的场景int res f[k - 1][m - 1][n - 1];for (int i 0; i n; i) {res max(res,f[k - 1][m - 1][i]);}coutres;
} 问题 如何初始化
这里默认初始化为零就行了。
定边技巧如何实现
这里是使用滚动数组实现的然后倒序遍历控制了临界条件总的来说我的方法也是保证了临界条件但是滚动数组优化效果会更好。
选择哪个维度最大进行遍历
这里仅仅选择要求的维度进行遍历比如这里的就是选择体力值这个维度进行遍历然后精灵球一定是用完的如果精灵球没有用完那么所收服的数量一定是小于等于精灵球用完的情况。这里是同样的。
参考实现
下面是自己根据理解和记忆修改的以下几个地方需要注意 关于体力值的遍历应该从n-1开始体力值不能用完皮神不能死。
#include iostreamusing namespace std;const int N 1010,M 510,K 110; // N精灵球的数量M皮卡丘的初始体力值K是野生小精灵的数量
int n,m,k;
int f[M][N];
int mt[K],nt[K];int main(){cinnmk;for (int i 1; i k; i) {cinnt[i]mt[i];// 分别记录收服每一个小精灵的数量、损耗的体力值}// 动态规划方程// 初始值的问题for (int i 1; i k; i) {for (int j m - 1; j mt[i]; j--) {// 遍历对应皮神的体力值for (int l n ; l nt[i]; l--) {// 遍历手上剩余的精灵球的数量f[j][l] max(f[j][l],f[j - mt[i]][l - nt[i]] 1);}}}// 现在是遍历右下角然后遍历精灵球用光的场景int res f[m - 1][n];coutres ;int cost_m m;for (int i 0; i m - 1; i) {if (res f[i][n])cost_m min(cost_m,i);}coutm - cost_m;
}新作
两两交换链表中的节点
题目链接
个人实现
这道题单纯是模拟整个过程进行实现然后是两个指针进行遍历实际上可能只需要一个指针的。
#include iostreamusing namespace std;struct ListNode{int val;ListNode* next;ListNode(int x,ListNode* y):val(x),next(y){};ListNode(int x):val(x),next(nullptr){};ListNode():val(-1),next(nullptr){};
};ListNode* swapPairs(ListNode* head){auto dummy new ListNode();dummy-next head;// 交换链表auto l dummy,r head;while( r r-next){// 交换链表然后更换数据l-next r-next;r-next l-next-next;l-next-next r;// 更新对应的左右指针if (r-next) r r-next;l l-next-next;}// 返回最终节点return dummy-next;}int main(){}少有的再25分钟之内通过了测试。 参考实现
总的来说思路是一样的但是他的表示还有代码太简洁了真的佩服的五体投地总结一下主要有以下几个点值得我学习。 对于经常使用的变量没有必要一直写next-next使用一个变量存一下不会好很多码为什么非得就画两个指针画三个指针不是更好懂吗 看了一遍思路这里实现一下哎
整体思路和我的一样的都是模拟
#include iostreamusing namespace std;struct ListNode{int val;ListNode* next;ListNode(int x,ListNode* y):val(x),next(y){};ListNode(int x):val(x),next(nullptr){};ListNode():val(-1),next(nullptr){};
};ListNode* swapPairs(ListNode* head){auto dummy new ListNode();dummy-next head;// 交换链表for (auto p dummy;p-next p-next-next;) {auto a p-next,b p-next-next;p-next b;a-next b-next;b-next a;p a;}// 返回最终节点return dummy-next;}int main(){}删除有序数组中的重复项
题目链接 个人实现
整个题很简单就是遍历一遍但是有一个问题就是vector怎么实现删除特定索引的元素 编程遇到的问题vector如何删除特定索引的元素使用迭代器遍历元素如何获取元素具体的值迭代器怎么访问
#include iostream
#include vector
using namespace std;int removeDuplicates(vectorint nums){int l nums.size();for (auto x nums.begin();x nums.begin() l;x ) {while (x 1 nums.end() *x * (x 1))nums.erase(x);}return nums.size();
}int main(){vectorint res {1,1,2};coutremoveDuplicates(res);
}这个代码有很大的问题的明明实现起来很简单但是语法不熟悉无论通过迭代器还是通过索引删除都会改变原来的结构索引就不成立了。不能删除除了开新数组然后逐个赋值其他就不知道了。但是这种没意义。这题重要的不是思路重要的是让我知道有很多知识点不会。
知识补全
迭代器的访问和控制
vectorint test;
for(auto it test.begin();it ! test.end();it ){ // 通过1实现向后迭代cout*itendl; // 通过*iterator进行访问
}vector删除特定的元素erase
使用迭代器进行删除
删除特定的元素
nums.erase(nums.begin() 1);删除特定范围的元素
nums.erase(nums.begin() 1,nums.begin() 3);vector底层删除元素的原理是什么
找到要删除的元素使用迭代器或索引找到要删除的元素位置。移动元素将后续的元素向前移动以填补被删除元素的位置。调整大小更新容器的大小缩减到实际存储的元素数量。所以使用erase的话就会出现上述问题时间复杂度还是很高的如果能够直接修改对应的size元素时间效率会更好。
实现思路
这道题他妈的没看清楚实际上有明确指出只要求前k个元素是不同的单调递增就行了不要求整个数组都是单调递增的这里出大问题的。 就是很简单的双指针遍历。
class Solution {
public:int removeDuplicates(vectorint nums) {int n nums.size();if (n 0) {return 0;}int fast 1, slow 1;while (fast n) {if (nums[fast] ! nums[fast - 1]) {nums[slow] nums[fast];slow;}fast;}return slow;}
};总结
尴尬今天是投论文的第一天又超时了上午刷算法用了太多时间不应该呀。不过对于单调队列还有二维背包有了更深层次的理解。早上两道题做的还行复习了一下都是自己写出来了虽然超时了。晚上有一道简单题没写出来很难受是因为看错了没理解题目的意思。
