tail(head(tail(C)))

求下列运算的结果:#xff08…面试中发现很多同学一股脑优化、润色项目经历但聊到基本的算法反而会一脸懵X得空整理下算法题给大家希望对你有帮助。

tail(head(tail(C)))

不考虑失效的方式就是不连贯的情况那么如果9个点的话排列组合有9362880种比9少的都达不到9的量级在减去失效的也不会跨量级所以是100000的量级。

2.线性表如果要频繁的执行插入和删除操作该线性表采取的存储结构应该是

正确答案:

3.某段文本中各个字母出现的频率分别是{a:4b:3o:12h:7i:10}使用哈夫曼编码则哪种是可能的编码

a(001)

每个字母都代表一个终端节点叶节点比较每个字母的出现频率将最小的两个字母频率相加合成一个新的节点将两个字母从序列中删除将生成的节点加入到字母队列中

重复前面两步直到序列中没有字母为止

----------------(14)------------------(22)

--------------/--------\----------------/-----\

---------/---\

--------------------/-----------------\

------------------/---------------------\

----------------(14)------------------(22)

--------------/--------\----------------/-----\

---------/---\

--------------------/-----------------\

------------------/---------------------\

----------------0(14)------------------1(22)

--------------/--------\----------------/-----\

---------/---\

旅行商问题(TravelingSalesmanProblemTSP)是一个经典的组合优化问题。

经典的TSP可以描述为一个商品推销员要去若干个城市推销商品该推销员从一个城市出发需要经过所有城市后回到出发地。

应如何选择行进路线以使总的行程最短。

从图论

。

由于其在交通运输、电路板线路设计以及物流配送等领域内有着广泛的应用国内外学者对其进行了大量的研究。

早期的研究者使用精确算法求解该问题常用的方法包括分枝定界

法、线性规划

法等。

但是随着问题规模的增大精确算法将变得无能为力因此在后来的研究中国内外学者重点使用近似算法或启发式算法

主要有遗传算法

例如{0,10,110}就是一个前缀码而{0,10,101}就不是前缀码。

