LeetCode 之 Pow(x, n)（分治法）

约定不等于承诺〃 2022-08-03 08:41 10阅读 0赞

【问题描述】

Implement pow(x, n).

1.【基础知识】

1）分治的意识，一道O(N)的算法题，琢磨出O(lgN)的思想出来就是要求；

2.【屌丝代码】

卡壳的地方：

1.Time Limit Exceeded。

#include <vector>  
    #include <iostream>
    #include <algorithm> 
    #include <vector>
    #include <string>
    
    using namespace std; 
    
    // Status: Time Limit Exceeded
    class Solution {
    public:
        double myPow(double x, int n) {
    		double res(1);
    		if(n==0)
    			return 1;
            for(int i=0;i<n;i++)
    			res = res*x;
    		return res;
        }
    };
    
    int main()  
    {
    	int n=1;
    	double x = 2.0;
    	Solution mySln;
    	double num = mySln.myPow(x, n);
    	cout<<num<<endl;
    	while(1);
        return 0; 
    }

3.【源码AC】

//LeetCode, Pow(x, n)
    // 二分法， $ x^n = x^{n/2} * x^{n/2} * x^{n\%2} $
    // 时间复杂度 O(logn)，空间复杂度 O(1)
    class Solution {
    public:
        double myPow(double x, int n) {
            if (n < 0) 
                return 1.0 / power(x, -n);
            else 
                return power(x, n);
            }
    private:
        double power(double x, int n) {
            if (n == 0) 
                return 1;
            double v = power(x, n / 2);
            if (n % 2 == 0) 
                return v * v;
            else 
                return v * v * x;
        }
    };

4.【复盘】

1）卡壳部分

O(N)与O(lgN)的差距；

指数的负数考虑。

2）AC源码思想——二分（分治思想）

二分法： x^n = x^n/2 × x^n/2 × x^n%2

发表评论取消回复

表情：

评论列表（有 0 条评论，10人围观）

还没有评论，来说两句吧...

相关阅读

相关 Python|分治（分而治之）法

本文首发于微信公众号："算法与编程之美"，欢迎关注，及时了解更多此系列文章。前言分治思想自古就有，在《孙子兵法》中有这么一句话：凡治众如治寡，分数是也：斗众如斗寡，

向右看齐/ 2022年10月12日 01:55/ 0 赞/ 178 阅读

相关 leetcode 932. Beautiful Array | 932. 漂亮数组（分治法）

题目 [https://leetcode.com/problems/beautiful-array/][https_leetcode.com_problems_beaut

忘是亡心i/ 2022年09月02日 01:14/ 0 赞/ 9 阅读

相关分治法之合并排序（C实现）

include <stdio.h> void merge(int a[],int p,int q,int r) { int

迷南。/ 2022年08月09日 18:51/ 0 赞/ 178 阅读

相关 LeetCode 之 Pow(x, n)（分治法）

【问题描述】 Implement pow(x, n). 1.【基础知识】 1）分治的意识，一道O(N)的算法题，琢磨出O(lgN)的思想出来就是要求； 2.

约定不等于承诺〃/ 2022年08月03日 08:41/ 0 赞/ 11 阅读

相关分治法

问题描述:假定一个已经排好顺序的一维数组,运用二分搜索算法,使得当前输入元素x不在数组中是，返回小于x的最大元素位置i和大于x的最小元素的位置j,当搜索元素在数组中，i 和j

怼烎@/ 2022年06月03日 05:52/ 0 赞/ 260 阅读

相关 [Leetcode][分治法]相关题目汇总/分析/总结

题目汇总以下链接均为我博客内对应博文，有解题思路和代码，不定时更新补充。目前范围：Leetcode前150题分治法相关题目 [两个排序数组的中位数]

迷南。/ 2022年05月17日 11:42/ 0 赞/ 227 阅读

相关算法应用之分治法

一、分治法的基本概念在生活中当我们遇到复杂的问题时，我们通常会将这个复杂的问题分为几个小的问题或者分为几个步骤来解决，当我们将原问题拆分成若干个小问题或

刺骨的言语ヽ痛彻心扉/ 2022年02月23日 05:16/ 0 赞/ 271 阅读

相关分治法

Problem1一元三次方程的解题目描述有形如：ax3+bx2+cx+d=0这样的一个一元三次方程。给出该方程中各项的系数(a，b，c，d均为实数)，并约定该方程存在三

╰半夏微凉°/ 2022年01月06日 22:11/ 0 赞/ 297 阅读

相关分治法简介

简介对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，[递归][L

r囧r小猫/ 2021年11月23日 06:30/ 0 赞/ 368 阅读

相关 [leetcode]分治算法之beautiful Array

分治算法之Beautiful Array 题目解析答案题目 [leetcode入口][leetcode] 解析一个基本的思想是：

r囧r小猫/ 2021年09月28日 12:08/ 0 赞/ 306 阅读