专栏首页Java小白成长之路数学题:查找,快速幂,二进制,剪绳子

数学题:查找,快速幂,二进制,剪绳子

各位小伙伴,又到周末啦~本周小白已经开始二刷《剑指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,此时计数结果即为最后n1的个数。

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;
    }

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

本文分享自微信公众号 - Java小白成长之路(Java_xiaobai),作者:鹏程万里

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-05-31

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 剑指offer第10题:矩阵中的路径

    根据题目要求,需要我们从一个已知矩阵中找到一个可以挨个形成给定字符串的路径。如果有这条路径的话,我们需要返回true,如果没有的话,我们返回false,并且相同...

    鹏-程-万-里
  • 剑指offer第2题:二维数组查找

    当前数组从上到下是升序,从左到右也是升序,所以我们可以选择一个合适的入口点,通过判断当前的值与target的大小比较,然后选择我们将要遍历的方向。这是一个比较好...

    鹏-程-万-里
  • 剑指offer第11题:机器人运动范围

    此方法我们可以直接按照题目中的要求,将所有的方格全都访问一遍,由于所有的格子需要满足一个条件,连续性和单元格的坐标和小于n即可。

    鹏-程-万-里
  • C语言标准工具库函数库:stdlib.h

      对于一些特殊的操作,C语言提供了标准工具库函数库,其中包括可以实现数值转换,内存分配,随机数操作以及字符串转换等函数。本篇博文一一来讲述这个函数库中的那些函...

    深度学习思考者
  • Netty 断线重连解决方案

    本篇文章是Netty专题的第七篇,前面六篇文章如下: 高性能NIO框架Netty入门篇 高性能NIO框架Netty-对象传输 高性能NIO框架Netty-整合k...

    猿天地
  • 05 - JavaSE之数组

    Daotin
  • 看完这个,Java IO从此不在难

    Java IO 体系看起来类很多,感觉很复杂,但其实是 IO 涉及的因素太多了。在设计 IO 相关的类时,编写者也不是从同一个方面考虑的,所以会给人一种很乱的感...

    Wizey
  • 二维数组的查找

    题目:在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否...

    猿人谷
  • XStream、JAXB 日期(Date)、数字(Number)格式化输出xml

    XStream、Jaxb是java中用于对象xml序列化/反序列化 的经典开源项目,利用它们将对象转换成xml时,经常会遇到日期(Date)、数字按指定格式输出...

    菩提树下的杨过
  • python下载百度音乐

    我把百度音乐的网页代码稍微分析了一下,如果要求不高,下载普通音质的歌曲是不需要登陆的(当然如果你用浏览器打开下载的话,普通音质也是要求登陆下载的)

    bear_fish

扫码关注云+社区

领取腾讯云代金券