【LeetCode Solutions】LeetCode 136 ~ 140 题解

LeetCode 136. 只出现一次的数字（简单）

【题目描述】

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

你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

【示例 1】

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

【示例 2】

输入：nums = [4,1,2,1,2]
输出：4

【示例 3】

输入：nums = [1]
输出：1

【提示】

$1<=nums.length<=3\ast 10^4$
$-3\ast 10^4<=nums[i]<=3\ast 10^4$
除了某个元素只出现一次以外，其余每个元素均出现两次。

【分析】

本题是很经典的一道考察异或运算性质的题，异或运算具有以下常用性质：

• 交换律：a ^ b = b ^ a；
• 结合律：(a ^ b) ^ c = a ^ (b ^ c)；
• 自反性：a ^ a = 0；
• 恒等性：a ^ 0 = a。

本题只有一个数出现了一次，其余所有数都出现了两次，因此讲所有相同的数配对进行异或运算后结果全部为 0，0 再与剩下那个唯一一个只出现了一次的数异或后就等于这个数本身，所以遍历一遍数组并不断进行异或运算，最后异或出来的结果就是只出现了一次的数。

【代码】

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        for (int i = 1; i < nums.size(); i++) nums[i] ^= nums[i - 1];
        return nums.back();
    }
};

LeetCode 137. 只出现一次的数字 II（中等）

【题目描述】

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

你必须设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题。

【示例 1】

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

【示例 2】

输入：nums = [0,1,0,1,0,1,99]
输出：99

【提示】

$1<=nums.length<=3\ast 10^4$
$-2^{31}<=nums[i]<=2^{31}-1$
nums 中，除某个元素仅出现一次外，其余每个元素都恰出现三次

【分析】

本题还是用位运算，但是思维非常有跳跃性，直接学一下做法就行。

设只出现了一次的数为 $a$，我们只需要知道所有数按位加在一起后每一位为 1 的数量是多少就行，设某一位为 1 的数量为 $k$，若 $k\%3=0$，说明 $a$ 这一位为 0，因为任何其他该位为 1 的数出现次数都是 3 次，如果 $a$ 这一位也是 1，最后该位为 1 的总数一定不是 3 的倍数，即 $k\%3=1$。

对于某一位为 1 的数量 $k$，我们可以构造一种状态机，有以下三种状态：

• $k\%3=0$：用状态 0 来描述，如果该位下一次来的是 0，则保持在这个状态，如果是 1，则转到状态 1；
• $k\%3=1$：用状态 1 来描述，如果该位下一次来的是 0，则保持在这个状态，如果是 1，则转到状态 2；
• $k\%3=2$：用状态 2 来描述，如果该位下一次来的是 0，则保持在这个状态，如果是 1，则转到状态 0；

然后用两位（bit）的数来表示这三个状态，状态转移方式很具有跳跃性，设高位为 $x$，低位为 $y$，当前来的数为 $z$，则状态转移的计算公式如下（注意要先算低位再算高位）：

• 00：如果来的数是 0，则：y = (y ^ z) & (~x) = (0 ^ 0) & (1) = 0，x = (x ^ z) & (~y) = (0 ^ 0) & (1) = 0，转到状态 00；如果来的数是 1，则：y = (0 ^ 1) & (1) = 1，x = (0 ^ 1) & (0) = 0，转到状态 01。
• 01：如果来的数是 0，则：y = (1 ^ 0) & (1) = 1，x = (0 ^ 0) & (0) = 0，转到状态 01；如果来的数是 1，则：y = (1 ^ 1) & (1) = 0，x = (0 ^ 1) & (1) = 1，转到状态 10。
• 10：如果来的数是 0，则：y = (0 ^ 0) & (0) = 0，x = (1 ^ 0) & (1) = 1，转到状态 10；如果来的数是 1，则：y = (0 ^ 1) & (0) = 0，x = (1 ^ 1) & (1) = 0，转到状态 00。

用代码实现的时候 $x$ 与 $y$ 的位数和数组元素的位数一样，这样能同时并行处理每一位，最终的答案也就是 $a$ 只要某一位为 1 那么那一位最终的状态一定停在状态 1，也就是 $y$ 的对应位为 1，$x$ 的对应位为 0 的状态，同理若 $a$ 的某一位为 0，那么该位的最终状态一定是状态 0，也就是 $y$ 的对应位为 0，因此其实 $y$ 就等于 $a$。

【代码】

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

LeetCode 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\sim 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]]

【示例 2】

输入：head = [[1,1],[2,1]]
输出：[[1,1],[2,1]]

【示例 3】

输入：head = [[3,null],[3,0],[3,null]]
输出：[[3,null],[3,0],[3,null]]

【提示】

$0<=n<=1000$
$-10^4<=Node.val<=10^4$
Node.random 为 null 或指向链表中的节点。

【分析】

和 LeetCode 133. 类似，我们需要复制所有的节点以及所有的边，可以采用之前的那种做法，先复制所有点，用哈希表维护原点与克隆点的映射关系，然后再遍历一遍哈希表，将对应的指针再复制一遍即可。

本题的链表相比之前的克隆图更特殊，可以不用开哈希表做，我们将每个克隆点接在原点的后面，这样其实也能实现映射关系，每个点的克隆点就是其 next 指针指向的点。

【代码】

【哈希表】

