解题思路：动态规划这是一道区间dp的题目。首先第一步是把区间从n扩展到2n，这样就不用尾首循环了。接下来按照区间大小，从小到大循环，先计算小区间的最优解，再计算大区间的最优解。状态转移方程：dp[l][r] = max(dp[l][j] + dp[j][r] + a[l] * a[j] * a[r])， j ∈ [ l + 1, r - 1 ]注意本题的数据范围：由于珠子的值满足val <= 1000，因此每次获取的能量不超过10^9；n <= 100表示最多100个珠子，故而能量总和不超过10^11。因此使用long long，并且计算的中途不要对109+7取模（如果你在计算中途...

1、正向思路：动态规划令dp[i]表示：所取之和sum最大，且sum % k = i。具体代码如下。注意每次状态转移之前，要备份一下dp数组。 #include <climits> #include <iostream> #include <vector> using namespace std; int main() { int n, k; long long a; cin >> n >> k; vector<long long> dp(k, LLONG_MIN); dp[0] = 0; while(n--) { cin...

解题思路第一问就是简单的01背包问题，这里不多赘述，有不明白的自己去找资料吧。关键是第二问，问背包恰好装满的情况下，最多能装价值多少的物品。这里的恰好装满是关键。为了避免不必要的空间浪费，我这里使用map进行处理，其中map的任意一个键值对[key, val]表示正好装满体积为key的空间的最大价值为val。map的底层是红黑树，它本身是一个有序的容器，增删改查的时间复杂度都在O(logn)。我们让map的key从大到小排列，这样方便后续的状态转移。具体做法是：1、初始化map[0] = 0，即体积为0时价值为0。2、对于每一件物品的v和w，我们遍历整个map的所有键值对[key, val]，...

解题思路：动态规划首先使用二维dp，令dp[i][j]表示s1的前i个字符构成的字符串和s2的前j个字符构成的字符串的最长公共子序列。那么有状态转移方程：当s1[i] == s2[j]时，dp[i + 1][j + 1] = dp[i][j] + 1；否则 dp[i + 1][j + 1] = max ( dp[i][j + 1], dp[i + 1][j] )时间复杂度O(mn)，空间复杂度O(mn)。空间压缩，dp数组由二维压缩到一维注意到动态转移方程中的 i+1只和 i 有关，因此可以将dp数组压缩到一维。注意到题目要求的空间复杂度为 O(min(m, n))，我们强制令n >= ...

解题思路传统的动态规划思想是，维护一个dp数组，dp[k] 表示以元素 arr[k] 为末尾的最长严格上升子序列的长度。但是这个方法要遍历 k 以前的所有位置，找到满足arr[i] < arr[k]且dp[i]最大的那一个，令dp[k] = dp[i] + 1。时间复杂度为O(n²），这个时间复杂度说实话真的不那么令人满意，有没有更优秀的解法呢？答案是有的。根据贪心的思想，如果我维护的子序列上升的速度越慢，那么它就可以加入更多的元素。比如原始序列 { 1, 4, 6, 2, 3, 5, 8, 7 }，其中子序列 {1, 4, 6 } 比 { 1, 2, 3 } 上升的更快，这两种情况下我...

解题思路根据题意，金片只能从一根柱子上顺时针移动到下一个柱子上，而不能反过来移动，因此我们只需要考虑两种情况。1、将n个金片移动到顺时针的下一个柱子上。所需的次数记为 move1[n]2、将n个金牌移动到逆时针的上一个柱子上，相当于是顺时针移动两次。所需的次数记为 move2[n]现在要做的是，推导 move1[n + 1] 和 move2[n + 1] 。我们先看 move1[n + 1] 。不妨假设现在要将n + 1个金片从A柱子移动到B柱子，那么可以把过程拆分为几个步骤： 1、把n个金片从A移动到C，所需次数为 move2[n]。 2、将最下面的一个金片从A移动到B，记移动1次。 3、最...

解题思路1、输入数据，获得数组a，并得到数组a中的最大值，记为maxa。2、使用欧拉筛，计算 2到maxa的所有素数。3、计算数组a中每个元素的素因子列表。4、暴力枚举，递归+回溯，求最优解。思路明确的话，写代码没有什么难度，就不做赘述了，下面详细讨论下素数的筛法。素数的筛法1、埃氏筛法（埃拉托斯特尼筛法，Sieve of Eratosthenes）该筛法的核心思想是从 2 开始，将每个素数的倍数标记为合数，逐步筛选出所有素数。具体来说，先假设所有数都是素数，然后从最小的素数 2 开始，把 2 的倍数（除 2 本身）都标记为合数；接着找到下一个未被标记的数，它就是素数，再把它的倍数标记为合数，...

解题思路简单使用递归即可。1、确定根节点，必然是后序遍历的最后一个元素，以此创建树。2、找到根节点在中序遍历中的位置。3、递归创建左右子树。 /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * }; */ #include <algorithm> class Solution { public: /** * 代码中的类名、方法名、参数名已经...

