131.分割回文串
- 131.1 思路
- 131.2 代码
132、分割回文串II
- 132.1 思路
- 132.2 代码
133.克隆图
- 133.1 思路
- 133.2 代码
134. 加油站
- 134.1 思路
- 134.2 代码
135. 分发糖果
- 135.1 思路
- 135.2 代码
136. 只出现一次的数字
- 136.1 思路
- 136.2 代码
137. 只出现一次的数字II
- 137.1 思路
- 137.2 代码
138.复制带随机指针的链表
- 138.1 思路
- 138.2 代码
140. 单词拆分II
- 140.2 代码

131.分割回文串

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文串。返回 s 所有可能的分割方案。

回文串是正着读和反着读都一样的字符串。

示例 1：
输入：s = “aab”
输出：[[“a”,”a”,”b”],[“aa”,”b”]]
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/palindrome-partitioning
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

131.1 思路

最坏情况是指数级别，比如aaaaa。
暴力搜索就行了。
加上的优化：快速判断字符串的子串是否是回文串。初始化，fij表示子串是否是回文串。fij也可以递推出来。

131.2 代码

class Solution {
public:
    vector<vector<bool>> f;
    vector<vector<string>> ans;
    vector<string> path;
    vector<vector<string>> partition(string s) {
        int 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][j] = true;
                }
        dfs(s, 0);
        return ans;
    }
    void dfs(string& s, int u) {
        // u是当前枚举到的位置
        if (u == s.size()) ans.push_back(path);
        else {
            for (int i = u; i < s.size(); i ++ )
            // 如果是回文串~、
                if (f[u][i]) {
                    path.push_back(s.substr(u, i - u + 1));
                    dfs(s, i + 1);
                    path.pop_back();
                }
        }
    }
};
作者：yxc
链接：https://www.acwing.com/activity/content/code/content/400664/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

132、分割回文串II

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文。

返回符合要求的最少分割次数。

示例 1：

输入：s = “aab”
输出：1
解释：只需一次分割就可将 s 分割成 [“aa”,”b”] 这样两个回文子串。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/palindrome-partitioning-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

132.1 思路

相当于分割成多少个部分。

132.2 代码

class Solution {
public:
    int minCut(string s) {
        int n = s.size();
        s = ' ' + s;
        vector<vector<bool>> g(n + 1, vector<bool>(n + 1));

        vector<int> f(n + 1, 1e8);

        // g数组是快速判断是否是回文串。
        for (int j = 1; j <= n; j ++ )
            for (int i = 1; i <= j; i ++ )
                if (i == j) g[i][j] = true;
                else if (s[i] == s[j]) {
                    if (i + 1 > j - 1 || g[i + 1][j - 1]) g[i][j] = true;
                }

        // 0 部分。 
        f[0] = 0;
        for (int i = 1; i <= n; i ++ ) {
            // j枚举的是每一类的起点。
            for (int j = 1; j <= i; j ++ )
                if (g[j][i])
                    f[i] = min(f[i], f[j - 1] + 1);
        }

        return f[n] - 1;
    }
};

作者：yxc
链接：https://www.acwing.com/activity/content/code/content/400682/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

133.克隆图

给你无向连通图中一个节点的引用，请你返回该图的深拷贝（克隆）。

图中的每个节点都包含它的值 val（int）和其邻居的列表（list[Node]）。

class Node {
public int val;
public List neighbors;
}

测试用例格式：

简单起见，每个节点的值都和它的索引相同。例如，第一个节点值为 1（val = 1），第二个节点值为 2（val = 2），以此类推。该图在测试用例中使用邻接列表表示。

邻接列表是用于表示有限图的无序列表的集合。每个列表都描述了图中节点的邻居集。

给定节点将始终是图中的第一个节点（值为 1）。你必须将给定节点的拷贝作为对克隆图的引用返回。

示例 1：

输入：adjList = [[2,4],[1,3],[2,4],[1,3]]
输出：[[2,4],[1,3],[2,4],[1,3]]
解释：
图中有 4 个节点。
节点 1 的值是 1，它有两个邻居：节点 2 和 4 。
节点 2 的值是 2，它有两个邻居：节点 1 和 3 。
节点 3 的值是 3，它有两个邻居：节点 2 和 4 。
节点 4 的值是 4，它有两个邻居：节点 1 和 3 。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/clone-graph
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

133.1 思路

这应该是一个连通图，从任何一个点都能直接访问到所有点。
深度拷贝应该复制所有的点和所有的边。

复制所有点。
看点上有什么边，然后复制的点连过去。【注意，边都是有两个方向的~】

133.2 代码

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> neighbors;

    Node() {
        val = 0;
        neighbors = vector<Node*>();
    }

    Node(int _val) {
        val = _val;
        neighbors = vector<Node*>();
    }

    Node(int _val, vector<Node*> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
};
*/

