week14

131 - 分割回文串

这里有一个很重要的思想，预处理减少复杂度；

这里可以用递推的思想把判断回文串的步骤提前判断出来； 从f[i, j] 表示 s[i ... j]是回文子串（闭区间）

f[i, j] 可以由 f[i + 1, j - 1] 递推而来 只要满足 s[i+1 ... j-1] 是回文子串并且s[i] == s[j]即可

这样再dfs搜索分界线即可。

class Solution {
public:
    int n;
    vector<vector<string>> res;
    vector<vector<bool>> f;
    vector<string> path;
public:
    vector<vector<string>> partition(string s) {
        n = s.size();
        f = vector<vector<bool>>(n, vector<bool>(n));

        // 注意这里的枚举顺序
        for(int j = 0; j < n; j++)
            for(int i = 0; i <= j; i++)
            {
                if (i == j)
                    f[i][j] = true; // 只有一个字母 
                else if (s[i] == s[j])
                {
                    if (i + 1 > j - 1 || f[i + 1][j - 1]) // 只有两个字母 或者 f[i+1][j-1]为true
                        f[i][j] = true;
                }
            }

        dfs(s, 0);
        return res;
    }
    void dfs(string& s, int u)
    {
        if(u == n) res.push_back(path);
        else
        {
            for(int i = u; i < n; i++)
            {
                if(f[u][i])
                {
                    path.push_back(s.substr(u, i - u + 1));
                    dfs(s, i + 1);
                    path.pop_back();
                }
            }
        }
    }
};

132 - 分割回文串ii

这里第一步 预处理回文串判断和上面一题是一样的；

接下来的动态规划的状态f[i] 表示 s[1 ... i]中满足都为回文子串的所有分割方式，值为最小的子块数量；

显然 f[i] 可以在所有满足s[k ... i]为回文子串的状态中转移过来， f[i] = min(f[k - 1] + 1)

最后的答案是f[n] - 1 分割次数比子块数量少1；

class Solution {
public:
    int minCut(string s) {
        // 1. 预处理回文串判断
        int n = s.size();
        s = ' ' + s;
        vector<vector<bool>> isPara(n + 1, vector<bool>(n + 1));
        for(int j = 1; j <= n; j++)
            for(int i = 1; i <= j; i++)
            {
                if(i == j) isPara[i][j] = true;
                else if (s[i] == s[j])
                {
                    if(i + 1 > j - 1 || isPara[i + 1][j - 1])
                        isPara[i][j] = true;
                }
            }
        // 2. 动态规划 f[i] 指s[1..i]的所有分类情况
        vector<int> f(n + 1, 1e9);
        f[0] = 0;
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= i; j++)
            {
                if(isPara[j][i])
                    f[i] = min(f[i], f[j - 1] + 1);
            }
        return f[n] - 1;
    }
};

133 - 克隆图

分为两次 先拷贝点 再拷贝边；

拷贝点要建立原始点和复制点的映射关系，遍历一遍图 （BFS/DFS) 注意遍历图要判重！

然后拷贝每个点的边就可以了

class Solution {
public:
    unordered_map<Node*, Node*> hash; // 原始点和拷贝点的映射
public:
    Node* cloneGraph(Node* node)
    {
        if(!node) return nullptr;
        // 1. 复制所有点
        dfs(node);
        // 2. 复制所有边
        for(auto& p : hash)
        {
            Node* origin = p.first, *cpy = p.second;
            for(auto n : origin->neighbors)
                cpy->neighbors.push_back(hash[n]);
        }
        return hash[node];
    }
    void dfs(Node* node)
    {
        hash[node] = new Node(node->val);
        for(auto ver : node->neighbors)
        {
            if(hash.count(ver)) continue;
            dfs(ver);
        }
    }
};

134 - 加油站

+ 单调队列

首先对于这种环状数组问题常见的操作方式就是复制一遍 破环成链；

[1,2,3,4,5]变成[1,2,3,4,5,1,2,3,4,5], 再用一个长度为n的窗口 即为从不同起点开始的路径。

每一个加油站i 能到达的花费实际上是gas[i] - cost[i] 才能开到下一站

