LeetCode - Easy - 326. Power of Three-蒲公英云

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:

Input: n = 27
Output: true

Example 2:

Input: n = 0
Output: false

Example 3:

Input: n = 9
Output: true

Example 4:

Input: n = 45
Output: false

Constraints:

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

Analysis

略

Submission

public class PowerOfThree { 
    //方法一：switch版
    public boolean isPowerOfThree1(int num) { 
        switch (num) { 
            case 1: return true;
            case 3: return true;
            case 9: return true;
            case 27: return true;
            case 81: return true;
            case 243: return true;
            case 729: return true;
            case 2187: return true;
            case 6561: return true;
            case 19683: return true;
            case 59049: return true;
            case 177147: return true;
            case 531441: return true;
            case 1594323: return true;
            case 4782969: return true;
            case 14348907: return true;
            case 43046721: return true;
            case 129140163: return true;
            case 387420489: return true;
            case 1162261467: return true;
            default: return false;
        }
    }
    //方法二：求余
    public boolean isPowerOfThree2(int n) { 
        // 1162261467 is 3^19, 3^20 is bigger than int
        return n > 0 && 1162261467 % n == 0;
    }
    //方法三：递归
    public boolean isPowerOfThree3(int n) { 
        return n > 0 && (n == 1 || (n % 3 == 0 && isPowerOfThree3(n / 3)));
    }
    //方法四：迭代
    public boolean isPowerOfThree4(int n) { 
        if (n > 1)
            while (n % 3 == 0)
                n /= 3;
        return n == 1;
    }
    private static HashSet<Integer> POWER_OF_THREE_SET = new HashSet<>(
            Arrays.asList(1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049, 177147, 531441, 1594323, 4782969,
                    14348907, 43046721, 129140163, 387420489, 1162261467));
    //方法五：哈希表缓存
    public boolean isPowerOfThree5(int n) { 
        return POWER_OF_THREE_SET.contains(n);
    }
    private static int[] POWER_OF_THREE_LIST = new int[] {  1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049, 177147,
            531441, 1594323, 4782969, 14348907, 43046721, 129140163, 387420489, 1162261467 };
    //方法六：二分查找缓存
    public boolean isPowerOfThree6(int n) { 
        return Arrays.binarySearch(POWER_OF_THREE_LIST, n) >= 0;
    }
}

Test

import static org.junit.Assert.*;
import java.util.ArrayList;
import java.util.List;
import org.junit.Test;
public class PowerOfThreeTest { 
    public static List<Integer> POWER_OF_THREE_LIST;
    static { 
        List<Integer> result = new ArrayList<Integer>();
        for(int i = 0; ; i++) { 
            int product = 1, lastPrduct = 0;
            for(int j = 1; j <= i; j++) { 
                lastPrduct = product;
                product *= 3;
            }
            if(product / 3 != lastPrduct)
                break;
            //System.out.println(product + " : " + Integer.toBinaryString(product));
            //System.out.println("case " + product + ": return true;");
            result.add(product);
        }
        POWER_OF_THREE_LIST = result;
    }
    @Test
    public void test() { 
        PowerOfThree obj = new PowerOfThree();
        for(int num : POWER_OF_THREE_LIST) { 
            assertTrue(obj.isPowerOfThree1(num));
            assertTrue(obj.isPowerOfThree2(num));
            assertTrue(obj.isPowerOfThree3(num));
            assertTrue(obj.isPowerOfThree4(num));
            assertTrue(obj.isPowerOfThree5(num));
            assertTrue(obj.isPowerOfThree6(num));
        }
    }
}