dw怎么做百度网站,邯郸网站,中国能建官网,wordpress主题带demo目录
#x1f4bb;最长递增子序列
AC 动态规划
AC 动态规划(贪心) 二分
#x1f3e0;乘积最大子数组
AC 动规
AC 用 0 分割
#x1f42c;分割等和子集
AC 二维DP
AC 一维DP
⚾最长有效括号
AC 栈 哨兵 #x1f4bb;最长递增子序列
300. 最长递增子序列…
目录
最长递增子序列
AC 动态规划
AC 动态规划(贪心) 二分
乘积最大子数组
AC 动规
AC 用 0 分割
分割等和子集
AC 二维DP
AC 一维DP
⚾最长有效括号
AC 栈 哨兵 最长递增子序列
300. 最长递增子序列 - 力扣LeetCode 子序列不用连续 子串要求连续 AC 动态规划
时间 O(n^2)
/*
dp[i] : 第 i 个元素结尾的最长子序列长度下标0开始
dp[i] max(dp[i], dp[j] 1)
初始化 : dp[i] 1
*/
class Solution {
public:int lengthOfLIS(vectorint nums) {int n nums.size();vectorint dp(n 1, 1);for (int i 1; i n; i)for (int j 0; j i; j) if (nums[j] nums[i])dp[i] max(dp[i], dp[j] 1);int ans 1;for (auto x : dp)ans max(ans, x);return ans;}
};
AC 动态规划(贪心) 二分 二分实现 O(logn) 查找为了使用二分我们需要让 dp[] 数组有序所以需要改变 dp[] 数组的含义状态 贪心策略tails 中存储的元素越小上升的子序列越长 举例解释 nums[] {7, 8, 9, 1, 2, 3, 4, 5}; 遍历完 7 8 9 后 tails[] {7, 8, 9}; 接着遍历到 1那么二分查找 tails[]找到第一个比 tails 大的位置即 7替换后变成 tails[] {1, 8, 9}; 如果没有比当前 nums[] 值大的元素直接加到后面 最后输出 tails[] 长度就是最长上升子序列长度 时间 O(nlogn)
/*
tails[i] : 长度 i1 子序列的尾部元素
1nums[] 中当前元素 x tails.back(), x 插入 tails 最后
2否则, 二分查找 tails[] 中第一个 x 的元素, 替换成 x
最后返回 tails[] 大小
*/
class Solution {
public:int lengthOfLIS(vectorint nums) {vectorint tails;tails.push_back(nums[0]);for (auto x : nums) {if (x tails.back()) {tails.push_back(x);continue;}int l 0, r tails.size() - 1;while (l r) {int mid (l r) 1;if (tails[mid] x)l mid 1;elser mid;}tails[l] x;}return tails.size();}
};
// 检验二分边界
// tails[]: 1 3 5 -- x: 3/4
// tails[]: 1 3 5 7 -- x: 3/4/5
乘积最大子数组
152. 乘积最大子数组 - 力扣LeetCode
注意是“连续子数组”
AC 动规 1滚动 本题dp[i] 都是基于 dp[i -1] 得到的所以可以将一维数组变成一个变量即 “滚动数组” 2坑 遍历数组更新 3 个 dp 变量时maxDp 基于上一个 maxDp 没问题 但是 maxDp 更新后minDp 还是基于上一个 maxDp 所以需要一个临时变量保存上一个 maxDp 然后 dp 可以直接基于新的 maxDp 3坑2 题目保证 32 位也就是 10^9但是样例里有一组 10^19 次方的.... 所以有 4 个地方要加 double防止类型不匹配 或 heap flow堆溢出 时间 O(n)
/*
滚动数组一维数组变变量
maxDp[i] : 第 i 个元素结尾的最大值
minDp[i] : 第 i 个元素结尾的最小值
dp[i] : 只选前 i 的元素的最大值
*/
class Solution {
public:int maxProduct(vectorint nums) {int n nums.size();if (n 1)return nums[0];double maxDp nums[0], minDp nums[0], dp nums[0];for (int i 1; i n; i) {double t maxDp; // 临时变量maxDp max(max((double)nums[i], maxDp*nums[i]), minDp*nums[i]);minDp min(min((double)nums[i], t*nums[i]), minDp*nums[i]);dp max(dp, maxDp); // 上一个 dp 和 新的 maxDp 取较大值}return (double)dp;}
};
AC 用 0 分割 用 0 分割成多个连续的子数组对每个子数组 1偶数个负数直接相乘负数数量 0, 2, 4, 6... 2奇数个负数 a. 左到右相乘直到最后一个负数之前 b. 右到左直到最后一个负数之前 取 a. b. 的 max() 3实际遍历中先左到右遍历后右到左遍历单次遍历中只需要动态更新最大值包含了偶数奇数个负数的两种情况 时间 O(n)
class Solution {
public:int maxProduct(vectorint nums) {double ans nums[0];double t 1; // 临时变量保存乘积// 左到右for (int i 0; i nums.size(); i) {t * nums[i];ans max(ans, t);if (t 0)t 1; // 用 0 分割子数组}// 右到左t 1;for (int i nums.size() - 1; i 0; --i) {t * nums[i];ans max(ans, t);if (t 0)t 1;}return (int)ans;}
};
分割等和子集
416. 分割等和子集 - 力扣LeetCode
AC 二维DP 01背包画表格类似这样 坑 和为奇数直接返回 false否则打表会发现出现了一些奇怪的错误 含义 dp[i][j] : 只从 [0, i] 区间里选每个数最多选 1 次和为 j 递推式 选第 i 个dp[i - 1][j - nums[i]] 不选第 i 个dp[i - 1][j] 第 i 个数 总和的一半 dp[i][j] dp[i - 1][j - nums[i]] || dp[i - 1][j] || (nums[i] sum/2) 初始化 根据递推式只需初始化第 0 行即只从 [0, 0] 区间选和为 nums[0] 的 1其他为 0 输出 dp[n - 1][sum / 2]表示从 [0, n - 1] 选, 和为总和一半, 即等和子集 O(n * sum/2)
// dp[i][j] dp[i - 1][j - nums[i]] || dp[i - 1][j] || (nums[i] sum/2)
// 输出 dp[n - 1][sum / 2]
class Solution {
public:bool canPartition(vectorint nums) {int sum 0, n nums.size();for (auto x : nums)sum x;if (sum % 2 1)return false; // 和为奇数// n 行, 每一行就是 vectorint(), 这一行表示总和 0 ~ sum/2, 初始化为 0vectorvectorint dp(n, vectorint(sum / 2 1, 0));if (nums[0] sum/2)dp[0][nums[0]] 1; // 从 [0, 0] 选, 和为nums[0]for (int i 1; i n; i)for (int j 0; j sum/2; j) {dp[i][j] dp[i - 1][j] || (nums[i] sum/2);if (j nums[i]) // 防止越界dp[i][j] dp[i][j] || dp[i - 1][j - nums[i]];}return dp[n - 1][sum / 2];}
};AC 一维DP 考虑到递推式 dp[i][j] 都是来源于 dp[i - 1][...]可以将二维变成一维优化空间 那么为什么要逆序遍历子集的和 j 呢因为dp[j] 都是基于上一行的旧的(未被修改的) dp[j] 和 dp[j - nums[i]] 如果顺序遍历dp[j - nums[i]] 会被多次修改也就是取了多个元素而题目规定只能取一个 顺序遍历适合完全背包而不是 01 背包 // dp[j] 和为 j
// dp[j] dp[j - nums[i]] || dp[j] || (nums[i] sum/2)
// 输出 dp[sum / 2]
class Solution {
public:bool canPartition(vectorint nums) {int sum 0, n nums.size();for (auto x : nums)sum x;if (sum % 2 1)return false; // 和为奇数// 和的一半 1 个元素vectorint dp(sum / 2 1, 0);if (nums[0] sum/2)dp[nums[0]] 1; // 从 [0, 0] 选, 和为nums[0]for (int i 1; i n; i)for (int j sum/2; j 0; --j) {dp[j] dp[j] || (nums[i] sum/2);if (j nums[i]) // 防止越界dp[j] dp[j] || dp[j - nums[i]];}return dp[sum / 2];}
};⚾最长有效括号
32. 最长有效括号 - 力扣LeetCode
AC 栈 哨兵 求连续的最长有效括号 如果不连续栈就会被清空最后一个元素再插入新的下标即更新了栈顶的元素 初始插入 -1哨兵防止先遇到右括号栈为空就 pop 导致的栈溢出 时间 O(n)
class Solution {
public:int longestValidParentheses(string s) {int ans 0;if (s.size() 0) return 0;stackint st;st.push(-1); // 防止溢出, 为后面的连续准备for (int i 0; i s.size(); i) {if (s[i] () // 左括号st.push(i); else { // 右括号st.pop();if (st.empty())st.push(i);else ans max(ans, i - st.top()); // 连续的长度}}return ans;}
};
