1187 - 重排列得到2的幂


如果先处理得到 n 的每一位,之后用全排列的方式枚举所有排列,再判断是否为2的幂,那么复杂度为指数的。反过来,如果我们先求出所有 2 的幂,再对每一个数用上面相同的方法,枚举对应的全排列,复杂度也是指数的。那么该如何快速判断呢?

我们考虑如果能够自定义一种方法 F ,让 F(n)=k,同时 F(2x)=k,假如 n 与 2k包括的字符完全相同时。

这里我们可以利用有序化的思想,对字符进行排序,如果两个字符串包括的字符完全相同,那么经过排序后得到的两个字符是完全相同的。例如:

bbca,bcab,cabbb虽然都不相同,但经过字符排序后,得到的都是 abbc 。

这样做的复杂度是对数字排序的复杂度,假设数字的长度为 L ,那么复杂度为 O(LlogL) 。