leetcode经典算法——快速幂

这篇具有很好参考价值的文章主要介绍了leetcode经典算法——快速幂。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

实现 pow(x, n) ,即计算 x 的整数 n 次幂函数(即,xn )。
暴力方法肯定是循环循环n次,
每一次*x
leetcode经典算法——快速幂,数据结构入门,算法,C语言,算法,leetcode,职场和发展
显然此方法遇到大的数字会超时
leetcode经典算法——快速幂,数据结构入门,算法,C语言,算法,leetcode,职场和发展
那么我们要引进一个思想,快速幂算法
例如: x^97

leetcode经典算法——快速幂,数据结构入门,算法,C语言,算法,leetcode,职场和发展
我们可以看出,从右向左
每当n为奇数时,就会多乘一次x
例如:x97 = x48 * x48 * x;
当n为偶数时,不需要此操作
x48 = x24 * x24 ;
由于从0~97 遍历的话 我们不知道何时+1;
所以我们选择从97~0递归

leetcode经典算法——快速幂,数据结构入门,算法,C语言,算法,leetcode,职场和发展
接下来代码实现文章来源地址https://www.toymoban.com/news/detail-642324.html

double quickly_pow(double x,long long N)
{
    if(N==0)
    {
        return 1.00;
    }
    else
    {
        double y=quickly_pow(x,N/2);
        return N%2==0?y*y:y*y*x;
    }
}

double myPow(double x, int n)
{
    long long N=n;
    return N>0?quickly_pow(x,N):1.0/quickly_pow(x,-N);
}

到了这里,关于leetcode经典算法——快速幂的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构与算法】十大经典排序算法-插入排序

    🌟 个人博客: www.hellocode.top 🏰 Java知识导航: Java-Navigate 🔥 CSDN: HelloCode. 🌞 知乎 :HelloCode 🌴 掘金 :HelloCode ⚡如有问题,欢迎指正,一起学习~~ 插入排序(Insertion Sort)是一种简单直观的排序算法,其基本思想是将一个记录插入到已排好序的有序序列中,直到所有记录

    2024年02月13日
    浏览(80)
  • 【数据结构与算法】十大经典排序算法-冒泡排序

    🌟 个人博客: www.hellocode.top 🏰 Java知识导航: Java-Navigate 🔥 CSDN: HelloCode. 🌴 掘金 :HelloCode 🌞 知乎 :HelloCode ⚡如有问题,欢迎指正,一起学习~~ 冒泡排序(Bubble Sort)是一种简单的排序算法,它通过重复地交换相邻元素的位置来将最大(或最小)的元素逐步“冒泡”到

    2024年02月14日
    浏览(69)
  • 200个经典面试题(算法思想+数据结构)_1

    1. 爬楼梯 70. Climbing Stairs (Easy) 题目描述:有 N 阶楼梯,每次可以上一阶或者两阶,求有多少种上楼梯的方法。 定义一个数组 dp 存储上楼梯的方法数(为了方便讨论,数组下标从 1 开始),dp[i] 表示走到第 i 个楼梯的方法数目。 第 i 个楼梯可以从第 i-1 和 i-2 个楼梯再走一步

    2024年02月13日
    浏览(42)
  • 【数据结构与算法】:10道链表经典OJ

    思路1:遍历原链表,将 val 所在的节点释放掉。(太麻烦) 思路2:创建新链表,再遍历原链表,找到不为 val 的节点尾插到新链表。 思路1代码实现如下: 注意: 1.当链表为空时,直接返回NULL即可。 2.当尾插上最后一个有效节点时,此时它的 next 可能还与最后一个节点相链接,

    2024年04月14日
    浏览(36)
  • 【数据结构入门指南】二叉树顺序结构: 堆及实现(全程配图,非常经典)

    普通的二叉树是不适合用数组来存储的,因为可能会存在大量的空间浪费。 而完全二叉树更适合使用顺序结构存储。   现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储 ,需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事,一个是数据结构,一

    2024年02月12日
    浏览(36)
  • 【数据结构】单链表经典算法题的巧妙解题思路

    目录 题目 1.移除链表元素 2.反转链表 3.链表的中间节点 4.合并两个有序链表 5.环形链表的约瑟夫问题 解析 题目1:创建新链表 题目2:巧用三个指针 题目3:快慢指针 题目4:哨兵位节点 题目5:环形链表   介绍完了单链表,我们这次来说几个经典的题目,本篇的题目衔接下一

    2024年04月28日
    浏览(54)
  • 头歌数据结构实训参考---十大经典排序算法

    可通过 目录 快速查阅对应排序算法

    2024年02月04日
    浏览(62)
  • 【数据结构入门指南】二叉树链式结构的实现(保姆级代码思路解读,非常经典)

    其他数据结构不同,二叉树的增删查改接口实现的意义不大(后续搜索树的增删查改才有意义)。普通初阶二叉树更重要的是学习控制结构,为后续的AVL树、红黑树等高级数据结构打下基础。同时大部分OJ题也出在此处。 所谓二叉树遍历(Traversal)是按照某种特定的规则,依次

    2024年02月11日
    浏览(44)
  • 【数据结构与算法】三个经典案例带你了解动态规划

    从表中我们可以看到,最大的公共子串长度为2,一共有两个长度为2的公共子串,分别是第一个字符串的第2个字符到第3个字符和第一个字符串的第3个字符到第4个字符,即 ba 和 ac 根据上面的方法,我们来用代码封装一下求取最大公共子串的函数 function publicStr(s1, s2) { // 创建

    2024年04月09日
    浏览(92)
  • 算法竞赛备赛之经典数据结构训练提升,暑期集训营培训

    我们将结构体和指针结合来实现链表 我们算法主要是用数组来模拟链表,这样效率会高一些。 数组模拟单链表 邻接表:存储图和树 实现一个单链表,链表初始为空,支持三种操作: 向链表头插入一个数 删除第k个插入的数后面的数 在第k个前面插入一个数 数组模拟双链表的

    2024年02月16日
    浏览(52)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包