/*
// 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:
    unordered_map<Node*, Node*> hash;

    Node* copyRandomList(Node* head) {
        if (!head) return nullptr;
        dfs(head);
        for (const auto &[k, v]: hash) {
            if (k->next) v->next = hash[k->next];
            if (k->random) v->random = hash[k->random];
        }
        return hash[head];
    }

    void dfs(Node* u) {
        hash[u] = new Node(u->val);
        if (u->next) dfs(u->next);
    }
};

【原地操作】

/*
// 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 (Node* p = head; p; p = p->next->next) {  // 因为会在后面复制点，因此每次需要向后移动两次指针
            Node* node = new Node(p->val);
            node->next = p->next;
            p->next = node;
        }

        // 复制 random 指针
        for (Node* p = head; p; p = p->next->next)
            if (p->random) p->next->random = p->random->next;  // p->random 不为空才需要处理

        // 分离两个链表，将原链表恢复到初始状态
        Node *dummy = new Node(-1), *cur = dummy;
        for (Node* p = head; p; p = p->next) {
            cur = cur->next = p->next;
            p->next = p->next->next;
        }
        return dummy->next;
    }
};

LeetCode 139. 单词拆分（中等）

【题目描述】

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。

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

【示例 1】

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

【示例 2】

输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。
     注意，你可以重复使用字典中的单词。

【示例 3】

输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false

【提示】

$1<=s.length<=300$
$1<=wordDict.length<=1000$
$1<=wordDict[i].length<=20$
s 和 wordDict[i] 仅由小写英文字母组成
wordDict 中的所有字符串互不相同

【分析】

看到这个数据范围就知道不是用爆搜去做，做法和 LeetCode 132. 一样，可以用动态规划求解。

• 状态表示：$f[i]$ 表示 s[1, i]（设下标从 1 开始）的所有合法划分方案的集合是否非空。
• 状态计算：划分最后一个单词的分割方式，即枚举 $j(1\le j\le i)$，将 s[j, i] 作为当前划分的最后一个单词，那么如果满足 s[j, i] 在字典中且 s[1, j - 1] 的所有合法划分方案不为空（也就是 f[j - 1]），那么当前这种情况也是一个合法划分方案，即 f[i] = true。

如果使用 substr() 函数获取子串，并用 unordered_set<string> 判断单词是否在字典中，这样时间复杂度是 $O(n)$ 的，库函数的哈希表只有判断整数时效率为 $O(1)$。可以通过 Trie 树或手写字符串哈希（将字符串映射为一个整数）将这一步操作的时间复杂度优化成 $O(1)$。

【代码】

【字符串哈希表】

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> st;
        for (string word: wordDict) st.insert(word);
        int n = s.size();
        s = ' ' + s;
        vector<bool> f(n + 1);
        f[0] = true;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= i; j++)
                if (st.count(s.substr(j, i - j + 1)) && f[j - 1]) {
                    f[i] = true;
                    break;
                }
        return f[n];
    }
};

【手写字符串哈希】

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        typedef unsigned long long ULL;  // 用 ULL 就不用将哈希值对 2^64 取模了
        unordered_set<ULL> st;
        for (string word: wordDict) {
            ULL h = 0;
            for (int i = word.size() - 1; i >= 0; i--)  // 为了方便后面枚举 j 时计算哈希值所以倒着计算
                h = h * 131 + word[i];
            st.insert(h);
        }
        int n = s.size();
        s = ' ' + s;
        vector<bool> f(n + 1);
        f[0] = true;
        for (int i = 1; i <= n; i++) {
            ULL h = 0;
            for (int j = i; j > 0; j--) {  // 从后往前枚举，能边枚举边计算哈希值
                h = h * 131 + s[j];
                if (st.count(h) && f[j - 1]) {
                    f[i] = true;
                    break;
                }
            }
        }
        return f[n];
    }
};

LeetCode 140. 单词拆分 II（困难）

【题目描述】

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

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

【示例 1】

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

【示例 2】

输入:s = "pineapplepenapple", wordDict = ["apple","pen","applepen","pine","pineapple"]
输出:["pine apple pen apple","pineapple pen apple","pine applepen apple"]
解释: 注意你可以重复使用字典中的单词。

【示例 3】

输入:s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
输出:[]

【提示】

$1<=s.length<=20$
$1<=wordDict.length<=1000$
$1<=wordDict[i].length<=10$
s 和 wordDict[i] 仅有小写英文字母组成
wordDict 中所有字符串都不同

【分析】

本题和上一题也差不多，需要求出所有方案，因此直接爆搜就行。

【代码】

class Solution {
public:
    typedef unsigned long long ULL;
    unordered_set<ULL> st;
    vector<string> res;

    vector<string> wordBreak(string s, vector<string>& wordDict) {
        for (string word: wordDict) {
            ULL h = 0;
            for (char c: word) h = h * 131 + c;
            st.insert(h);
        }
        dfs(s, 0, "");
        return res;
    }

    void dfs(string& s, int u, string path) {
        if (u == s.size()) {
            path.pop_back();  // 去掉末尾的空格
            res.push_back(path);
            return;
        }
        ULL h = 0;
        for (int i = u; i < s.size(); i++) {
            path += s[i];
            h = h * 131 + s[i];
            if (st.count(h)) dfs(s, i + 1, path + ' ');
        }
    }
};