整段路程的花费实际上就是每一小段的花费的前缀和s[j] - s[i]，只要满足前缀和的最小值大于等于0就证明可以完整走完这一段路程。

转化为滑动窗口求最小值的问题：单调队列

枚举起点i, 对于s[j] - s[i] 而言 i 不变 实际上找的就是s[j]的在[i ... i + n - 1]中的最小值，这样我们需要从后往前维护单调队列才行（从前往后 i 后面的还没见过）

这样最小值即为队首元素s[q[hh]]

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        if(gas.empty()) return -1;
        int n = gas.size();
        vector<int> s(2 * n + 2), q(2 * n + 2);
        for(int i = 1; i <= n; i++)
            s[i] = s[i + n] = gas[i - 1] - cost[i - 1];
        // 1. 计算前缀和
        for(int i = 1; i <= 2 * n; i++)
            s[i] += s[i - 1];
        // 2. 维护单调队列
        // 这里求的是[i ... i + n - 1] 中的最小值 所以是包含 i的 区间最小值就是队列的队首元素 q[hh]
        int hh = 0, tt = -1;
        for(int i = 2 * n; i; i --)
        {
            if(hh <= tt && q[hh] > i + n - 1) hh++; 
            while(hh <= tt &&  s[q[tt]] >= s[i]) tt--;
            q[++tt] = i;
            if(i <= n && s[q[hh]] >= s[i - 1]) return i - 1;       
        }
        return -1;
    }
};

135 - 分发糖果

avatar

这题实际上就是 每个小朋友得到的最少糖果数是根据左右两边 连续下降的次数 决定的； 比如图上的情况 这个小朋友至少要得到3个 才能满足要求；

按照这个想法, 分别统计左右两边 连续下降的次数 最后加起来得到答案即可

class Solution {
public:
    int candy(vector<int>& ratings) {
        int n = ratings.size();
        vector<int> sl(n + 1), sr(n + 1);
        for(int i = 0; i < n; i++)
            if(i && ratings[i] > ratings[i - 1]) 
                sl[i] = sl[i - 1] + 1;
        for(int i = n - 1; i >= 0; i--)
            if(i < n - 1 && ratings[i] > ratings[i + 1])
                sr[i] = sr[i + 1] + 1;
        int res = 0;
        for(int i = 0; i < n; i++)
            res += max(sl[i], sr[i]) + 1;
        return res;
    }
};

136 - 只出现一次的数字

+ 位运算

相同两个数的异或值为0

所以所有的数异或操作后，剩下的一个数字就是只出现一次的了；

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int res = 0;
        for(auto n : nums)
            res ^= n;
        return res;
    }
};

137 - 只出现一次的数字ii

avatar

主要是这个按位的状态转移方程怎么来的很奇怪

one = (one ^ x) & (~two) two = (two ^ x) & (~one)

理解这么做是对的就好了

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int one = 0, two = 0;
        for(auto x : nums)
        {
            one = (one ^ x) & (~two);
            two = (two ^ x) & (~one);
        }
        return one;
    }
};

138 - 复制带随机指针的链表

这个题和上一个克隆图是一样的 也是分两步 先复制Node 再复制指针

同样也是建立一个原始Node 和 复制Node 的hash表

class Solution {
public:
    Node* copyRandomList(Node* head) {
        // 和上面的克隆图是类似的  都是分两步 先克隆node 再克隆指针
        if(!head) return head;
        unordered_map<Node*, Node*> hash;
        // 1. 克隆Node
        for(Node* t = head; t; t = t->next)
        {
            hash[t] = new Node(t->val);
        }
        // 2. 克隆指针
        for(Node* t = head; t; t = t->next)
        {
            Node* t_cpy = hash[t];
            if(t->next)   t_cpy->next   = hash[t->next];
            if(t->random) t_cpy->random = hash[t->random];
        }
        return hash[head];
    }
};

但这个需要额外开一个哈希表去记录对应关系, 根据链表的特性可以节省这个空间；

avatar

