小奥的学习笔记

  • 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]题目解析(190425)

2019年5月13日 912点热度 0人点赞 0条评论

Remove Duplicates from sorted Array II

题目描述

Follow up for "Remove Duplicates":
What if duplicates are allowed at most twice?For example,
Given sorted array A =[1,1,1,2,2,3],Your function should return length =5, and A is now[1,1,2,2,3].

题目解析

类似于Remove Duplicates from sorted Array,但是这个题目要求重复的数字要保留两位。所以做适当修改即可。

代码实现

    int removeDuplicates(int A[], int n) {
        if(n<=2)
            return n;
        int count=2;
        for(int i=2;i<n;i++)
        {
            if(A[i]!=A[count-2])
                A[count++]=A[i];
        }
        return count;
    }

Sqrx

题目说明

求一个数字的平方根

题目解析

利用牛顿逼近法。

代码实现

    int sqrt(int x) {
        long r=x;
        while(r*r>x)
            r=(r+x/r)/2;
        return r;
    }

Length of last word

题目描述

Given a string s consists of upper/lower-case alphabets and empty space characters' ', return the length of last word in the string.If the last word does not exist, return 0.Note: A word is defined as a character sequence consists of non-space characters only.For example, 
Given s ="Hello World",
return5.

题目解析

这个题的关键就是抓住最后一个单词有什么特征,最后一个单词一定是它的前面有一个单词和空格,而后面没有单词(本题允许最后有空格),所以我们可以根据这个特点,很容易想到两种复杂度为O(n)的解题方法。第一种是最容易想到的,也就是从前往后走的方法,这个方法我们可以走这样的路子:判断当前字符不是空格,就对计数加1,如果是空格,就把计数重新置0,然后再开始计数。如果最后一个字符是空格怎么办呢?那我们就可以考虑空格是最后一个字符与不是一个字符时的区别:

情况 是最后一个字符 不是最后一个字符
s[i] ‘ ’ ‘ ’
s[i+1 '\0' 某个字符

所以可以基于上面这两个条件来进行判断,即若s[i]=' '且s[i+1]!='\0'的时候,那就是中间的空格符,所以可以计数置零。具体见代码1。

还有一种思路就是从后往前走,因为题目要求的是最后一个单词,所以在一般情况下,这种方法的时间都要快于第一种方法,特别是语句中单词特别多的时候。这种思路就是直接寻找除了最后一个字符位置之外第一个空字符的位置,得到这个位置后直接break即可。所以这个方法的步骤就是:

  • 不断对计数加1,直到遇到第1个空格。
  • 然后判断此时count是否为0,若为0,说明空格是最后一个字符,所以循环不跳出,继续进行;若count不为零,说明第一个单词已经结束,直接break跳出,返回count。

代码实现1

int lengthOfLastWord(const char *s) {

       if (s == nullptr)
              return 0;
       int count = 0;
       int len = strlen(s);
       for (int i = 0; i < len; i++)
       {
              if (s[i] != ' ')
                     ++count;
              else if (s[i] == ' '&&s[i + 1] != '\0')
                     count = 0;
              else
                     break;
       }
       return count;
}

代码实现2

    int lengthOfLastWord(const char *s) {
    if (s == nullptr)
        return 0;
    int count = 0;
    int len = strlen(s);
    for (int i = len - 1; i >= 0; i--)
    {
        if (s[i] != ' ')
            ++count;
        else
            if(count)
                break;
    }
    return count;
    }
本作品采用 知识共享署名 4.0 国际许可协议 进行许可
标签: leetcode
最后更新:2019年5月13日

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:一种基于深度滤波的全频带音频低复杂度语音增强框架
《我们在一中的日子》正式发布 AEC个人学习串讲之AEC3:时延对齐、线性处理、非线性处理 奥特曼历史介绍1:TV版 在Windows10+VS2019环境下编译Opus 论文阅读之Study of the General Kalman Filter for Echo Cancellation 2009 S.V Beijing Travel 23~25:杂谈
标签聚合
linux Python 生活 高中 python学习 算法 leetcode 学习 Java 鸟哥的linux私房菜
最近评论
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号