{a1,

结点的带权路径长度结点到树根之间的路径长度与该结点上权的乘积。

Path

用邻接矩阵表示图,容易判断任意两个结点之间是否有边相连,并求得各结点的度

若有向图G中从结点Vi到结点Vj有一条路径,则在图G的结点的线性序列中结点Vi,必在结点Vj之前的话,则称为一个拓扑序

正确答案:

哈希表是一个在时间和空间上做出权衡的经典例子。

如果没有内存限制那么可以直接将键

线性表实现相对比较简单

哈希表是一个在时间和空间上做出权衡的经典例子。

如果没有内存限制那么可以直接将键作为数组的索引。

那么所有的查找时间复杂度为O(1)如果没有时间限制那么我们可以使用无序数组并进行顺序查找这样只需要很少的内存。

在平衡二叉树中插入结点要随时保证插入后整棵二叉树是平衡的所以可能需要通过一次或多次树旋转来重新平衡这个树推荐

9.在ASC算法team日常开发中常常面临一些数据结构的抉择令人纠结。

目前大家在策划一个FBI项目Fast

Binary

Indexing其中用到的词汇有6200条词汇长度在10-15之间词汇字符是英文字母区分大小写。

请在下面几个数据结构中选择一个使检索速度最快的

二叉搜索树比较函数开销1次运算/每字符

注解:又称单词查找树Trie树是一种树形结构是一种哈希树的变种。

典型应用是用于统计排序和保存大量的字符串但不仅限于字符串所以经常被搜索引擎系统用于文本词频统计。

它的优点是利用字符串的公共前缀来减少查询时间最大限度地减少无谓的字符串比较查询效率比哈希表高。

Monte

Sherwood算法的主要作用是减少或是消除好的和坏的实例之间的差别

正确答案:

数值概率算法数值问题的求解最优化问题的近似解、蒙特罗卡算法判定问题的准确解不一定正确、拉斯维加斯算法不一定会得到解但得到的解一定是正确解、舍伍德算法总能求得一个解且一定是正确解

前序线索树

后序遍历要稍微复杂一点点在前序和中序遍历的程序中当我们准备进入根结点的右子树时根结点就被扔出栈外了。

但在后序遍历时我们仍需保留它直到右子树处理完毕。

12.关于

对于同一背包与相同的物品做背包问题取得的总价值一定大于等于做01背包问题

正确答案:

next[j]。

此举意味着失配时模式串P相对于文本串S向右移动了j

next

数组各值的含义代表当前字符之前的字符串中有多大长度的相同前缀后缀。

例如如果next

[j]

16.采用二叉链表作为存储结构,树的前序遍历和其相应的二叉树的前序遍历的结果是一样的

正确答案:

树的二叉链表存储时一个结点有两个指针域一个指向它第一个孩子一个指向它第一个兄弟。

而将一般树转换为二叉树时也是一个结点有一个结点有两个指针域一个指向它第一个孩子一个指向它第一个兄弟。

17.

一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同

一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差

关键活动一定位于关键路径上

2如果顶点A-B有弧如果让弧表示为L则A为L的弧尾B为L的弧头即有箭头的那一端叫头。

18.

一个凸N边形可以用N-3条互不相交的对角线将凸N边形分成N-2个三角形这称为凸N边形的一种三角剖分。

例如N5时共有以下5种三角剖分

140

D8(D8\D7)*(D7\D6)*(D6\D5)(22\7)*(3)*(14\5)132

20.已知字符A、B、C、D的使用频率权值分别为227927。

对其进行HUFFMAN编码各字符对应的编码为

A001B100C110

在计算机科学中折半搜索也称二分查找算法、二分搜索是一种在有序数组中查找某一特定元素的搜索算法。

搜素过程从数组的中间元素开始如果中间元素正好是要查找的元素则搜素过程结束如果某一特定元素大于或者小于中间元素则在数组大于或小于中间元素的那一半中查找而且跟开始一样从中间元素开始比较。

如果在某一步骤数组为空则代表找不到。

这种搜索算法每一次比较都使搜索范围缩小一半。

有序线性链表不可以是因为链表的对结点的操作只能通过p-next的方式对下标的操作不适合。

22.当一棵具有n个叶结点的二叉树的WPL值为最小时,称其树为哈夫曼树,且其二叉树的形状必是唯一的

正确答案:

错误。

应为二叉树中节点的左右子树是有序的。

当根据n个叶结点的二叉树的WPL值最小构造树时如果兄弟结点的权值相等形状就不唯一了。

题目描述

数轴上从左到右有n个点a[0],a[1]...a[n-1],给定一根长度为L的绳子求绳子最多能覆盖其中的几个点。

分析与解法

注意每次循环best和i都只增不减尽管两个循环复杂度还是O(n)的。

int

这是因为前(i-1)项的子序列本身以及添加上第i项都是一个子序列这是比较容易的情况。

如果全是这样人生就完美了……因为我们会推出dp[i]

原来的前(j-1)项的子序列末尾添加上第j项和添加上第i项是一样的就这些是重复的。

所以dp[j-1]是重复的。

dp[i]

当Alice取完本轮石子后剩下的石子为3的倍数(3*n)那么无论Bob怎么取Alice都会赢。

简单解释如下

1时即Alice取完后只剩下3颗那么无论Bob怎么取Alice下次取都会取到最后一颗会赢。

1时即Alice取完后剩下3*n颗当Bob取完后剩下的石子数量总可以表示为

3*k1

0)那么此时Alice可以将剩下的石子数重新变为3的倍数如此递推下去。

...

也就是说只要Alice取完后剩下的石子数是3的倍数那么Alice肯定会赢。

//头文件

给一个字符串S只包含R,G,B三种字符起点在S[0]目标走到S[n-1],

G到BB到R

1]最大值的下标。

而这个东西我们可以用前缀、后缀的方法预处理出来。

for

利用LIS的思想因为我们实际上就是要找到一个长度为3的单调子序列那么我们可以用O(nlogn)的LIS思想但是由于长度只维护到3所以没有必要2分而且没有必要用数组保存长度为x的单调子序列的最后一项的最小值用变量存就好了但思路是不变的。

我们这么记录x表示目前为止长度为1的单增子序列最后一项的最小值在数组a中的下标实际上x就是我们刚才那个b数组而y表示目前为止长度为2的单增子序列最后一项的最小值在数组a中的下标。

a[y],

-1表示目前长度为1的单增自序列就是第一项没有长度为2的单增子序列。

同时我们需要维护一个z表示长度为2的单增自序列的首项也就是y之前那一项。

