[数据结构与算法]【解题报告】《LeetCode零基础指南》(第二讲) 函数 - Java

零、相关知识

1.快速幂

• 我一开始听到快速幂，不知道这是做什么用的，就去先自己了解了一下，也在这里简单做一个记录，有错漏的地方欢迎指正。
• 快速幂计算：$$a^{b}modc$$
• 在很多地方都能使用到快速幂，比如说RSA加密算法，需要用到：$(明文{)}^{e}modn和(密文{)}^{d}modn$，下面通过一个例子来引入快速幂
• 例子：5⁵ mod 7
  （1）简单的，可以直接 5×5×5×5×5 mod 7，这里的4步幂次计算，时间复杂度近似为$O_{(N)}$。这里幂次比较小还好，但是一般幂次都会比较大，这样耗时就会比较长。
  （2）如果通过二分法做一个降幂的优化，如下图所示：
  
  （3）将 $5^5$ 的幂次除以2，因为指数是奇数，所以还需要乘 $5^1$ ，得到 $5^2\times 5^2\times 5^1$。继续降幂，$5^2$ 又可以分为 $5^1\times 5^1$，最后得到的就是：$(5^2{)}^2\times 5$，这里的运算总共就是3步，相较于上一种方法运算步骤要少了。
  （4）虽然在这里看起来还是差不多，但是当幂次大了之后，两者的区别就会显现出来。
• 例如：计算 $5^{16}$
  （1）如果是直接乘，就需要乘（16 - 1）=15次；
  （2）如果用二分快速幂，就是 $(((5^2{)}^2{)}^2{)}^2$，总共4步运算，时间复杂度近似为 $O_{(lo{g}_{2}N)}$，区别就很显而易见了。
• 最后总结一下二分快速幂，需要分为三种情况来计算：
  

一、371. 两整数之和

1.题目

371. 两整数之和

给你两个整数 a 和 b ，不使用 运算符 + 和 - ???????，计算并返回两整数之和。

2.分析

题目说不能使用加减号，第一时间想到的是位运算，要通过位运算来实现，首先要了解基本的位运算符：

1. & 按位与：都为1才是1，有0为0
2. | 按位或：有1为1，都为0才是0
3. ^ 按位异或：相同为0，不同为1
4. << 左移：高位舍弃，低位补0
5. >> 右移：高位补0，低位舍弃

了解了以上位运算符，看以下例子：
例子：2 + 3
在二进制运算中，可以表示为：
$$\begin{array}{r}010\\ +011\\ 101\end{array}$$

这个位运算的过程，可以拆分成几个步骤：

1. 找出需要进位的位置
2. 把要进位的位置左移一位，得到新的二进制数
3. 找出不需要进位的位置
4. 把左移后的新二进制数与不需要进位的位合并

现在把各个步骤变成代码：

1. 需要进位的位置，必定都为1，所以 a & b 得到的就是需要进位的位数
   a & b = 2 & 3：
   $$\begin{array}{r}010\\ 011\\ 010\end{array}(得出需要进位的是第2位)$$
2. 把要进位的位置左移一位，得到新的二进制数
   $$010<<1得到：100$$
3. 不需要进位的位置，即都为0和都为1的位置计算后要得0，有且只有一个1的位置计算后得1，我们会发现这就是异或运算
   a ^ b = 2 ^ 3：
   $$\begin{array}{r}010\\ 011\\ 001\end{array}(得出不需要进位的是第1位)$$
4. 最后把左移后的数和不需要进位的数合起来就是结果，也就是a | b
   $$\begin{array}{r}100\\ 001\\ 101\end{array}(得出结果：2+3=5)$$
5. 特殊情况：有可能经过左移后得到的数与异或得到的数按位或（|）时，还是会出现进位，所以需要一个循环的判断，直到按位与（&）为0，再进行按位或运算返回结果。

3.代码

class Solution {
    public int getSum(int a, int b) {
        int n = a,m = b;
        while ((n & m) != 0){
            n = (a & b) << 1;
            m = a ^ b;
            a = n;
            b = m;
        }
        return n | m;
    }
}

二、面试题 17.01.不用加号的加法

1.题目

面试题 17.01.不用加号的加法

