2019-11-19  84 views 评论

Leetcode题目解析(191119):136&137&139

 标签:

Leetcode 136:只出现一次的数字

题目描述

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

说明:

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

示例

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

解题思路

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

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

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

代码实现

复杂度

运行时间

时间复杂度: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/

代码实现

复杂度分析

运行时间
时间复杂度 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分解为s1s2,然后这两个是独立的问题,同时s1和s2又可以继续拆分下去。所以说这符合动态规划的条件。

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

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

代码实现

复杂度

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

给我留言

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: