leetcode 647 771

leetcode 647题 771题

leetcode 647题 题目:

给定一个字符串,你的任务是计算这个字符串中有多少个回文子串。

具有不同开始位置或结束位置的子串,即使是由相同的字符组成,也会被计为是不同的子串。

示例1:

  输入: “abc”

  输出: 3

  解释: 三个回文子串: “a”, “b”, “c”.

示例2:

  输入: “aaa”

  输出: 6

  说明: 6个回文子串: “a”, “a”, “a”, “aa”, “aa”, “aaa”.

解答1(复杂度高的版本):
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
var countSubstrings = function(s) {
var count = s.length;
for(var len=2;len<=s.length;len++){
for(var i=0;i<=s.length-len;i++){
var subStr = s.substr(i,len);
if(judge(subStr)){
count++;
}
}
}
return count;
};

//首先判断一个字符串是否为回文子串
function judge(s){
var s = s.split('');
if(s.length==1){
return true;
}
for(var i=0;i<parseInt(s.length/2);i++){
if(s[i]!=s[s.length-1-i]){
return false;
}
}
return true;
}
解答2(复杂度低的版本):
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
var countSubstrings = function(s) {
var count = 0;
for(var i=0;i<=s.length;i++){
count += countSinglePoint(s,i,i);//计算子串长度为奇数对应的回文子串个数
count += countSinglePoint(s,i,i+1);//计算子串长度为偶数对应的回文子串个数
}
return count;
};
function countSinglePoint(s,i,j){
var num = 0;
while(i>=0&&j<s.length&&s[i]==s[j]){
i--;
j++;
num++;
}
return num;
}

leetcode771题题目:

给定字符串J 代表石头中宝石的类型,和字符串 S代表你拥有的石头。 S 中每个字符代表了一种你拥有的石头的类型,你想知道你拥有的石头中有多少是宝石。

J 中的字母不重复,J 和 S中的所有字符都是字母。字母区分大小写,因此”a”和”A”是不同类型的石头。

示例1:

  输入: J = “aA”, S = “aAAbbbb”

  输出: 3

示例2:

  输入:J = “z”, S = “ZZ”

  输出:0

解答1:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
var numJewelsInStones = function(J, S) {
var str1 = J.split('');
var str2 = S.split('');
var count = 0;
for(var i=0;i<str2.length;i++){
for(var j=0;j<str1.length;j++){
if(str2[i]==str1[j]){
count++;
break;
}
}
}
return count;
};
解答2:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var numJewelsInStones = function(J, S) {
var str1 = J.split('');
var str2 = S.split('');
var obj = {};
var count = 0;
for(var i=0;i<str1.length;i++){
obj[str1[i]] = 1;
}
for(var j=0;j<str2.length;j++){
if(obj[str2[j]]==1){
count++;
}
}
return count;
}
解答3:
1
2
3
4
5
var numJewelsInStones = function(J, S) {
var str1 = J.split('');
var str2 = S.split('');
return str2.filter(item=>str1.includes(item)).length;
}

taylor swift

分享到