LeetCode - Easy - 326. Power of Three

港控/mmm° 2023-01-11 05:00 267阅读 0赞

Topic

  • Math

Description

https://leetcode.com/problems/power-of-three/

Given an integer n, return true if it is a power of three. Otherwise, return false.

An integer n is a power of three, if there exists an integer x such that n == 3x.

Example 1:

  1. Input: n = 27
  2. Output: true

Example 2:

  1. Input: n = 0
  2. Output: false

Example 3:

  1. Input: n = 9
  2. Output: true

Example 4:

  1. Input: n = 45
  2. Output: false

Constraints:

  • -2³¹ <= n <= 2³¹ - 1

Analysis

Submission

  1. public class PowerOfThree {
  2. //方法一:switch版
  3. public boolean isPowerOfThree1(int num) {
  4. switch (num) {
  5. case 1: return true;
  6. case 3: return true;
  7. case 9: return true;
  8. case 27: return true;
  9. case 81: return true;
  10. case 243: return true;
  11. case 729: return true;
  12. case 2187: return true;
  13. case 6561: return true;
  14. case 19683: return true;
  15. case 59049: return true;
  16. case 177147: return true;
  17. case 531441: return true;
  18. case 1594323: return true;
  19. case 4782969: return true;
  20. case 14348907: return true;
  21. case 43046721: return true;
  22. case 129140163: return true;
  23. case 387420489: return true;
  24. case 1162261467: return true;
  25. default: return false;
  26. }
  27. }
  28. //方法二:求余
  29. public boolean isPowerOfThree2(int n) {
  30. // 1162261467 is 3^19, 3^20 is bigger than int
  31. return n > 0 && 1162261467 % n == 0;
  32. }
  33. //方法三:递归
  34. public boolean isPowerOfThree3(int n) {
  35. return n > 0 && (n == 1 || (n % 3 == 0 && isPowerOfThree3(n / 3)));
  36. }
  37. //方法四:迭代
  38. public boolean isPowerOfThree4(int n) {
  39. if (n > 1)
  40. while (n % 3 == 0)
  41. n /= 3;
  42. return n == 1;
  43. }
  44. private static HashSet<Integer> POWER_OF_THREE_SET = new HashSet<>(
  45. Arrays.asList(1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049, 177147, 531441, 1594323, 4782969,
  46. 14348907, 43046721, 129140163, 387420489, 1162261467));
  47. //方法五:哈希表缓存
  48. public boolean isPowerOfThree5(int n) {
  49. return POWER_OF_THREE_SET.contains(n);
  50. }
  51. private static int[] POWER_OF_THREE_LIST = new int[] { 1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049, 177147,
  52. 531441, 1594323, 4782969, 14348907, 43046721, 129140163, 387420489, 1162261467 };
  53. //方法六:二分查找缓存
  54. public boolean isPowerOfThree6(int n) {
  55. return Arrays.binarySearch(POWER_OF_THREE_LIST, n) >= 0;
  56. }
  57. }

Test

  1. import static org.junit.Assert.*;
  2. import java.util.ArrayList;
  3. import java.util.List;
  4. import org.junit.Test;
  5. public class PowerOfThreeTest {
  6. public static List<Integer> POWER_OF_THREE_LIST;
  7. static {
  8. List<Integer> result = new ArrayList<Integer>();
  9. for(int i = 0; ; i++) {
  10. int product = 1, lastPrduct = 0;
  11. for(int j = 1; j <= i; j++) {
  12. lastPrduct = product;
  13. product *= 3;
  14. }
  15. if(product / 3 != lastPrduct)
  16. break;
  17. //System.out.println(product + " : " + Integer.toBinaryString(product));
  18. //System.out.println("case " + product + ": return true;");
  19. result.add(product);
  20. }
  21. POWER_OF_THREE_LIST = result;
  22. }
  23. @Test
  24. public void test() {
  25. PowerOfThree obj = new PowerOfThree();
  26. for(int num : POWER_OF_THREE_LIST) {
  27. assertTrue(obj.isPowerOfThree1(num));
  28. assertTrue(obj.isPowerOfThree2(num));
  29. assertTrue(obj.isPowerOfThree3(num));
  30. assertTrue(obj.isPowerOfThree4(num));
  31. assertTrue(obj.isPowerOfThree5(num));
  32. assertTrue(obj.isPowerOfThree6(num));
  33. }
  34. }
  35. }

发表评论

表情:
评论列表 (有 0 条评论,267人围观)

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

相关阅读