各位小伙伴,又到周末啦~本周小白已经开始二刷《剑指offer》了,这次在LeetCode上面刷题,发现LeetCode上面的《剑指offer》和牛客上面的题目好像有一些差别。也提醒一下其他的小伙伴儿刷题的时候可以稍作留意啊!
好啦~闲话少说,咱们现在开始上干货。本周小白刷题过程中,刷的题目挺多的,前面的一些高级算法已经写过一些了~咱们本周就来分享几个有意思的数学题。下面的几道题目,都可以用暴力法求解,都是可以AC的。但是咱们介绍几个比较巧妙的方法来完成解题。就当做刷题过程中的一个调味剂,享受一下刷题的乐趣吧~
leetcode 面试题04 --- 二维数组中的查找【简单】
题目描述
从题目中我们可以知道,对于整个数组而言,是有顺序的。每一行从左到右是递增序列,每一列从上到下是递增序列。
方法一: 如果我们无视这个规律,完全可以使用暴力法,遍历整个数组,然后一个一个的与数组中的每一个元素进行比较,最后确定整个数组中是否有给定的值。
方法二: 那么我们此时就该想一想其他的方法啦~既然每一行和每一列都是递增的,对于递增数组中查找某个值,我们比较喜欢使用二分法。那么这个时候,是不是就让你的眼前豁然开朗了呢~题目给到的天然条件,我们终于用到了~
在本道题中,给出的是一个二维数组,所以我们需要对行和列分别进行二分法查询,最后确定答案。第一次二分法先查找给定的值在整个数组中的哪一行,首先确定行号。第二次二分法我们用于定位一列。最终查找到结果值。
方法三: 当然上面的两种都是可以解出来的,但是我们介绍一个更加巧妙的方法,在遍历的过程中,我们从右上角或者左下角进行遍历。下面我们以右上角为例,走一下下面的这个流程图:
解题思路
我们的起始坐标位于右上角,拿当前值与给定的目标值进行比较。
matrix[i][j] < target
,则代表着,若数组中存在target
,则target
一定存在于当前值[i][j]
坐标的下面,则此时我们更新坐标为[i+1][j]
,以得到更大的值;matrix[i][j] > target
,则代表着,若数组中存在target
,则target
一定存在于当前值[i][j]
坐标的左面,则此时我们更新坐标为[i][j-1]
,以得到较小的值;target
。 //从左下角开始向上遍历
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;
}
leetcode 面试题14- II --- 剪绳子II【中等】
题目描述
对于这道题而言,要求我们求出乘积最大的数,从评论区里,我们看到了一位大佬的证明方法,截图如下:
求解过程
这位大佬从证明到算法的推导,都完美的展示了出来,小白就不在这里画蛇添足啦~这个证明真的很厉害!直接排除了暴力方法的疑难细节问题。下面我们就给出上面算法的代码实现吧!
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);
}
leetcode 面试题15 --- 二进制中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
的个数。
//方法一:循环移位
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 --- 数值的整数次方【中等】
题目描述
题目中的要求很简单,就是让我们计算数值的给定次方的幂。
方法一: 本题我们依旧可以使用暴力法,一遍一遍的将所有的基数乘以给定的次数,即可得到最后的答案。
方法二: 我们使用快速幂的算法,快速幂算法的解析过程中有很多数学符号,小白找到了一个详细的解答过程,就直接粘贴过来吧!
解题思路
在快速幂中,我们不断的对基数进行翻倍,对指数进行缩小,最后类似于使用了二分法,将整体需要运行的次数缩减了一半。最后的代码实现,我们就放在下面吧!
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;
}
好了,本周的分享就到这里啦,有没有感觉到刷题的一些小快乐了呢~哈哈!