2019-10-14 348 views 评论

[leetcode]题目解析（191014）

标签：leetcode

Leetcode 647：回文子串

题目描述

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

示例

示例 1:

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

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

题目思想

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

代码实现

int countNums(string&amp; s, int i, int j)
{
    if (i &gt; j || i &lt; 0 || j &gt;= s.size())
        return 0;
    int nums = 0;
    while (i &gt;= 0 &amp;&amp; j &lt; s.size() &amp;&amp; s[i] == s[j])
    {
        --i;
        ++j;
        ++nums;
    }
    return nums;
}
int countSubstrings(string s)
{
    int res = 0;
    for (int i = 0; i &lt; s.size(); ++i)
    {
        res += countNums(s, i, i);
        res += countNums(s, i, i + 1);
    }
    return res;
}

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++。

代码实现

int numJewelsInStones(string J, string S) {
    int nums = 0;
    for (auto s : S)
    {
        if (J.find(s) != J.npos)//如果能找到这个字母
            nums++;
    }
    return nums;
}