我们从i

我们看一下a[i]

那么我们可以把长度为1的单调子序列最后一项更新一下也就是目前最小值所以更新x

int

一个环形跑道上有若干个储油点。

储油点油的总量刚好够一辆汽车走完一圈。

假设汽车是均匀耗油的并且油箱足够大初始为空。

它可以选择一个储油点为起点装好油沿着环形跑道走下去每到一个储油点就可以装上那里的油。

问是否可以选择这样一个的起点使得让汽车走完一圈回到起点。

分析与解法

如果把每个储油点的油量减去到下一个储油点的耗油量当成一个变量a[i]则我们有

a[1]

1]是前缀的最小值并且假设A0,因为如果A0则从第一个储油点开始走不会出现负数这个储油点就是解了。

我们令Ba[k]

这些前缀必须都是非负数因为如果前缀有一个负数的x的话从a[1]开始的前缀和A

我们再继续

因为从B开始加的那部分就是从a[1]开始的前缀我们知道A是最小的所以这串数的最小值是A

0这就证明了从a[k]开始出发加出来的数不会出现负数。

所以k是一个解。

我们这个算法的时间复杂度是O(n)因为我们只需要自己加一次把和最小的位置找出来就可以了。

另外我们其实并没有规定顺时针还有逆时针行走所以可以分别考虑求出不同方向行驶的出发点。

题目描述

某Hash函数将任一字符串非均匀映射到正整数k概率为2^(-k)即P{Hash()k}2^(-k)。

现有字符串集合S其元素经映射后得到的最大整数为10。

试估计S的元素个数。

提示被映射得到的整数快速衰减“最大整数为10”这一条件可近似考虑为“存在某整数为10”。

分析与解法

某Hash函数将任一字符串非均匀映射到正整数k概率为2-k如下所示。

现有字符串集合S其元素经映射后得到的最大整数为10。

试估计S的元素个数。

问题分析

由于Hash映射成整数是指数级衰减的“最大整数为10”这一条件可近似考虑成“整数10曾经出现”继续近似成“整数10出现过一次”。

字符串被映射成10的概率为p2-101/1024从而一次映射即两点分布

题目描述

那么k1,k2,⋯,kn的最大公约数就是对于x来说最大的可能的b。

也即

x(pk1b1pk2b2⋯pknbn)b

设整数x1x2并且有x1x2d。

由于数组a是一个严格单调递增的整数数组所以必然有a[x1]⩾a[x2]d。

两边同时减去x1即a[x1]−x1⩾a[x2]d−x2−da[x2]−x2。

所以f(x)a[x]−x

那么原问题寻找a[x]x的位置也就变成了查找单调递增函数f(x)0时对应的x。

这样就可以直接使用二分查找来做了时间复杂度为O(logn)

void

二维平面上有一个机器人初始面朝北(N)。

有一个字符串代表它的指令序列commend它只包含4种字符,LRFB。

表示朝左转90度、朝右转90度前进一个单位和退后一个单位。

但是机器人是循环执行指令的即执行完这个字符串后再从第一个字符开始再执行一次如此下去不断执行。

分析与解法

至多5次必然有两次朝向一样的分析这两次实际上有一个位移如果这个位移是0说明他在转圈否则就相当于它不断沿着这个向量方向再走直到无穷远……

33.Two

给定一个整数sum,从有N个有序元素的数组中寻找元素a,b,使得ab的结果最接近sum,最快的平均时间复杂度是多少

分析与解法

1、设定两个指针P1、P2分别指向数组开始和结尾即P1指向最小值P2指向最大值

2、计算

如果数组是无序的先排序n*logn然后用两个指针ij各自指向数组的首尾两端令i0jn-1然后ij--逐次判断a[i]a[j]?sum如果某一刻a[i]a[j]sum则要想办法让sum的值减小所以此刻i不动j--如果某一刻a[i]a[j]

sum则要想办法让sum的值增大所以此刻ij不动。

所以数组无序的时候时间复杂度最终为On*lognnOn*logn。

当然如果原数组是有序的则不需要事先的排序直接On搞定且空间复杂度还是O1。

所以如果有序直接两个指针两端扫描时间ON如果无序先排序后两端扫描时间ON*logNNON*logN空间始终都为O1。

