leetcode数学习题

2020-01-18 by 杜宏伟

数字习题不光是涉及了数学知识,还涉及了计算机原理。

整数反转

给出一个 32 位的有符号整数,你需要将这个整数中每位上的数字进行反转。

如果不考虑空间复杂度,可以你会想直接转成字符串,然后reverse,再转成数字。不幸的是转成数字的时候,同样会有溢出的问题。所谓溢出就是数字太大,已经不没有办法存了。

要解决这个问题,首先需要计算机是如何存数据的。

在计算机中是用二进制表示数字的。所以32无符号整数可以表示的范围是 0 - 232-1。有符号整数的范围是 -231 - 231-1 为什么不是-231+1 - 231 ?了解这些需要看下原码、反码、补码的产生、应用以及优缺点有哪些。开始人们为了自己看着方便,用原码表示,结果发现,很难让计算机进行运算。然后用反码表示负数,相当于负数是一个相反的世界,这样就可以用统一的加运算解决减的运算。但是反码有正0和负0之分,于是就产生了补码,把两个0合二为一了。不管怎么说吧,就是用232种0,1所有排列的可能性,表示了232个数,这个232个10进制的数可以完美用不同的二进制的01表示。其实不用管反码,补码,可以把10进制到2进制的转换看做是哈希映射,这样理解就好了。10进制转到2进制的时间复杂度是O(1),没有冲突,非常完美的哈希映射。

回归正题,先看答案

int rev = 0;
while (x != 0) {
    int pop = x % 10;
    x /= 10;
    if (rev > INT_MAX/10 || (rev == INT_MAX / 10 && pop > 7)) return 0;
    if (rev < INT_MIN/10 || (rev == INT_MIN / 10 && pop < -8)) return 0;
    rev = rev * 10 + pop;
}
return rev;

思路就是在转之前,先预判会不会溢出。

7,8是怎么来的,是不是有点费解呢?这是因为 INT_MAX / 10的时候会把小数部分舍掉,因为rev是int类型,是不保留小数的。在二进制表示中,最大的正数除了首位,一定全是1。转成十进制个位就是7,所以舍掉的就是7,所以判断的时候为了完美,需要把这个7加上。

上面是从计算机原理的层面说的,可以直接用 n位二进位的最大数是 2n-1-1最小数是-2n-1就可以直接知道结果了。

回文数

判断一个整数是否是回文数。回文数是指正序(从左向右)和倒序(从右向左)读都是一样的整数。

判断一个整数是否是回文数。回文数是指正序(从左向右)和倒序(从右向左)读都是一样的整数。

示例:

输入: 121
输出: true
示例 2:

输入: -121
输出: false
解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。
示例 3:

输入: 10
输出: false
解释: 从右向左读, 为 01 。因此它不是一个回文数。

最佳的是数字翻转,但会面临溢出的问题。所以我们可以只翻转一半。临界点是翻转后的数字比剩余的大。如果是奇数,停止循环后,舍掉最后一位即可。

pow(x, n)

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

分治法。 O(logn)

二进制求和

给定两个二进制字符串,返回他们的和(用二进制表示)。

输入为非空字符串且只包含数字 10

示例 1:

输入: a = "11", b = "1"
输出: "100"

示例 2:

输入: a = "1010", b = "1011"
输出: "10101"

把较短的字符串开头用0补齐,再相加

x的平方根

实现 int sqrt(int x) 函数。

计算并返回 x 的平方根,其中 x 是非负整数。

由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。

示例 1:

输入: 4
输出: 2

示例 2:

输入: 8
输出: 2
说明: 8 的平方根是 2.82842..., 
     由于返回类型是整数,小数部分将被舍去。

二分 + 牛顿迭代法

位1的个数

编写一个函数,输入是一个无符号整数,返回其二进制表达式中数字位数为 1 的个数(也被称为汉明重量)。

  1. 对2取余,把 1 个数加起来
  2. x & x-1 可以打掉最后一位1,变成0时就算出了1的个数

我叫杜宏伟,前端开发。

一直想写博客,在2018的年的最后几天,终于上线了。

对于前端开发,一个特点就是太零散,很容易会了后面忘了前面,所以归纳总结很重要。再有就是分享,做前端好多年,以前都是看你们写的文章, 现在我也开始写一些,希望可以帮到入行的小伙伴。微信号 duhongwei5775

欢迎转载,只需注明作者,出处即可

版权说明:署名 4.0 国际(CC BY 4.0)