【leetcode】Pow(x,n)

时间:2023-01-16 09:49:40

马上各种校招要开始了,怎么也得准备一下,之前一直在看看机器学习,NLP方面的东西,收获很多。最近换换脑子,回过头来做做leetcode,感觉还是蛮有意思的。今天刷了个水题,AC不高,然而难度也不高。。不知道为啥。第一次提交用了最最锉的方法,找虐的,很明显超时。于是开始想,第一个想到的就是二分,本来要做n次的计算,现在只要log(n)就可以了,没啥边界,注意n是非正数的情况就可以了:

class Solution:
# @param {float} x
# @param {integer} n
# @return {float}
def myPow(self, x, n):
res = 1
if n == 0:
#return 1
if n < 0:
x = float(1)/x
n = 0-n
while(n > 0):
if n % 2 == 1:
res *= x
n = n/2
x *= x
return res

  之后还想过是不是可以弄个3次方、4次方啥的,后来给AC了也就没整了。不过想想道理也是一样的,就是考虑不能整除的情况,相对来说,2次方考虑的较少,时间也算可以。不过上面非递归的情况理解起来有点困难的话,来个递归的版本:

class Solution:
# @param {float} x
# @param {integer} n
# @return {float}
def myPow(self, x, n):
if n < 0:
x = float(1)/x
n = 0-n if n == 0:
return 1
v = self.myPow(x, n/2)
if n % 2 == 0:
return v * v
else:
return v * v * x

【leetcode】Pow(x,n)的更多相关文章

  1. 【LeetCode】数学(共106题)

    [2]Add Two Numbers (2018年12月23日,review) 链表的高精度加法. 题解:链表专题:https://www.cnblogs.com/zhangwanying/p/979 ...

  2. 【leetcode】907&period; Sum of Subarray Minimums

    题目如下: 解题思路:我的想法对于数组中任意一个元素,找出其左右两边最近的小于自己的元素.例如[1,3,2,4,5,1],元素2左边比自己小的元素是1,那么大于自己的区间就是[3],右边的区间就是[4 ...

  3. 【leetcode】688&period; Knight Probability in Chessboard

    题目如下: On an NxN chessboard, a knight starts at the r-th row and c-th column and attempts to make exa ...

  4. 【LeetCode】Minimum Depth of Binary Tree 二叉树的最小深度 java

    [LeetCode]Minimum Depth of Binary Tree Given a binary tree, find its minimum depth. The minimum dept ...

  5. 【Leetcode】Pascal&amp&semi;&num;39&semi;s Triangle II

    Given an index k, return the kth row of the Pascal's triangle. For example, given k = 3, Return [1,3 ...

  6. 53&period; Maximum Subarray【leetcode】

    53. Maximum Subarray[leetcode] Find the contiguous subarray within an array (containing at least one ...

  7. 27&period; Remove Element【leetcode】

    27. Remove Element[leetcode] Given an array and a value, remove all instances of that value in place ...

  8. 【刷题】【LeetCode】007-整数反转-easy

    [刷题][LeetCode]总 用动画的形式呈现解LeetCode题目的思路 参考链接-空 007-整数反转 方法: 弹出和推入数字 & 溢出前进行检查 思路: 我们可以一次构建反转整数的一位 ...

  9. 【刷题】【LeetCode】000-十大经典排序算法

    [刷题][LeetCode]总 用动画的形式呈现解LeetCode题目的思路 参考链接 000-十大经典排序算法

随机推荐

  1. 能产生粒子效果的CAEmitterLayer

    能产生粒子效果的CAEmitterLayer 下雪效果: // // RootViewController.m // Cell // // Copyright (c) 2014年 Y.X. All r ...

  2. kvm虚似机监控

    [root@ok Desktop]# yum install virt-top [root@ok Desktop]# virt-top virt-top 22:53:44 - x86_64 4/4CP ...

  3. Ajax返回中文乱码问题(未解决)

    (未解决) 暂时使用办法:改用返回Map<String,String>形式的返回值,在ajax中获取json形式的数据.

  4. VS2010 安装使用STLPort

    VS2010 安装使用STLport 1.本机环境 win7 64位 visual studio 2010 中文旗舰版 STLport-5.2.1.tar.bz2 2.下载STLport http:/ ...

  5. eclipse 插件之Code Folding

    功能: eclipse自带折叠包括方法, import, 注释等得折叠功能, code folding 插件对其增强. 1. 下载插件:( 也可以用link方式, 我的是link安装, jar包网上很 ...

  6. Thread和Runnable差别

    继承Thread类的,我们相当于拿出三件事即三个卖票10张的任务分别分给三个窗体,他们各做各的事各卖各的票各完毕各的任务.由于MyThread继承Thread类.所以在new MyThread的时候在 ...

  7. Android常用的颜色列表 color&period;xml

    转自:http://blog.csdn.net/libaineu2004/article/details/41548313 <?xml version="1.0" encod ...

  8. html天气预报小插件

    <head></head> <body> <iframe width="225" scrolling="no" hei ...

  9. SE 2014年5月5日

    如图配置 某企业网络规划图(三台交换设备/三台路由设备) 接入层 SW1 连接终端用户 汇聚层 SW2 SW3 核心层 R1 R2 R5 1. 如图 SW1 SW2 SW3 物理链路两两相连接,网络中 ...

  10. JS对JSON对象遍历输出的时候真的是按照顺序输出吗?

    对象的遍历输出并不是按照对象属性定义顺序来的,那么是按照什么规则来的呢,仔细深入研究你会发现,这还跟浏览器有关系,Chrome跟IE是不一样的,所以给出以下结论: Chrome Opera 的 Jav ...