logo头像

不忘初心,奋力前行

leetcode题目解析(191014)

Leetcode 647:回文子串

题目描述

给定一个字符串,你的任务是计算这个字符串中有多少个回文子串。具有不同开始位置或结束位置的子串,即使是由相同的字符组成,也会被计为是不同的子串。

示例

示例 1:

输入: “abc”
输出: 3
解释: 三个回文子串: “a”, “b”, “c”.
示例 2:

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

题目思想

这里我的思路就是分为了两步:第一步提取出该字符串的所有子串;第二步,对每个子串判断是否是回文,若是则计数。最后返回结果。
但是这种方法复杂度太高,因为重复计算了太多。可以使用一种名为中心扩展的方法。这种方法的思路是选定一个点i,然后分别以i及(i,i+1)向两边扩展开始计算。这种扩展的思路就在countNums()函数中得以实现。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int countNums(string& s, int i, int j)
{
if (i > j || i < 0 || j >= s.size())
return 0;
int nums = 0;
while (i >= 0 && j < s.size() && s[i] == s[j])
{
--i;
++j;
++nums;
}
return nums;
}
int countSubstrings(string s)
{
int res = 0;
for (int i = 0; i < s.size(); ++i)
{
res += countNums(s, i, i);
res += countNums(s, i, i + 1);
}
return res;
}

Leetcode 771:宝石与石头

题目描述

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

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

示例

示例 1:输入: J = “aA”, S = “aAAbbbb”
输出: 3
示例 2:输入: J = “z”, S = “ZZ”
输出: 0

题目思想

这个题目思路很简单,我感觉没必要做太多解释。就是说,对于S中的每一个字母,看在J中是否存在,若存在则nums++。

代码实现

1
2
3
4
5
6
7
8
9
int numJewelsInStones(string J, string S) {
int nums = 0;
for (auto s : S)
{
if (J.find(s) != J.npos)//如果能找到这个字母
nums++;
}
return nums;
}
支付宝打赏 微信打赏 QQ钱包打赏

感觉不错?欢迎给我 打个赏~我将不胜感激!