Leetcode 136：只出现一次的数字

题目描述

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

说明：

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

示例

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

解题思路

这里我们可以利用异或的原理，我们发现在异或中：

a⊕0=a；a⊕a=0。a⊕b⊕a=(a⊕a)⊕b=0⊕b=b

所以我们只需要将所有的数进行 XOR 操作，得到那个唯一的数字。

代码实现

int singleNumber(vector<int>& nums) {
    //if (nums.empty())
    //  return 0;
    for (int i = 1; i < nums.size(); i++)
        nums[0] ^= nums[i];//异或
    return nums[0];
}

复杂度

时间复杂度：O(n)，空间复杂度：没有使用额外的空间。

拓展：Leetcode137（只出现一次的数字2）

题目描述

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。你的算法应该具有线性时间复杂度。 你不可使用额外空间来实现。

解题思路

我们前面的基础上用到了“异或”，它本质上是一种二进制下不考虑进位的加法。所以对于本题，我们可以考虑构造一种三进制下不考虑进位的加法，这种方法存在以下运算规则：假设运算符号为@，则0@1=1,1#1=2,2#1=0。所以在这种运算规则之下，出现3次的数字全部抵消为0，而只留下只出现1次的数字。
所以有以下步骤：
* ones^=num：记录至目前元素num，二进制某位出现1次（当某位出现3次时有ones=1，与twos=1共同表示“出现3次”）。
* twos|=ones&num：记录至目前元素num，二进制某位出现2次（当某位出现2次时，twos=1且ones=0）
* threes=ones&twos：记录至目前元素num，二进制某位出现3次（即当ones和twos对应位同时为1时three=1）。
one&=~threes,two&=~threes：将onestwos中出现了3次的对应位清零，实现“不考虑进位的三进制加法”。

进一步简化：
以上过程本质上是通过构建3个变量的状态转换表来表示对应位的出现次数：使所有数字“相加”后出现3N+1次的位ones=1，出现3N，3N+2次的位为ones=0。由于three其实是ones&twos的结果，因此我们可以舍弃threes，仅使用ones和twos来记录出现次数。

解析转载自：
https://leetcode-cn.com/problems/single-number-ii/solution/single-number-ii-mo-ni-san-jin-zhi-fa-by-jin407891/

代码实现

int singleNumber(vector<int>& nums) {
    //if (nums.empty())
    //  return 0;
    int ones = 0, twos = 0;
    for (int num : nums) {
        ones = ones ^ num & ~twos;
        twos = twos ^ num & ~ones;
    }
    return ones;
}

复杂度分析

时间复杂度 O(n)：遍历一遍 nums 需要线性时间复杂度；
空间复杂度 O(1)：使用常数额外空间。

Leetcode 139：单词拆分

题目描述

给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。

说明：
拆分时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。

示例

示例 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

解题说明

这个题可以想到可以用动态规划的思想。原因是这个问题可以将给定的字符串s分解为s1和s2，然后这两个是独立的问题，同时s1和s2又可以继续拆分下去。所以说这符合动态规划的条件。

我们可以考虑如何进行动态规划求解。既然是分成两个字符串，实际上就是用两个指针i和j，其中i是当前字符串从头开始的子字符串的长度，j是当前字符串的拆分位置，于是字符串就被拆分为了(0,j)和(j+1,i)的区间。然后设置一个一维dp数组，dp数组中的下标代表着字符串结束的下标。

我们在求dp的时候，首先初始化dp[0]=true，剩余元素都初始化为false。我们用下标i来考虑所有从当前字符串开始的可能的字符串。对于每一个字符串，我们用j将它们分解为s1和s2，也就是说只有s1和s2都为true才可以，所以等价于，如果想要求dp[i]，就要看dp[j]（dp[j]代表到字符串下标到j的这个子字符串是否是子串，也就是s1是否是子串）和s2的情况。我们首先看dp[j]是否为true，若是则检查s2，s2实际上是下标(j+1,i)，所以只需要执行find(wordDict.begin(), wordDict.end(), s.substr(j, i - j)) != wordDict.end()即可。这样就完成了整个判断操作。最后返回dp[len]就好了。

代码实现

bool wordBreak(string s, vector<string>& wordDict) {
    int len = s.size();
    if (len == 0 || wordDict.size() == 0)
        return false;
    vector<bool> dp(len + 1, false);
    dp[0] = true;
    for (int i = 1; i <= len; i++)
    {
        for (int j = i - 1; j >= 0; j--) {
            if (dp[j] && find(wordDict.begin(), wordDict.end(), s.substr(j, i - j)) != wordDict.end())
            {
                dp[i] = true;
                break;
            }
        }
    }
    return dp[len];
}

复杂度

时间复杂度：O(n2)，因为两层for循环。
空间复杂度：O(n)，因为使用了长度为n+1的dp数组。