判断一个数字是否可以表示成三的幂之和【LC1780】
Given an integer n, return true if it is possible to represent n as the sum of distinct powers of three. Otherwise, return false.
An integer y is a power of three if there exists an integer x such that y == 3x.
属实想不到
进制转换
- 思路：当我们把二进制转换为十进制时，采用的方法是二的幂之和。那么，本题可以将十进制转换为三进制，当所有位的值为0或者1时，满足题意，返回true；但有一位值为2时，返回false
- 实现
class Solution { public boolean checkPowersOfThree(int n) { while (n > 0){ if (n % 3 == 2){ return false; } n /= 3; } return true; } }
。复杂度
- 时间复杂度：O(logn)
- 空间复杂度：O ( 1 )
二分
- 思路：小于1 0 7 的3的幂次方一共只有15个，因此可以先打表，然后二分查找最接近target的3的幂次方，如果已经使用过该三进制或者target<0，那么返回false；当target==0时，返回true【感觉也是有点进制转换在里面的】
- 实现
class Solution { public boolean checkPowersOfThree(int n) { int[] tri = new int[16]; for(int i = 0;i<16;i++){ tri[i] = (int)Math.pow(3,i); } int temp = n; boolean[] vis = new boolean[16]; int l = 0,r = 15; while(temp > 0){ l = 0; while(l<r){ int mid = l + r + 1 >> 1; if(tri[mid] > temp) r = mid - 1; else l = mid; } if(vis[l]) return false; temp -= tri[l]; vis[l] = true; } return temp == 0; } }
。复杂度
- 时间复杂度：O(logn)
- 空间复杂度：O ( C )
