[题解]LeetCode 326. 3的幂(C++)
2021/9/23 20:11:30
本文主要是介绍[题解]LeetCode 326. 3的幂(C++),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目
给定一个整数,写一个函数来判断它是否是 3 的幂次方。如果是,返回 true ;否则,返回 false 。
整数 n 是 3 的幂次方需满足:存在整数 x 使得 n == 3x
示例 1:
输入:n = 27 输出:true
示例 2:
输入:n = 0 输出:false
示例 3:
输入:n = 9 输出:true
示例 4:
输入:n = 45 输出:false
提示:
- \(-2^{31} <= n <= 2^{31} - 1\)
进阶:
- 你能不使用循环或者递归来完成本题吗?
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/power-of-three
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
思路
递归,如果n = 0就判定false,如果n = 1就判定true。如果n除以3有余数就返回false,没有就递归判断n/3。
时间复杂度O(log(n)),空间复杂度O(log(n))。
代码
class Solution { public: bool isPowerOfThree(int n) { if(n == 0) return false; if(n == 1) return true; if(n % 3) return false; return isPowerOfThree(n / 3); } };
改进
循环,当n > 0且n除以3余数为0时,不停地令n/=3。最后判断n是否为1。
时间复杂度O(log(n)),空间复杂度O(1)。
代码
class Solution { public: bool isPowerOfThree(int n) { while(n && n % 3 == 0) { n /= 3; } return n == 1; } };
改进2
这题进阶要求不用递归也不用循环,我想了一会没想出来方法就去看题解了,然后给我看傻了。原来可以用int范围内最大的3的幂次方来除以n,没有余数且n为正数就说明是正确结果。
时间复杂度O(1),空间复杂度O(1)。
代码
class Solution { public: bool isPowerOfThree(int n) { return n > 0 && 1162261467 % n == 0; } };
这篇关于[题解]LeetCode 326. 3的幂(C++)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-12-24怎么切换 Git 项目的远程仓库地址?-icode9专业技术文章分享
- 2024-12-24怎么更改 Git 远程仓库的名称?-icode9专业技术文章分享
- 2024-12-24更改 Git 本地分支关联的远程分支是什么命令?-icode9专业技术文章分享
- 2024-12-24uniapp 连接之后会被立马断开是什么原因?-icode9专业技术文章分享
- 2024-12-24cdn 路径可以指定规则映射吗?-icode9专业技术文章分享
- 2024-12-24CAP:Serverless?+AI?让应用开发更简单
- 2024-12-23新能源车企如何通过CRM工具优化客户关系管理,增强客户忠诚度与品牌影响力
- 2024-12-23原创tauri2.1+vite6.0+rust+arco客户端os平台系统|tauri2+rust桌面os管理
- 2024-12-23DevExpress 怎么实现右键菜单(Context Menu)显示中文?-icode9专业技术文章分享
- 2024-12-22怎么通过控制台去看我的页面渲染的内容在哪个文件中呢-icode9专业技术文章分享