《程序员面试金典(第6版)》面试题 08.05. 递归乘法

题目描述

  • 递归乘法。 写一个递归函数,不使用 * 运算符, 实现两个正整数的相乘。可以使用加号、减号、位移,但要吝啬一些。

示例1:

输入:A = 1, B = 10
输出:10

示例2:

输入:A = 3, B = 4
输出:12
提示:

保证乘法范围不会溢出

解题思路与代码

我认为这道题都不能算一道中等难度的题?难道说,就是为了要考验你会不会写递归函数吗?有点搞不懂。
我认为这道题就是到简单题

方法一: 乘法变累加

这种方法没什么特别的,就是B去做递减,A去累加自身,然后最后返回A就行了。这道题没难度。

具体实现看代码:

class Solution {
public:
    int multiply(int A, int B) {
        if(A == 0 || B == 0) return 0;
        int temp = A;
        overloadOperator(A,B,temp);
        return A;
    }
    
    int overloadOperator(int& A,int& B,int temp){
        if(B == 1) return A;
        A += temp;
        B -= 1;
        overloadOperator(A,B,temp);
        return A;
    }
};

在这里插入图片描述

复杂度分析

这段代码实现了一个简单的整数乘法算法,通过重复加法代替乘法。multiply函数是主要的接口,而overloadOperator函数递归地执行加法。分析时间复杂度和空间复杂度如下:

时间复杂度:overloadOperator函数中的递归次数取决于整数B的大小,每次递归调用时B减1。因此,时间复杂度为O(B),其中B是整数B的值。在最坏的情况下,如果B是一个较大的正整数,时间复杂度将趋向于O(B)。

空间复杂度:由于overloadOperator函数是递归调用的,每次调用都会在栈上为局部变量分配空间。递归调用的次数与整数B的值成正比,因此空间复杂度为O(B)。在最坏的情况下,如果B是一个较大的正整数,空间复杂度将趋向于O(B)。

需要注意的是,这个代码实现中使用了尾递归,有些编译器可能会对尾递归进行优化,将其转换为迭代形式。如果编译器执行了这种优化,那么空间复杂度将降为O(1),因为递归调用不再需要额外的栈空间。然而,并非所有编译器都会执行这种优化,因此在分析空间复杂度时,我们假设它为O(B)。

总结

这道题是一道没有什么难度的简单题,虽然它自认为自己是中等难度的题

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/5486.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

vue3使用useMouseInElement实现图片局部放大预览效果

1、首先要安装vueuse/core npm i vueuse/core2、实现过程如下&#xff1a; <template><div class"goods-image"><!-- 大图 --><div v-show"show" class"large" :style"[{backgroundImage:url(${images[currIndex]})…

Cursor,程序员的 AI 代码编辑助手

相信大家都或多或少地听说过、了解过 chatGPT &#xff0c;半个月前发布的 GPT-4 &#xff0c;可谓是 AI 赛道上的一个王炸 那么今天咸鱼给大家分享一个开源的 AI 代码编辑器——Cursor&#xff0c;让各位程序员在编程之路上一骑绝尘 &#x1f603; 介绍 Cursor 是一个人工智…

深度学习应用技巧4-模型融合:投票法、加权平均法、集成模型法

大家好&#xff0c;我是微学AI&#xff0c;今天给大家介绍一下&#xff0c;深度学习中的模型融合。它是将多个深度学习模型或其预测结果结合起来&#xff0c;以提高模型整体性能的一种技术。 深度学习中的模型融合技术&#xff0c;也叫做集成学习&#xff0c;是指同时使用多个…

209. 长度最小的子数组

209. 长度最小的子数组 力扣题目链接(opens new window) 给定一个含有 n 个正整数的数组和一个正整数 s &#xff0c;找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组&#xff0c;并返回其长度。如果不存在符合条件的子数组&#xff0c;返回 0。 示例&#xff1a; 输入…

Java实现查找文件

1 问题 如何利用java来查找文件&#xff1f; 2 方法 2.1定义一个查找类&#xff0c;设置两个参数&#xff08;查找的目录和文件后缀名&#xff09;&#xff0c;然后判断文件夹是否为空 2.2 判断是否是文件夹&#xff0c;如果是文件夹则将里面的文件放入数组进行遍历&#xff08…

【Python零基础学习入门篇①】——基本语法与变量

⬇️⬇️⬇️⬇️⬇️⬇️ ⭐⭐⭐Hello&#xff0c;大家好呀我是陈童学&#xff0c;一个普通大一在校生&#xff0c;请大家多多关照呀嘿嘿&#x1f601;&#x1f60a;&#x1f618; &#x1f31f;&#x1f31f;&#x1f31f;技术这条路固然很艰辛&#xff0c;但既已选择&#x…

Redis 事务相关操作

Redis 作为一个非关系型内存数据库&#xff0c;也有事务定义 1. 事务的定义-ACID特性 A表示原子性&#xff1a;即事务是一个不可分割的实体&#xff0c;事务中的操作要么都完成&#xff0c;要么都不完成 C表示一致性&#xff1a;即事务前后数据完整性必须一致&#xff0c;假…

基于springboot实现数码论坛系统设计与实现演示【附项目源码+论文说明】