设计一个函数把两个数字相加。不得使用 + 或者其他算术运算符。

2.分析

跟第一题是一样的，也是位运算，具体思路可以往上翻一下哈。

3.代码

class Solution {
    public int add(int a, int b) {
        int n = a,m = b;
        while ((n & m) != 0){
            n = (a & b) << 1;
            m = a ^ b;
            a = n;
            b = m;
        }
        return n | m;
    }
}

三、剑指 Offer 65. 不用加减乘除做加法

1.题目

剑指 Offer 65. 不用加减乘除做加法

写一个函数，求两个整数之和，要求在函数体内不得使用 “+”、“-”、“*”、“/” 四则运算符号。

2.分析

额…还是跟第一题一样的思路。。

3.代码

class Solution {
    public int add(int a, int b) {
        int n = a,m = b;
        while ((n & m) != 0){
            n = (a & b) << 1;
            m = a ^ b;
            a = n;
            b = m;
        }
        return n | m;
    }
}

四、面试题 08.05. 递归乘法

1.题目

面试题 08.05. 递归乘法

递归乘法。 写一个递归函数，不使用 * 运算符， 实现两个正整数的相乘。可以使用加号、减号、位移，但要吝啬一些。

2.分析

暴力的写法，一个个加。。位运算的写法还没想到额。。。

3.代码

class Solution {
    public int multiply(int A, int B) {
        int i = 1,res = 0;
        while (i <= B){
            res = res + A;
            i++;
        }
        return res;
    }
}

五、29. 两数相除

1.题目

29. 两数相除

给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。
返回被除数 dividend 除以除数 divisor 得到的商。
整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2

提示：
1.被除数和除数均为 32 位有符号整数。
2.除数不为 0。
3.假设我们的环境只能存储 32 位有符号整数，其数值范围是 [?2³¹, 2³¹ ? 1]。本题中，如果除法结果溢出，则返回 2³¹ ? 1。

2.分析

判断溢出的情况，直接除。

3.代码

class Solution {
    public int divide(int dividend, int divisor) {
        if (divisor == -1){
            if (dividend == -2147483648){
                //溢出
                return 2147483647; 
            }
        }
        return dividend / divisor;
    }
}

六、50. Pow(x, n)

1.题目

50. Pow(x, n)

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

提示：
-100.0 < x < 100.0
-2³¹ <= n <= 2³¹-1
-10⁴ <= xⁿ <= 10⁴

2.分析

这里用到了二分快速幂。具体介绍可以在文章开头导读了解一下哈。

3.代码

class Solution {
    public double myPow(double x, int n) {
        //n为负数不能写 1 / binaryQuickPow(x,-n)，因为当n为-2147483648时，会溢出
        return n > 0 ? binaryQuickPow(x,n) : 1 / binaryQuickPow(x,n);
    }

    /**
     * 二分快速幂
     */
    private double binaryQuickPow(double x, int n) {
        //终止递归的条件
        if (n == 1 || n == -1){
            return x;
        }
        if (n == 0){
            return 1;
        }
        double t = binaryQuickPow(x, n / 2);
        return n % 2 == 0 ? t * t : t * t * x;
    }
}

七、69. Sqrt(x)

1.题目

69. Sqrt(x)

给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

提示：
0 <= x <= 2³¹ - 1

2.分析

二分查找，因为 $x$ 的算术平方根 $n$ 必定满足 $n^2\le x$，所以找满足 $n^2＞x$ 的最小 $n$，最后返回 $n?1$

3.代码

class Solution {
    public int mySqrt(int x) {
        if (x == 0 || x == 1){
            return x;
        }
        int l = 0,r = x;
        int mid = 0;
        while (r - l > 1){
            mid = l + (r - l) / 2;
            if ((long)mid * mid <= x){
                l = mid;
            } else {
                r = mid;
            }
        }
        return r - 1;
    }
}

八、面试题 16.07. 最大数值

1.题目

面试题 16.07. 最大数值

编写一个方法，找出两个数字a和b中最大的那一个。不得使用if-else或其他比较运算符。

2.分析

三目运算符：$a>b?a:b$

3.代码

class Solution {
    public int maximum(int a, int b) {
        return a > b ? a : b;
    }
}