[数据结构与算法]LeetCode动态规划专题：第九天

单词拆分

class Solution {
public:
    bool wordBreak(string s, vector<string>& words) {
        typedef unsigned long long ULL;
        const int P = 131;
        unordered_set<ULL> S;
        for (auto& word : words){
            ULL h = 0;
            for (auto& c : word)
                h = h * P + c;
            S.insert(h);
        } 

        int n = s.size();
        vector<bool> f(n + 1);
        f[0] = true;
        s = ' ' + s;
        for (int i = 0; i < n; i ++ ){
            if (f[i]){
                ULL h = 0;
                for (int j = i + 1; j <= n; j ++ ){
                    h = h * P + s[j];
                    if (S.count(h)) f[j] = true;
                }
            }
        }
        return f[n];
    }
};

接雨水

双指针

某一边最高的墙比另一边要高的话，另一边指针所在的位置一定可以接到与最高高度差的雨水，直到两边的指针相遇

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size(), res = 0;
        int l = 0, r = n - 1;
        int lm = 0, rm = 0;
        while (l < r){
            lm = max(lm, height[l]);
            rm = max(rm, height[r]);
            if (height[l] < height[r]){
                res += lm - height[l];
                l ++ ;
            }
            else {
                res += rm - height[r];
                r -- ;
            }
        }
        return res;
    }
};