1、对每个a[i]二分查找sum-a[i]是否也在原始序列中若无序则先排序后二分时间复杂度总为On*logn空间复杂度为O1

2、扫描一遍X-S[i]

映射到一个数组或构造hash表时间复杂度为On空间复杂度为On

3、两个指针两端扫描若无序先排序后扫描时间复杂度最后为有序On无序On*lognnOn*logn空间复杂度都为O1。

所以要想达到时间ON空间O1的目标除非原数组是有序的指针扫描法不然当数组无序的话就只能先排序后指针扫描法或二分时间n*logn空间O1或映射或hash时间On空间On。

时间或空间必须牺牲一个自个权衡。

综上若是数组有序的情况下优先考虑两个指针两端扫描法以达到最佳的时ON空O1效应。

否则如果要排序的话时间复杂度最快当然是只能达到N*logN空间O1则是不在话下。

//代码一

下面是折半查找的实现data是按升序排列的数据x是查找下标y是查找的上标

v是查找的数值返回v在data的索引若没找到返回-1。

代码不正确是____。

分析与解法

解析上下标没有写清楚题目所指的应该是[x,y),这样5应该是m-1

而在下标为[x,y]的情况下1,4,5都是有问题的。

。

。

。

正确版本应该是这样吧

while(xy)

补充这里下标是个坑记住上限有没有包含就可以对付1,4,5处的问题熟记理解两个版本的代码区别然后是2写成x(y-x)/2是防止xy都很大的情况下xy越界。

这样的话应对二分查找应该够了

题目描述

一看到数组本身已经有序直观的反应可能是用二分查找算法毕竟二分查找算法的适用条件就是要求数组是有序的。

那么什么是二分查找呢

T要查找的值那么通过不断缩小包含T的数据范围就可以最终找到要找的数T。

其算法流程如下。

2将数组的中间项与T进行比较如果T比数组的中间项小则到数组的前半部分继续查找反之则到数组的后半部分继续查找。

3这样每次查找都可以排除一半元素相当于范围缩小一半。

这样反复比较反复缩小范围最终会在数组中找到T或者确定T不在此数组中。

此时可能有读者心里想不就二分查找嘛太简单了。

但是《编程珠玑》的作者Jon

Bentley曾在贝尔实验室做过一个实验即给一些专业的程序员几个小时的时间用任何一种语言编写二分查找的程序写高级伪代码也可以结果参与编写的一百多个人中90%的程序员写的程序中有bug没发现bug的代码不代表就正确。

也就是说在足够的时间内只有大约10%的专业程序员可以把二分查找写对。

此外高德纳在《计算机程序设计的艺术

第3卷排序和查找》的6.2.1节的“历史与参考文献”中指出虽然早在1946年就有人将二分查找的方法公诸于世但直到1962年才有人写出没有bug的二分查找程序。

实际上要想编写出正确的二分查找程序必须注意到两点一点是判断循环体是否终止的语句的编写另外一点是边界值left、right和区间值这三个地方要保持一致。

关于第二点再详细说明一下。

例如如果令rightn−1则while循环的循环条件为left

right从而更新右边界位置的时候为rightmiddle−1而如果令rightn则while循环的循环条件为left

right从而更新右边界位置的时候为rightmiddle。

同时middle的计算不能写在while循环外否则无法得到更新。

int

求中间位置使用移位的方法是为了防止溢出同时也更高效。

注意每次循环都需要更新

int

可能会有读者认为刚开始时就要判断相等但其实无关紧要毕竟数组中不相等的情况更多

return

假设张三的mp3里有1000首歌现在希望设计一种随机算法来随机播放。

与普通随机模式不同的是张三希望每首歌被随机到的概率是与一首歌的豆瓣评分0~10分成正比的如朴树的《平凡之路》评分为8.9分逃跑计划的《夜空中最亮的星》评分为9.5分则希望听《平凡之路》的概率与《夜空中最亮的星》的概率比为89:95。

分析与解法

scores[]{5.5,6.5,4.5,8.5,9.5,7.5,3.5,5.0,8.0,2.0};

int

nsizeof(scores)/sizeof(scores[0]);

double

段则分割分数一定介于最大值与和之间。

因此采用二分查找每次取一个值对序列进行划分若能划分出

段使得每段的和都小于这个数值则满足划分反之不满足直至找到一个最小的满足划分的值为止。

代码实现如下