解题思路本题由于原数组a中存在负数，扩大区间范围可能会导致区间和反倒减少，因此不能简单使用滑动窗口。假设已知前缀和数组sum，那么区间和 s[l, r] = sum[r] - sum[l - 1] >= k的必要条件为sum[l - 1] <= sum[r] - k。我们对于每一个右边界r，判断其左边存在多少个左边界l，满足不等式sum[l - 1] <= sum[r] - k，就代表存在多少个满足条件的解。为了快速判断小于等于 sum[r] - k的数量，这里用到树状数组。此外，本题的数据量为10^5，而数据范围在10^14，因此开树状数组的时候必须用到离散化。知识点：树状...

解题思路：滑动窗口（双指针）假设区间 [l, r] 的元素之和大于等于k，那么必然有后续区间区间 [l, r+1]、[l, r+2] ……所有这些区间的元素之和必然大于等于k。因此本体可以使用滑动窗口的思路进行解答。下面给出cpp代码。 #include <iostream> #include <vector> using namespace std; int main() { int n, l = 0, r = -1; long long k, sum = 0, ans = 0; cin >> n >> k; vector<int>...

解题思路看到题目后，我们很容易得出一个结论：令所有蛋糕的美味度总和为sum。那么当s1越接近sum的一半，|s1 - s2|就越小。同时s1 + s2 = sum，故|s1 - s2| = |sum - s1 - s1|。本题的关键是求计算s1，即枚举所有正方形的美味度。将一维数组的前缀和扩展到二维对于一维数组a，我们可以维护一个前缀和数组s。s[i]表示a[0]到a[i]的和。那么当我们要求数组a的一段连续子数组的和，比如a[i]到a[j]的和，就可以得到答案 = s[j] - s[i - 1]。类似的，将一维数组扩展到二维数组。s[i][j]表示从a[0][0]开始，a[i][j]结束的矩...

描述小招喵喜欢在数轴上跑来跑去，假设它现在站在点n处，它只会3种走法，分别是：1.数轴上向前走一步，即n=n+1 2.数轴上向后走一步,即n=n-1 3.数轴上使劲跳跃到当前点的两倍，即n=2*n现在小招喵在原点，即n=0，它想去点x处，快帮小招喵算算最快的走法需要多少步？输入描述：小招喵想去的位置x输出描述：小招喵最少需要的步数解题思路首先给出几个显而易见的推论：1、从0走到x，和从0走到-x，用的步数是相同的，因此只要考虑正数。2、从0走到x的步数，和从x走到0是一样的，因此可以反向计算。3、反向计算的情况下，按照贪心的思想，若x为偶数，那么直接除以2就是最优解，若x为奇数，则要考虑+1或...

题目描述哈希表看到题目的第一反应就是用哈希表，在c++中是unordered_map。这里用了一个小技巧，当某个数出现k次后，从哈希表中删除，这样最后哈希表中只会剩下一个数，就是答案。时间复杂度O(n)，空间复杂度O(n)。 #include <unordered_map> class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param arr int整型vector * @param k int整型 * @return int整型 */ int foundOnceNumber(vec...

题目描述给定一个长度为n的正整数数组nums，可以任意改变数组的其中一个元素，原来的和改变的元素范围都在[1,100000]之内，然后返回nums的最长"严格上升"子数组的长度。1.子数组是连续的，比如[1,3,5,7,9]的子数组有[1,3]，[3,5,7]等等，但是[1,3,7]不是子数组。2.严格上升指在数组上任意位置都满足 nums[i] < nums[i+1]，比如[1,2,2,3]，其中[1,2,2]不是严格上升的子数组，[1,2]则是的。数据范围： 1≤n≤10^5， 1≤num[i]≤10^5要求： 空间复杂度 O(n)，时间复杂度 O(n)解题思路：...