class Solution {
public:
    // 原点和克隆点之间的对应关系
    unordered_map<Node*, Node*> hash;

    Node* cloneGraph(Node* node) {
        if (!node) return NULL;
        dfs(node);  // 复制所有点

        for (auto [s, d]: hash) {
            // 原点的所有边。
            for (auto ver: s->neighbors)
            // 复制所有边~、
                d->neighbors.push_back(hash[ver]);
        }

        return hash[node];
    }

    void dfs(Node* node) {
        hash[node] = new Node(node->val);

        for (auto ver: node->neighbors)
            // 如果邻居还没有被遍历到~
            if (hash.count(ver) == 0)
                dfs(ver);
    }
};

作者：yxc
链接：https://www.acwing.com/activity/content/code/content/400699/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

134. 加油站

在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。

你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。

给定两个整数数组 gas 和 cost ，如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则保证它是唯一的。

示例 1:

输入: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
输出: 3
解释:
从 3 号加油站(索引为 3 处)出发，可获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油
开往 4 号加油站，此时油箱有 4 - 1 + 5 = 8 升汽油
开往 0 号加油站，此时油箱有 8 - 2 + 1 = 7 升汽油
开往 1 号加油站，此时油箱有 7 - 3 + 2 = 6 升汽油
开往 2 号加油站，此时油箱有 6 - 4 + 3 = 5 升汽油
开往 3 号加油站，你需要消耗 5 升汽油，正好足够你返回到 3 号加油站。
因此，3 可为起始索引。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/gas-station
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

134.1 思路

转一圈，不会出现油量小于0的情况，
可以用单调队列的做法O（n）

枚举加优化。
从第i个站开始走，最多走到第j个站。那么从i~j之间的第k个站开始走也是肯定走不通的。所以每个站点只会遍历一次，所以时间复杂度O（n）

有个技巧，环拼接一下，任何一个长度为n的也可以表示成一环。求长度为n的窗口的最小值是否小于0.

134.2 代码

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int n = gas.size();
        for (int i = 0, j; i < n; ) {  // 枚举起点
            // 剩余油量。
            int left = 0;
            for (j = 0; j < n; j ++ ) {
                int k = (i + j) % n;
                // 补油加消耗油量。
                left += gas[k] - cost[k];
                if (left < 0) break;
            }
            if (j == n) return i;
            i = i + j + 1;
        }

        return -1;
    }
};

作者：yxc
链接：https://www.acwing.com/activity/content/code/content/400723/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

135. 分发糖果

n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。

你需要按照以下要求，给这些孩子分发糖果：

每个孩子至少分配到 1 个糖果。
相邻两个孩子评分更高的孩子会获得更多的糖果。
请你给每个孩子分发糖果，计算并返回需要准备的最少糖果数目。

示例 1：

输入：ratings = [1,0,2]
输出：5
解释：你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/candy
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

135.1 思路

fi的最小值，往两边走，最多走si步，fi就至少是多少。

135.2 代码

class Solution {
public:
    // f表示的是最小的步数。
    vector<int> f;
    // 小朋友的分值。
    vector<int> w;
    int n;

    int candy(vector<int>& ratings) {
        n = ratings.size();
        w = ratings;
        f.resize(n, -1);

        int res = 0;
        // 所有f
        for (int i = 0; i < n; i ++ ) res += dp(i);
        return res;
    }

    int dp(int x) {
        // 记忆化搜索。
        if (f[x] != -1) return f[x];
        // 最少分一个糖果。
        f[x] = 1;
        // 看两边~。、
        if (x && w[x - 1] < w[x]) f[x] = max(f[x], dp(x - 1) + 1);
        if (x + 1 < n && w[x + 1] < w[x]) f[x] = max(f[x], dp(x + 1) + 1);
        return f[x];
    }
};

作者：yxc
链接：https://www.acwing.com/activity/content/code/content/400742/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

136. 只出现一次的数字

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗？

示例 1:

输入: [2,2,1]
输出: 1

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/single-number
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

136.1 思路

异或运算：交换律+结合律
x^x = 0 x^0 =x

136.2 代码

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

137. 只出现一次的数字II

给你一个整数数组 nums ，除某个元素仅出现一次外，其余每个元素都恰出现三次。请你找出并返回那个只出现了一次的元素。

示例 1：

输入：nums = [2,2,3,2]
输出：3

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/single-number-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

137.1 思路

位运算，一位一位考虑，32位。考虑最终答案的每一位是0还是1.
只有一个数出现了1次，其他出现的都是三次。

两位数字表示状态，one是个位，two是十位。

