小奥的学习笔记

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

2019年7月2日 960点热度 0人点赞 0条评论

leetcode9: Palindrome(回文数)

题目描述

判断一个整数是否是回文数。

题目解析

我们通过观察可以看出,回文数有以下两种类型:ABA和ABBA。所以本质上它们都还是镜像对称的,所以可以想到一个结构,就是队列。我们可以把数字以中间位为对称轴拆成两部分,然后做下面这几步:

  1. 按顺序将对称轴右侧的几位push到一个queue里面(比如上面中的A/BA,剩下的就是AB/AB)。
  2. 然后判断这个数字的长度是奇数还是偶数,若是偶数,直接到下一步,若是奇数,操作x /=10,也就是把对称轴删掉(这样X剩下的就是A/AB了)。
  3. 然后将queue里面的数字按pop的顺序连起来,判断与原来那个数字剩下的几位是否相等,若相等就是回文数。

代码实现

    bool isPalindrome(int x) {
    if (x < 0)
        return false;
    queue<int> tmp;
    int len = 0;
    int copy = 0;
    //1.计算数字的长度
    for (int i = x; i; i /= 10)
        ++len;
    //2.按顺序将对称轴右侧的push到queue中。
    for (int j = len / 2; j > 0; --j)
    {
        tmp.push(x % 10);
        x /= 10;
    }
    //3.若是奇数,则提取出来对称轴前面的数字
    if (len % 2 == 1)
        x /= 10;
    //4.把pop出来的数字连起来
    for (int j = len / 2; j > 0; j--)
    {
        copy = copy * 10 + tmp.front();
        tmp.pop();
    }
    //5.与x剩下的部分对比
    if (copy == x)
        return true;
    else
        return false;
}

Leetcode 1:Two sum

题目描述

Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

代码解析

代码实现

vector<int> twoSum(vector<int> &numbers, int target) {
    vector<int>result;
    int nlen = numbers.size();
    if (nlen < 2)
        return result;
    vector<int>num;
    for (int i = 0; i < nlen; i++)
    {
        num.push_back(numbers[i]);
    }
    sort(numbers.begin(), numbers.end());
    int i = 0, j = nlen - 1,tmp1=INT_MIN,tmp2=INT_MIN;
    while (i < j)
    {
        if (numbers[i] + numbers[j] == target)
        {
            tmp1 = numbers[i];
            tmp2 = numbers[j];
            break;
        }
        else if (numbers[i] + numbers[j] < target)
            ++i;
        else if (numbers[i] + numbers[j] > target)
            --j;
    }
    for (int k = 0; k < nlen; k++)
    {
        if (num[k] == tmp1)
        {
            result.push_back(k + 1);
            continue;
        }

        if (num[k] == tmp2)
            result.push_back(k+1);
    }
    sort(result.begin(), result.end());
    return result;
}

代码2:

    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int>res(2,-1);
        map<int,int> tmp;
        for(int i=0;i<nums.size();i++)
        {
            if(tmp.count(target-nums[i]))
            {
                res[0]=tmp[target - nums[i]];
                res[1]=i;
                break;
            }
            tmp[nums[i]]=i;
        }
        return res;
    }

Leetcode 50:计算x的n次幂

题目描述

实现pow(x,n),即计算x的n次幂函数。

题目解析

在剑指offer之中,我们可以使用二进制移位来实现相应的功能,但实际上,当数字过大的时候,这个方法已经不能使用了。这个时候我们可以用二分法。步骤如下:

  1. 依旧是先判断n是不是小于零,若是,令x等于原来的倒数,n变为原来的绝对值;否则不变,然后进入第2步。
  2. 执行一个fastPow()函数,这个函数是递归调用执行。首先如果此时n=0了,那么自然结果就是1.0;然后递归调用half=fastPow(x,n/2),这实际上就是计算x的n/2次方的结果,然后这个时候判断n是奇数还是偶数,如果是偶数,那自然x的n次方就等于x的n/2次方乘x的n/2次方;如果是奇数,则结果就等于x的n次方就等于x的n/2次方乘x的n/2次方再乘x。

代码实现

double fastPow(double x, long long n)
{
    if (n == 0)
        return 1.0;
    double half = fastPow(x, n / 2);
    if (n % 2 == 0)
        return half*half;
    else
        return half*half*x;
}

double myPow(double x, int n) {
    if (x == 1.0)
        return x;
    if (n == 0)
        return 1.0;
    long long N = n;
    if (N < 0)
    {
        x = 1 / x;
        N = -N;
    }
    return fastPow(x, N);
}

leetcode 69:x的平方根(sqrt of x)

题目描述

实现int sqrt(int x)函数,计算并返回x的平方根,其中x是非负整数。由于返回类型是整数,所以结果只保留整数部分,将小数部分舍去。

题目解析

所以我们要做的事情就是让这个x(n+1)不断逼近x。由于只要求保留到整数,所以误差可以选择大一点,比如误差到0.5就可以结束逼近了。所以代码实现如下。

代码实现

int mySqrt(int x) {
    if(x<0)
        return -1;
    double res=1.0;
    if(x==0||x==1)
        return x;
    while(fabs(res*res-x)>0.5)
    {
        res=(res+x/res)/2;
    }
    return int(res);

}
本作品采用 知识共享署名 4.0 国际许可协议 进行许可
标签: 暂无
最后更新:2019年7月2日

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:一种基于深度滤波的全频带音频低复杂度语音增强框架
2015.1—2015.3【寒假】的计划(证书考试)安排 计算机组成原理笔记第九章 吴恩达深度学习课程 DeepLearning.ai 编程作业(2-2) 元旦竞猜活动开启 通信工程学院关于2020年硕士研究生毕业和学位申请的补充通知 AEC个人学习串讲之AEC3:时延对齐、线性处理、非线性处理
标签聚合
leetcode 算法 Python Java linux 生活 鸟哥的linux私房菜 高中 学习 python学习
最近评论
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号