leetcode-136-139-141

leetcode136题139题141题

leetcode136题(只出现一次的数字):

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

示例:

输入:[2,2,1]

输出:1

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

输出:4

解答:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
//方法1
var singleNumber = function(nums) {
for(var i=0;i<nums.length;i++){
if(nums.indexOf(nums[i])==nums.lastIndexOf(nums[i])){
return nums[i];
}
}
};
//方法2
var singleNumber = function(nums) {
obj = {};
for(var i=0;i<nums.length;i++){
if(obj[nums[i]]==undefined){
obj[nums[i]]=1;
}else{
obj[nums[i]]++;
}
}
for(var prop in obj){
if(obj[prop]==1){
return prop;
}
}
};
//方法3
var singleNumber = function(nums) {
var ans = 0;
for(var i=0;i<nums.length;i++){
ans = ans^nums[i];//一个数与0异或得到自己,与自己异或得到零(因此出现两次的自己与自己异或之后得到0)
}
return ans;
};

leetcode139题(单词拆分):

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

说明:

  • 拆分时可以重复使用字典中的单词。

  • 你可以假设字典中没有重复的单词

示例:

输入: s = “leetcode”, wordDict = [“leet”, “code”]
输出: true
解释: 返回 true 因为 “leetcode” 可以被拆分成 “leet code”。

输入: s = “applepenapple”, wordDict = [“apple”, “pen”]
输出: true
解释: 返回 true 因为 “applepenapple” 可以被拆分成 “apple pen apple”。
注意你可以重复使用字典中的单词。

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

解答(动态规划):
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var wordBreak = function(s, wordDict) {
var dp = [];//代表以该下标之前的字符串是否可由字典表组成
dp[0] = true;
for(var i=1;i<=s.length;i++){
dp[i] = false;
}
for(var i=1;i<=s.length;i++){
for(var j=0;j<i;j++){
if(dp[j]&&(wordDict.indexOf(s.slice(j,i))!=-1)){
dp[i] = true;
break;
}
}
}
return dp[s.length];
};

leetcode141题(环形链表):

给定一个链表,判断链表中是否有环。

为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。

示例:

示例

示例

解答(可参考142题):
1
2
3
4
5
6
7
8
9
10
11
12
var hasCycle = function(head) {
var slow = head;
var fast = head;
while(fast!=null&&fast.next!=null){
slow = slow.next;
fast = fast.next.next;
if(slow==fast){
return true;
}
}
return false;
};
分享到