面试 | 移位妙解递归乘法【细节决定成败】
不用[ * ]如何使两数相乘❓
- 一、题目明细
- 二、思路罗列 & 代码解析
- 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);}
};
① 解析(递归展开图)
递归对有些同学来说可能不好理解,因此讲说一下代码逻辑
- 首先题目说到,两个数相乘不可以使用【*】号,那其实我们其看一下两个数相乘的原理也就是从加法转化过来的,
例1:3 * 4 == 4 + 4 + 4 | 例2:2 * 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是一个操作符,而不是一个函数
学会不断思考,不断突破自己,才是最大的进步
相关文章:

面试 | 移位妙解递归乘法【细节决定成败】
不用[ * ]如何使两数相乘❓一、题目明细二、思路罗列 & 代码解析1、野蛮A * B【不符合题意】2、sizeof【可借鉴】解析3、简易递归【推荐】① 解析(递归展开图)② 时间复杂度分析4、移位<<运算【有挑战性💪】① 思路顺理② 算法图解…...

项目缓存问题处理
1、public/index.html文件头部配置 <meta http-equiv"pragram" content"no-cache"> <meta http-equiv"cache-control" content"no-cache,no-store,must-revalidate"> <meta http-equiv"expires" content&…...

DS期末复习卷(八)
一、选择题(30分) 1.字符串的长度是指( C )。 (A) 串中不同字符的个数 (B) 串中不同字母的个数 (C ) 串中所含字符的个数 (D) 串中不同数字的个数 2.建立一个长度为n的有序单链表的时间复杂度为( C ) (A) O(n) (B) O(1) © …...
第50讲:SQL优化之LIMIT分页查询的优化
文章目录 1.LIMIT分页查询的优化概念2.LIMIT分页查询优化前后的效果2.1.LIMIT分页查询优化前2.2.LIMIT分页查询优化后1.LIMIT分页查询的优化概念 当表中数据量小时,分页查询基本上没有什么压力,查询速度也会很快,但是一般当表的数据量很庞大时,上千万条数据,此时分页查询…...

做独立开发者,能在AppStore赚到多少钱?
成为一名独立开发者,不用朝九晚五的上班,开发自己感兴趣的产品,在AppStore里赚美金,这可能是很多程序员的梦想,今天就来盘一盘,这个梦想实现的概率有多少。 先来了解一些数据: 2022年5月26日&am…...

CSS 基础【快速掌握知识点】
目录 一、什么是CSS 二、CSS发展史 三、CSS基本语法结构 1、语法 2、例如 四、style标签 五、HTML中引入CSS样式 1、行内样式 2、内部样式表 3、外部样式表 六、CSS基本选择器 1、标签选择器 2、类选择器 3、ID选择器 4、总结 5、基本选择器的优先级 七、CSS的…...

Linux 驱动基础
注册驱动模块时给模块传递参数 在一些情况下,我们要动态的改变驱动中某个变量的值,那么就可以在注册时给驱动模块传递参数。 给驱动模块中传递参数,需要定义好接受参数值的全局变量,并调用module_param 来引用它,具体…...
linux 共享内存操作(shm_open、mmap、编译链接库:-lz -lrt -lm -lc都是什么库)
文章目录linux 共享内存操作(shm_open)一、背景二、函数使用说明shm_openftruncate(改变文件大小)mmap共享内存三、示例代码创建内存共享文件并写入数据打开内存共享文件读数据四、问题总结shm_write.c:(.text0x18): undefined re…...

做出改变:农业科技和区块链在为地球的未来而战中的力量
到2050年,全球有100亿人需要养活,全世界都在关注区块链和农业信息化,以推动发展中国家的技术革新。 自成立以来,区块链技术已经找到了多样化和有价值的应用,以帮助提高效率和激励社区在不同领域和行业的参与。 农业是…...
树莓派介绍
文章目录一.树莓派介绍二.树莓派分类一.树莓派介绍 树莓派,(英语:Raspberry Pi,简写为RPi,别名为RasPi / RPI)是为学习计算机编程教育而设计,只有信用卡大小的微型电脑,其系统基于L…...

[神经网络]基干网络之VGG、ShuffleNet
一、VGG VGG是传统神经网络堆叠能达到的极限深度。 VGG分为VGG16和VGG19,其均有以下特点: ①按2x2的Pooling层,网络可以分成若干段 ②每段之内由若干same卷积操作构成,段内Feature Map数量固定不变; ③Feature Map按2的…...

Java 日期时间与正则表达式,超详细整理,适合新手入门
目录 1、java.time.LocalDate类表示日期; 2、java.time.LocalTime类表示时间; 3、java.time.LocalDateTime类表示日期和时间; 4、java.time.format.DateTimeFormatter类用于格式化日期和时间; 5、创建正则表达式对象 6、匹配…...
用Netty实现物联网04:自定义通信协议
上一讲咱们澄清了Netty的一些基本概念,然后也写了一个服务端与客户端通信的简单应答程序。从这一讲开始,就来一步步搭建一个Netty物联网应用。 大多数硬件电子产品,都自带了嵌入式软件,或者说固件。这些嵌入式软件/固件基本上都是用C/C++编写的。由于这些小微电子设备资源极…...

「smardaten」上架钉钉应用中心!让进步再一次发生
使用钉钉的团队小伙伴们,smardaten给您送来福利啦~为了给更多团队提供更优质的应用开发体验,方便用户在线、快速使用无代码,数睿数据近期在【钉钉应用中心】发布smardaten在线版本。继与华为云、亚马逊云建立战略合作之后,smardat…...