列真值表，有通法可以变成表达式，然后表达式化解。

自动机，编码状态，看真值表，表达式。

137.2 代码

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

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

给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。

构造这个链表的深拷贝。深拷贝应该正好由 n 个全新节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点。

例如，如果原链表中有 X 和 Y 两个节点，其中 X.random —> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random —> y 。

返回复制链表的头节点。

用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：

val：一个表示 Node.val 的整数。
random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。
你的代码只接受原链表的头节点 head 作为传入参数。

示例 1：

输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/copy-list-with-random-pointer
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

138.1 思路

可以开哈希表，像克隆图一样，先复制点，再克隆边。

开小弟
复制random
拆分链表

138.2 代码
```java / // Definition for a Node. class Node { public: int val; Node next; Node* random;

Node(int _val) {
```
 val = _val;
 next = NULL; 
 random = NULL;
```
} }; */

class Solution { public: Node copyRandomList(Node head) { for (auto p = head; p; p = p->next->next) { // 复制一个小弟 auto q = new Node(p->val); q->next = p->next; p->next = q; }

    // 复制random指针
    for (auto p = head; p; p = p->next->next)
        if (p->random)
            p->next->random = p->random->next;

    // 拆分两个链表
    auto dummy = new Node(-1), cur = dummy;
    for (auto p = head; p; p = p->next) {
        auto q = p->next;
        cur = cur->next = q;
        p->next = q->next;
    }
    return dummy->next;
}

};

作者：yxc 链接：https://www.acwing.com/activity/content/code/content/400796/ 来源：AcWing 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

<a name="dFAXG"></a>
# 139.单词拆分
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。

注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。



示例 1：

输入: s = "leetcode", wordDict = ["leet", "code"]<br />输出: true<br />解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。

来源：力扣（LeetCode）<br />链接：[https://leetcode.cn/problems/word-break](https://leetcode.cn/problems/word-break)<br />著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
<a name="MomEt"></a>
## 139.1 思路

<a name="rmXwc"></a>
## 139.2 代码
```java
class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        typedef unsigned long long ULL;
        const int P = 131;
        unordered_set<ULL> hash;
        for (auto& word: wordDict) {
            ULL h = 0;
            for (auto c: word) h = h * P + c;
            hash.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 (hash.count(h)) f[j] = true;
                }
            }

        return f[n];
    }
};
class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        typedef unsigned long long ULL;
        unordered_set<ULL> S;
        const int P = 131;

        for (auto& word: wordDict) {
            ULL h = 0;
            for (auto c: word) h = h * P + c;
            S.insert(h);
        }

        int n = s.size();
        vector<bool> f(n + 1);
        f[n] = true;

        for (int i = n - 1; i >= 0; i -- ) {
            ULL h = 0;
            for (int j = i; j < n; j ++ ) {
                h = h * P + s[j];
                if (S.count(h) && f[j + 1]) {
                    f[i] = true;
                    break;
                }
            }
        }

        return f[0];
    }
};

作者：yxc
链接：https://www.acwing.com/activity/content/code/content/400818/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

140. 单词拆分II

给定一个字符串 s 和一个字符串字典 wordDict ，在字符串 s 中增加空格来构建一个句子，使得句子中所有的单词都在词典中。以任意顺序返回所有这些可能的句子。

注意：词典中的同一个单词可能在分段中被重复使用多次。

示例 1：

输入:s = “catsanddog”, wordDict = [“cat”,”cats”,”and”,”sand”,”dog”]
输出:[“cats and dog”,”cat sand dog”]

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/word-break-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

140.2 代码

class Solution {
public:
    vector<bool> f;
    vector<string> ans;
    unordered_set<string> hash;
    int n;

    vector<string> wordBreak(string s, vector<string>& wordDict) {
        n = s.size();
        f.resize(n + 1);
        for (auto word: wordDict) hash.insert(word);
        f[n] = true;
        for (int i = n - 1; ~i; i -- )
            for (int j = i; j < n; j ++ )
                if (hash.count(s.substr(i, j - i + 1)) && f[j + 1])
                    f[i] = true;

        dfs(s, 0, "");
        return ans;
    }

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

作者：yxc
链接：https://www.acwing.com/activity/content/code/content/400839/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

Week8 131~140

131.分割回文串

131.1 思路

131.2 代码

132、分割回文串II

132.1 思路

132.2 代码

133.克隆图

133.1 思路

133.2 代码

134. 加油站

134.1 思路

134.2 代码

135. 分发糖果

135.1 思路

135.2 代码

136. 只出现一次的数字

136.1 思路

136.2 代码

137. 只出现一次的数字II

137.1 思路

137.2 代码

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

138.1 思路

138.2 代码

140. 单词拆分II

140.2 代码