湖北住房城乡建设厅网站,wordpress雪人主题2.0,企业网站维护合同,咋么做网站文章目录 引言复习#xff08;单调队列优化DP#xff09;——最大子序和单调队列的基本实现思路——求可移动窗口中的最值总结 背包模型——宠物小精灵收服问题思路分析参考思路分析 新作二叉树的后续遍历加指针调换 总结 引言
复习
#xff08;单调队列优化DP#xff09… 文章目录 引言复习单调队列优化DP——最大子序和单调队列的基本实现思路——求可移动窗口中的最值总结 背包模型——宠物小精灵收服问题思路分析参考思路分析 新作二叉树的后续遍历加指针调换 总结 引言
复习
单调队列优化DP——最大子序和
这个已经是第二天做了昨天基本上已经做了很多推理今天就要把这道题完成下述是昨天的学习的链接单调递增队列的推理昨天经过推理知道了要将这个问题进行转换由原先的特定长度和的最大值转成求特定长度和的最小值。然后通过画图证明了为什么要通过单调队列实现最小值的计算。今天主要是关注代码的执行。
单调队列的基本实现思路——求可移动窗口中的最值
使用队列维系一个集合m将无用的元素从后往前进行排除保证队列是一个单调递增的队列找出最大值或者最小值
在这里的队列保存的元素是的特定序列的累加和不是具体的元素的大小保证单调递增
这个代码不是那么好懂我自己再写一遍。
#include iostreamusing 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 - 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;
}总结
重新写了一遍效果好多了并没有像之前那么难以理解了主要有两个地方需要好好整理一下分别是 这里的单调递增是针对S也就是每一个前序和来说的不是针对特定的某一个元素说的。这里使用一个数组模拟队列hh模拟队列的头指针tt模拟队列的尾指针 hh头指针只需要保证是最小值并且队列的长度不超过mtt尾指针需要覆盖新的元素保证整个队列是单调递增的因为这是一个序列和如果后续的序列和比前面的小那么最终就不一定不会选择前面的序列和。
背包模型——宠物小精灵收服问题 思路分析 这道题是经典的背包模型问题收服的精灵就是要求在特定空间下装的货越多然后的皮卡丘收到的伤害就是代价越小越好 每一个状态的集合主要分为两个部分收取当前的精灵和不收取当前的精灵而且要同时满足两个约束的就是最多收服精灵的个数皮卡丘最少收到的伤害不过究竟哪个更加重要明白了尽可能多的精灵然后同样多的情况下保证尽可能多的剩余体力。所以这里要两个矩阵 一个保存数量这个属性值也是dp的主要目标另外一个保存剩余的体力值这个用来后续判断 感觉有点不对这里是不是要再增加一个新的遍历条件也就是体力值如果不增加就没有意义了。 暂时实现成这样了还有点问题不过时间不够了直接看代码了
#include iostreamusing namespace std;const int N 1010,M 505,K 105; // N是精灵球的数量M是皮卡丘的体力值K是野生小精灵的数量
int f[K][N],mr[K][N],n1[K],m1[K];
int n,m,k;
int main(){cinnmk;for (int i 1; i k; i) {cinn1[i]m1[i];}// 遍历对应的数据for (int i 1; i k; i) {for (int j 0; j N; j) {f[i][j] 0;// 两种状态// 一种是收服当前的精灵f[i-1][j - n1[i]] 1// 判定当前剩余的体力以及精灵球的数量是否满足要求if (m m1[i] k n1[i])f[i][j] f[i-1][j - n1[i]] 1;// 另外一种是不收服当前的精灵f[i-1][j]int temp f[i-1][j];if (temp f[i][j]){// 不收服的结果大于当前的结果f[i][j] temp;}else{m - m1[i];n - n1[i];}}}// 输出最终的结果遍历一下}参考思路分析
这里是二维背包问题需要考虑两个维度所以我上面的思路有问题应该使用二维背包去解决这个问题。这里先直接贴代码参考分析一下 二维背包然后使用滚动数组进行优化然后遍历最后一个维度下精灵球最多的情况下体力值消耗最小的情况。 还是得看看之前的背包问题咋写的一维和二维之间的相互转换。
#include iostream
#include cstring
#include algorithmusing namespace std;const int N 110, M 1010, K 510;int n, m, t;
int v1[N], v2[N];
int f[M][K];int main()
{//inputcin m t n;for (int i 1; i n; i) cin v1[i] v2[i];//dpfor (int i 1; i n; i){for (int j m; j v1[i]; -- j){for (int k t - 1; k v2[i]; -- k){f[j][k] max(f[j][k], f[j - v1[i]][k - v2[i]] 1);}}}//outputcout f[m][t - 1] ;//找到满足最大价值的所有状态里第二维费用消耗最少的int cost_health t;for (int k 0; k t - 1; k){if (f[m][k] f[m][t - 1]){cost_health min(cost_health, k);}}cout t - cost_health endl;return 0;
}作者一只野生彩色铅笔 链接https://www.acwing.com/solution/content/52741/ 来源AcWing 著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。
新作
今天晚上会进行的某公司的主管面今天新做的题目就是主管面的手撕算法题。
二叉树的后续遍历加指针调换
这道题吃亏在于我没有看清楚题目没有理解他的题目我觉得他说的比较混乱而且有一个东西感觉没有任何意义。不过我也发现我的问题了二叉树定义哪里有问题没有实现的好。下面是我写的 大概是写对的
#include iostream
#include vector
using namespace std;struct Node{int val;Node* left;Node* right;Node(int x):val(x),left(NULL),right(NULL){};
};vectorint res;void dfs(Node* root){if (root-left) dfs(root-left);if (root-right) dfs(root-right);res.push_back(root-val);
}int main(){Node* root new Node(1);dfs(root);for(int i 0;i res.size();i )coutres[i],;delete root;
}针对第二个问题表述如下 要将二叉树的左右子节点更换为后序遍历中的左右子节点并且更改之后的结果可能不是一个树甚至有可能成为其他结构。 其实我蛮不能理解他的用意的究竟是让我干什么把一个二叉树的左右子节点变为后续遍历顺序中的节点那么指针的方向有没有改变然后构建出来是什么样原来的结构还要保存吗 如果只是单纯换一个方式不就是在创建一个后序遍历的链表吗把每一个节点都加进去不就行了吗 现在还不是很懂这个题目 下面是ChatGPT写的感觉没有什么意义。
#include iostream
#include vectorstruct Node {int val;Node* left;Node* right;Node(int x) : val(x), left(nullptr), right(nullptr) {}
};// 后序遍历记录节点访问顺序
void postOrderDFS(Node* root, std::vectorNode* nodes) {if (root nullptr) {return;}postOrderDFS(root-left, nodes);postOrderDFS(root-right, nodes);nodes.push_back(root);
}// 根据后序遍历的节点顺序调整左右子节点
void adjustNodes(std::vectorNode* nodes) {for (size_t i 0; i nodes.size() - 1; i) {nodes[i]-left nullptr;nodes[i]-right nodes[i 1];}nodes.back()-left nullptr;nodes.back()-right nullptr;
}// 辅助函数中序遍历打印二叉树
void inOrderPrint(Node* root) {if (root nullptr) {return;}inOrderPrint(root-left);std::cout root-val ;inOrderPrint(root-right);
}// 辅助函数后序遍历打印二叉树
void postOrderPrint(Node* root) {if (root nullptr) {return;}postOrderPrint(root-left);postOrderPrint(root-right);std::cout root-val ;
}int main() {// 创建一个简单的二叉树Node* root new Node(1);root-left new Node(2);root-right new Node(3);root-left-left new Node(4);root-left-right new Node(5);root-right-left new Node(6);root-right-right new Node(7);std::cout Original tree (in-order): ;inOrderPrint(root); // 预期输出: 4 2 5 1 6 3 7std::cout std::endl;std::cout Original tree (post-order): ;postOrderPrint(root); // 预期输出: 4 5 2 6 7 3 1std::cout std::endl;// 后序遍历并记录节点顺序std::vectorNode* postOrderNodes;postOrderDFS(root, postOrderNodes);// 根据后序遍历顺序调整节点adjustNodes(postOrderNodes);std::cout Adjusted structure (in-order): ;inOrderPrint(root); // 可能无法正确打印因为树结构已改变std::cout std::endl;std::cout Adjusted structure (post-order): ;postOrderPrint(root); // 预期输出与原后序遍历顺序一致std::cout std::endl;return 0;
}总结
面试很难受不过我尽力了算法也复习到了。不过反映出我的问题就是很多东西看的不够细致不够深入先过一遍后续再继续深化。时间不是很够加油。
