怎样建设相亲网站广西明电建设有限公司网站

当前位置： 首页 > news >正文

怎样建设相亲网站,广西明电建设有限公司网站,做机械外贸什么网站好,深圳市宝安区怎么样不用[ * ]如何使两数相乘❓一、题目明细二、思路罗列 代码解析1、野蛮A * B【不符合题意】2、sizeof【可借鉴】解析3、简易递归【推荐】① 解析#xff08;递归展开图#xff09;② 时间复杂度分析4、移位运算【有挑战性#x1f4aa;】① 思路顺理② 算法图解… 不用[ * ]如何使两数相乘❓一、题目明细二、思路罗列 代码解析1、野蛮A * B【不符合题意】2、sizeof【可借鉴】解析3、简易递归【推荐】① 解析递归展开图② 时间复杂度分析4、移位运算【有挑战性】① 思路顺理② 算法图解③ 代码分析④ 调试分析视频解说三、总结与提炼一、题目明细 原题传送门 可能有读者会说为什么那么简单的题目也要写个题解答【细节决定成败不可忽视细枝末节】对算法题的思考尽量要做到多维度考虑、多思考继而找出最优解 二、思路罗列 代码解析 下面会列出我所AC的所有解有些可能不符合题意 1、野蛮A * B【不符合题意】 本以为不让使用【*】运算符但是试了一下竟然也可以过 int multiply(int A, int B){return A * B; }2、sizeof【可借鉴】 这个方法我觉得还是比较巧妙如果题目没有指定说要使用递归来进行求解可以考虑 int multiply(int A, int B){char a[A][B];return sizeof(a); }解析 有很多学习完C语言的同学在使用sizeof()的时候都会觉得它是一个函数但真的是吗其实可以去cpluplus中看看。就可以观测到无论是搜索多久都不会有结果 其实对于sizeof()来说是一个操作符而且是一个单目操作符如果不清楚的可以看看我的操作符汇总大全。用来计算某一个数据类型的变量所占的字节大小。不要和Pascal中的sizeof()混淆了在这门语言中是作为【函数】来看待的 在 Pascal 语言中sizeof() 是一种内存容量度量函数功能是返回一个变量或者类型的大小以字节为单位在 C语言中sizeof() 是一个判断数据类型或者表达式长度的运算符《来源于百度百科》 所以在这道题中其实我们利用两数相乘的这个逻辑去定义一个字符型的二维数组然后将这个数组当做是长方体那对于长方体的面积来说就是长 * 宽那对于二维数组这个矩阵来说其实就是去计算它在内存中所占地字节数是多少这样就可以很轻易地想到使用sizeof()去进行求解这里要注意的是需定义为【字符数组】因为char类型的变量在内存中只占一个字节若是定义为整型数组算出来就是结果的4倍了 3、简易递归【推荐】 这才是最符合题意的做法使用递归去进行求解 class Solution { public:int Mul(int big, int small){if(small 0) return 0; //与0相乘一定为0if(small 1) return big; //与1相乘一定为自身return big Mul(big, small - 1); //small个big相加small递减}int multiply(int A, int B) {//首先区分两者中的大的那个和小的那个int big A B ? A : B;int small A B ? A : B;return Mul(big, small);} };① 解析递归展开图 递归对有些同学来说可能不好理解因此讲说一下代码逻辑 首先题目说到两个数相乘不可以使用【*】号那其实我们其看一下两个数相乘的原理也就是从加法转化过来的例13 * 4 4 4 4 | 例22 * 5 5 5 选取到小的那个数作为相加的次数 选取大的那个数作为相加的数字 在递归的函数中若是发现small 0那直接return 0即可因为任何数和0相乘都是0若是发现small 1,那就直接返回big因为任何数和1相乘都是1若是都不满足则进行递归调用注意要保留当前层的big然后再产生递归让small - 1即可 若是感觉有点抽象的话就通过递归展开图来看看吧
② 时间复杂度分析 对于上面这种方法的时间复杂度为O(N)。准确点来说是O(small)相当于一个线性阶。如果对时间复杂度如何计算不是很懂可以看看我的这篇文章—— 时间与空间复杂度就看这篇了那有没有更优的方法呢就来看看下面这种吧 4、移位运算【有挑战性】 若是你搞懂了上面这种方法那便来看看这种移位这种方法吧会让你更上一层楼 int Mul(int big, int small) {if(small 0) return 0;if(small 1) return big;int half_small small 1; //右移运算符每次使small缩小一半//递归算出每一半的乘积int half_Sum Mul(big, half_small); //判断每一层的递归中的small为偶数还是奇数if(small % 2 0){return half_Sum half_Sum; //若为偶数直接是double倍}else{return half_Sum half_Sum big; //若为奇数则还需加上一个big} }int multiply(int A, int B){//1.划分二者的大小int big A B ? A : B;int small A B ? A :B;int ret Mul(big, small);return ret; }① 思路顺理 首先对于主接口函数还是一样区分两者中谁大谁小然后传入递归函数中在递归函数中我的思路是这样的既然在上一题中想到了线性阶那便想要优化为对数阶那对于对数阶而言一定存在一个二分的关系然后就可以想到一半的关系所以对于small个big相乘其实并不需要加small次加small/2次即可对于small/2次其实也只需要加small/2次即可那么这就相当于是一个递归的问题要求出8个10的和先求出4个10的和要求出4个10的和先求出2个10的和要求出2个10的和就先求出1个10最后再进行层层回调便可以算出small个big的和为多少了不过这个small的情况还是判断其为奇数还是偶数对于偶数来说就是一个二分但是对于奇数来说就不一样了因为÷2之后相当于是一个整除所以会漏掉一次的big相加要在求当前和的最后加上一个big对于上述这种算法的时间复杂度很明显可以看出来是O(log2small) ② 算法图解 经过思路的讲解与分析可能你还有些云里雾里那就通过算法分解图来看看吧 small为偶数的情况 small为奇数的情况 ③ 代码分析 通过算法图的展示之后相信你一定很清楚该如何去解决这个问题了我们再来回顾一下代码 若是small进来直接为0那么直接return 0便可 if(small 0) return 0;这句便是算出当前层small的一半为多少使用的便是移位运算符右移是缩小1/2 int half_small small 1; //右移运算符每次使small缩小一半求出当前层small的一半之后就继续进行递归 //递归算出每一半的乘积 int half_Sum Mul(big, half_small); 若是当递归调用的时候small 1了便return big进行回调 if(small 1) return big;在回调之后便会进行当前层一半总数的计算这里就是我说的要对small进行奇偶数分类的情况 //判断每一层的递归中的small为偶数还是奇数 if(small % 2 0){return half_Sum half_Sum; //若为偶数直接是double倍 }else{return half_Sum half_Sum big; //若为奇数则还需加上一个big }④ 调试分析 通过调试再来看看程序到底是如何运行的 以big 6, small 4为例进到递归函数中 通过右移运算符便算出small的一半 继续递归直到small 1为止 此时small便为1执行return big 递归回来之后便计算当前层的总和因为small 2为偶数所以无需再加上big 此时继续回调算出small 4这一层的总和 最后便通过递归计算出了【4 * 6】的和为24 为了更好地对照算法图也来测试一下奇数的情况 这次的对比是运算是big 8, small 6 可以看到出现了small为奇数的情况 继续递归直到small 1为止 然后开始计算每一层的总和注意回到small 3的递归层时要进入第二个if分支 此时就需要加上整除之后遗漏的那个big了 回到small 6的递归层时继续计算当前层的总和 最后就算出了6 * 8 48的结果 视频解说 本文的题解都是通过看下面这位UP主写出来的可以看看他的讲解—— 主页 leetcode 面试题 08.05. 递归乘法三、总结与提炼 最后来总结一下本文所学习的内容 【递归乘法】这道题是LeetCode上的一道面试题虽然题目看起来比较简单但是递归对很多同学来说还是比较困难所以我在这里做一个细致的讲解主要是详细解说了有关递归的两种解法对于简易递归来说就是本题的答案但是我们要像在面试中胜出就必须要想到更好、更优的解法对于第二种sizeof的解法可供读者参考也是比较巧妙的方法不过要清楚sizeof是一个操作符而不是一个函数 学会不断思考不断突破自己才是最大的进步