基于springboot实现数码论坛系统设计与实现演示开发语言&#xff1a;Java 框架&#xff1a;springboot JDK版本&#xff1a;JDK1.8 服务器&#xff1a;tomcat7 数据库&#xff1a;mysql 5.7 数据库工具&#xff1a;Navicat11 开发软件&#xff1a;eclipse/myeclipse/idea Maven…

Jieba分词的准确率提升:使用paddle模式进行分词(使用百度飞桨深度学习模型进行分词)

1 Paddle模式简介 jieba中的paddle模式是指使用飞桨&#xff08;PaddlePaddle&#xff09;深度学习框架加速分词的一种模式。相对于传统的分词算法&#xff0c;paddle模式采用了深度学习模型&#xff0c;可以获得更高的分词准确度和更快的分词速度。 paddle模式是基于卷积神经…

数据分析之Pandas(2)

3.Pandas 文章目录3.Pandas3.3 Pandas进阶3.3.1 数据重塑和轴向旋转&#xff08;1&#xff09;层次化索引Series的层次化索引DataFrame的层次化索引层次化——电影数据示列&#xff08;2&#xff09;数据旋转3.3.2 数据分组、分组运算3.3.3 离散化处理3.3.4 合并数据集&#xf…

使用langchain打造自己的大型语言模型(LLMs)

我们知道Openai的聊天机器人可以回答用户提出的绝大多数问题,它几乎无所不知&#xff0c;无所不能&#xff0c;但是由于有机器人所学习到的是截止到2021年9月以前的知识&#xff0c;所以当用户询问机器人关于2021年9月以后发送的事情时&#xff0c;它无法给出正确的答案&#x…

【Java 21 新特性 】顺序集合(Sequenced Collections)

Java 21 中增加了一种新的集合类型&#xff1a;顺序集合&#xff08;Sequenced Collections&#xff09;。要介绍顺序集合&#xff0c;就首先要说明一下出现顺序&#xff08;encounter order&#xff09;。出现顺序指的是在遍历一个集合时&#xff0c;集合中元素的出现顺序。有…

Redis高频40问

Redis连环40问&#xff0c;绝对够全&#xff01; Redis是什么&#xff1f; Redis&#xff08;Remote Dictionary Server&#xff09;是一个使用 C 语言编写的&#xff0c;高性能非关系型的键值对数据库。与传统数据库不同的是&#xff0c;Redis 的数据是存在内存中的&#xf…

Python:每日一题之《全排列的价值》真题练习

问题描述 对于一个排列 A(a1​,a2​,⋯,an​), 定义价值 ci​ 为 a1​ 至 ai−1​ 中小于 ai​ 的数 的个数, 即 。 ci​∣{aj​∣j<i,aj​<ai​}∣。 ​ 定义 A 的价值为 ∑i1n​ci​ 。 给定 n, 求 1 至 n 的全排列中所有排列的价值之和。 输入格式 输入一行包含…

SpringBoot(五) Docker

一、简介 Docker是一个开源的应用容器引擎&#xff1b; Docker支持将软件编译成一个镜像&#xff1b;然后在镜像中各种软件做好配置&#xff0c;将镜像发布出去&#xff0c;其他使用者可以直接使用这个镜像。 运行中的这个镜像称为容器&#xff0c;容器启动是非常快速的。类似…

HTB-soccer

信息收集 22 ssh80 http9091 对80进行检查。 搜索得知存在默认登陆密码admin:admin123 和 user:12345。 右上角有一个upload&#xff0c;试试能不能本地上传。 能够获取上传的路径&#xff0c;但是此文件没有写入权限。 切换到tiny文件夹再次上传。 在/tiny/uploads能够…

文心一言,被网友玩坏了哈哈哈哈哈哈哈

现在人工智能正火&#xff0c;百度“文心一言”出来&#xff0c;虽然只是小范围测试&#xff0c;但已经被玩坏了&#xff01;这应该算是卖全羊送狗肉娃娃…菜…也没毛病哈看来对美女还有些误解虎头虎脑的胖大胖小子哈哈哈哈哈鸳鸯和锅都有&#xff0c;还不满意吗什么奇行种似乎…

数据结构和算法(3):递归

目录概述单路递归 Single Recursion多路递归 Multi Recursion递归优化-记忆法递归时间复杂度-Master theorem递归时间复杂度-展开求解概述 定义 计算机科学中&#xff0c;递归是一种解决计算问题的方法&#xff0c;其中解决方案取决于同一类问题的更小子集 In computer scien…

情感语音转换学习

情感语音转换&#xff08;Emotional Voice conversion&#xff09; 言语不仅仅是词汇&#xff0c;它承载着说话者的情感。之前的研究(Mehrabian和Wiener, 1967)表明&#xff0c;在交流情感和态度时&#xff0c;口头语言只传达了7%的信息&#xff0c;非语言的声音属性(38%)和面…

简单研究一下 OpenAI 的官方文档

文档地址&#xff1a;https://platform.openai.com/docs/ 接口说明&#xff1a;https://platform.openai.com/docs/api-reference 一、概览 OpenAI API 可直接调用模型接口&#xff0c;也可在线微调&#xff08;不过只能微调GPT-3系列模型&#xff09;。 本小节主要介绍 toke…