leetcode-50-Pow(x, n)
2022/2/28 23:26:44
本文主要是介绍leetcode-50-Pow(x, n),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
1.问题描述
https://leetcode-cn.com/problems/powx-n/
2. 解题代码
2.1. 基本解法
public double MyPow(double x, int n) { if (x == 1 || n == 0) { return 1; } if (n == 1) { return x; } double dReturn = x; int num = n; if (n < 0) { dReturn = 1 / x; num = n * -1; } else { dReturn = dReturn * dReturn; } for (int i = 2; i <= num;) { if (i * 2 > num) { if (n > 0) { dReturn = dReturn * x; } else { dReturn = dReturn / x; } i = i + 1; } else { dReturn = dReturn * dReturn; i = i * 2; } } return dReturn; }
2.2. 快速幂 + 递归解法
public double MyPow(double x, int n) { long N = n; return N >= 0 ? QuickMul(x, N) : 1.0 / QuickMul(x, -N); } public double QuickMul(double x, long N) { if (N == 0) { return 1.0; } double y = QuickMul(x, N / 2); return N % 2 == 0 ? y * y : y * y * x; }
复杂度分析
-
时间复杂度:O(\log n)O(logn),即为递归的层数。
-
空间复杂度:O(\log n)O(logn),即为递归的层数。这是由于递归的函数调用会使用栈空间。
2.2. 快速幂 + 迭代解法
public double MyPow(double x, int n) { long N = n; return N >= 0 ? QuickMul(x, N) : 1.0 / QuickMul(x, -N); } public double QuickMul(double x, long N) { double ans = 1.0; // 贡献的初始值为 x double x_contribute = x; // 在对 N 进行二进制拆分的同时计算答案 while (N > 0) { if (N % 2 == 1) { // 如果 N 二进制表示的最低位为 1,那么需要计入贡献 ans *= x_contribute; } // 将贡献不断地平方 x_contribute *= x_contribute; // 舍弃 N 二进制表示的最低位,这样我们每次只要判断最低位即可 N /= 2; } return ans; }
复杂度分析
-
时间复杂度:O(\log n)O(logn),即为对 nn 进行二进制拆分的时间复杂度。
-
空间复杂度:O(1)O(1)。
这篇关于leetcode-50-Pow(x, n)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-26小白家庭 nas 搭建方案-icode9专业技术文章分享
- 2024-06-23AI大模型企业应用实战(14)-langchain的Embedding
- 2024-06-23AI大模型企业应用实战(15)-langchain核心组件
- 2024-06-23AI大模型企业应用实战(16)-langchain核心组件
- 2024-06-23AI 大模型企业应用实战(06)-初识LangChain
- 2024-06-19EntBot.ai: AI Website Chatbot for Product Guides and Development Doc
- 2024-06-17zero-shot-learning-definition-examples-comparison
- 2024-06-06Package Easy(基于 NSIS 的打包exe安装包工具)使用方法-icode9专业技术文章分享
- 2024-06-06基于 casdoor 的 ELK 开源登录认证解决方案: elk-auth-casdoor-icode9专业技术文章分享
- 2024-05-29Elasticsearch慢查询日志配置