最容易想到的办法是枚举所有的子串分别判断其是否为回文。

这个思路初看起来是正确的但却做了很多无用功如果一个长的子串包含另一个短一些的子串那么对子串的回文判断其实是不需要的。

解法一

那么如何高效的进行判断呢我们想想如果一段字符串是回文那么以某个字符为中心的前缀和后缀都是相同的例如以一段回文串“aba”为例以b为中心它的前缀和后缀都是相同的都是a。

那么我们是否可以可以枚举中心位置然后再在该位置上用扩展法记录并更新得到的最长的回文长度呢答案是肯定的参考代码如下

int

在上文的解法一枚举中心位置中我们需要特别考虑字符串的长度是奇数还是偶数所以导致我们在编写代码实现的时候要把奇数和偶数的情况分开编写是否有一种方法可以不用管长度是奇数还是偶数而统一处理呢比如是否能把所有的情况全部转换为奇数处理

答案还是肯定的。

这就是下面我们将要看到的Manacher算法且这个算法求最长回文子串的时间复杂度是线性O(N)的。

首先通过在每个字符的两边都插入一个特殊的符号将所有可能的奇数或偶数长度的回文子串都转换成了奇数长度。

比如

abba

此外为了进一步减少编码的复杂度可以在字符串的开始加入另一个特殊字符这样就不用特殊处理越界问题比如$#a#b#a#。

S[]

来记录以字符S[i]为中心的最长回文子串向左或向右扩张的长度包括S[i]。

接下来怎么计算P[i]呢Manacher算法增加两个辅助变量id和mx其中id表示最大回文子串中心的位置mx则为idP[id]也就是最大回文子串的边界。

得到一个很重要的结论

如果mx

的时候以S[j]为中心的回文子串包含在以S[id]为中心的回文子串中由于i和j对称以S[i]为中心的回文子串必然包含在以S[id]为中心的回文子串中所以必有P[i]

P[j]

的时候以S[j]为中心的回文子串不一定完全包含于以S[id]为中心的回文子串中但是基于对称性可知下图中两个绿框所包围的部分是相同的也就是说以S[i]为中心的回文子串其向右至少会扩张到mx的位置也就是说

P[i]

此Manacher算法使用id、mx做配合可以在每次循环中直接对P[i]的快速赋值从而在计算以i为中心的回文子串的过程中不必每次都从1开始比较减少了比较次数最终使得求解最长回文子串的长度达到线性O(N)的时间复杂度。

39.字符串包含

给定两个分别由字母组成的字符串A和字符串B字符串B的长度比字符串A短。

请问如何最快地判断字符串B中所有字母是否都在字符串A里

为了简单起见我们规定输入的字符串只包含大写英文字母请实现函数bool

string

答案是true即String2里的字母在String1里也都有或者说String2是String1的真子集。

String

答案是false因为字符串String2里的E字母不在字符串String1里。

分析与解法

题目描述虽长但题意很明了就是给定一长一短的两个字符串AB假设A长B短要求判断B是否包含在字符串A中。

初看似乎简单但实现起来并不轻松且如果面试官步步紧逼一个一个否决你能想到的方法要你给出更好、最好的方案时恐怕就要伤不少脑筋了。

解法一

判断string2中的字符是否在string1中?最直观也是最简单的思路是针对string2中每一个字符逐个与string1中每个字符比较看它是否在String1中。

bool

假设n是字符串String1的长度m是字符串String2的长度那么此算法需要O(n*m)次操作。

显然时间开销太大应该找到一种更好的办法。

解法二

如果允许排序的话我们可以考虑下排序。

比如可先对这两个字符串的字母进行排序然后再同时对两个字串依次轮询。

