LeetCode 231. Power of Two (Java版; Easy)

男娘i 2023-07-03 06:11 106阅读 0赞

welcome to my blog

LeetCode Top Interview Questions 231. Power of Two (Java版; Easy)

题目描述

  1. Given an integer, write a function to determine if it is a power of two.
  3. Example 1:
  5. Input: 1
  6. Output: true 
  7. Explanation: 20 = 1
  8. Example 2:
  10. Input: 16
  11. Output: true
  12. Explanation: 24 = 16
  13. Example 3:
  15. Input: 218
  16. Output: false

第一次做; 最优解, 利用性质:2的幂满足n&(n-1)==0, 还要注意n>0

  1. class Solution { 
  2.     public boolean isPowerOfTwo(int n) { 
  3.         return n>0 && (n&(n-1))==0;
  4.     }
  5. }

第一次做; 递归, base case: n==0, n==1; 其余的按照%2是否为零分成两个分支讨论

  1. /* 除了2^0, 2的幂的因数只有2 特殊的例子:0, 1 */
  2. class Solution { 
  3.     public boolean isPowerOfTwo(int n) { 
  4.         if(n<1)
  5.             return false;
  6.         if(n==1)
  7.             return true;
  8.         if(n%2==0){ 
  9.             return isPowerOfTwo(n/2);
  10.         }
  11.         return false;
  12.     }
  13. }

第一次做; 让一个数每次乘2, 如果某一次能等于n, 说明n是2的幂, 如果大于n, 说明n不是2的幂, 注意避免溢出问题

  1. class Solution { 
  2.     public boolean isPowerOfTwo(int n) { 
  3.         //找个数每次乘2, 如果结果大于n说明n不是2的幂
  4.         int a = 1;
  5.         //注意避免溢出问题
  6.         while(a<n && a<Integer.MAX_VALUE/2){ 
  7.             a = a*2;
  8.         }
  9.         return a==n;
  10.     }
  11. }

发表评论

表情：
评论列表 （有 0 条评论，106人围观）

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

相关阅读