Question:
Implement pow(x,n).
Answer 1: O(n)
class Solution {
public:
double pow(double x, int n) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if(n == 0) return 1;
if(x == 0) return 0;
bool flag = false; // is negative
if(n < 0) {
flag = true;
n = -n;
}
/*
double ret = 1;
for(int i = 0; i < n; ++i){ // error when n is max integer, such as n = 2147483647 overflow
ret *= x;
}
*/
double tmp = x;
double ret = 1;
while(n > 0) {
if(n & 1 == 1){ // or (n & 1) or (n % 2) or (n % 2 == 1)
ret *= tmp;
}
tmp *= tmp;
n >>= 1;
}
return flag ? 1.0/ret : ret;
}
};
注意点:
题目非常简单,担忧许多细节需要考虑
1) x = 0 或 n = 0
2) n 为正或负数
3) n为正整数边界值(error 错误)
Answer 2: O(log(n))
class Solution {
public:
double pow2(double x, int n){
if(n == 0){
return 1;
}
double mul = pow2(x, n/2);
if(n & 1) {
return x * mul * mul;
} else {
return mul * mul;
}
}
double pow(double x, int n) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if(n < 0){
return 1.0 / pow2(x, -n);
} else {
return pow2(x, n);
}
}
};
注意点:
1) 递归二分法
2) n为正/负数
分享到:
相关推荐
15 | [3 Sum](https://leetcode.com/problems/3sum/) | [C++](./C++/3sum.cpp) [Python](./Python/3sum.py) | _O(n^2)_ | _O(1)_ | Medium || Two Pointers 16 | [3 Sum Closest]...
示例 1:输入:x = 2.00000, n = 10输出:1024.00000示例 2:输入:x = 2.10000, n = 3输出:9.26100示例 3
11.1 实现pow(x, n) 11.2 Sqrt(x) 12. 贪心算法 12.1 跳台阶游戏 12.2 买卖股票的最佳时机 12.2.1 最多允许交易一次 12.2.2 可以交易任意多次 12.2.3 最多可以交易两次 12.2.4 可以交易任意多次 12.2.5 交易后需要...
leetcode中国 LeetcodeSolution leetcode题目解法(持续更新) ...Pow(x, n) divide and conquer 51 N皇后 backtracking 52 N皇后 II backtracking 54 螺旋矩阵 array 62 不同路径 dynamic program
Pow(x,n)](#50。Pow(x,n)) [257。(#257。二叉树的所有路径) [230。二叉搜索树中第K小的元素](#230。二叉搜索树中第K小的元素) [119。杨辉三角II](#119。杨辉三角II) [136。只出现一次的数字]...
atoi盛最多水的容器三数之和最接近的三数之和四数之和删除链表的倒数第 n 个节点括号生成两两交换链表中的节点两数相除在排序数组中查找元素的第一个和最后一个位置有效的数独字符串相乘字母异位词分组pow-...
Pow(xn) leetcode Binary-Search-3 问题1 Pow(x,n) () 问题2 找到 K 个最近的元素 ()
pow(x,n) 简单的 7号 反向整数 简单的 6号 之字形反转 简单的 2号 添加两个数字 简单的 3号 无重复字符的最长子串 中等的 4号 两个有序数组的中位数 难的 2016 年 11 月 17 日更新 数字 问题 等级 最长回文子串 中等...
第 338 章leetcode_cpp ...Pow(x,n) 中51 N 皇后区硬52 N 皇后区 II 硬53 Max Subarray Easy 56 合并间隔 中等58 最后一句话的长度 Easy 59 Spiral Matrix II 培养基61 轮播列表中第62话第63话64 最小路径和中66
在旋转排序数组中搜索140.Fast Power 428.Pow(x,n) 845.最大公约数39.恢复旋转排序数组8,旋转字符串 两个指针56.两次相加415.有效回文891.有效回文II 521.删除重复的号码604.窗口总和610.TwoSum-差等于目标228....
Leetcode扑克 项目简介 该项目为《剑指Offer》题解 OnlineJudge 题目 个人建议能使用LeetCode还是尽量用LeetCode。...Pow(x, n) 调整数组顺序使奇数位于偶数前面 905. Sort Array By Parity 链表中倒数第
Pow(x, n) 实现 pow(x, n),它计算 x 的 n (xn) 次幂。 字符串到整数 (atoi) 实现 atoi 将字符串转换为整数。 该函数首先根据需要丢弃尽可能多的空白字符,直到找到第一个非空白字符。 然后,从这个字符开始,取一个...
leetcode卡 DataWhale编程集训第1期...递归:学习斐波那契数列及递归思想,并最终盲打代码实现斐波那契数列及LeetCode上的Pow(x,n)(不限制语言)!最终打卡方式为:斐波那契数列+递归心得笔记+LeetCode提交结果与代码!
编写程序计算pow(x, y) 50. pow(x, n) 5.7 计算 x^y 2. 给定一个指向单向链表中要删除的节点的指针,如何删除它? 237. 删除链表中的节点 2.3 删除中间节点 3.从第一个字符串中删除出现在第二个字符串中的字符 4. ...
Pow(x, n) 列表 #1431. 拥有最多糖果的孩子 #1385. 找出两个数组之间的距离值 #1337. 矩阵中最弱的 K 行 #15. 3Sum(前指针和后指针) #347. 前 K 个频繁元素(堆) #203. 删除链表元素 动态规划 #1043. 最大和的...
pow(x, n) 34. 查找有序数组中元素的首尾位置 1-是 35. 搜索插入位置 1-是 658. 找出 K 个最近的元素 1-否 33. 在旋转排序数组中搜索 1-否 81. 在旋转排序数组中搜索 II 1-否 153. 在旋转排序数组中求最小值 154. 在...
Pow(x,n) 优化 Permutations (交换 取子集两种方式) Trie树 11 中序遍历 无堆栈 (前序 后序) 12 map边删除 边输出 不太建议这么用。。。 以及其他基本用法 iterate 红黑树 13.set 16.unordered_map 与 map 17.最大...
leetcode 跳跃 leetcodeTest 刷题 leetcode 1.两数之和 2.两数相加 ...Pow(x,n) 中等题 快速幂算法 53 最大子序和 简单题 54 螺旋矩阵 中等题 设置上下左右边界 55 跳跃游戏 中等题 关于递归返回值,如果
Pow(x,n) 58 最后一句话的长度 88 合并排序数组 100同一棵树 101 对称树 104 二叉树的最大深度 3 无重复字符的最长子串 4月14日 第107章 二叉树层次遍历二 4 月 18 日搜索 274 国指 34 搜索范围 33 在旋转
n).md](Leetcode/0050-Pow(x, n).md) 中等 困难 困难 简单 中等 中等 中等 困难 简单 中等 困难 中等 中等 中等 中等 困难 简单 简单 困难 简单 简单 中等 困难 中等 中等 中等 困难 中等 中等 中等 中等 中等 中等 ...