class Solution {
public:
    Node* copyRandomList(Node* head) {
        // 1. 复制next
        for(Node* t = head; t; t = t->next->next)
        {
            Node* t_cpy = new Node(t->val);
            t_cpy->next = t->next;
            t->next = t_cpy;
        }

        // 2. 复制random
        for(Node* t = head; t; t = t->next->next)
            if(t->random)
                t->next->random = t->random->next;
        // 3. 拆分链表
        Node* dummy = new Node(0), *cur = dummy;
        for(Node* t = head; t; t = t->next)
        {
            Node* q = t->next;
            cur = cur->next = q;
            t->next = q->next;
        }
        return dummy->next;
    }
};

139 - 单词拆分

简单的动态规划，这里去substr带来的复杂度同样可以用字符串哈希来处理

typedef unsigned long long ULL;
class Solution {
public:
    vector<ULL> hs, hw, p;
    vector<bool> f;
public:
    ULL get(int l, int r)
    {
        return hs[r] - hs[l - 1] * p[r - l + 1];
    }
    bool wordBreak(string s, vector<string>& wordDict) {
        int n = s.size(), m = wordDict.size();
        hs = vector<ULL>(n + 1, 0), hw = vector<ULL>(m + 1, 0), p = vector<ULL>(n + 1, 0);
        f = vector<bool>(n + 1);
        // 字符串哈希 初始化
        p[0] = 1;
        for(int i = 1; i <= n; i++)
        {
            hs[i] = hs[i - 1] * 131 + s[i - 1] - 'a' + 1;
            p[i] = p[i - 1] * 131;
        }
        // 初始化 wordDict 的 哈希值
        for(int i = 0; i < m; i++)
        {
            string sw = wordDict[i];
            for(int j = 0; j < sw.size(); j++)
            {
                hw[i] = hw[i] * 131 + sw[j] - 'a' + 1;
            }
        }
        // 状态转移
        f[0] = true;
        for(int i = 1; i <= n; i++)
            for(int j = 0; j < m; j++)
            {
                int k = wordDict[j].size();
                if(i >= k)
                    f[i] = f[i] || (f[i - k] && get(i - k + 1, i) == hw[j]);
            }
        return f[n];
    }
};

140 - 单词拆分ii

上面的基础上额外记录一个从那个状态转移而来的，最后dfs枚举所有的组合即可；

typedef unsigned long long ULL;
class Solution {
public:
    vector<ULL> hs, hw, p;
    vector<bool> f;
    unordered_map<int, vector<int>> trans;
    vector<string> res;
public:
    ULL get(int l, int r)
    {
        return hs[r] - hs[l - 1] * p[r - l + 1];
    }
    vector<string> wordBreak(string s, vector<string>& wordDict) {
        int n = s.size(), m = wordDict.size();
        hs = vector<ULL>(n + 1, 0), hw = vector<ULL>(m + 1, 0), p = vector<ULL>(n + 1, 0);
        f = vector<bool>(n + 1);
        // 字符串哈希 初始化
        p[0] = 1;
        for(int i = 1; i <= n; i++)
        {
            hs[i] = hs[i - 1] * 131 + s[i - 1] - 'a' + 1;
            p[i] = p[i - 1] * 131;
        }
        // 初始化 wordDict 的 哈希值
        for(int i = 0; i < m; i++)
        {
            string sw = wordDict[i];
            for(int j = 0; j < sw.size(); j++)
            {
                hw[i] = hw[i] * 131 + sw[j] - 'a' + 1;
            }
        }
        // 状态转移
        f[0] = true;
        for(int i = 1; i <= n; i++)
            for(int j = 0; j < m; j++)
            {
                int k = wordDict[j].size();
                if(i >= k)
                    if(f[i - k] && get(i - k + 1, i) == hw[j])
                    {
                        f[i] = true;
                        trans[i].push_back(i - k);
                    }
            }
        if(!f[n]) return res;
        else
        {
            vector<int> path;
            dfs(n, path, s);
            return res;
        }
    }
    void dfs(int u, vector<int>& path, string& s)
    {
        if(u == 0)
        {
            stringstream ss;
            for(int i = path.size() - 1; i; i--)
                ss << s.substr(path[i], path[i - 1] - path[i]) << ' ';
            ss << s.substr(path[0]);
            res.push_back(ss.str());
        }
        else
        {
            for(auto x : trans[u])
            {
                path.push_back(x);
                dfs(x, path, s);
                path.pop_back();
            }
        }
    }
};