leetcode习题分类汇总-Math篇

Single Number-在其他数均出现两次的数组中找到唯一出现一次的数字

思路:位运算,0^0=0,0^1=1 0异或任何数=任何数,1^0=1,1^1=0 1异或任何数-任何数取反,任何数异或自己=把自己置0。




Count Primes-统计到N的素数

思路:
(1)计算出每个素数,TLE
(2)要得到自然数n以内的全部素数,必须把不大于的所有素数的倍数剔除,剩下的就是素数。
给出要筛数值的范围n,找出根号N以内的素数。先用2去筛,即把2留下,把2的倍数剔除掉;再用下一个质数,也就是3筛,把3留下,把3的倍数剔除掉;接下去用下一个质数5筛,把5留下,把5的倍数剔除掉;不断重复下去……。
用boolean[]来跟踪当前位置是否是prime.




### Happy Number-

Example: 19 is a happy number

12 + 92 = 82 82 + 22 = 68
62 + 82 = 100 12 + 02 + 02 = 1

解题思路:一开始直接模拟,循环100次还不是1直接剪掉return false,也能AC,
但是毕竟可能有情况覆盖不到,改用HastSet存放中间数就行了,
如果得到的新结果在中间数集合中出现了,那么一定会陷入循环并且得到的不是1。

###

5.Plus One-模拟加法,数组表示数字加一然后返回

思路:纯数学,注意进位carry和特殊情况999+1…




### Palindrome Number-判断数字是否回文

思路:转换为字符串比较




### Factorial Trailing Zeroes-给定一个整数n,返回n!(n的阶乘)数字中的后缀0的个数。

思路:首先求出n!,然后计算末尾0的个数。(重复÷10,直到余数非0)

该解法在输入的数字稍大时就会导致阶乘得数溢出,不足取。

### O(logn)解法:

一个更聪明的解法是:考虑n!的质数因子。后缀0总是由质因子2和质因子5相乘得来的。如果我们可以计数2和5的个数,问题就解决了。考虑下面的例子:

n = 5: 5!的质因子中 (2 2 2 3 5)包含一个5和三个2。因而后缀0的个数是1。

n = 11: 11!的质因子中(2^8 3^4 5^2 * 7)包含两个5和三个2。于是后缀0的个数就是2。

我们很容易观察到质因子中2的个数总是大于等于5的个数。因此只要计数5的个数就可以了。那么怎样计算n!的质因子中所有5的个数呢?一个简单的方法是计算floor(n/5)。例如,7!有一个5,10!有两个5。除此之外,还有一件事情要考虑。诸如25,125之类的数字有不止一个5。例如,如果我们考虑28!,我们得到一个额外的5,并且0的总数变成了6。处理这个问题也很简单,首先对n÷5,移除所有的单个5,然后÷25,移除额外的5,以此类推。下面是归纳出的计算后缀0的公式。


Pow(x, n)-返回x的n次方

思路:(1)先判断n±,然后递归二分x的n/2次方,时间logn




### Reverse Integer-数值的翻转

思路:利用运算符,注意值的溢出判断




### Add Binary-二进制数的加法

思路:维护carry和count值,while循环不断insert即可,注意最后一次carry==1需要插入




### Sqrt(x)-实现x的平方根

思路:
二分法提高效率,对于一个非负数n,注意不要溢出。 它的平方根不会小于大于(n/2+1)。在[0, n/2+1]这个范围内可以进行二分搜索,求出n的平方根。



### Add Two Numbers-两个链表每个节点分别表示一个数字,求数字相加的第三个链表,可以进位

思路: carry表示进位,p1,p2,p3遍历,考虑链表长度不同的状况






### Multiply Strings-字符串相乘,非负数

思路:不能化为数字,要考虑溢出。


方法一:大整数乘法,一位一位往上乘,注意进位的处理即可。此外,注意0的处理
方法二:思路:
1 翻转string
2 建立数组,双层循环遍历两个string,把单位的乘积累加到数组相应的位置
3 处理进位并输出
4 注意前导零的corner case



###

String to Integer -字符串转换为数字

思路:基本操作,考虑各种corner case.

1.null or empty string 判断

2.white spaces trim()

3. +/- sign 用flag判断

4.calculate real value double来存储

5.handle min & max

Fraction to Recurring Decimal-分数化为小数

思路:
难点:如何识别循环体?

解决方法:用一个HashMap记录每一个余数,当出现重复的余数时,那么将会进入循环,两个重复余数之间的部分就是循环体。

示例:1/13=0.076923076923076923…,当小数部分第二次出现0时,就意味着开始了循环,那么需要把076923用括号括起来,结果为0.(076923)。

涉及技巧:1)在不断相除的过程中,把余数乘以10再进行下一次相除,保证一直是整数相除;2)HashMap的key和value分别是<当前余数, 对应结果下标>,这样获取076923时就可根据value值来找。

注意点1:考虑正负数,先判断符号,然后都转化为正数;

注意点2:考虑溢出,如果输入为Integer.MIN_VALUE,取绝对值后会溢出。

一定要先把 int 转为 long,然后再取绝对值。如果写成 long num = Math.abs(numerator) 就会有问题,因为这句代码在 numerator=Integer.MIN_VALUE 时相当于 long num = Math.abs
(-2147483648),这样得到的 num还是 -2147483648。

Excel Sheet Column Title-

For example:

    1 -> A
2 -> B
3 -> C

26 -> Z
27 -> AA
28 -> AB
思路:

将n转化为26进制表示的数,然后对每一位的数,根据『1->A,2->B,3->C….25->Y,26->Z』来转化。

当然,按照进制转换的方法(不断地除26取余数),不可能有26的余数,比如:52->(20)->AZ,此时余数是0,这种情况要特殊处理。




### Excel Sheet Column Number-

For example:
    A -> 1
B -> 2
C -> 3

Z -> 26
AA -> 27
AB -> 28

思路:hashmap存储对应关系,然后从左到右按照26进制相加。

总结:数值计算主要考察运算符的利用,一些常见的数学规律,和字符串的互操作以及corner case的全面考虑。