3、Maven安装
前言:工具下载地址阿里云盘:Maven:https://www.aliyundrive.com/s/SgHKjQ5doSp提取码: ml40一、什么是maven?Apache Maven是个项目管理和自动构建工具,基于项目对象模型(POM)的概念。作用:完成…...
tkinter
# 隐藏控件 tl.pack_forget() tb.pack_forget() # 显示控件 tl.pack() tb.pack() 如果您使用 grid 布局管理器,则可以使用 grid_remove() 方法将控件隐藏,使用 grid() 方法将控件显示。例如: # 隐藏控件 tl.grid_remove() tb.grid_remove() #…...
Servlet笔记(6):HTTP状态码
1、状态码 代码消息描述100 Continue只有请求的一部分已经被服务器接收,但只要它没有被拒绝,客户端应继续该请求。101 Switching Protocols服务器切换协议。200 OK请求成功。201 Created该请求是完整的,并创建一个新的资源。202 Accepted该请…...

RocketMQ 延迟队列
什么是延迟队列指消息发送到某个队列后,在指定多长时间之后才能被消费。应用场景RocketMQ 延迟队列定时消息(延迟队列)是指消息发送到broker后,不会立即被消费,等待特定时间投递给真正的topic。broker有配置项messageD…...
【精准计时】北斗GPS卫星时钟同步改变精准计时年代
【精准计时】北斗GPS卫星时钟同步改变精准计时年代 【精准计时】北斗GPS卫星时钟同步改变精准计时年代 北斗GPS成精确计时先锋 北斗GPS精确时间自动校准技术,是一种简便的获取北斗GPS精确时间信息的专利技术,具有灵敏度高、不受时间及地域限制等特点…...
【C#基础】C# 面向对象编程
序号系列文章5【C#基础】C# 运算符总结6【C#基础】C# 常用语句讲解7【C#基础】C# 常用数据结构文章目录前言面向对象的 C#1,类的概念2,类的定义3,类成员4,对象5,继承6,多态性结语前言 😊大家好&…...

【Oracle APEX开发小技巧12】
有如下需求: 有一个问题反馈页面,要实现在apex页面展示能直观看到反馈时间超过7天未处理的数据,方便管理员及时处理反馈。 我的方法:直接将逻辑写在SQL中,这样可以直接在页面展示 完整代码: SELECTSF.FE…...

【JavaEE】-- HTTP
1. HTTP是什么? HTTP(全称为"超文本传输协议")是一种应用非常广泛的应用层协议,HTTP是基于TCP协议的一种应用层协议。 应用层协议:是计算机网络协议栈中最高层的协议,它定义了运行在不同主机上…...

Maven 概述、安装、配置、仓库、私服详解
目录 1、Maven 概述 1.1 Maven 的定义 1.2 Maven 解决的问题 1.3 Maven 的核心特性与优势 2、Maven 安装 2.1 下载 Maven 2.2 安装配置 Maven 2.3 测试安装 2.4 修改 Maven 本地仓库的默认路径 3、Maven 配置 3.1 配置本地仓库 3.2 配置 JDK 3.3 IDEA 配置本地 Ma…...

初探Service服务发现机制
1.Service简介 Service是将运行在一组Pod上的应用程序发布为网络服务的抽象方法。 主要功能:服务发现和负载均衡。 Service类型的包括ClusterIP类型、NodePort类型、LoadBalancer类型、ExternalName类型 2.Endpoints简介 Endpoints是一种Kubernetes资源…...

【从零学习JVM|第三篇】类的生命周期(高频面试题)
前言: 在Java编程中,类的生命周期是指类从被加载到内存中开始,到被卸载出内存为止的整个过程。了解类的生命周期对于理解Java程序的运行机制以及性能优化非常重要。本文会深入探寻类的生命周期,让读者对此有深刻印象。 目录 …...
django blank 与 null的区别
1.blank blank控制表单验证时是否允许字段为空 2.null null控制数据库层面是否为空 但是,要注意以下几点: Django的表单验证与null无关:null参数控制的是数据库层面字段是否可以为NULL,而blank参数控制的是Django表单验证时字…...

DBLP数据库是什么?
DBLP(Digital Bibliography & Library Project)Computer Science Bibliography是全球著名的计算机科学出版物的开放书目数据库。DBLP所收录的期刊和会议论文质量较高,数据库文献更新速度很快,很好地反映了国际计算机科学学术研…...
32位寻址与64位寻址
32位寻址与64位寻址 32位寻址是什么? 32位寻址是指计算机的CPU、内存或总线系统使用32位二进制数来标识和访问内存中的存储单元(地址),其核心含义与能力如下: 1. 核心定义 地址位宽:CPU或内存控制器用32位…...

使用homeassistant 插件将tasmota 接入到米家
我写一个一个 将本地tasmoat的的设备同通过ha集成到小爱同学的功能,利用了巴法接入小爱的功能,将本地mqtt转发给巴法以实现小爱控制的功能,前提条件。1需要tasmota 设备, 2.在本地搭建了mqtt服务可, 3.搭建了ha 4.在h…...

【笔记】结合 Conda任意创建和配置不同 Python 版本的双轨隔离的 Poetry 虚拟环境
如何结合 Conda 任意创建和配置不同 Python 版本的双轨隔离的Poetry 虚拟环境? 在 Python 开发中,为不同项目配置独立且适配的虚拟环境至关重要。结合 Conda 和 Poetry 工具,能高效创建不同 Python 版本的 Poetry 虚拟环境,接下来…...