力扣869-重新排列得到2的幂

力扣869-重新排列得到2的幂

 首先分析题目：前导不为0，也就是不管顺序如何第一个数不是0，也就是给定的数位数是固定的

可以先找到紧低于这个位数的2的i次幂的最大值，然后最多乘3次2，就能得到对应位数的虽有2的幂。分别对每一个2的幂与给定的数字每一位数字比较即可。

代码：

    public static void main(String[] args){
        int a =8042;//给定的数字
        int flag=0;//结果标志
        int b = find(digit(a));//仅次于给定数字位数的2的最大次幂位数
        int sum = (int)Math.pow(2,b);仅次于给定数字位数的2的最大次幂
        for (int i = 0; i <3 ; i++) {
           if (compare(sum,a)==1){
               flag=1;
               break;
           }
           sum = sum * 2;//最多乘3次2
        }
        System.out.println(flag);

    }

    public static  int compare(int sum,int a){
        HashSet set = new HashSet();//用于存放给定数字的每一位数字用来比较
        int flag = 1;
        sum = sum*2;
        while (a>0){
            set.add(a%10);//将给定数字的每一位存进set
            a=a/10;
        }
        while (sum>0){
            int c = 0;
            c = sum%10;
            if(!set.contains(c)){//如果set中没有这个数字说明不符合，就结束
                flag = 0;
                break;
            }
            sum = sum/10;
        }
        return flag;
    }
    public static int find(int digits){
        int i = 0;
        int sum = 0;
        for (i =0; ; i++) {
            sum = (int) Math.pow(2,i);
            if(digit(sum)>=digits){
                break;
            }

        }
        return i-1;
    }

    public static int digit(int a){
        int i = 1;
        while (a>=10){
            a=a/10;
            i++;
        }
        return i;
    }

代码中用到了一个HashSet的数据结构，可以简单理解为没有key的HashMap，很多算法题用这两个数据结构都很好用