两个字串的排序需要(常规情况)O(m

log

B中可能包含重复字符所以注意A下标不要轻易移动。

这种方法改变了字符串。

如不想改变请自己复制

bool

假设有一个仅由字母组成字串让每个字母与一个素数对应从2开始往后类推A对应2B对应3C对应5......。

遍历第一个字串把每个字母对应素数相乘。

最终会得到一个整数。

利用上面字母和素数的对应关系对应第二个字符串中的字母然后轮询用每个字母对应的素数除前面得到的整数。

如果结果有余数说明结果为false。

如果整个过程中没有余数则说明第二个字符串是第一个的子集了判断是不是真子集可以比较两个字符串对应的素数乘积若相等则不是真子集。

思路总结如下

如前所述算法的时间复杂度为O(mn)的最好的情况为O(n)遍历短的字符串的第一个数与长字符串素数的乘积相除即出现余数便可退出程序返回falsen为长字串的长度空间复杂度为O(1)。

bool

此种素数相乘的方法看似完美但缺点是素数相乘的结果容易导致整数溢出。

解法四

事实上可以先把长字符串a中的所有字符都放入一个Hashtable里然后轮询短字符串b看短字符串b的每个字符是否都在Hashtable里如果都存在说明长字符串a包含短字符串b否则说明不包含。

再进一步我们可以对字符串A用位运算26bit整数表示)计算出一个“签名”再用B中的字符到A里面进行查找。

m)空间复杂度O(1)

这个方法的实质是用一个整数代替了hashtable空间复杂度为O(1)时间复杂度还是O(n

举一反三

如果两个字符串的字符一样但是顺序不一样被认为是兄弟字符串比如bad和adb即为兄弟字符串现提供一个字符串如何在字典中迅速找到它的兄弟字符串请描述数据结构和查询过程。

40.字符串转换成整数

输入一个由数字组成的字符串把它转换成整数并输出。

例如输入字符串123输出整数123。

给定函数原型int

本题考查的实际上就是字符串转换成整数的问题或者说是要你自行实现atoi函数。

那如何实现把表示整数的字符串正确地转换成整数呢以123作为例子

当我们扫描到字符串的第一个字符1时由于我们知道这是第一位所以得到数字1。

当扫描到第二个数字2时而之前我们知道前面有一个1所以便在后面加上一个数字2那前面的1相当于10因此得到数字1*10212。

继续扫描到字符33的前面已经有了12由于前面的12相当于120加上后面扫描到的3最终得到的数是12*103123。

因此此题的基本思路便是从左至右扫描字符串把之前得到的数字乘以10再加上当前字符表示的数字。

int

空指针输入输入的是指针在访问空指针时程序会崩溃因此在使用指针之前需要先判断指针是否为空。

正负符号整数不仅包含数字还有可能是以或-开头表示正负整数因此如果第一个字符是-号则要把得到的整数转换成负整数。

非法字符输入的字符串中可能含有不是数字的字符。

因此每当碰到这些非法的字符程序应停止转换。

整型溢出输入的数字是以字符串的形式输入因此输入一个很长的字符串将可能导致溢出。

上述其它问题比较好处理但溢出问题比较麻烦所以咱们来重点看下溢出问题。

一般说来当发生溢出时取最大或最小的int值。

即大于正整数能表示的范围时返回MAX_INT2147483647小于负整数能表示的范围时返回MIN_INT-2147483648。

我们先设置一些变量

10522545459会出错因为正常的话理应得到MAX_INT2147483647但程序运行结果将会是1932610867。

为什么呢因为当给定字符串

10522545459时而MAX_INT是2147483647即MAX_INT(2147483647)

n*10(1052254545*10)所以当扫描到最后一个字符‘9’的时候执行上面的这行代码

MAX_INT

针对这种由于输入了一个很大的数字转换之后会超过能够表示的最大的整数而导致的溢出情况我们有两种处理方式可以选择

long即long

10那么说明最后一步转换时n*10必定大于MAX_INT所以在得知n

MAX_INT

对于上面第一种方式虽然我们把n定义了长整型但最后返回时系统会自动转换成整型。

咱们下面主要来看第二种处理方式。

对于上面第二种方式先举两个例子说明下

如果我们要转换的字符串是2147483697那么当我扫描到字符9时判断出214748369

MAX_INT

214748364C语言里整数相除自动取整不留小数则返回MAX_INT

如果我们要转换的字符串是2147483648那么判断最后一个字符8所代表的数字8与MAX_INT

一直以来我们努力的目的归根结底是为了更好的处理溢出但上述第二种处理方式考虑到直接计算n

可能会大于MAX_INT导致溢出那么便两边同时除以10只比较n和MAX_INT

10的大小从而巧妙的规避了计算n*10这一乘法步骤转换成计算除法MAX_INT/10代替不能不说此法颇妙。

*str

分析此题虽然类似于atoi函数但毕竟double为64位而且支持小数因而边界条件更加严格写代码时需要更加注意。