数学题：查找，快速幂，二进制，剪绳子

各位小伙伴，又到周末啦~本周小白已经开始二刷《剑指offer》了，这次在LeetCode上面刷题，发现LeetCode上面的《剑指offer》和牛客上面的题目好像有一些差别。也提醒一下其他的小伙伴儿刷题的时候可以稍作留意啊！

好啦~闲话少说，咱们现在开始上干货。本周小白刷题过程中，刷的题目挺多的，前面的一些高级算法已经写过一些了~咱们本周就来分享几个有意思的数学题。下面的几道题目，都可以用暴力法求解，都是可以AC的。但是咱们介绍几个比较巧妙的方法来完成解题。就当做刷题过程中的一个调味剂，享受一下刷题的乐趣吧~

一、二维数组查找

leetcode 面试题04 --- 二维数组中的查找【简单】

题目描述

1、解题思路

从题目中我们可以知道，对于整个数组而言，是有顺序的。每一行从左到右是递增序列，每一列从上到下是递增序列。

方法一： 如果我们无视这个规律，完全可以使用暴力法，遍历整个数组，然后一个一个的与数组中的每一个元素进行比较，最后确定整个数组中是否有给定的值。

方法二： 那么我们此时就该想一想其他的方法啦~既然每一行和每一列都是递增的，对于递增数组中查找某个值，我们比较喜欢使用二分法。那么这个时候，是不是就让你的眼前豁然开朗了呢~题目给到的天然条件，我们终于用到了~

在本道题中，给出的是一个二维数组，所以我们需要对行和列分别进行二分法查询，最后确定答案。第一次二分法先查找给定的值在整个数组中的哪一行，首先确定行号。第二次二分法我们用于定位一列。最终查找到结果值。

方法三： 当然上面的两种都是可以解出来的，但是我们介绍一个更加巧妙的方法，在遍历的过程中，我们从右上角或者左下角进行遍历。下面我们以右上角为例，走一下下面的这个流程图：

解题思路

我们的起始坐标位于右上角，拿当前值与给定的目标值进行比较。

• 如果当前值matrix[i][j] < target，则代表着，若数组中存在target，则target一定存在于当前值[i][j]坐标的下面，则此时我们更新坐标为[i+1][j]，以得到更大的值；
• 如果当前值matrix[i][j] > target，则代表着，若数组中存在target，则target一定存在于当前值[i][j]坐标的左面，则此时我们更新坐标为[i][j-1]，以得到较小的值；
• 当坐标更新越界的时候，则数组中不存在target。

2、实现代码

    //从左下角开始向上遍历
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        if(matrix == null || matrix.length == 0 )return false;
        int row = matrix.length;
        int col = matrix[0].length;
        for(int i = row - 1 , j = 0 ; i >= 0 && j < col ;){
            if(matrix[i][j] == target){
                return true;
            }else if(matrix[i][j] > target){
                i--;
            }else{
                j++;
            }
        }
        return false;
    }

二、剪绳子II

leetcode 面试题14- II --- 剪绳子II【中等】

题目描述

1、解题思路

对于这道题而言，要求我们求出乘积最大的数，从评论区里，我们看到了一位大佬的证明方法，截图如下：

求解过程

这位大佬从证明到算法的推导，都完美的展示了出来，小白就不在这里画蛇添足啦~这个证明真的很厉害！直接排除了暴力方法的疑难细节问题。下面我们就给出上面算法的代码实现吧！

2、实现代码

    public int cuttingRope(int n) {//经过数学分析推导分析，应该将数字n尽可能分割为3
        long res = 1;
        int mod = (int)1e9 + 7;
        if(n <= 3) return n-1;
        while(n > 4){
            res *= 3;
            res = res % mod;
            n -= 3;
        }
        return (int)(res*n % mod);
    }

三、二进制中1的个数

leetcode 面试题15 --- 二进制中1的个数【简单】

题目描述

1、解题思路

方法一： 首先想到的肯定是循环移位啦~对给定的数字进行循环移位，不断的左移，然后和1做与运算，每次结果为1的时候累加一次。直到最后的数字为0，停止累加，返回给定的结果。对于这种方法，小白也在下面的实现代码里面给出了案例哈，各位小伙伴可以参考一下啊！

方法二： 还有一种算法是使用n&(n-1)，这种解决方案是基于这样一个事实：每次使用n&(n-1)，都会将n的最低位的1置为0，而其他位不变。我们举个例子吧！

示例1：
n = 8    1000
			&	>= 0000 将n=8的最低位1置为0，最后得到0
n-1 = 7	 0111

示例2：
n = 5	101
		&		>= 100 将n=5的最低位1置为0，得到100
n-1=4   100

所以我们依据这种方法，可以循环的将n&(n-1)的值赋给n，然后每次循环时计数，直到最后n==0，此时计数结果即为最后n中1的个数。

2、实现代码

    //方法一：循环移位
    public int hammingWeight(int n) {
        int res = 0 ;
        while(n != 0){
            res += n & 1 ;
            n >>>= 1;
        }
        return res;
    }
	/*方法二：
    public int hammingWeight(int n) {
        int res = 0 ;
        while(n ！= 0){
            res ++ ;
            n &= n -1 ;
        }
        return res;
    }*/

四、数值的整数次方

leetcode 面试题16 --- 数值的整数次方【中等】

题目描述

1、解题思路

题目中的要求很简单，就是让我们计算数值的给定次方的幂。

方法一： 本题我们依旧可以使用暴力法，一遍一遍的将所有的基数乘以给定的次数，即可得到最后的答案。

方法二： 我们使用快速幂的算法，快速幂算法的解析过程中有很多数学符号，小白找到了一个详细的解答过程，就直接粘贴过来吧！

解题思路

在快速幂中，我们不断的对基数进行翻倍，对指数进行缩小，最后类似于使用了二分法，将整体需要运行的次数缩减了一半。最后的代码实现，我们就放在下面吧！

2、实现代码

    public double myPow(double x, int n) {
        if(x == 0) return 0;
        long b = n;
        double res = 1.0;
        if(b < 0) {
            x = 1 / x;
            b = -b;
        }
        while(b > 0) {
            if((b & 1) == 1) res *= x;
            x *= x;
            b >>= 1;
        }
        return res;
    }

好了，本周的分享就到这里啦，有没有感觉到刷题的一些小快乐了呢~哈哈！