【刷题】 leetcode 面试题 08.05.递归乘法

简介: 递归算法是一种在计算机科学和数学中广泛应用的解决问题的方法,其基本思想是利用问题的自我相似性,即将一个大问题分解为一个或多个相同或相似的小问题来解决。递归算法的核心在于函数(或过程)能够直接或间接地调用自身来求解问题的不同部分,直到达到基本情况(也称为基础案例或终止条件),这时可以直接得出答案而不必再进行递归调用。


递归算法介绍:

递归算法是一种在计算机科学和数学中广泛应用的解决问题的方法,其基本思想是利用问题的自我相似性,即将一个大问题分解为一个或多个相同或相似的小问题来解决。递归算法的核心在于函数(或过程)能够直接或间接地调用自身来求解问题的不同部分,直到达到基本情况(也称为基础案例或终止条件),这时可以直接得出答案而不必再进行递归调用。

以下是递归算法的几个关键特征和步骤:

递归定义:

递归算法通常基于一个问题的递归定义,也就是说,问题的解决方案可以通过一系列越来越小的同类型子问题的解决方案来构建。

基本情况(Base Case):

每个递归算法都需要一个或多个基本情况,这是递归链条终止的条件。对于任何递归问题而言,必须存在至少一个基本情况,使得递归函数在遇到这种情况时不进行进一步的递归调用,而是直接返回结果。

  1. 递归步骤(Recursive Step):
    当问题不满足基本情况时,递归函数需要将原问题转换成一个或多个更简单的子问题,并通过调用自身来解决这些子问题。
  2. 归纳原理:
    递归算法背后的理念类似于数学归纳法,假设问题的较小规模实例已经正确解决,那么通过递归步骤逐步将问题规模扩大, 直到到达原问题的规模,从而得出原问题的解。
  3. 堆栈机制:
    在实际运行过程中,每一次递归调用都会将待解决的子问题压入系统调用栈中,直到遇到基本情况并开始逐层返回结果,这就是所谓的“有去有回”。

动图帮你理解:

image.gif

1 题目描述


题目描述简洁明了,却蕴含着深厚的算法设计与逻辑推演的智慧。题目要求我们不使用标准的乘法运算符 * 来实现两个整数之间的乘法操作。乍一看,这似乎是对传统乘法运算的一种颠覆,实则是对编程能力和数学思维深度的一次独特考验。

2 思路一(返璞归真版)

首先我就想到了乘法的加法表示:A * B = B 个 A 相加。

也可得到递推公式:

A * B = A * (B - 1) + A

我们很容易就可以构造出递归算法

int multiply(int A, int B){
  //B 为 1 直接返回B
    if(B == 1) return A;
    return A + multiply(A , B - 1);
}

来看运行效果:

3 思路二(二进制乘法器版)

接下来我们换一种方法,大家一定记得小时候计算乘法的时候,在纸上打草稿的那种竖式。这其实乘法器的思路。这种算法我们以后会经常遇到,一定要记住我们的竖式计算,这样可以把复杂的问题简单化!!!

来看代码:

int multiply(int A, int B){
    //乘法器
    //二进制运算
    //B 为乘数 不为零才继续
    if(B)
    {
        if(B & 1)//B 末位是1 
        {
            // A 左移(放大 因为下一位乘数进位)
            //使用 long long 类型防止 A 超出范围
            return multiply((long long)A << 1, B >> 1) + A;
        }
        else//B 为零 就不加 A
        {
            return multiply((long long)A << 1 , B >> 1);
        }
    }
    //B 为 0 直接返回 0 
    else 
        return 0;
}

运行效果:

4 思路三(变态版)

该思路也是使用了二进制乘法器的思路

巧妙的使用了三目运算符简化if语句。

来看代码:

int multiply(int A, int B){
  return B ? multiply((long long)A << 1,B >> 1) +((B & 1)? A:0) : 0 ;
}

效果也是非常好!!!!过啦!!!

送给大家一句话:

肆无忌惮的放任自己,这样得来的自由,终将在现实中轰然倒塌。而自律赢来的,是你对现实的自主感,是真正的自由

Thanks♪(・ω・)ノ谢谢阅读

下一篇文章见!!!

相关文章
|
2月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
3月前
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
116 2
|
24天前
|
机器学习/深度学习 人工智能 自然语言处理
280页PDF,全方位评估OpenAI o1,Leetcode刷题准确率竟这么高
【10月更文挑战第24天】近年来,OpenAI的o1模型在大型语言模型(LLMs)中脱颖而出,展现出卓越的推理能力和知识整合能力。基于Transformer架构,o1模型采用了链式思维和强化学习等先进技术,显著提升了其在编程竞赛、医学影像报告生成、数学问题解决、自然语言推理和芯片设计等领域的表现。本文将全面评估o1模型的性能及其对AI研究和应用的潜在影响。
19 1
|
2月前
|
数据采集 负载均衡 安全
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口
本文提供了多个多线程编程问题的解决方案,包括设计有限阻塞队列、多线程网页爬虫、红绿灯路口等,每个问题都给出了至少一种实现方法,涵盖了互斥锁、条件变量、信号量等线程同步机制的使用。
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口
|
3月前
|
存储
LeetCode------递归(爬楼梯)
这篇文章通过LeetCode上的"爬楼梯"问题介绍了递归的基本概念和实现方法,包括递归公式的推导、基本递归实现、使用备忘录优化以避免重复计算,以及自底向上的迭代方法来提高效率。
LeetCode------递归(爬楼梯)
|
3月前
|
算法 Python
【Leetcode刷题Python】 LeetCode 2038. 如果相邻两个颜色均相同则删除当前颜色
本文介绍了LeetCode 2038题的解法,题目要求在一个由'A'和'B'组成的字符串中,按照特定规则轮流删除颜色片段,判断Alice是否能够获胜,并提供了Python的实现代码。
51 3
|
3月前
|
Python
【Leetcode刷题Python】50. Pow(x, n)
本文介绍了LeetCode第50题"Pow(x, n)"的解法,题目要求实现计算x的n次幂的函数,文章提供了递归分治法的详细解析和Python实现代码。
27 1
|
3月前
|
Python
【Leetcode刷题Python】LeetCode 478. 在圆内随机生成点
本文介绍了LeetCode 478题的解法,题目要求在给定圆的半径和圆心位置的情况下实现在圆内均匀随机生成点的功能,并提供了Python的实现代码。
31 1
|
3月前
|
算法 Python
【Leetcode刷题Python】295. 数据流的中位数
本文介绍了一种使用Python实现的数据结构,用以支持数据流中添加整数并返回当前所有元素的中位数,通过排序列表来计算中位数。
25 1
|
3月前
|
算法 Python
【Leetcode刷题Python】73. 矩阵置零
本文介绍了LeetCode第73题的解法,题目要求在给定矩阵中将所有值为0的元素所在的行和列全部置为0,并提供了一种原地算法的Python实现。
32 0
【Leetcode刷题Python】73. 矩阵置零
下一篇
无影云桌面