小奥的学习笔记

  • Home
  • Learning & Working
    • Speech Enhancement Notes
    • Programming language
    • Computer & DL
    • MOOC
  • Life
    • Life Time
    • Thinking & Comprehension
    • Volunteer
    • Plan
    • Travel
  • Footprints
  • GuestBook
  • About
    • About Me
    • 个人履历
    • 隐私策略
  1. 首页
  2. Study-notes
  3. Programming language
  4. Algorithm
  5. Leetcode
  6. 正文

[leetcode]题目解析(191014)

2019年10月14日 842点热度 0人点赞 0条评论

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& 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;
}

若代码出现错误,可查看:http://tech.yushuai.xyz/2019/10/15/leetcode191014/

本作品采用 知识共享署名 4.0 国际许可协议 进行许可
标签: leetcode
最后更新:2019年10月14日

davidcheung

这个人很懒,什么都没留下

打赏 点赞
< 上一篇
下一篇 >

文章评论

razz evil exclaim smile redface biggrin eek confused idea lol mad twisted rolleyes wink cool arrow neutral cry mrgreen drooling persevering
取消回复

搜索
欢迎关注我的个人公众号
最新 热点 随机
最新 热点 随机
DEEPFILTERNET:一种基于深度滤波的全频带音频低复杂度语音增强框架 奥地利匈牙利九日游旅程 论文阅读之Study of the General Kalman Filter for Echo Cancellation 小奥看房之鸿荣源珈誉府 杭州往返旅途及西溪喜来登和万怡的体验报告 2022年的第一篇碎碎念
奥地利匈牙利九日游旅程小奥看房之鸿荣源珈誉府论文阅读之Study of the General Kalman Filter for Echo CancellationDEEPFILTERNET:一种基于深度滤波的全频带音频低复杂度语音增强框架
基于python绘制世界人口地图 2014年寒假(C语言程序设计)学习、复习计划及完成情况表 吴恩达深度学习课程 DeepLearning.ai 编程作业(1-4)Part.1 安装IIS报错(0X80240022)的问题解决方案 vivo2019校招笔试题(C++部分题目) 吴恩达深度学习课程DeepLearning.ai笔记(5-1)
标签聚合
鸟哥的linux私房菜 Java 生活 算法 python学习 Python linux leetcode 学习 高中
最近评论
davidcheung 发布于 5 个月前(02月09日) The problem has been fixed. May I ask if you can s...
tk88 发布于 5 个月前(02月07日) Hmm is anyone else having problems with the pictur...
cuicui 发布于 9 个月前(10月20日) :wink:
niming 发布于 10 个月前(09月19日) 同级校友,能刷到太巧了
davidcheung 发布于 2 年前(08月16日) 我得找一下我之前整理的word文档看一下,如果找到了我就更新一下这篇文章。
Nolan 发布于 2 年前(07月25日) 您的笔记非常有帮助。贴图不显示了,可以更新一下吗?
davidcheung 发布于 3 年前(06月19日) 到没有看webrtc的代码。现在主要在看我们公司的代码了。。。只是偶尔看一看webrtc的东西。。。
aobai 发布于 3 年前(03月13日) gain_change_hangover_ 应该是每三个block 只能够调整一次,这样保证每帧...
匿名 发布于 5 年前(12月30日) 烫
小奥 发布于 5 年前(12月12日) webRTC里面的NS本身我记得就是在C++里面呀

COPYRIGHT © 2025 小奥的学习笔记. ALL RIGHTS RESERVED.

Theme Kratos Made By Seaton Jiang

陕ICP备19003234号-1

鲁公网安备37120202000100号