文和906

题解

未归档(4) 项目笔记(5)

/ 注册

全部文章 / 题解（共16篇）

题解 | #【模板】二维前缀和#

思路是用一个二维数组sum来储存(0, 0)到该点所形成的子矩阵中所有数的和。即sum.at(i).at(j)储存着以(0,0)(i,j)为反对角线的矩阵的所有元素的和。当要计算(x1, y1)与(x2, y2)所形成的矩阵中所有元素的和时，只需要用(0, 0)(x2, y2)这个大的矩形，减去(0...

C++ 前缀和动态规划

2021-10-28

0 540

题解 | #【模板】前缀和#

经典前缀和问题。具体做法是在接受输入数字创建数组时，同时创建一个前缀和数组sum，sum.at(i)维护的是数组前i+1项的和(0为首项)。在处理每一组l与r时，直接让前r项的和减去前l项的和在加上第l项的和即可。时间复杂度O(n)，空间复杂度O(n)。 #include <iostream&...

C++ 动态规划前缀和

2021-10-28

0 354

题解 | #重建二叉树#

看题目首先确定采用分治的思想，通过题目给出的先序遍历与中序遍历确定头结点，然后通过该头结点得到两个子树的先序遍历与中序遍历，重复该过程，最后就可以得到完整的树。具体实现中采用递归的方法，递归的最大栈深度为n，在递归中有一步需要循环来查找头节点，平均时间复杂度为O(logn)，故该方法时间复杂度为O...

C++ 动态规划链表二叉树

2021-10-08

0 390

题解 | #买卖股票的最好时机#

比较简单的动态规划。用一个变量保存最小值，另一个变量保存最大收益。遍历数组：1.当该数比最小值小时，将其赋给最小值。2.将该数与最小值相减得到该数所能得到的最大收益，若该收益比最大收益大，将其赋给最大收益最终即得最大收益。 class Solution { public: /** ...

C++ 动态规划

2021-09-29

0 331

题解 | #最长回文子串#

比较经典的回文判断题型。由于题目要求时间复杂度为O(n^2)，故考虑较为直接的暴力解法。使用一个二重循环，第一重循环i从数组的第一个元素开始，第二重循环j从数组的最后一个元素开始，每趟循环都判断从i到j是否构成回文，若构成，则直接退出内层循环，在外层更新最大值。当i到j的字符串长度小于最大值时，直接...

C++ 动态规划字符串

2021-09-27

0 456

题解 | #连续子数组的最大和#

动态规划。使用遍历array的同时，使用array自身来保存当前连续子数组的和，第i趟遍历时查看前i-1项中最大子数组的和，若其小于0，则将第i项的值作为前i项中最大子数组的和，否则将前i-1项最大子数组的和加上第i项的值作为前i项中最大子数组的和。前i项最大子数组的和保存在数组的第i项中。 cla...

C++ 动态规划分治

2021-09-26

0 347