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数组。
文章评论