每日两题 / 131. 分割回文串 42. 接雨水（LeetCode热题100）
131. 分割回文串 - 力扣（LeetCode）
数据量较小，考虑直接暴力，每次dfs：以bg作为左区间，往右遍历，找到一段回文串区间后，将回文串插入vector<string>，并以下一个下标为bg，再次进行dfs，dfs后记得回溯
class Solution {
public:vector<vector<string>> ans;bool f(string &s, int l, int r) {while (l < r) {if (s[l] != s[r]) return false;l ++ , r -- ;}return true;}void dfs(string &s, int bg, vector<string> &t) {if (bg == s.size()) {ans.push_back(t);return;}for (int i = bg; i < s.size(); ++ i) {if (f(s, bg, i)) {t.push_back(s.substr(bg, i - bg + 1));dfs(s, i + 1, t);t.pop_back();}}}vector<vector<string>> partition(string s) {vector<string> t;dfs(s, 0, t);return ans;}
};
42. 接雨水 - 力扣（LeetCode）
第i个位置的雨水高度为：左边最高柱子与右边最高柱子的最小值
那么能接的水量为：雨水高度 - height[i]
先预处理左右两边的最高柱子高度，然后线性遍历一遍即可
class Solution {
public:
#define N 20010int left[N], right[N];int trap(vector<int>& height) { int ans = 0;int n = height.size();right[n - 1] = height[n - 1];left[0] = height[0];for (int i = 1; i < n; ++ i) {left[i] = max(left[i - 1], height[i]);}for (int i = n - 2; i >= 0; -- i) {right[i] = max(right[i + 1], height[i]);}for (int i = 0; i < n; ++ i) {ans += min(left[i], right[i]) - height[i];}return ans;}
};