拆分单词
常见的子数组问题 ⇒ 要使用动态规划的解法
那么要确定dp数组的含义 ⇒ do[i] — — 以 s[i] 结尾的子数组可不可以用 wordDict中的字符串来表示
那么问题来了, 如何判断字符串[j, i] 在没在wordDict中呢?
我们可以用一个 哈希表 . 将wordDict导入一个哈希表中, count 判读一个字符是否在哈希表中出现
遍历方向 — — 从前到后
初始化 — — 由于出现了 j-1, 那么我们可以让dp数组多开一个位置 ⇒ 利于我们初始化, 由于都是从第一个位置往后推导dp状态的, 那么dp[0] 就初始化为 true
class Solution { public: bool wordBreak(string s, vector<string>& wordDict) { // 将wordDict 导入一个哈希表, 用于判断字符串是否出现过 unordered_set<string> hash; for(auto e : wordDict) hash.insert(e); int n = s.size(); vector<bool> dp(n+1); // 初始化 dp[0] = true; // 填表 // 在字符串中头插一个空格, 方便确定dp的i 和 s中的i的关系 s = ' ' + s; for(int i = 1; i <= n; i++) { for(int j = i; j >= 1; j--) { if(dp[j-1] && hash.count(s.substr(j, i-j+1))) { // 已经可以构成, 那就没有必要往后遍历了 dp[i] = true; break; } } } return dp[n]; } };
乘积为正数的最长子数组长度
还是 子数组问题 ⇒ dp[i]的含义是: 以nums[i] 结尾的子数组中乘积为正数的最长长度
接下来来分析 dp转移方程 ⇒ 从nums[i] 位置开始分析起
- 遍历顺序 – –
f表 和 g表 同时遍历, 从前往后 - 初始化 — —
涉及到 i - 1 ⇒ f表 和 g表 都多开一个空间, 且 f[0] = g[0] = 0;/
class Solution { public: int getMaxLen(vector<int>& nums) { int n = nums.size(); // 建表 + 初始化 vector<int> f(n+1, 0); vector<int> g(n+1, 0); // 填表 int res = 0; for(int i = 1; i <= n; i++) { if(nums[i-1] > 0) { f[i] = f[i-1] + 1; g[i] = g[i-1] == 0 ? 0 :g[i-1]+1; } if(nums[i-1] < 0) { f[i] = g[i-1] == 0 ? 0 : g[i-1] + 1; g[i] = f[i-1] + 1; } res = max(res, f[i]); } return res; } };
